Efficient algorithms achieve optimal rates for nonsmooth convex optimization
Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates
Machine Learning
Summary
Optimization methods often try to find the best solution with limited information about a problem. This paper tackles optimizing certain convex functions that change smoothly within some limits, called Lipschitz conditions. The authors present new algorithms that nearly reach the best theoretical speed for finding solutions relying on limited queries. They achieve this by framing the problem as a sequence of nested sets to chase, balancing finding promising points and cutting bad regions efficiently. Their approach also controls how much the solution moves, ensuring stable and efficient progress.
What this means in practice
- •For machine learning engineers: Design faster and more stable training algorithms for nonsmooth convex models with guarantees on query efficiency under norm constraints.
- •For operations research practitioners: Improve solution methods for high-dimensional resource allocation problems constrained by different ℓp and ℓq norms using stable convex optimization steps.
Authors
David Martínez-Rubio, Cristóbal Guzmán
Abstract
We study efficient algorithms for realizing the first-order oracle complexity of optimization of $G$-Lipschitz convex functions with respect to the $\ell_{q}$-norm over an $\ell_{p}$-ball of radius $R$, where $1\leq p,q\leq \infty$. For $p<q$, we obtain error $\widetilde{O}_{p,q}(GR/T^{1/p-(1/q-1/2)_{+}})$ after $T$ oracle queries, efficiently realizing the nearly optimal rates of (MBG+26), thereby resolving the nonsmooth end of the COLT 2015 open problem (Guz15b). In particular, the rate is $\widetilde{O}(GR/T)$ for Euclidean Lipschitzness over an $\ell_1$-ball of radius $R$ ($p=1,q=2$). Our solution consists of reducing convex Lipschitz optimization to the chasing nested convex sets problem in sublevel sets of an evolving bundle (LNN95; BBE+20): at each query we either find a point with low function value or we produce a deep cut in the current sublevel of the bundle, that we chase. The dichotomy between stability of selectors and forced movement by deep cuts bounds the number of iterations of the algorithm near optimally. For nested subsets of $R B_{p}^{d}$, we introduce a novel notion of stable center whose movement is bounded by $\widetilde{O}_{p,q}(RT^{1-1/p+(1/q-1/2)_{+}})$ in the $\ell_{q}$-norm after $T$ steps, which we show is nearly optimal in high dimensions. A Monte Carlo average of the proposed selector achieves near-optimal rates with high probability and can be implemented in polynomial time for our optimization algorithm in the real-arithmetic model.