Error bounds and convergence of proximal methods for composite minimization

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)Non UBCUnreviewedAuthor affiliation: Cornell UniversityFacult