{"id":"arxiv/2609.10314","url":"https://arxiv.org/abs/2609.10314","tags":["math.OC"],"score":0,"title":"An $O(1/T^3)$ algorithm for minimizing convex quadratic functions over the $L_1$ ball","domain":"math.OC","source":"arxiv","authors":["Yuyuan Ouyang"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-09","reactions":{}}