论文标题
与球优化的加速度甲骨文
Acceleration with a Ball Optimization Oracle
论文作者
论文摘要
考虑一个需要点$ x $的甲骨文，并返回$ \ ell_2 $ radius $ r $ y $ x $的凸函数$ f $的最小化器。很容易证明大约$ r^{ - 1} \ log \ frac {1}ε$调用Oracle足以在$ \ ell_2 $单位球中找到$ε$ -F $ $ f $的最小化。也许令人惊讶的是，这并不是最佳的：我们设计了一种加速算法，该算法达到了$ε$ -Appapproximate的最小化器，大约是$ r^{ - 2/3} \ 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}ε$ calls to the oracle suffice to find an $ε$-approximate minimizer of $f$ in an $\ell_2$ unit ball. Perhaps surprisingly, this is not optimal: we design an accelerated algorithm which attains an $ε$-approximate minimizer with roughly $r^{-2/3} \log \frac{1}ε$ 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.
