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

arXiv: https://arxiv.org/abs/2609.21880 · HTML: https://mlsanity.com/paper/2609.21880/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 14 references that are in the map.
- First posted on arXiv 18 Sep 2026.

## Builds on (most cited first, 8 of 8)

- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization](https://mlsanity.com/paper/1307.5001/) (2013)
- [Optimal and Adaptive Monteiro-Svaiter Acceleration](https://mlsanity.com/paper/2205.15371/) (2022)
- [Normalized Gradients for All](https://mlsanity.com/paper/2308.05621/) (2023)
- [Convex optimization with p-norm oracles](https://mlsanity.com/paper/2410.24158/) (2024)
- [Non-Euclidean High-Order Smooth Convex Optimization](https://mlsanity.com/paper/2411.08987/) (2024)
- [An O(1/T3) algorithm for minimizing convex quadratic functions over the L1 ball](https://mlsanity.com/paper/2609.10314/) (2026)
- [Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates](https://mlsanity.com/paper/2609.20701/) (2026)

## Abstract (arXiv)

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.