An O(1/T3) algorithm for minimizing convex quadratic functions over the L1 ball

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/varepsilon)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.