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

We study the optimization of convex objectives with (L,κ-1) -Hölder-continuous gradients in q over R B p d, 1<κ 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 d and for p< q,2, has error O κ,p,q! ( LR κ over T κ(1+1/p-(1/q-1/2)+)-1 ), 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 (LR κ/T 2κ-1), including (LR 2/T cubed) cubic decay in the smooth case.