A Unified Framework for Sparse Relaxed Regularized Regression: SR3

Peng Zheng; Travis Askham; Steven L. Brunton; J. Nathan Kutz; Aleksandr Y. Aravkin

Source-linked AI summary

A Unified Framework for Sparse Relaxed Regularized Regression: SR3

Peng Zheng, Travis Askham, Steven L. Brunton, J. Nathan Kutz, Aleksandr Y. Aravkin

arXiv:1807.05411v4Jul 14, 2018stat.MLcs.LGmath.OC

TL;DR

Sparse regularized regression needs methods that remain effective on large, ill-conditioned, noisy, missing, and nonconvex problems. SR3 relaxes the original problem with an auxiliary variable, and the paper reports better solution quality, conditioning, convergence, and flexibility across several applications. Its broader application to neural networks is explicitly left beyond the manuscript’s scope.

Problem
Sparse regression faces restrictive practical conditions, limited fast solvers for large ill-conditioned problems, difficulties with nonconvex implementations, and high-fidelity data requirements.
Method
SR3 reformulates regularized regression with an auxiliary variable w constrained near Cx, separating sparsity and accuracy requirements and supporting composite and nonconvex regularizers.
Results
SR3 improves computational efficiency, accuracy, convergence rates, and flexibility across compressed sensing, LASSO, matrix completion, total variation, and group sparsity.
Takeaways & Limitations
The relaxation provides a broadly applicable architecture for sparse regularized regression, with w especially useful for identifying supports in noisy and ill-conditioned settings.
Takeaways & Limitations
Applying the architecture to neural networks is beyond the scope of the manuscript.

Abstract

from arXiv · show

Regularized regression problems are ubiquitous in statistical modeling, signal processing, and machine learning. Sparse regression in particular has been instrumental in scientific model discovery, including compressed sensing applications, variable selection, and high-dimensional analysis. We propose a broad framework for sparse relaxed regularized regression, called SR3. The key idea is to solve a relaxation of the regularized problem, which has three advantages over the state-of-the-art: (1) solutions of the relaxed problem are superior with respect to errors, false positives, and conditioning, (2) relaxation allows extremely fast algorithms for both convex and nonconvex formulations, and (3) the methods apply to composite regularizers such as total variation (TV) and its nonconvex variants. We demonstrate the advantages of SR3 (computational efficiency, higher accuracy, faster convergence rates, greater flexibility) across a range of regularized regression problems with synthetic and real data, including applications in compressed sensing, LASSO, matrix completion, TV regularization, and group sparsity. To promote reproducible research, we also provide a companion MATLAB package that implements these examples.

I. INTRODUCTION

SR3 addresses persistent challenges in sparse regularized regression by relaxing the original problem and separating sparsity from accuracy requirements. The resulting formulation supports broad regularizers while improving conditioning, convergence, and solution quality.

Motivation: Sparse regression remains difficult because practical performance can require restrictive theory, fast solvers are lacking for large ill-conditioned problems, nonconvex methods are challenging, and data may need high fidelity.
Contributions: SR3 is reported to improve computational efficiency, accuracy, convergence rates, and flexibility across compressed sensing, LASSO, matrix completion, total variation, and group sparsity.
SR3 formulation: SR3 introduces an auxiliary variable w constrained to remain close to Cx, allowing sparsity and accuracy requirements to be split between w and x.The relaxation parameter κ controls both the gap between Cx and w and the trade-off between improved geometry and fidelity to the original problem.
Generality: The relaxed framework applies to convex and nonconvex regularizers, including ℓ1, ℓp with p < 1, SCAD, compressed sensing, and total variation.The formulation also covers linear composite regularizers through the choice of C.
Value-function geometry: Partial minimization in x yields a problem in w with nearly spherical level sets, making support identification easier than with the elongated ellipses of the original least-squares geometry.For square orthogonal C, the transformed map Fκ shrinks singular values with less shrinkage for smaller ones, reducing the condition number.
Theory: When λ = 0, SR3 and the original formulation share the same solution set, while the relaxed problem can have substantially better conditioning under appropriate assumptions on C.For square orthogonal C, choosing κ as described gives cond(Fκ) ≤ 1 + cond(A)/µ.

B. Algorithms for the SR3 Problem

SR3 solves a relaxed regularized problem with proximal-gradient and related algorithms that support convex and nonconvex regularizers. The relaxation yields simpler proximal updates, convergence guarantees, and improved behavior for ill-conditioned problems.

Algorithmic formulation: SR3 applies proximal-gradient updates to the relaxed problem, using the prox of R(w) rather than a composed regularizer.This avoids the potentially difficult iterative prox evaluation required for the original formulation when C ≠ I.
Convergence: SR3 converges at a sublinear rate to a stationary point of its regularized least-squares objective.The stated theorem applies to SR3's value function, including settings where R may be nonsmooth and nonconvex.
Convergence: SR3 convergence rates depend less on A than the corresponding original-problem rates, including independence from A when A is rank-deficient.For full-rank A, the dependence is characterized as weak in the cited theorem.
Conditioning and trade-offs: When C^⊤C = I and n > d, SR3 remains implementable with rates given by a separate corollary, although the comparison algorithm may not be implementable.The stated limitation concerns the original comparison algorithm, not SR3 itself.
Algorithmic formulation: The SR3 algorithm supports both convex and nonconvex regularizers whenever their proximal operators are available.Examples include soft-thresholding for the ℓ1 norm and several nonconvex proximal operators.

C. Nonconvex Regularizers and Constraints

SR3 accommodates nonconvex sparsity regularization through specialized proximal operators. For the ℓ0 penalty, the method uses hard thresholding instead of soft thresholding.

Nonconvex regularizers: The ℓ0 regularizer counts nonzero entries and uses hard thresholding as its proximal operator in SR3.This replaces the soft-thresholding operator used for the ℓ1 regularizer in the algorithm.

1) Nonconvex Regularizers:

The paper extends SR3 across nonconvex penalties, constraints, and applications including LASSO, compressed sensing, and total variation. The framework combines available proximal operators with a relaxation whose parameter trades original-problem optimality against easier computation.

Nonconvex regularizers: For 0 < p < 1, the ℓp regularizer promotes sparsity through a nonconvex proximal subproblem that can be solved globally coordinatewise.A provably convergent Newton method is available for all p, and ℓ1/2 is reported as particularly important for compressed sensing.
Nonconvex regularizers: The clipped absolute deviation regularizer reduces bias, and its combination with SR3 obtains the best compressed-sensing results reported in the paper.The cited passage refers to the un-smoothed CAD form and its analytic proximal operator.
Applications: In total variation, SR3 handles TV(x) = R(Cx) = ∥Cx∥1 with a primal proximal-gradient method rather than the primal-dual methods commonly used for the composition.The difference matrix C supplies the analysis operator in the TV formulation.
Constraints: SR3 supports projection-based constraints, including convex non-negativity and nonconvex spherical constraints.These constraints are represented by indicator-function regularizers whose proximal operators are projections.
Relaxation trade-off: As κ increases, the relaxed solution moves closer to optimality for the original problem, while smaller κ values make the relaxed problem easier to solve.Moderate κ values produce useful solutions across applications according to the paper's practical observation.
Applications: SR3 is applied to variable selection, compressed sensing, total-variation denoising, and matrix completion, with support identification emphasized for noisy or ill-conditioned data.The LASSO experiments use noisy observations, and the paper reports improved support usefulness in that setting.

1) LASSO Path.:

Across sparse regression experiments, SR3 improves support recovery, noise robustness, and computational efficiency, while extending to compressed sensing, analysis formulations, and total variation regularization. Its advantages are strongest for ill-conditioned or coherent measurement settings, though specific applications retain scope limitations.

LASSO path: SR3 recovers the support without false positives across the LASSO path until overfitting begins at the 201st nonzero entry.LASSO makes mistakes early along the path, whereas SR3 maintains support recovery throughout the stated range.
Noise robustness: SR3 achieves a uniformly higher F1-score than LASSO across the tested noise levels.The comparison uses 200 random trials over noise levels σ ∈ {0.2i : i = 0, 1, ..., 20}.
Computational efficiency: SR3 requires far fewer iterations than ADMM and proximal gradient methods while retaining nearly identical per-iteration complexity.ADMM and SR3 require one-time formation and factorization of an n × n matrix, unlike IRucLq-v, which repeats matrix formation and inversion each iteration.
Compressed sensing: For coherent uniform measurements, SR3 recovery is only slightly degraded and is the only approach with perfect recovery at m/k ≤ 10.The perfect-recovery formulations are SR3-CAD, SR3-ℓ1/2, and SR3-ℓ0.
Analysis versus synthesis: SR3 directly extracts sparse analysis coefficients through w, whereas standard analysis requires post-processing because Cx is not completely sparse.In the reported comparison, w captures the true support cleanly while Cx requires thresholding for a support estimate.
Total variation regularization: For total variation deblurring, FISTA acceleration makes SR3 converge much more rapidly to the minimum loss, although unaccelerated SR3 has comparable SNR to standard TV.The reported SNRs are approximately 26.10 for SR3 and 26.03 for standard TV, with variation depending on parameter choice and iteration limits.

C. SR3 for Exact Derivatives

SR3 uses an auxiliary derivative variable to recover piecewise-constant signals and estimate their discrete derivatives. In the synthetic TV example, ℓ0 regularization produced a more faithful derivative magnitude and integrated reconstruction than ℓ1.

Visualization: Figure 9 compares recovered signals against the true signal in its first row and estimated derivatives against true magnitudes in its second row.The columns correspond to ℓ0 and ℓ1 regularization.
Derivative recovery: SR3 TV regularization uses a forward-difference map so the auxiliary variable w estimates the signal’s discrete derivative.The recovered signals and derivative estimates are compared for ℓ0 and ℓ1 regularizers.
Derivative recovery: Both ℓ0 and ℓ1 reasonably identify derivative-support groups, enabling accurate piecewise-constant signal recovery after grouping.The grouping procedure averages x over contiguous indices where w_i = 0.
Regularizer comparison: ℓ0-TV gives a less biased derivative-magnitude estimate than ℓ1-TV, producing a more faithful signal after integration.This generic inversion avoids relying on an explicit step-function assumption.

D. SR3 for Matrix Completion

SR3 is applied to low-rank matrix completion for seismic interpolation with heavily subsampled data. Across image quality and Pareto-frontier comparisons, SR3 and ℓ0 formulations outperform their classic and ℓ1 counterparts.

Problem setup: The seismic interpolation task addresses missing-data artifacts caused by subsampled sources and receivers in computationally expensive acquisition settings.The method targets simultaneous signal sampling and compression for seismic applications.
SR3 formulation: SR3 relaxes the classic rank-penalty formulation and alternates least-squares updates for X with singular-value thresholding for W.The recovered interpolation is evaluated using X rather than the auxiliary W.
Problem setup: 85% of the data is missing in the frequency-slice experiment, which is transformed to the midpoint-offset domain before interpolation.The slice is arranged as a 401×401 matrix and transformed back for comparison.
Results: SR3 fits the original data better than the classic formulation, reaching a maximum SNR of 12.6.The comparison uses SNR because image quality is difficult to assess visually.
Results: ℓ0 formulations achieve better data fitting at a given rank than ℓ1 formulations, while SR3 Pareto curves lie below the corresponding classic curves.Lower Pareto curves indicate lower observed-data misfit for the same rank.

E. SR3 for Group Sparsity

SR3 handles group sparsity by relaxing pairwise-difference penalties across multiple underdetermined systems. In the synthetic experiment, its auxiliary variable identifies shared groups that enable a near-optimal refit.

Problem setup: Group sparsity regularizes multiple underdetermined learning tasks by encouraging redundancy among their solution vectors.The formulation assumes that some systems may share the same solution vector.
Problem setup: The original group-sparsity objective is difficult because the composed ℓ2 penalty is nonsmooth and lacks an efficient proximal operation.Pairwise differences are represented through a linear mapping D.
SR3 formulation: SR3 introduces auxiliary variables w_ij to approximate the pairwise differences D_ijx.This relaxation separates the composite penalty from the primary variables.
Experiment: With n = 200, m_i = 150, k = 7, Gaussian sensing matrices, and noise level σ = 0.1, the experiment tests recovery of predefined groups.The problem uses underdetermined random linear systems.
Results: 47% relative error from the direct SR3 solution falls to 1% after regrouping least-squares problems using the pattern discovered by w.The 1% error is described as essentially optimal given the noise.
Discussion: The paper presents SR3 as a broadly applicable architecture satisfying robustness, computational-efficiency, and generalizability goals for sparse regression.The discussion also identifies automatic parameter tuning as future work.

APPENDIX

The appendix reviews nonsmooth optimization concepts, proximal operators, and algorithms supporting SR3 for convex and nonconvex regularizers. It emphasizes stationarity for nonconvex problems and gives operator-specific examples and limitations.

Optimization preliminaries: For nonconvex objectives, stationarity is necessary but not sufficient for global optimality, so iterative methods target stationary points.Distance to stationarity is used to detect convergence and analyze algorithms.
Moreau envelope: The Moreau envelope smooths proper closed convex functions, but it may remain nonsmooth when the underlying function is nonconvex.The ℓ0 example illustrates this nonconvex limitation.
Proximal operators: The ℓ1 proximal operator is element-wise soft-thresholding, whereas the ℓ0 proximal operator is element-wise hard-thresholding.These operators enable SR3 updates for common sparse regularizers.
Proximal operators: The ℓ2-squared proximal operator scales the input vector, while the ℓ2 norm promotes group sparsity and does not decouple into scalar problems.The ℓ2 norm nevertheless has a closed-form solution.
Algorithms: Proximal gradient descent alternates a gradient step on the smooth term with a proximal update for the nonsmooth term.The appendix gives the iteration x^k = prox_ηg(x^(k−1) − η∇f(x^(k−1))).

Proximal Gradient Descent

This section states assumptions and convergence context for proximal gradient descent applied to p = f + g. Under convexity and Lipschitz-gradient conditions, it gives a standard convergence result.

Proximal gradient descent is presented for objectives of the form p(x) = f(x) + g(x).
The theorem assumes that p and g are closed convex functions and defines optimal values and solutions.
When ∇f is β-Lipschitz continuous, the prescribed step size is 1/β.
The section identifies these convergence results as well known in the proximal-gradient literature.

THEORETICAL RESULTS

The theoretical results explain SR3's empirical advantages through the relaxed coordinates w. They derive a w-only formulation, analyze its conditioning, and relate relaxed and original solutions.

The analysis derives an explicit SR3 formulation in the relaxed coordinates w alone.
The w-only problem has greatly improved conditioning compared with the original regression problem.
The theory also obtains a quantitative measure of the distance between solutions of the original problem and the SR3 relaxation.
The analysis uses singular-value decompositions of A and C to characterize spectral properties of the relaxed problem.
The condition-number expression depends on σmin(A⊤A), σmax(C⊤C), and the relaxation parameter κ.

2) Proof of Theorem 2.:

This proof section applies proximal-gradient iterates and first-order optimality conditions to establish the stated convergence result. The derivation proceeds through successive inequalities and simplification.

The proof analyzes the iterates generated by the proximal gradient method.
It combines the iterates with a first-order optimality condition to derive the needed inequality.
After summing and simplifying the inequalities, the proof obtains the desired convergence result.
The result is obtained by combining Theorem 2 and Theorem 1.

4) Proof of Corollary 2.:

This section relates solutions of the original and relaxed problems under fixed κ and C = I, then gives a corollary for orthogonal designs. It also summarizes implementation details for a nonconvex scalar subproblem.

4) Proof of Corollary 2.:: The solution-comparison analysis fixes κ as a constant and sets C = I.
4) Proof of Corollary 2.:: The proof uses optimality conditions and subgradient sets for the original and relaxed problems.
4) Proof of Corollary 2.:: When A⊤A = I, the relaxed solution is a stationary point of the original problem.
4) Proof of Corollary 2.:: When AA⊤ = I, the distance from zero to the relevant subgradient set is bounded by 1/(1 + 2κ).
4) Proof of Corollary 2.:: The implementation analyzes derivatives and uses Newton's method to locate a local minimum before comparing it with the value at zero.