Research map / Learning theory and algorithms / Prediction and decision losses
Solving Sparse \& High-Dimensional-Output Regression via Compression
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.
Proposes SHORE, a sparse high-dimensional-output linear regression, solved by random Gaussian output compression for training and projected gradient descent for s-sparse prediction, with theory on loss preservation and generalization.
Problem
Multi-output regression with very high-dimensional outputs faces interpretability (outputs should be sparse) and computational scalability problems; existing compression and sparse regression methods lack provable guarantees under weak sample conditions.
Approach
Compress the K-dimensional output space with a random Gaussian matrix Phi (RIP) to train a compressed linear regressor W, then predict an s-sparse output at test time by projected gradient descent on min ||Phi y - W x||^2 over s-sparse vectors, with provable training-loss and convergence guarantees.</params>
Key results
- Theorem: compressed training loss is bounded by (1+delta) times the uncompressed optimal training loss with m = O(delta^-2 log(K/tau)) rows.
- Projected gradient descent converges globally linearly to a ball around the optimal sparse prediction, with radius O(||Phi y_hat - W x||), under m = O(s delta^-2 log(K/tau)).
- Generalization error bounds for compressed SHORE are of the same order (O(d/n)) as uncompressed under sub-Gaussian samples; experiments show the proposed prediction method is faster and more accurate than OMP, FISTA and Elastic Net on most metrics.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed projected-gradient prediction algorithm instead of existing prediction baselines | SHORE prediction · Synthetic and real datasets | computational cost | Helped |
| Use the proposed projected-gradient prediction algorithm instead of existing prediction baselines | SHORE prediction · Synthetic and real datasets | accuracy | Helped |
Limitations
- Theory covers linear models only; nonlinear/nonconvex SHORE left to future work.
- Sparsity-constrained prediction assumes a known sparsity level s.
- Real-data experiments are only in appendix and the main text reports synthetic results for most claims.
Experimental setup
Datasets: synthetic Gaussian inputs with sparse outputs (d=10^4, K=2x10^4, s=3) real-world datasets (unnamed in main text)
Benchmarks: synthetic SHORE data real-world datasets (unspecified in main text)
Metrics: Precision@s Output-diff (squared l2 error) Prediction-Loss running time
Baselines: Orthogonal Matching Pursuit FISTA Elastic Net
Builds on: Johnson-Lindenstrauss lemma restricted isometry property iterative hard thresholding
Closest papers by meaning
- Generalized Tensor Decomposition for Understanding Multi-Output Regression under Combinatorial Shifts (NeurIPS 2024 · similarity 0.86)
- A Unified Comparative Study with Generalized Conformity Scores for Multi-Output Conformal Regression (ICML 2025 · similarity 0.85)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.85)
- High-Dimensional Analysis for Generalized Nonlinear Regression: From Asymptotics to Algorithm (AAAI 2024 · similarity 0.84)
- Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization (ICML 2024 · similarity 0.84)
- Navigating Extremes: Dynamic Sparsity in Large Output Spaces (NeurIPS 2024 · 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.