Near-Optimal Acceleration for Smooth ${\ell }_p$ / ${\ell }_q$ Nondual Convex First-Order Oracle Optimization

Abstract

We study the optimization of convex objectives with $(L,\kappa -1)$-Hölder-continuous gradients in ${\ell }_q$ over $R{B}_p^d$, $1<\kappa \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 $${\tilde{O}}_{\kappa ,p,q}\left(\frac{L{R}^{\kappa }}{T^{\kappa (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 $\tilde{O}(L{R}^{\kappa }/T^{2\kappa -1})$, including $\tilde{O}(L{R}^2/T^3)$ cubic decay in the smooth case.