Research map / Learning theory and algorithms / Kernels and regression theory
The Reliability of OKRidge Method in Solving Sparse Ridge Regression Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives a high-dimensional asymptotic error analysis (via CGMT) of the OKRidge sparse ridge regression estimator, showing its normalized squared error converges to a constant determined by the regularizer λ, and validates this with synthetic experiments.
Problem
Sparse ridge regression (k-SRO) is NP-hard, and while OKRidge is a fast and accurate solver, it lacked theoretical error analysis, limiting its reliable large-scale use.
Approach
Rewrites the OKRidge estimation error as a primary optimization problem using a Fenchel-Moreau reformulation of an equivalent tight lower bound, then applies the convex Gaussian min-max theorem to reduce it to a scalar auxiliary problem, yielding a closed-form limit of NSE as a function of λ.
Key results
- For fixed lambda, NSE converges to a constant as sigma goes to 0, matching the theoretical limit Delta(lambda) = D̄(λ)/(1−D̄(λ)) in numerical experiments with d=100, n/d=0.5, k/d=0.1 averaged over 10 trials.
- NSE as sigma goes to 0 depends on lambda, and the empirical curves converge to the theoretical prediction as sigma^2 decreases (0.1, 0.01, 0.001).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Fix the regularizer parameter λ | OKRidge · k-sparse linear regression with Gaussian inputs and noise | NSE | No clear effect |
| Reduce the noise level σ toward zero | OKRidge · k-sparse linear regression with Gaussian inputs and noise | squared estimation error | Helped |
| Vary the regularizer parameter λ | OKRidge · k-sparse linear regression with Gaussian inputs and noise | NSE | Mixed |
Limitations
- Theory relies on Gaussian i.i.d. input design and Gaussian noise
- Analysis is asymptotic (d to infinity, sigma to 0) in idealized settings
- Experiments limited to synthetic data with d up to 1000
Experimental setup
Metrics: normalized squared error (NSE)
Baselines: OKRidge
Builds on: OKRidge convex gaussian min-max theorem approximate message passing
Closest papers by meaning
- OKRidge: Scalable Optimal k-Sparse Ridge Regression (NeurIPS 2023 · similarity 0.91)
- An Iterative, Sketching-based Framework for Ridge Regression (ICML 2018 · similarity 0.87)
- On the Optimality of Misspecified Kernel Ridge Regression (ICML 2023 · similarity 0.86)
- A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression (NeurIPS 2024 · similarity 0.85)
- An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regression (ICLR 2024 · similarity 0.85)
- Kernel Regression in Structured Non-IID Settings: Theory and Implications for Denoising Score Learning (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.