Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss
Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss
复制标题
DOI：
--
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Y. Carmon;A. Jambulapati;Yujia Jin;Aaron Sidford
中科院分区：
文献类型：
--
作者：
Y. Carmon;A. Jambulapati;Yujia Jin;Aaron Sidford
我们描述了最小化$\max_{i\in[N]} f_i(x)$对于凸Lipschitz函数$f_1,\ldots, f_N$的复杂性。对于非光滑函数，现有的方法需要对一阶oracle进行$O(N\epsilon^{-2})$查询以计算$\epsilon$ -次优点，如果$f_i$是$O(1/\epsilon)$ -光滑，则需要进行$\tilde{O}(N\epsilon^{-1})$查询。我们开发了改进了非光滑情况下的$\tilde{O}(N\epsilon^{-2/3} + \epsilon^{-8/3})$和$O(1/\epsilon)$ -光滑情况下的$\tilde{O}(N\epsilon^{-2/3} + \sqrt{N}\epsilon^{-1})$的复杂度界的方法。我们的方法包括最近提出的球优化oracle加速算法（我们对其进行了改进）和对softmax函数的oracle的仔细实现。我们还证明了一个oracle复杂性下界缩放为$\Omega(N\epsilon^{-2/3})$，表明我们对$N$的依赖是最优的，直到多对数因子。
We characterize the complexity of minimizing $\max_{i\in[N]} f_i(x)$ for convex, Lipschitz functions $f_1,\ldots, f_N$. For non-smooth functions, existing methods require $O(N\epsilon^{-2})$ queries to a first-order oracle to compute an $\epsilon$-suboptimal point and $\tilde{O}(N\epsilon^{-1})$ queries if the $f_i$ are $O(1/\epsilon)$-smooth. We develop methods with improved complexity bounds of $\tilde{O}(N\epsilon^{-2/3} + \epsilon^{-8/3})$ in the non-smooth case and $\tilde{O}(N\epsilon^{-2/3} + \sqrt{N}\epsilon^{-1})$ in the $O(1/\epsilon)$-smooth case. Our methods consist of a recently proposed ball optimization oracle acceleration algorithm (which we refine) and a careful implementation of said oracle for the softmax function. We also prove an oracle complexity lower bound scaling as $\Omega(N\epsilon^{-2/3})$, showing that our dependence on $N$ is optimal up to polylogarithmic factors.