Efficient evaluation of scaled proximal operators
It provides an efficient computational tool for a broad class of convex optimization problems, particularly benefiting applications in machine learning and signal processing that use quadratic-support regularizers.
The paper shows how to efficiently compute the proximal operator of quadratic-support functions using an interior method, achieving nearly linear cost in input size for structured problems, enabling quasi-Newton methods for nonsmooth optimization in sparse optimization, image denoising, and sparse logistic regression.
Quadratic-support functions [Aravkin, Burke, and Pillonetto; J. Mach. Learn. Res. 14(1), 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 cost 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.