An O(1/T3) algorithm for minimizing convex quadratic functions over the L1 ball
Abstract
We study convex quadratic minimization over the unit L1 ball in which the maximum eigenvalue of the Hessian matrix is bounded by a positive constant L. We propose a novel first-order algorithm with objective value error bounded by O(L/T3) after T gradient evaluations, assuming that the subproblems involved in the algorithm can be solved exactly. To the best of our knowledge, the best convergence rate of algorithms in the literature is O(L/T2). From the perspective of information-based complexity theory, our proposed algorithm is the first in the literature that achieves the O((L/ε)1/3) first-order oracle complexity, although its current version is not necessarily practical for implementation. We hope that our proposed algorithm could shed some light on future implementable and efficient O(L/T3)-convergence-rate algorithms. The proposed algorithm incorporates a decomposition of components of vectors in the unit L1-norm ball to "good" and "bad" parts, and uses symmetric rank-1 (SR1) updates on the bad parts. The proposed algorithm was developed after the author instructed the OpenAI ChatGPT 6 (Astra) model to study the problem using ideas of weak-type L1 estimates and good-bad part decomposition in harmonic analysis and a recent result.
Related
- Minimizing cumulative infections in SIS epidemic models over networks via an edge deletion algorithm
- On the Optimal Linear Minimization Oracle Complexity of Active-Hull Methods for Minimizing Convex Hölder Smooth Functions
- Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex (L0,L1)-Smooth Functions
- A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
- Computing the convex envelope of bivariate piecewise linear-quadratic functions in linear time
BibTeX
@misc{ouyang2026o1t3,
title = {{An $O(1/T^3)$ algorithm for minimizing convex quadratic functions over the $L_1$ ball}},
author = {Yuyuan Ouyang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10314},
eprint = {2609.10314},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10314},
}
RIS
TY - UNPB
TI - An O(1/T^3) algorithm for minimizing convex quadratic functions over the L_1 ball
AU - Yuyuan Ouyang
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.10314
UR - https://arxiv.org/abs/2609.10314
AB - We study convex quadratic minimization over the unit L_1 ball in which the maximum eigenvalue of the Hessian matrix is bounded by a positive constant L. We propose a novel first-order algorithm with objective value error bounded by O(L/T^3) after T gradient evaluations, assuming that the subproblems involved in the algorithm can be solved exactly. To the best of our knowledge, the best convergence rate of algorithms in the literature is O(L/T^2). From the perspective of information-based complexity theory, our proposed algorithm is the first in the literature that achieves the O((L/ε)^1/3) first-order oracle complexity, although its current version is not necessarily practical for implementation. We hope that our proposed algorithm could shed some light on future implementable and efficient O(L/T^3)-convergence-rate algorithms. The proposed algorithm incorporates a decomposition of components of vectors in the unit L_1-norm ball to "good" and "bad" parts, and uses symmetric rank-1 (SR1) updates on the bad parts. The proposed algorithm was developed after the author instructed the OpenAI ChatGPT 6 (Astra) model to study the problem using ideas of weak-type L^1 estimates and good-bad part decomposition in harmonic analysis and a recent result.
ER -