Faster first-order methods for convex optimization in mixed norm settings
Near-Optimal Acceleration for Smooth $\ell_p$ / $\ell_q$ Nondual Convex First-Order Oracle Optimization
Machine Learning
Summary
This paper addresses how to more efficiently find minimum points of certain smooth, high-dimensional shapes using first-order methods, which only rely on gradient information. The authors build on previous mathematical tools to design an approach that accelerates convergence rates for problems with mixed settings of ℓp and ℓq norms. Their results solve an open question from previous work by showing near-optimal runtime bounds under smoothness assumptions. The findings improve how quickly one can minimize some convex functions when working with complex geometric constraints.
What this means in practice
- •For machine learning engineers: Improve training speed for high-dimensional convex models with mixed norm constraints using faster gradient methods.
- •For signal processing teams: Optimize recovery algorithms in settings involving ℓp and ℓq norms with provably faster convergence guarantees.
A theory result. No direct application yet.
Authors
David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán, Mathieu Molina
Abstract
We study the optimization of convex objectives with $(L,κ-1)$-Hölder-continuous gradients in $\ell_q$ over $R B_p^d$, $1<κ\le 2$. (MG26) provides selectors with a movement bound for the problem of chasing high-dimensional convex nested sets for every $p<q$ and generally reduces Lipschitz convex optimization to bounds on the movement of selectors. We couple that movement with Hölder descent yielding a polynomial-runtime first-order method whose feasible output, in the high-dimensional regime $T\le d$ and for $p<\min\{q,2\}$, has error $$ \widetilde O_{κ,p,q}\!\left( \frac{LR^κ}{T^{κ(1+1/p-(1/q-1/2)_+)-1}} \right), $$ after $T$ queries to a first-order oracle, solving the COLT 2015 open problem of (Guz15), up to logarithmic factors. At $(p,q)=(1,2)$, the rate is $\widetilde{O}(LR^κ/T^{2κ-1})$, including $\widetilde{O}(LR^2/T^{3})$ cubic decay in the smooth case.