Source-linked AI summary
Proximal Newton-type methods for minimizing composite functions
Jason D. Lee, Yuekai Sun, Michael A. Saunders
TL;DR
Composite optimization must handle a smooth loss together with a nonsmooth function whose proximal mapping is simple. This paper develops curvature-aware proximal Newton-type methods, analyzes exact and inexact search directions, and reports fast convergence results while identifying subproblem solution cost as the main disadvantage.
Problem
Many relevant bioinformatics, signal-processing, and statistical-learning problems minimize a composite function with a smooth loss and a nonsmooth penalty handled through a proximal mapping.
Method
The paper approximates the smooth part with curvature-aware local quadratic models, retains the nonsmooth part in proximal subproblems, and analyzes both exact and inexact directions with line search or unit steps.
Results
Proximal Newton and proximal quasi-Newton methods with line search converge superlinearly, while inexact proximal Newton converges locally linearly or superlinearly depending on the forcing sequence.
Takeaways & Limitations
Many popular composite-optimization methods are special cases of proximal Newton-type methods, and the analysis provides new convergence results for some of them.
Takeaways & Limitations
The main disadvantage is the cost of solving the proximal subproblems, although inexact solves can reduce computation while retaining fast convergence.
Abstract
from arXiv · showhide
We generalize Newton-type methods for minimizing smooth functions to handle a sum of two convex functions: a smooth function and a nonsmooth function with a simple proximal mapping. We show that the resulting proximal Newton-type methods inherit the desirable convergence behavior of Newton-type methods for minimizing smooth functions, even when search directions are computed inexactly. Many popular methods tailored to problems arising in bioinformatics, signal processing, and statistical learning are special cases of proximal Newton-type methods, and our analysis yields new convergence results for some of these methods.
1. Introduction.
The paper develops proximal Newton-type methods for composite convex optimization, combining curvature-aware local models with proximal handling of nonsmooth terms. It establishes convergence results and connects the framework to widely used methods in statistical learning, signal processing, and related applications.
- 1. Introduction.: Composite objectives combine a convex continuously differentiable loss g with a convex, possibly nondifferentiable penalty h.Examples include the lasso, graphical lasso, and trace-norm matrix completion.
- 1. Introduction.: The paper generalizes Newton-type optimization to composite functions by approximating the smooth part g with a local quadratic model while retaining h in proximal form.The matrix H_k approximates the Hessian ∇^2g(x_k) and accounts for curvature.
- 1. Introduction.: Proximal Newton-type methods extend proximal gradient methods by using curvature when selecting search directions.The methods compute directions by minimizing local models and update x using a step length and search direction.
- 1. Introduction.: The framework encompasses many specialized and generic methods, including glmnet, newglmnet, QUIC, Newton-LASSO, proximal quasi-Newton, and projected Newton-type methods.The paper also places proximal Newton-type methods within the broader cost-approximation and generalized-equation literatures.
- 1.2. Newton-type methods.: The analysis covers exact and inexact proximal Newton-type methods, including adaptive control of subproblem accuracy.The stated results include superlinear convergence for proximal Newton and proximal quasi-Newton methods, with inexact proximal Newton convergence depending on the forcing sequence.
2. Proximal Newton-type methods.
Proximal Newton-type methods extend proximal-gradient ideas by incorporating curvature through a positive-definite Hessian approximation, while retaining descent and optimality properties for composite functions. The framework also covers inexact subproblem solves and multiple Newton-type variants.
- Proximal gradient foundations: Composite gradient steps minimize a local quadratic model of the smooth part plus the nonsmooth function h.They use proximal mappings to handle h and generalize the proximal gradient method’s search direction.
- Proximal gradient foundations: The composite gradient step combines an explicit gradient at x with an implicit subgradient at prox_h(x), rather than being a gradient or subgradient itself.
- Proximal Newton-type methods: Proximal Newton-type methods model curvature with a symmetric positive-definite matrix H_k ≈ ∇^2g(x_k) and compute search directions by minimizing the resulting composite local model.Choosing the exact Hessian gives proximal Newton; quasi-Newton and limited-memory updates give proximal quasi-Newton variants.
- Proximal Newton-type methods: The resulting search direction is a descent direction, and it is zero at an optimal solution exactly when the current point is optimal.These properties require a positive-definite curvature matrix H.
- Step selection: A backtracking line search accepts a step when it meets a sufficient-decrease condition, with α ∈ (0, 0.5) specifying the accepted fraction of predicted decrease.Arc search can identify a low-dimensional solution manifold, but requires solving a subproblem at each trial point.
- Inexact methods: Inexact proximal Newton methods approximately solve subproblems to reduce per-iteration computation, and an adaptive stopping criterion supports convergence and practical efficiency.The Eisenstat–Walker choice is reported to yield desirable convergence results and perform well in practice.
3. Convergence of proximal Newton-type methods.
Proximal Newton-type methods achieve global convergence under convexity and positive-definiteness assumptions, with stronger local rates under smoothness and Hessian-approximation conditions. Inexact proximal Newton methods are q-linearly or q-superlinearly convergent depending on their forcing terms.
- 3. Convergence of proximal Newton-type methods: The section’s convergence analysis covers exact proximal Newton, proximal quasi-Newton, and inexact proximal Newton methods, including adaptive control of subproblem accuracy.The forcing-term rule recovers the Eisenstat–Walker result in the smooth-function setting.
- 3.1. Global convergence: With exact subproblem solutions, proximal Newton-type methods converge globally to an optimal solution under closed convexity, attainment of the optimum, and uniformly positive-definite Hk.The global result applies from any x0 in the domain.
- 3.2. Local convergence of proximal Newton methods: The exact proximal Newton method converges q-quadratically to x⋆ when the smooth part satisfies standard strong-convexity and Lipschitz-continuity assumptions.Using Hk = ∇2g(xk), unit step lengths satisfy sufficient decrease for sufficiently large k.
- 3.3. Local convergence of proximal quasi-Newton methods: If Hk satisfies the Dennis-Moré criterion and mI ⪯ Hk ⪯ MI, proximal quasi-Newton methods converge q-superlinearly to x⋆.Under the same conditions, unit step lengths eventually satisfy sufficient decrease.
- 3.4. Local convergence of the inexact proximal Newton method: Inexact proximal Newton methods with unit step lengths converge q-linearly for sufficiently small forcing terms and q-superlinearly when those terms decay to zero.The results require x0 to be sufficiently close to x⋆; an adaptive stopping rule also yields q-superlinear convergence.
4. Computational experiments.
The experiments examine inexact proximal Newton-type search directions on inverse covariance estimation and compare proximal L-BFGS with first-order methods for logistic regression. Adaptive subproblem stopping preserves fast convergence and is especially effective when smooth-function evaluations dominate cost.
- Inverse covariance estimation: On Estrogen and Leukemia, proximal BFGS transitions empirically from linear to superlinear convergence despite log det not being strongly convex.The observed transition is characteristic of BFGS and other quasi-Newton methods with superlinear convergence.
- Inverse covariance estimation: Exact subproblem solves converge fastest per step, while adaptive stopping is fastest when time per step is included.Adaptive stopping also yields superlinear convergence; stopping after 10 iterations yields only linear convergence.
- Inverse covariance estimation: The fixed 10-iteration rule yields linear convergence, with slower convergence on Leukemia where the condition number of ˆΘ is worse.The comparison uses Estrogen and Leukemia gene-expression datasets.
- Logistic regression: On dense gisette, proximal L-BFGS clearly outperforms FISTA and SpaRSA because expensive smooth evaluations dominate computational cost.The design matrix has 30 million nonzero entries, and subproblem objectives are cheap to evaluate.
- Logistic regression: On sparse rcv1, proximal L-BFGS barely outperforms SpaRSA because smooth-function evaluation makes up a smaller share of total cost.The rcv1 design matrix has 40 million nonzero entries in a 542000 × 47000 matrix.
5. Conclusion.
The conclusion positions proximal Newton-type methods as rapidly convergent alternatives for composite minimization, while recognizing the computational cost of solving their subproblems. Inexact subproblem solutions can reduce that cost while retaining fast convergence.
- Proximal Newton-type methods converge rapidly near the optimum, can achieve high accuracy, and scale well with problem size.The conclusion also states that the proximal Newton method is insensitive to coordinate-system choice and level-set condition number.
- Proximal Newton-type methods can handle composite functions where g is not convex if the local model ˆgk remains strongly convex.Extensions of the convergence analysis are deferred to future work.
- The main disadvantage is the cost of solving subproblems, but inexact solutions can reduce this cost while retaining the fast convergence rate.
Appendix A. Proof of Lemma 3.5.
The lemma establishes sufficient descent for eventually unit-length steps under strong convexity, Lipschitz Hessian, bounded positive-definite approximations, and the Dennis-Moré criterion. The proof bounds the objective change using the composite model and shows the search direction vanishes asymptotically.
- If g is strongly convex with constant m and has Lipschitz-continuous Hessian with constant L2, bounded Hk satisfying Dennis-Moré yields eventual unit-step sufficient descent.The bounds are mI ⪯ Hk ⪯ MI for 0 < m ≤ M.
- The proof bounds f(x + ∆x) by combining the smooth term, the nonsmooth increment h(x + ∆x) − h(x), and the local-model relation.
- After substituting the model expression and rearranging, Lipschitz continuity of ∇2g and the Dennis-Moré criterion control the resulting descent terms.
- Because ∆xk converges to zero, sufficiently late iterations satisfy the required objective-change bound.