Acceleration with a Ball Optimization Oracle
Acceleration with a Ball Optimization Oracle
复制标题
DOI：
--
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
Y. Carmon;A. Jambulapati;Qijia Jiang;Yujia Jin;Y. Lee;Aaron Sidford;Kevin Tian
中科院分区：
文献类型：
--
作者：
Y. Carmon;A. Jambulapati;Qijia Jiang;Yujia Jin;Y. Lee;Aaron Sidford;Kevin Tian
考虑一个预言机，它取一个点x，并返回一个凸函数f在x周围半径为r的球中的最小值。我们可以直接证明，对oracle的大约$r^{-1}\log\frac{1}{\displaystyle $$调用就足以在一个$\ell_2 $单位球中找到一个$f$的$\log $-近似最小化。也许令人惊讶的是，这不是最佳的：我们设计了一个加速算法，达到$\log \frac{1}$ Oracle查询的近似最小值，并给出了一个匹配的下限。此外，我们实现球优化预言的功能与局部稳定的海森使用牛顿的方法的变体。由此产生的算法适用于一些实际和理论上的进口问题，改善后，以前的结果为逻辑和$\ell_\infty$回归和实现保证相媲美的国家的最先进的$\ell_p$回归。
Consider an oracle which takes a point $x$ and returns the minimizer of a convex function $f$ in an $\ell_2$ ball of radius $r$ around $x$. It is straightforward to show that roughly $r^{-1}\log\frac{1}{\epsilon}$ calls to the oracle suffice to find an $\epsilon$-approximate minimizer of $f$ in an $\ell_2$ unit ball. Perhaps surprisingly, this is not optimal: we design an accelerated algorithm which attains an $\epsilon$-approximate minimizer with roughly $r^{-2/3} \log \frac{1}{\epsilon}$ oracle queries, and give a matching lower bound. Further, we implement ball optimization oracles for functions with locally stable Hessians using a variant of Newton's method. The resulting algorithm applies to a number of problems of practical and theoretical import, improving upon previous results for logistic and $\ell_\infty$ regression and achieving guarantees comparable to the state-of-the-art for $\ell_p$ regression.