{"id":"arxiv/2604.18321","url":"https://arxiv.org/abs/2604.18321","tags":["math.OC"],"score":0,"title":"Accuracy Certificates for Convex Optimization at Accelerated Rates via Primal-Dual Averaging","domain":"math.OC","source":"arxiv","authors":["Matthew X. Burns","Jiaming Liang"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-20","reactions":{}}