- Rating
- 1
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This work considers the sparse linear regression problem from the perspective of random local search based in subsampling. A majority of the manuscript is to establish some theoretical tight bound to prove that it achieves an approximation with high probability and reasonable computational cost.
Critical strengths
The problem is well defined. The proposed method considers the worst-case scenario, comparing how far the proposed algorithm’s solution can be in the worst case? The manuscript also examines the computational complexity. The theoretical analysis accommodates the situation of dependence of the current support on earlier sampled data. The conditional lower bound can help explain the worst-case order of the approximation factor.
Critical weaknesses
The novelty on methodology is limited. The theoretical contribution is also marginal since the manuscript does not consider the commonly-studied situation with p >> n, and both p and n go to infinity.
The practical advantage is not fully established. The practical information supplied by the residual bound is unclear.
The comparisons with recent sparse ridge methods are missing.
The performance of the proposed method is not appealing.
The numerical setting is mainly for n >p, which is not for high-dimensional data.
Questions for authors
I have major concerns listed above in the critical weakness. In addition, there are major questions as follows:
-
The experimental algorithm uses a ridge penalty of 0.05, whereas the proof uses 1. The paper does not explain how this change affects the exchange score or residual guarantee.
-
The numerical experiments are toy examples. All responses are generated, but from the real data.
-
In Table 2, it is not clear what metric is the loss? Do authors consider the prediction loss? The proposed method does not have a better performance on loss.
-
How is the penalty of 0.05 incorporated into the exchange score and deletion update, and what version of Theorem 3.6 applies to the evaluated algorithm?
-
It is better to compare with the established sparse ridge methods under the same feature budget and evaluation objective.