Proximal Newton-Type Methods for Minimizing Composite Functions

Jason D. Lee, Yuekai Sun, Michael A. Saunders

Introduction

In modern machine learning and bioinformatics, optimization problems often take the form of minimizing a composite function: $$f(x) = g(x) + h(x)$$ where $g$ is a smooth convex loss function (e.g., logistic regression) and $h$ is a nonsmooth convex regularizer (e.g., the $\ell_1$ norm for sparsity). While first-order methods like Proximal Gradient Descent are widely used due to their simplicity, they often suffer from slow linear convergence, particularly on ill-conditioned problems. This paper introduces a framework for Proximal Newton-type methods that leverage second-order curvature information to achieve superior convergence rates while handling the nonsmooth component $h$.

The Proximal Newton-Type Framework

The core strategy of the proposed method is to approximate the smooth part $g$ with a quadratic model at each iteration, while keeping the nonsmooth part $h$ intact. This leads to a sequence of subproblems that incorporate the Hessian (or an approximation thereof) to guide the search direction.

Algorithm 1: A generic proximal Newton-type method for composite optimization.

As shown in Algorithm 1, the method iteratively chooses a positive definite approximation $H_k$ to the Hessian and solves a subproblem for the search direction $\Delta x_k$. This subproblem is defined as: $$\Delta x_k \leftarrow \arg \min_d \nabla g(x_k)^T d + \frac{1}{2} d^T H_k d + h(x_k + d)$$ Following the determination of the search direction, a backtracking line search is employed to select a step size $t_k$ that ensures sufficient descent, maintaining the stability of the algorithm.

Technical Innovations: Scaled Mappings and Adaptive Inexactness

A significant challenge in second-order methods for composite optimization is the computational cost of solving the quadratic subproblem. The authors address this through two primary innovations:

  1. Scaled Proximal Mappings: The standard proximal operator is generalized to a "scaled" version defined by the Hessian $H$. This allows the algorithm to account for the local geometry of the function, which is critical for achieving superlinear convergence.
  2. Adaptive Stopping Criteria: Solving the subproblem to high precision in every iteration is often unnecessary, especially when far from the optimum. The authors introduce an "inexact" framework with an adaptive "forcing sequence." This strategy ensures the subproblem is solved only as accurately as needed to maintain fast global convergence, preventing "oversolving" in early iterations.

Empirical Evaluation

The effectiveness of the Proximal Newton-type methods was evaluated on high-dimensional datasets across two problem classes: $\ell_1$-regularized logistic regression and Inverse Covariance Estimation (Graphical Lasso).

Datasets

  • Logistic Regression: Evaluated on the Gisette dataset (5,000 features) and the rcv1 news archive (47,000 features).
  • Graphical Lasso: Evaluated on gene expression datasets including Estrogen (682 probe sets) and Leukemia (1255 genes).

Key Results

The theoretical analysis proves that the exact method achieves quadratic convergence, while the Quasi-Newton (e.g., L-BFGS) variant achieves superlinear convergence. These rates are preserved even in the inexact version under the proposed adaptive stopping conditions.

Empirically, the Proximal L-BFGS method (implemented in the PNOPT software) demonstrated significant performance gains. On the Gisette dataset, it outperformed state-of-the-art first-order solvers like FISTA and SpaRSA in both total wall-clock time and the number of function evaluations. Furthermore, the method showed remarkable robustness to the condition number of the problem, a common failure point for first-order techniques.

Conclusion and Future Work

Proximal Newton-type methods provide a rigorous and efficient bridge between second-order optimization and nonsmooth regularization. By trading off more computation per iteration for a drastic reduction in the total number of iterations, these methods offer a powerful alternative for large-scale composite optimization.

While the current framework assumes convexity for both $g$ and $h$, future work may extend these guarantees to non-convex functions. Additionally, developing specialized subproblem solvers for complex regularizers beyond the $\ell_1$ norm remains an active area of interest.

Summary updated

Abstract

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.
BibTeX
@article{lee2014proximal,
  author = {Jason D. Lee and Yuekai Sun and Michael A. Saunders},
  title = {{Proximal Newton-Type Methods for Minimizing Composite Functions}},
  journal = {SIAM J. Optim.},
  year = {2014},
  doi = {10.1137/130921428},
}
Figure