Abstract. We introduce a framework for quasi-Newton forward-backward splitting algorithms (proximal quasiNewton methods) with a metric induced by diagonal ± rank-r symmetric positive definite matrices. This special type of metric allows for a highly efficient evaluation of the proximal mapping. The key to this efficiency is a general proximal calculus in the new metric. By using duality, formulas are derived that relate the proximal mapping in a rank-r modified metric to the original metric. We also describe efficient implementations of the proximity calculation for a large class of functions; the implementations exploit the piece-wise linear nature of the dual problem. Then, we apply these results to acceleration of composite convex minimization problems, which leads to elegant quasi-Newton methods for which we prove convergence. The algorithm is tested on several numerical examples and compared to a comprehensive list of alternatives in the literature. Our quasi-Newton splitting algorithm with the prescribed metric compares favorably against state-of-the-art. The algorithm has extensive applications including signal processing, sparse recovery, machine learning and classification to name a few. Key words. forward-backward splitting, quasi-Newton, proximal calculus, duality. AMS subject classifications. 65K05, 65K10, 90C25, 90C31. 1. Introduction. Convex optimization has proved to be extremely useful to all quantitative disciplines of science. A common trend in modern science is the increase in size of datasets, which drives the need for more efficient optimization schemes. For large-scale unconstrained smooth convex problems, two classes of methods have seen the most success: limited memory quasi-Newton methods and non-linear conjugate gradient (CG) methods. Both of these methods generally outperform simpler methods, such as gradient descent. However, many problems in applications have constraints or should be modeled naturally as non-smooth optimization problems. A problem structure that is sufficiently broad to cover many applications in machine learning, signal processing, image processing, computer vision (and many others) is the minimization of the sum of two convex function, one being smooth and the other being non-smooth and "simple" in a certain way. The gradient descent method has a natural extension to these structured non-smooth optimization problems, which is known as proximal gradient descent (which includes projected gradient descent as a sub-case) or forward-backward splitting [5] . Algorithmically, besides a gradient step with respect to the smooth term of the objective, the generalization requires to solve proximal subproblems with respect to the non-smooth term of the objective. The property "simple" from above refers the proximal subproblems. In many situations, these subproblems can be solved analytically or very efficiently. However, a change of the metric, which is the key feature of quasi-Newton methods or non-linear CG, often leads to computationally hard subproblems. While the convergence of proximal quasi-Newton methods has been analyzed to some extent in the context of variable metric proximal gradient methods, little attention is paid to the efficient evaluation of the subproblems in the new metric. In this paper, we emphasize the fact that quasiNewton methods construct a metric with a special structure: the metric is successively updated using low rank matrices. We develop efficient calculus rules for a general rank-r modified metric. This allows popular quasi-Newton methods, such as the SR1 (symmetric rank-1) and the L-BFGS methods, to be efficiently applied to structured non-smooth problems. The SR1 method pursues a rank-1 update of the metric and the L-BFGS method uses a rank-2 update. We consider the results in this paper as a large step toward the applicability of quasi-Newton
Recently, proximal mappings with respect to metrics of type "identity plus/minus rank R" have been studied in REF .
On Quasi-Newton Forward--Backward Splitting: Proximal Calculus and Convergence
arXiv: Optimization and Control
Computer Science Mathematics