Near-Optimal Acceleration for Smooth ell_p / ell_q Nondual Convex First-Order Oracle Optimization

arXiv:2609.21880v1 Announce Type: cross Abstract: We study the optimization of convex objectives with (L,kappa-1)-Holder-continuous gradients in ell_q over R B_p^d, 1<kappale 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 Holder descent yielding a polynomial-runtime first-order method whose feasible output, in the high-dimensional regime Tle d and for p<min{q,2}, has error $ widetilde O_{kappa,p,q}!left( frac{LR^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 widetilde{O}(LR^kappa/T^{2kappa-1}), including widetilde{O}(LR^2/T^{3})$ cubic decay in the smooth case.

Source: arXiv cs.LG | 2026-09-21