BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Error bounds and convergence of proximal methods for composite minimization Lewis, Adrian


Minimizing a simple nonsmooth outer function composed with a smooth inner map offers a versatile framework for structured optimization. A unifying algorithmic idea solves easy subproblems involving the linearized inner map and a proximal penalty on the step. I sketch a typical such algorithm - ProxDescent - illustrating computational results and representative basic convergence theory. Although such simple methods may be slow (without second-order acceleration), eventual linear convergence is common. An intuitive explanation is a generic quadratic growth property - a condition equivalent to an "error bound" involving the algorithm's stepsize. The stepsize is therefore a natural termination criterion, an idea that extends to more general Taylor-like optimization models.

Joint work with D. Drusvyatskiy (Washington), A. Ioffe (Technion), S.J. Wright (Wisconsin)

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International