An $O(1/T^3)$ algorithm for minimizing convex quadratic functions over the $L_1$ ball
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.10314
curl -X POST /api/v1/records/arxiv/2609.10314/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.10314/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'