Acceleration with a Ball Optimization Oracle

2020/03/18 by Carmon, Yair, Jambulapati, Arun, Jiang, Qijia +4 · 3 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2003.08078

Abstract

Consider an oracle which takes a point x and returns the minimizer of a convex function f in an ℓ₂ ball of radius r around x. It is straightforward to show that roughly r^-1log\frac1ε calls to the oracle suffice to find an ε-approximate minimizer of f in an ℓ₂ unit ball. Perhaps surprisingly, this is not optimal: we design an accelerated algorithm which attains an ε-approximate minimizer with roughly r^-2/3 log \frac1ε 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 ℓ_∞ regression and achieving guarantees comparable to the state-of-the-art for ℓ_p regression.

Cited by

• Quasi-Self-Concordant Optimization with Lewis Weights
• Non-Euclidean Broximal Point Method: A Blueprint for Geometry-Aware Optimization
• Solving Zero-Sum Games with Fewer Matrix-Vector Products

Related

• Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss
• A Simple Method for Convex Optimization in the Oracle Model
• Convex optimization with p-norm oracles
• Smooth Convex Optimization using Sub-Zeroth-Order Oracles
• Distributionally Robust Optimization via Ball Oracle Acceleration