Acceleration with a Ball Optimization Oracle

Abstract

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.

arXiv comment37 pages

References in corpus (6)

• On Acceleration with Noise-Corrupted Gradients
• Complexity of Highly Parallel Non-Smooth Convex Optimization
• Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients
• Lower Bound for Randomized First Order Convex Optimization
• Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression
• Higher-Order Accelerated Methods for Faster Non-Smooth Optimization

Cited by in corpus (2)

• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• Robust Regression Revisited: Acceleration and Improved Estimation Rates