TL;DR
This paper introduces a novel active-set method for solving $\ell_1$-regularized convex quadratic optimization problems, combining a proximal method of multipliers (PMM) with a semismooth Newton (SSN) approach. The method demonstrates strong performance, outperforming existing solvers like OSQP and IP-PMM on various regression and PDE-constrained optimization tasks, particularly for large-scale and ill-conditioned problems.
What Problem Does This Paper Address?
Many real-world problems in machine learning, signal processing, and control theory involve solving $\ell_1$-regularized convex quadratic optimization problems. These problems often arise from the need for sparse solutions or as sub-problems in larger optimization frameworks. While first-order methods can find approximate solutions, achieving high accuracy requires second-order methods. Existing second-order methods, such as interior-point methods (IPMs) or standard Newton-like approaches, can struggle with computational cost, memory requirements, or numerical stability, especially when dealing with the non-smoothness introduced by $\ell_1$ regularization and box constraints. This paper aims to develop a robust, efficient, and scalable second-order method that effectively handles these challenges.
Methods
The core of the proposed method is an active-set strategy built upon a primal-dual proximal method of multipliers (PMM). The PMM iteratively updates primal and dual variables, and at each step, it requires solving a sub-problem. This sub-problem, which involves a non-smooth composite objective, is tackled using a standard semismooth Newton (SSN) method. The linear systems arising from the SSN are solved efficiently using preconditioned Krylov subspace methods (specifically, MINRES). A key contribution is the development of general-purpose, positive-definite preconditioners for these linear systems that are robust with respect to the PMM's penalty parameters. To further enhance practical efficiency, the algorithm incorporates a warm-starting strategy using a proximal alternating direction method of multipliers (pADMM).
Datasets
The paper evaluates the proposed method on:
- Elastic-net linear regression: Using four real-world regression datasets from the LIBSVM library: abalone, cpusmall, YearPredictionMSD, and E2006-tfidf.
- PDE-constrained optimization: Specifically, Poisson optimal control and convection-diffusion optimal control problems. These problems are discretized using Q1 finite elements, leading to large-scale optimization instances.
Key Insights and Ideas
- Synergy of PMM and SSN: Combining PMM with SSN for sub-problem solving effectively handles the non-smoothness of $\ell_1$ regularization and box constraints, leading to a robust algorithm.
- Effective Preconditioning: The development of general-purpose, optimal preconditioners for the SSN linear systems is crucial for the efficiency of the Krylov subspace solver. These preconditioners are shown to be robust against PMM parameter changes.
- Warm-starting Advantage: Using pADMM for warm-starting significantly improves the practical performance, especially for problems where an initial good estimate is available.
- Active-Set Efficiency: By implicitly managing active sets, the method avoids the need for auxiliary variables and potentially reduces the size of the linear systems compared to IPMs.
Key Results
- Convergence Guarantees: The PMM component is shown to achieve global convergence under mild feasibility assumptions, with global linear and local superlinear convergence under additional standard assumptions. The SSN component offers local superlinear convergence.
- Performance Comparison: The active-set method consistently outperforms OSQP (an ADMM-based solver) and IP-PMM (a regularized IPM solver) in terms of speed and reliability, especially on large-scale and ill-conditioned problems.
- Scalability and Memory: The method demonstrates superior scalability and memory efficiency, successfully solving instances that cause memory issues for IP-PMM and OSQP. For example, it handles large instances from the E2006-tfidf dataset that other solvers fail on.
- Numerical Examples: In elastic-net regression, the active-set method often requires fewer SSN iterations than IP-PMM requires interior-point iterations, leading to fewer Krylov iterations due to better-conditioned linear systems. For PDE-constrained optimization, the method achieves high accuracy (tol=10β»βΆ) efficiently and reliably, outperforming others in terms of speed and robustness across various regularization parameters and grid sizes.
Limitations and Future Work
- Limitations: While the method is robust, the paper notes that IPMs might still be more competitive for arbitrary convex quadratic instances without $\ell_1$ terms due to their theoretical properties. The current preconditioner is designed for $n \ge m$, and alternative strategies are suggested for $m > n$.
- Future Work: The authors mention an accompanying paper that extends the methodology to problems with general piecewise-linear terms, allowing for full exploitation of their structure. They also suggest that non-diagonal approximations of the Hessian within the preconditioner could be explored for certain instances.
Summary updated