Near-Optimal Acceleration for Smooth ℓp / ℓq Nondual Convex First-Order Oracle Optimization
Abstract
We study the optimization of convex objectives with (L,κ−1)-Hölder-continuous gradients in ℓq over R Bpd, 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<min{q,2}, has error Õκ,p,q ( LRκ/(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κ/T2κ−1), including Õ(LR2/T3) cubic decay in the smooth case.
Related
- Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates
- Can Acceleration in Gradient-Norm Minimization Be Anytime? Sharp Last-Iterate Limits in Smooth Convex Optimization
- Optimal Gradient-Norm Minimization in Non-Euclidean Hölder-Smooth Convex Optimization
- Near-Optimal Exact-Value Zeroth-Order Complexity for Smooth Strongly Convex Optimization
- Near-Optimal Deterministic Exact-Value Complexity for Smooth Convex Optimization
BibTeX
@misc{martinezrubio2026nearoptimal,
title = {{Near-Optimal Acceleration for Smooth $\ell_p$ / $\ell_q$ Nondual Convex First-Order Oracle Optimization}},
author = {David Martínez-Rubio and Brian Bullins and Cristóbal Guzmán and Mathieu Molina},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21880},
eprint = {2609.21880},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21880},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Near-Optimal Acceleration for Smooth ℓ_p / ℓ_q Nondual Convex First-Order Oracle Optimization
AU - David Martínez-Rubio
AU - Brian Bullins
AU - Cristóbal Guzmán
AU - Mathieu Molina
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.21880
UR - https://arxiv.org/abs/2609.21880
AB - 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<min{q,2}, has error Õ_κ,p,q ( LR^κ/(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^3) cubic decay in the smooth case.
ER -