Volume 46, pp. 1-22, 2017.

Efficient evaluation of scaled proximal operators

Michael P. Friedlander and Gabriel Goh

Abstract

Quadratic-support functions, cf. Aravkin, Burke, and Pillonetto [J. Mach. Learn. Res., 14 (2013)], constitute a parametric family of convex functions that includes a range of useful regularization terms found in applications of convex optimization. We show how an interior method can be used to efficiently compute the proximal operator of a quadratic-support function under different metrics. When the metric and the function have the right structure, the proximal map can be computed with costs nearly linear in the input size. We describe how to use this approach to implement quasi-Newton methods for a rich class of nonsmooth problems that arise, for example, in sparse optimization, image denoising, and sparse logistic regression.

Full Text (PDF) [956 KB]

Key words

support functions, proximal-gradient, quasi-Newton, interior method

AMS subject classifications

90C15, 90C25

< Back