Improved convergence rates for nonsmooth convex optimization over small sets
The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
Machine Learning
Summary
This paper studies how quickly certain optimization problems can be solved when working with shapes (called balls) defined by different distance rules. The authors show that if the set you're searching over is smaller in a certain sense, you can find solutions faster than previously known. They develop a new mathematical game to prove this and connect it to ideas in online learning and geometry. Their results improve on classical limits for how fast optimization algorithms can work in these settings.
What this means in practice
- •For machine learning engineers: Design optimization routines for training models with nonsmooth loss functions over sparse parameter sets using improved convergence guarantees.
- •For algorithm designers: Develop more efficient first-order optimization algorithms tailored to problem geometries with smaller feasible regions relying on refined geometric insights.
A theory result. No direct application yet.
Authors
David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán, Mathieu Molina
Abstract
We study first-order black-box convex optimization over an $\ell_p$-ball for objectives Lipschitz in the $\ell_q$-norm, solving in the affirmative the nonsmooth version of the COLT open question (Guz15b) on whether the geometry of a smaller feasible set ($p < q$) can improve convergence rates in convex optimization, and matching prior lower bounds up to logarithmic factors. Our rates include \(\widetilde O(1/T)\) for convex Euclidean-Lipschitz optimization over the $\ell_1$-ball, improving on the $O(1/\sqrt{T})$ classical rate under general assumptions. The key technical device is a new online learning game, where the comparator is evaluated using the maximum of affine losses observed so far. We bound the value of this game above and below in terms of a combinatorial online learning quantity: the sequential fat-shattering dimension, which we characterize for the $\ell_p / \ell_q$ case. Our results generally apply when the feasible set $X$ and the set of possible subgradients $H$ are convex, centrally symmetric, and admit a type of minmax theorem, advancing on a fundamental question by Sridharan [Sri12, Section 10.1.2, Q3]. As a geometric consequence of our analysis, of independent interest, we obtain estimates for the expected distance of a convex hull of samples to their mean in several Banach geometries, a version of the celebrated Wendel's theorem (Wen62), but quantitative and for bounded general distributions as opposed to centrally symmetric ones.