English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We design algorithms for minimizing $\max_{i\in[n]} f_i(x)$ over a$d$-dimensional Euclidean or simplex domain. When each $f_i$ is $1$-Lipschitzand $1$-smooth, our method computes an $\epsilon$-approximate solution using$\widetilde{O}(n \epsilon^{-1/3} + \epsilon^{-2})$ gradient and functionevaluations, and $\widetilde{O}(n \epsilon^{-4/3})$ additional runtime. Forlarge $n$, our evaluation complexity is optimal up to polylogarithmic factors.In the special case where each $f_i$ is linear -- which corresponds to findinga near-optimal primal strategy in a matrix game -- our method finds an$\epsilon$-approximate solution in runtime $\widetilde{O}(n (d/\epsilon)^{2/3}+ nd + d\epsilon^{-2})$. For $n>d$ and $\epsilon=1/\sqrt{n}$ this improves overall existing first-order methods. When additionally $d = \omega(n^{8/11})$ ourruntime also improves over all known interior point methods.  Our algorithm combines three novel primitives: (1) A dynamic data structurewhich enables efficient stochastic gradient estimation in small $\ell_2$ or$\ell_1$ balls. (2) A mirror descent algorithm tailored to our data structureimplementing an oracle which minimizes the objective over these balls. (3) Asimple ball oracle acceleration framework suitable for non-Euclidean geometry.

A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions