A Fast Dual Projected Newton Method for l1-Regularized Least Squares

Pinghua Gong, Changshui Zhang

Introduction

$\ell_1$-regularized least squares, commonly known as the Lasso problem, is a fundamental tool in modern machine learning, signal processing, and statistics. Its primary appeal lies in its ability to produce "sparse" solutions—models where the majority of coefficients are zero. This sparsity is crucial for both model interpretability and memory efficiency in large-scale applications.

Despite its utility, the $\ell_1$ norm presents a significant optimization challenge: it is non-differentiable at zero. This "pointy" nature of the objective function makes standard calculus-based optimization methods inapplicable. Historically, solvers for this problem have fallen into three main categories:

  1. Reformulation: These methods double the number of variables to transform the non-differentiable problem into a standard constrained quadratic program. However, this approach is often computationally expensive.
  2. First-order methods: Algorithms like FISTA and SpaRSA rely solely on gradient information. While easy to implement, they typically exhibit linear convergence rates and struggle as the regularization parameter $\tau$ becomes smaller.
  3. Active-set methods: These heuristics attempt to identify the non-zero variables but often lack the theoretical guarantees required for consistently fast convergence.

This paper introduces the Dual Projected Newton Method (DPNM), a second-order approach designed to bridge the gap between theoretical speed and computational efficiency.

Methodology

The core innovation of DPNM is the transformation of the Lasso problem into a dual space that is more amenable to second-order optimization.

Dual Formulation with Box Constraints

Most dual formulations of the Lasso problem involve complex constraints. The authors derive a dual problem that is a quadratic program characterized by simple box constraints—specifically, every variable is constrained to lie within the interval $[-\tau, \tau]$. This simplification is pivotal because it allows for efficient projection of candidate solutions back into the feasible region.

The Projected Newton Method

By leveraging the box-constrained dual formulation, the authors apply a Newton method, which utilizes second-order derivative information (the Hessian). Unlike first-order methods that can oscillate near the optimum, the Newton method accounts for the curvature of the optimization landscape, enabling more direct paths to the solution.

Computational Optimizations

To overcome the $O(n^3)$ cost typically associated with inverting the Hessian in Newton methods, DPNM employs several optimizations:

  • Precomputation: The inverse Hessian is computed once at the start of the algorithm.
  • Active-Set Identification: The algorithm identifies an "active set" of variables—those currently at the box boundaries.
  • Cholesky Decomposition: By solving the Newton step only for the "non-active" variables using Cholesky decomposition, the computational cost per iteration is significantly reduced.

The authors provide a theoretical guarantee that the algorithm achieves a quadratic convergence rate, meaning the precision of the solution approximately doubles with each iteration.

Experimental Evaluation

The performance of DPNM was benchmarked against several state-of-the-art solvers, including BPR, L1LS, FISTA, and SpaRSA. The evaluation spanned six diverse real-world datasets:

  • ExtYaleB & YaleB: Image reconstruction tasks using face databases.
  • USPS: Handwritten digit recognition.
  • PIE: A face database featuring variations in pose and illumination.
  • Isolet: Spoken letter recognition.
  • dna: Classification of biological sequence data.

Key Results

The experimental results demonstrate that DPNM is consistently more efficient and robust than its competitors.

Convergence Speed and Precision

While first-order methods often require thousands of iterations to reach a solution—sometimes failing to converge within a 10,000-iteration limit—DPNM typically reaches the optimal solution in fewer than 20 iterations. This efficiency is a direct result of its quadratic convergence rate.

Comparison of objective values achieved by DPNM and other solvers across six datasets at varying tolerance levels.

As shown in Figure 4, DPNM consistently achieves lower or comparable objective values across all datasets and tolerance levels. Notably, DPNM maintains high precision even at coarser tolerances, where other methods may struggle to find a stable solution.

Performance in the Small-τ Regime

A unique advantage of DPNM is its behavior as the regularization parameter $\tau$ decreases. In this "weak regularization" regime, the feasible region in the dual space shrinks. This makes the optimal solution easier for a projected method to locate, whereas first-order methods typically experience a significant slowdown.

Conclusion and Future Work

DPNM represents a significant advancement in solving $\ell_1$-regularized least squares problems by effectively utilizing second-order information. However, some limitations remain. The current derivation assumes a full-rank matrix $A^TA$, which may not hold in high-dimensional settings where the number of features $n$ greatly exceeds the number of samples $m$. Additionally, the initial $O(n^3)$ overhead for the inverse Hessian computation could be a bottleneck for extremely large-scale problems.

Future research will focus on extending DPNM to handle rank-deficient cases and further optimizing the initial computational requirements to support even higher-dimensional datasets.

Summary updated

BibTeX
@inproceedings{gong2011fast,
  author = {Pinghua Gong and Changshui Zhang},
  title = {{A Fast Dual Projected Newton Method for l1-Regularized Least Squares}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
}
Figure