aiqbench analysis
This paper presents a theoretical breakthrough in first-order optimization by solving the 2015 COLT open problem regarding high-dimensional convex nested sets with Hölder-continuous gradients. By coupling selector movement bounds with Hölder descent, it achieves polynomial-runtime methods that offer improved convergence rates for specific norm regimes like $(\ell_1, \ell_2)$. These advances in optimization complexity directly benefit the development of efficient algorithms for large-scale machine learning models where gradient smoothness varies.
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)$-H\"older-continuous gradients in $\ell_q$ over $R B_p^d$, $1<\kappa\le 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\le 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^{2\kappa-1})$, including $\widetilde{O}(LR^2/T^{3})$ cubic decay in the smooth case.
Abstract:We study the optimization of convex objectives with $(L,\kappa-1)$-Hölder-continuous gradients in $\ell_q$ over $R B_p^d$, $1<\kappa\le 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\le 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^{2\kappa-1})$, including $\widetilde{O}(LR^2/T^{3})$ cubic decay in the smooth case.
Optimization and Control (math.OC); Machine Learning (cs.LG)
arXiv:2609.21880 [math.OC]
(or arXiv:2609.21880v1 [math.OC] for this version)
https://doi.org/10.48550/arXiv.2609.21880 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 212 words
Related coverage
On the Condition Number Dependency in Bilevel Optimization
arXiv · Jun 10, 2026
Near-Optimal Decentralized Stochastic Convex Optimization over Networks
arXiv · Jun 5, 2026
Accelerated stochastic first-order method for convex optimization under heavy-tailed noise
arXiv · Sep 22, 2026
[AINews] not much happened today
Latent Space · Sep 10, 2026