Matthew X. Burns – Optimization Online

Accuracy Certificates for Convex Optimization at Accelerated Rates via Primal-Dual Averaging

Published: 2026/04/20

Convex and Nonsmooth Optimization, Nonlinear Optimization accelerated method, accuracy certificate, conditional gradient method, gradient extrapolation method, 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 computable optimality certificate. We first analyze primal and dual methods based … Read more

Improved Analysis of Restarted Accelerated Gradient and Augmented Lagrangian Methods via Inexact Proximal Point Frameworks

Published: 2026/02/23

Matthew X. Burns

Jiaming Liang

Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization, Convex Optimization accelerated composite gradient method, accelerated inexact proximal iteration, inexact augmented lagrangian method, inexact proximal point method, optimal iteration-complexity

This paper studies a class of double-loop (inner-outer) algorithms for convex composite optimization. For unconstrained problems, we develop a restarted accelerated composite gradient method that attains the optimal first-order complexity in both the convex and strongly convex settings. For linearly constrained problems, we introduce inexact augmented Lagrangian methods, including a basic method and an outer-accelerated … Read more