optimal first-order methods – Optimization Online

OSGA: A fast subgradient algorithm with optimal complexity

Published: 2014/02/05

Convex Optimization, Nonsmooth Optimization complexity, convex optimization, large-scale optimization, nesterov's optimal method, nonsmooth optimization, optimal first-order methods, optimal subgradient method, smooth optimization, strongly convex

This paper presents an algorithm for approximately minimizing a convex function in simple, not necessarily bounded convex domains, assuming only that function values and subgradients are available. No global information about the objective function is needed apart from a strong convexity parameter (which can be put to zero if only convexity is known). The worst … Read more

Templates for Convex Cone Problems with Applications to Sparse Signal Recovery

Published: 2010/09/23

Stephen Becker

Emmanuel Candès

Michael Grant

Constrained Nonlinear Optimization, Linear, Cone and Semidefinite Programming, Nonsmooth Optimization duality, nesterov's accelerated descent algorithms, nuclear norm minimization, optimal first-order methods, proximal algorithms, smoothing by conjugation, the dantzig selector, the lasso

This paper develops a general framework for solving a variety of convex cone problems that frequently arise in signal processing, machine learning, statistics, and other fields. The approach works as follows: first, determine a conic formulation of the problem; second, determine its dual; third, apply smoothing; and fourth, solve using an optimal first-order method. A … Read more