Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: [Summary]
This paper proposes a new method called Half-space Stochastic Projected Gradient (HSPG) to find a group sparse solution of regularized finite-sum problems. Theoretical analysis tries to show the sparsity identification guarantees. In experiments, the effectiveness of HSPG was verified on the classification tasks.

[Strength]
The idea behind the proposed method seems to be reasonable and interesting.

[Weakness]
A major concern is the correctness of the statements. In the equation (97) in the proof, the equation $E_B[e(x)] = 0$ is used essentially, and it is also stated in page 6. However, I think it does not hold because the proximal operator associated with sparse regularization is nonlinear. It may be probably difficult to fix this issue.

[Minor comment]
There is a missing reference. It is known that RDA has the superior ability to find a manifold structure of solutions as shown in the following paper. 

S. Lee and S. J. Wright. Manifold identification in dual averaging for regularized stochastic online learning. JMLR, 2012.

[Improvement]
If there is a misunderstanding in my review, I'd appreciate it if you could mention them.

review_title: The idea is interesting, but I have a concern.

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposed a new algorithm for the group sparsity regularization problem. They claim most existing algorithms, though return solutions with low objective function value, only give dense solutions and cannot effectively ensure the desired structured sparsity. The new technique requires an initialization that is closed to some truly sparse local minimum, which is achieved by running proximal gradient descent first. Then, they proposed a new half-space iterative step to force elements in specific groups exactly to zero. The authors also provide convergence analysis and numerical evidence for the newly proposed algorithm.

Comments:
1. It is not clear to me, in Theorem 1, how are the parameters depend on the confidence \tau? I am confused as it seems no parameter is explicitly dependent on \tau, so the convergence in Theorem is almost surely one? I skim the proof and find that dependence vanished on the page (appendix) 10, proof of Lemma 6. I don’t understand why (1+\theta) can be omitted. Please clarify.
2. Where is N_P defined? N_P is used almost everywhere, for example, in statement of Theorem 1 and Algorithm 1. I didn’t find the definition of it. I guess N_P := min{k: ||x_k - x^*|| <= R/2} and R is further constrained by 2\delta_1 - R > 0.
3. In Theorem 1 and Proposition 1, only asymptotic and polynomial bounds are given. No rate of convergence for either the initialization phase or the half-space projection phase.

review_title: interesting algorithm to promote sparsity 

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper studies how to solve a class of group sparsity regularized minimization problems. In particular, a half-space stochastic projected gradient (HSPG) method is proposed, which is based on the Prox-SG and a new half-space step that promotes group sparsity. This step is to decompose the feasible space and then perform group projection. Convergence analysis is provided, together with the theoretical discussion that HSPG has looser requirements to identify the sparsity patter than Prox-SG. Numerical experiments on the DCNNs based image classification shows the proposed method achieves the state-of-the-art performance in terms of accuracy. The work looks interesting with wide applications, especially in deep neural networks. However, the novelty is incremental and limited. 

1. There are some places where the notation is confusing. Vectors and scalars are constantly not distinguished.
2. Practical guidance on the selection of the parameters $\lambda$ and $\varepsilon$ could be provided. 
3. In the numerical experiments, comparison of computational complexity and running time for the listed methods is not provided. Discussions on the group sparsity level and noise robustness could be included. 
review_title: Review of "A Half-Space Stochastic Projected Gradient Method for Group Sparsity Regularization"

final_score: rating: 5: Marginally below acceptance threshold
review_content: In summary, this paper proposes a post-processing algorithm on the estimator obtained by the usual proximal Stochastic gradient method. This leads to an estimator with enhanced group sparsity without the sacrifice of accuracy.

My major concern is how to use such a group sparsity result? We end up with a more group sparse estimator, which is good. But I feel like that is not the end of the story. In a deep neural network, the group sparsity seems not the major point people care about. My hope is that the enhanced group sparsity can be used to guide maybe the design of the neural network structure, or at least provide some better understandings of the model. For example, if we always see that some groups of filters are inactive, then we may modify the neural network structure accordingly, etc. In all, my understanding is that the group sparsity could be an intermediate result that can be further analyzed and used to improve the design of the model, instead of being the final goal itself.

If we start with different initialization (probably just slightly different), then will we end up with the same final estimator or at least the same group sparsity results?

After obtaining the final estimator with group sparsity, can we refit the model on the active group index only? Will this improve the performance? 
review_title: A good post processing trick to enhance group sparsity, but the usage of the group sparsity structure is unclear

Meta-review: The paper received four borderline reviews.  Overall, the manuscript has improved after the rebuttal (in particular, an issue in the convergence proof has been fixed), and a reviewer has increased his score to borderline accept. Yet, the paper did not convince the reviewers that the contribution was significant enough and none of the reviewer got enthusiastic about the paper. The main issue with the paper seems to be the unclear positioning between the optimization literature for stochastic composite optimization, the literature on support identification (e.g., Nutini, 2019), and the (more empirical) deep learning literature.

The paper postulates that the group-sparsity regularization is crucial for deep neural networks, which seems to be the main motivation of the paper. Yet, the experiments do not demonstrate any concrete consequence of better group sparsity, wether it is in terms of accuracy or interpretability.  If positioned in this literature, a comparison should be made with classical pruning approaches, where pruning occurs as an iterative procedure that is distinct from optimization. If positioned instead in the stochastic optimization literature, better analysis of the convergence rates should be provided; if positioned in the support identification literature, the paper should explain how the results compare to those of the literature (e.g., Nutini, 2019 and others). In other words, any point of view requires clarifications and additional discussions. 

Besides, 
   - the theoretical assumptions need to be discussed:  does the Lipschitz assumption holds for multilayer neural networks ? Certainly not for ReLu networks, but what can we say something useful, even with smooth activation functions?
   - the experimental setup needs more details. Reproducing the experiments with the current paper seems difficult; in particular, the choice of hyper-parameters is not crystal clear.

For these reasons, the area chair recommends to reject the paper, but encourages the authors to resubmit to a future venue while taking into account the previous comments.
Decision: Reject