Open Collections

Error bounds and convergence of proximal methods for composite minimization

Banff International Research Station for Mathematical Innovation and Discovery

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)

Mathematics; Operations research, mathematical programming; Operator theory; Control/optimization/operation research

video/mp4

Author affiliation: Cornell University

2018-03-26

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/64937

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/