On the Complexity of BFGS Method for Smooth Convex Optimization
We study the BFGS method with an Armijo-Wolfe line search for minimizing convex functions with Lipschitz-continuous gradients, without assuming strong convexity. We establish a global iteration complexity bound of $\mathcal{O}(k^{-1/2})$ for the smallest gradient norm among the first $k$ iterates. Moreover, when the initial sublevel set is bounded, we show that the function value gap converges at a rate of $\mathcal{O}(k^{-1})$. Our analysis leverages the classical trace-log-determinant potential function and reveals that a key inequality underlying this potential function remains valid…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.16009
curl -X POST /api/v1/records/arxiv/2608.16009/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.16009/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'