Solving Sparse \& High-Dimensional-Output Regression via Compression

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 07:13:37

Abstract: Multi-Output Regression (MOR) has been widely used in scientific data analysis for decision-making. Unlike traditional regression models, MOR aims to simultaneously predict multiple real-valued outputs given an input. However, the increasing dimensionality of the outputs poses significant challenges regarding interpretability and computational scalability for modern MOR applications. As a first step to address these challenges, this paper proposes a Sparse \& High-dimensional-Output REgression (SHORE) model by incorporating additional sparsity requirements to resolve the output interpretability, and then designs a computationally efficient two-stage optimization framework capable of solving SHORE with provable accuracy via compression on outputs. Theoretically, we show that the proposed framework is computationally scalable while maintaining the same order of training loss and prediction loss before-and-after compression under arbitrary or relatively weak sample set conditions. Empirically, numerical results further validate the theoretical findings, showcasing the efficiency and accuracy of the proposed framework.

Main paper: 
  
 Appendix:  


Decision: The authors propose in this article a two-stage approach to tackle multi-output regression under a pre-determined sparsity level on the output vector and provide performance guarantees for this computational efficient method. Several points raised by the reviewers regarding the comparison to other methods, the experimental study and the clarity were effectively addressed by the authors' rebuttal, leading to a consensus to accept the paper, with recommendation to incorporate the discussion and the additional results into the final version.

Reviews: review: paper_summary: paper_summary: This manuscript proposes a new approach the authors refer to as Sparse & High-dimensional-Output REgression (SHORE) to tackle linear regression problems promoting sparse predictions. A major component of the author's approach is to reduce the computational cost with a random normal matrix compressing the signal first and then producing sparse predictions in the second phase. The manuscript provides a theoretical analysis of the accuracy of the sparse prediction. The authors include further some numerical numerical investigations supporting their theoretical findings.
strength_weakness: strength_weakness: Comparison to state-of-the-art methods such as FISTA (Fast Iterative Shrinkage-Thresholding Algorithm) or ADMM (Alternating Direction Method of Multipliers) would strengthen the contribution of this work. A clear comparison highlighting the advantages of the proposed method in terms of convergence speed, memory efficiency, or specific problem suitability would be valuable. Additionally, the paper could benefit from exploring connections to randomized linear algebra, particularly regarding the selection of the matrix Φ. The paper Randomized Numerical Linear Algebra: Foundations & Algorithms by Martinsson and Tropp provides a comprehensive overview of how random projections can be leveraged to achieve efficient solutions in high-dimensional problems. Further, Equation (1) is a simple linear regression or least squares problem  ||Y-ZX||_F^2 =  ||\vec(Y) - (X'  \kron  I) vec(Z)||_2^2 which does not require a new renaming as SHORE.
questions: questions: See weaknesses.
limitations: limitations: yes.
paper_summary: paper_summary: In this paper, the author has proposed a new method for solving the high-dimensional output regression (MOR) problem through compression. The authors introduce a two-stage framework that incorporates output compression to achieve computational efficiency while maintaining accuracy. Theoretical results demonstrate the framework's scalability and error bounds, while empirical results validate its performance.
strength_weakness: strength_weakness: - [Comparison Methods] In this paper, the authors has compare the model performance with some existing prediction baselines like Orthogonal Matching Pursuit and Elastic Net. Both of those two methods seems not to be the latest sparse regression methods that would be interesting to compare with. Therefore, I am wondering if some methods related to sparse high dimension regression like [1,2,3,4] can be discussed within the paper, and tested on the model performances. Also, there are plenty of the methods that are mentioned within the literature review parts, those methods are also not taken into considerations instead of elasticnet, which make the conclusion less convincing from the numerical results perspective.

- [Missing of the Sparsity levels] with the synthetic dataset. The paper doesn't mentioned the sparsity level while the sparsity level is pre-defined within the numerical experimental settings since the set up sparsity level tends to be the most correct baseline for evaluating the sparsity level of the model, so it would be really important to be shown within the paper.

[1] Bertsimas, D., and B. Van Parys. "Sparse high-dimensional regression: Exact scalable algorithms and phase transitions (2017)." arXiv preprint arXiv:1709.10029 (2019).
[2] Bertsimas, Dimitris, and Bart Van Parys. "SPARSE HIGH-DIMENSIONAL REGRESSION." The Annals of Statistics 48.1 (2020): 300-323.
[3] Liu, Liu, et al. "High dimensional robust sparse regression." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.
[4] Sun, Qiang, et al. "Sprem: sparse projection regression model for high-dimensional linear regression." Journal of the American Statistical Association 110.509 (2015): 289-302.
questions: questions: - [The influence on the compressed hyperparameter m] With the increase of the hyperparameter $m$ as the compressed dimension. The model performance of the methods has been significantly improved. Therefore, I am wondering if the model training time is depending on m, so it would be interesting to see how the training time increase in real datasets as the hyperparameter m change since the current training time is just a range, while the computational complexity O(KM) in the second stage, so the training time wshould definitely increase with the improvement of m.

- [The selection of m] I can understand there is a trade-off between model performance and compressed output dimension. However, if the dataset is totally unknown, the training time would increase under the trial. Therefore, I am wondering if that is also an issue when this method is finally applied for real application.
limitations: limitations: N/A
paper_summary: paper_summary: The paper proposes the Sparse & High-dimensional-Output REgression (SHORE) model to address challenges in Multi-Output Regression (MOR). SHORE introduces a two-stage framework to handle high-dimensional outputs efficiently. Theoretical analysis shows that the framework maintains training and prediction loss while being computationally scalable. Empirical results validate these findings, demonstrating the framework’s efficiency and accuracy in handling SHORE for modern MOR applications.
strength_weakness: strength_weakness: - The prediction stage is significantly different from the classical manner (i.e., $Z X$). It involves solving sparsity-constrained optimization (SCO) problems. It would be good to highlight this difference. Additionally, solving SCO is more computationally intensive than the classical method, so more discussion (in both theory and experiments) is necessary.

- Algorithm 1: Algorithm 1: Steps 3-4 resemble iterative hard thresholding [1, 2]. It would be better to discuss this in the appropriate place. 

- Lines 217-218: The setting for $y$ seems to imply that only $s$ columns have non-zero values while the remaining columns always take zero values. Under this assumption, why not filter out some columns according to the magnitude of the columns of $y$?

- It would be better to explicitly describe how OMP is compared. Is it used for solving (3) or (1)?

- Line 310-311: Elastic net may have better performance in a low signal regime [3].

- Considering these assumptions are mild in practice, why not test the algorithm on real-world datasets and present the results in the main text?

- Lines 437, 467, 542: Incomplete sentences. Perhaps they can be changed to "Recall the following theorem in the main text."
questions: questions: - Theorem 4: $\hat{y}$ in the theorem is the optimal solution of (3). How about the algorithmic solution?

- The selection $\eta$ is much easier than in [2]. However, it would be good to provide some default values for practical usage. Furthermore, is it possible to select $\eta$ in a more data-driven way, for example, by leveraging the value of the loss function like in [4]?
limitations: limitations: The authors have discussed the limitations in this paper.

### Reference

- [1] Blumensath, Thomas, and Mike E. Davies. "Iterative hard thresholding for compressed sensing." Applied and computational harmonic analysis 27.3 (2009): 265-274.

- [2] Jain, Prateek, Ambuj Tewari, and Purushottam Kar. "On iterative hard thresholding methods for high-dimensional m-estimation." Advances in neural information processing systems 27 (2014).

- [3] Hastie, Trevor, Robert Tibshirani, and Ryan Tibshirani. "Best subset, forward stepwise or lasso? Analysis and recommendations based on extensive comparisons." Statistical Science 35.4 (2020): 579-592.

- [4] Wang, Zezhi, et al. "Sparsity-Constraint Optimization via Splicing Iteration." arXiv preprint arXiv:2406.12017 (2024).

Comments: comment: Thank you for your response. We truly appreciate your feedback and would be grateful if you could consider raising your rating score, as we have taken steps to address the concerns you mentioned.
Thank you for addressing my concerns. I have slightly increased my rating.
Thank you for the insightful comments and willingness to raise your score! We will add the related references, discussions, clarifications, and additional numerical results to the revised manuscript.
Thank you again for the helpful comments and critiques! 
We will add the discussions, clarifications, and additional numerical results to the revised manuscript.
Dear authors,

Thank you so much for the detailed response and additional results. Most of my concerns have been cleared.

I hope this discussion and clarification can be incorporated into the revised manuscript, which should benefit the paper's quality and contribution.

I've increased my rating to 7.
Thank you for your response, and that solves my concerns to the paper. I have slightly increase my rating for this paper.