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:
- 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.
- 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.
- 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.
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