We consider the problem of minimizing the average of a large number of smooth
but possibly non-convex functions. In the context of most machine learning
applications, each loss function is non-negative and thus can be expressed as
the composition of a square and its real-valued square root. This reformulation
allows us to apply the Gauss-Newton method, or the Levenberg-Marquardt method
when adding a quadratic regularization. The resulting algorithm, while being
computationally as efficient as the vanilla stochastic gradient method, is
highly adaptive and can automatically warmup and decay the effective stepsize
while tracking the non-negative loss landscape. We provide a tight convergence
analysis, leveraging new techniques, in the stochastic convex and non-convex
settings. In particular, in the convex case, the method does not require access
to the gradient Lipshitz constant for convergence, and is guaranteed to never
diverge. The convergence rates and empirical evaluations compare favorably to
the classical (stochastic) gradient method as well as to several other adaptive
methods.

用 Gauss-Newton 方法最小化大量平滑但可能非凸函数的平均值，并提供收敛分析。

非负 Gauss-Newton 步长的自适应随机梯度方法

An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton  Stepsizes

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$-Lipschitz
and $1$-smooth, our method computes an $\epsilon$-approximate solution using
$\widetilde{O}(n \epsilon^{-1/3} + \epsilon^{-2})$ gradient and function
evaluations, and $\widetilde{O}(n \epsilon^{-4/3})$ additional runtime. For
large $n$, our evaluation complexity is optimal up to polylogarithmic factors.
In the special case where each $f_i$ is linear -- which corresponds to finding
a 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 over
all existing first-order methods. When additionally $d = \omega(n^{8/11})$ our
runtime also improves over all known interior point methods.
Our algorithm combines three novel primitives: (1) A dynamic data structure
which enables efficient stochastic gradient estimation in small $\ell_2$ or
$\ell_1$ balls. (2) A mirror descent algorithm tailored to our data structure
implementing an oracle which minimizes the objective over these balls. (3) A
simple ball oracle acceleration framework suitable for non-Euclidean geometry.

算法设计为在欧几里得或单纯形域内最小化 max (f_i (x))，若每个 f_i 为 1-Lipschitz 和 1 - 光滑函数，我们的方法可以在评价复杂度中找到 ε- 近似解，并具有优化性能。

全新的角色扮演加速方法：矩阵游戏和平滑函数的最大化最小化

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

Submodular functions describe a variety of discrete problems in machine
learning, signal processing, and computer vision. However, minimizing
submodular functions poses a number of algorithmic challenges. Recent work
introduced an easy-to-use, parallelizable algorithm for minimizing submodular
functions that decompose as the sum of "simple" submodular functions.
Empirically, this algorithm performs extremely well, but no theoretical
analysis was given. In this paper, we show that the algorithm converges
linearly, and we provide upper and lower bounds on the rate of convergence. Our
proof relies on the geometry of submodular polyhedra and draws on results from
spectral graph theory.

本文介绍一种易用且可并行的用于最小化由 “简单” 子模函数组成的子模函数的算法，并在几何子模多面体的基础上，利用谱图理论结果证明该算法线性收敛，并给出了收敛速率的上下界。