Near-Optimal Acceleration for Smooth ℓp / ℓq Nondual Convex First-Order Oracle Optimization

We study the optimization of convex objectives with (L,kappa-1)-H"older-continuous gradients in ℓq over R Bpd, 1<kappa≤ 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"older descent yielding a polynomial-runtime first-order method whose feasible output, in the high-dimensional regime T≤ d and for p<minq,2, has error widetilde Okappa,p,q!left( fracLR^kappaTkappa(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 widetildeO(LR^kappa/T2kappa-1), including widetildeO(LR2/T3) cubic decay in the smooth case.