TL;DR
This paper introduces a novel active-set method for solving $\ell_1$-regularized convex quadratic optimization problems, which are common in machine learning and signal processing. The method combines a proximal method of multipliers (PMM) with a semismooth Newton (SSN) solver, efficiently handling sparsity and box constraints. It demonstrates superior performance and scalability compared to existing methods on various regression and PDE-constrained optimization tasks.
What Problem Does This Paper Address?
Many modern applications, particularly in machine learning and signal processing, require solving optimization problems that promote sparsity in the solution. This often translates to $\ell_1$-regularized convex quadratic optimization problems. While first-order methods can find approximate solutions, achieving high accuracy necessitates second-order methods. Existing second-order methods, like interior-point methods (IPMs) or standard Newton-like approaches, often struggle with large-scale problems due to ill-conditioned linear systems, high memory requirements, or limited robustness. This paper aims to develop a robust, efficient, and scalable second-order method that can handle separable $\ell_1$ terms and box constraints effectively.
Methods
The core of the proposed method is an active-set strategy integrated within a primal-dual proximal method of multipliers (PMM). The PMM framework is used to iteratively refine estimates of primal and dual variables. For solving the sub-problems arising from the PMM, a standard semismooth Newton (SSN) method is employed. A key innovation is the use of preconditioned Krylov subspace methods (specifically MINRES) to solve the linear systems generated by the SSN. The authors propose optimal preconditioners that are robust with respect to the PMM's penalty parameters. To further enhance efficiency, a warm-starting strategy using a proximal alternating direction method of multipliers (pADMM) is incorporated, allowing the algorithm to begin from a good initial guess. The method explicitly handles box constraints without introducing auxiliary variables, simplifying the linear systems.
Datasets
The paper evaluates the proposed method on:
- Elastic-net linear regression problems: Using four standard regression datasets from the LIBSVM library (abalone, cpusmall, YearPredictionMSD, E2006-tfidf).
- PDE-constrained optimization problems: Specifically, $\ell_1/\ell_2$-regularized Poisson optimal control problems and convection-diffusion optimal control problems. These problems are discretized using Q1 finite elements.
Key Insights and Ideas
- Active-set strategy for sparsity: By implicitly identifying active variables, the method can potentially reduce the size of the problem at each iteration, leading to more efficient linear system solves.
- Robust Preconditioners: The development of general-purpose, optimal preconditioners for the SSN linear systems is crucial. These preconditioners are shown to be robust to the PMM's penalty parameters, a common challenge in such methods.
- Warm-starting for efficiency: The pADMM-based warm-start significantly improves practical performance by providing a good initial guess, leading to faster convergence, especially for ill-conditioned problems.
- Scalability: The combination of an active-set approach, efficient preconditioning, and warm-starting allows the method to scale better than competitors, particularly on larger and more challenging instances.
Key Results
- Superior Performance: The active-set method consistently outperforms IP-PMM and OSQP on several large-scale and ill-conditioned problems, especially in terms of computational time and memory usage.
- Reliability: The method demonstrates robustness across various regularization parameters and problem sizes, successfully solving instances where other methods fail due to memory limitations or convergence issues.
- Efficiency: For elastic-net regression, the active-set method often requires fewer SSN iterations than IP-PMM's interior-point iterations, leading to fewer Krylov iterations due to better-conditioned linear systems.
- Scalability: The method shows excellent scalability on PDE-constrained optimization problems, handling large grid sizes and complex dynamics where other methods struggle. For instance, it successfully solves instances from the E2006-tfidf dataset, which caused memory issues for IP-PMM and OSQP.
Limitations and Future Work
- Assumptions: The convergence analysis relies on certain assumptions, such as primal and dual feasibility, and additional regularity conditions for superlinear convergence.
- Generalization: This paper focuses on separable $\ell_1$ terms. The authors mention an accompanying paper that extends the methodology to general piecewise-linear terms, which would broaden its applicability.
- Numerical Performance: While the proposed preconditioner is effective, further exploration of non-diagonal Hessian approximations within the preconditioner is suggested for potentially even better performance on certain instances.
- Comparison with IPMs: The authors acknowledge that IPMs might still be more robust for arbitrary convex quadratic instances without sparsity-inducing terms, but for problems with $\ell_1$ regularization, their active-set method offers significant advantages.
Summary updated