accelerated method – 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

An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems

Published: 2014/04/29

Yunlong He

Renato D.C. Monteiro

Convex Optimization, Generalized Convexity/Monoticity, Nonsmooth Optimization accelerated method, complexity, composite convex optimization, hybrid proximal extragradient, inexact proximal point method, monotone inclusion problem, saddle point problem, smoothing

This article proposes a new algorithm for solving a class of composite convex-concave saddle-point problems. The new algorithm is a special instance of the hybrid proximal extragradient framework in which a Nesterov’s accelerated variant is used to approximately solve the prox subproblems. One of the advantages of the new method is that it works for … Read more