Accuracy Certificates for Convex Optimization at Accelerated Rates via Primal-Dual Averaging
Many works in convex optimization provide rates for achieving a small primal gap. However, this quantity is typically unavailable in practice. In this work, we show that solving a regularized surrogate with algorithms based on simple primal-dual averaging provides non-asymptotic convergence guarantees for a \textit{computable} optimality certificate. We first analyze primal and dual methods based on one average, namely modified dual averaging and generalized conditional gradient, and establish $\tilde{O}(\varepsilon^{-1})$ certificate complexities. Motivated by asymmetries in the one-average…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.18321
curl -X POST /api/v1/records/arxiv/2604.18321/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.18321/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'