Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Regularization is generally used to impose desired structure on NN during training. The authors developed RMDA (Regularized Modernized Dual Averaging) which uses the weighted average of the previous SG to compute the tentative update via proximal operation associated with the regularizer. Then the parameters of the model are updated in the direction of this tentative update with a pre-defined factor. The authors theoretically analyzed the performance of their algorithm and showed that under some assumptions, RMDA can identify the structure of model in finite iterations.

main_review: Using momentum and different regularizers to impose the desired structure during optimization and esp. NN training is common in machine learning. The proposed RMDA can be viewed as a non-trivial extension of the dial averaging algorithm to use momentum. 

1. I found the claims not 100% accurate, and sometimes misleading:
 - **Variance reduction beyond ...**: It was not clear how this achieved? can the authors explain what they meant by variance reduction and where in the paper they showed that? Also, despite claiming that RDMA's cost is the same as SGD, keeping track of momentum and dual averaging makes it slightly more complex than SGD (although still better than other variance reduction techniques)
- **Guaranteed strucutre identification**: I find this slightly exaggeration of the results as there is no theoretical result on the convergence of the RDMA at all. Theorem 2 assumes that the algorithm converges, and under some assumptions, the converged parameter belongs to the active manifold.
- **Superior empirical performance**: "RDMA identifies the optimum structure" is hard to prove, as there is no way to show that the structure found by any algorithm is the best and optimum, even though it is better than baseline.

2. The theoretical analysis is not complete, and is based on the restrictive assumptions and expecting that with the given values of $\\beta_t$, $\\eta_t$ the algorithm converges. 
3. In theorem 2, does $T_0$ refer to the extra iterations of RDMA after having $\\tilde{W}^t$ converged? or it includes all iterations of RDMA, including the convergence of $\\tilde{W}^t$?
4. Section 3, It is stated that in convex optimization, "algorithms based on proximal stochastic gradient are unable to identify the manifold within finite iterations". However, RMDA can identify the active manifold in finite iterations. What is the main reason to achieve this contradicting result? Is it because of the set of assumptions made in the analysis? or the way that momentum is incorporated in developing the algorithm?

minor suggestions:
- It would be much better to define all notations used in the paper, for example the notations for subdifferential, interior, relative-interior (although mostly standard).

summary_of_the_review: By adding momentum and proximal operation associated with the regularization to the modernized dual averaging algorithm, the authors developed RDMA. Using tools from non-linear optimization and manifold identification, they theoretically showed that if RDMA converges, then it will find the active manifold after a finite number of iterations. Experimentally, they showed that RDMA outperforms proxSGD and ProxSSI in terms of both accuracy (sometimes) and group sparsity (always).
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper, the authors propose Regularized Modernized Dual Averaging (RDMA) algorithm to train structured neural networks. This is a proximal method that achieves variance reduction without any extra cost per iteration. The algorithm does not require any extra hyperparameters than what stochastic gradient descent requires. Authors theoretically prove that structure identification is guaranteed after a finite number of iterations.

Experiments have been performed to obtain group sparse neural networks. Networks and datasets used in the experiments are simple logistic regression network on MNIST, 7-layer fully-connected network on FashionMNIST, LeNet5 on MNIST, and VGG16 on CIFAR10. The method has been compared with SGD, ProxSGD, and ProxSSI. 
main_review: Positive aspects:

1. The proposed algorithm is well motivated.
2. The proposed algorithm is a unique and different take on structured learning.
3. The proposed algorithm and the related math is well explained in the paper. 


Negative aspects:
1. Experiments are limited. It is understandable that the main goal of the paper is to share a new proximal based method for structured learning but it will be good to have a few more experiments. 
2. It will also be good if comparisons with other structure learning-based methods are done. 
3. Related work is missing a recent work that leverages proximal operators to find a sparse network from a pretrained network which can also be applied during training for group sparsity. Verma, Sagar, and Pesquet, Jean-Christophe. "Sparsifying Networks via Subdifferential Inclusion."  International Conference on Machine Learning. PMLR, 2021.
summary_of_the_review: I am leaning towards acceptance given that authors address the problems listed out. Overall the idea is good and the paper is well written to be considered at par with ICLR.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes an algorithm for training neural networks with a regularization term for promoting desired structures in the model. The paper (claims to) prove that the proposed method can correctly identify within finite steps the underlying structure. The simulations then show that the method outperforms existing packages in identifying structured sparsity without compromising prediction accuracy.
main_review: ### Strengths

1. The paper introduces an algorithm for training neural networks with a regularization term for promoting desired structures in the model. The new method does not incur computation additional to SGD with momentum and could be of practical use. The ideas of the paper are based on well-founded rationales.
2. In general, the paper is quite well-written, with the main ideas outlined clearly. The approach is well-motivated and seems to be built upon established literature. The review of related works is informative.
3. The main theoretical results of the paper (Theorem 1 and Theorem 2) are non-trivial and meaningful, and the proofs are rigorous.

### Weakness

I have a few concerns with the manuscript in its current state.

1. In my opinion, the paper overstates the significance and implications of its results in its presentation. More precisely:
    - In the abstract, introduction, and throughout the discussion, the paper claims that "we rigorously prove that the proposed method can correctly identify within finite steps the underlying structure".
    - In the experiments, they conclude that "RMDA is the only algorithm that steadily identifies the correct structured sparsity".

    I think those are not correct characterizations of the results obtained in this work:
    - Roughly speaking, Theorem 2 for structured sparsity of neural networks just proves that:

         *If the estimator converges to some stationary point W, then its sparsity converges to the sparsity of W within finite step*

    - Similarly, the experiments just show that RMDA has a stable structured sparsity

    While these results are non-trivial, they concern the **stability** of the algorithm, and have little to do with **correctness**: a bad algorithm that got stuck at a non-optimal stationary point also satisfies those properties. To obtain what the paper claims, some more work is needed. In the theory part, results that are equivalent to model-selection consistency for linear models are required. For the simulations part, some experiments with simulated data, when a measure of deviation from the "ground truth" or "correct/optimal sparsity" could be recognized, are necessary.
2. While the results of Section 3 of the manuscript are rigorous, the applications to neural networks (Section 4) lack several important details. When moving from a general framework to a specific case (Section 4.1 and 4.2), two central concepts:
    - the corresponding active manifold,
    - the precise description of the limit point W^*

    are not defined explicitly. This causes significant unnecessary confusion and makes it harder to judge the accuracy and the importance of the results. Specifically,
    - In Definition 1: M is required to be a C^2 manifold, and in general, should be independent of the limit point W^*
    - In Section 4.1 (Structured sparsity), the active manifold seems to be defined as a hyperplane around (and depends on) W^*. To make this fit into the framework, W^* needs to be unique for all random realizations (but this is unlikely). If this is not the case, then M is a union of several hyperplanes of different dimensions (correspond to different limit points for each realization) and is no longer a manifold.

    I believe a clear description of the active manifolds for each case and some verification of their geometric properties would help improve the manuscript.
3. My last concern about the theoretical analysis is its (somewhat hidden and informally defined) assumption that the tentative iterate {W ̃ t} converges almost surely to a certain point W∗. This statement can be interpreted in different ways and needs to be spelled out mathematically. My main question is: Is W* the same for all realizations of randomness? In principle, this is not true, but the analysis was written as if that was the case (see point (2) below).

    The manuscript also stated that verifying this assumption is possible, but these are not the purpose of this work, so they avoid distracting the readers from such technical results. However, it is worth pointing out that W ̃ and W are intertwined in their constructions, and making the convergence of the W~ an assumption is a bit too strong. Even if rigorous results don't need to be provided, some examples and quick discussions about this should be included, perhaps in the appendix. This part will also help resolve the lack of understanding about the structure of W* described above.

### Other comments and questions

- Beginning of Section 3: "In stark contrast to our results, it is actually well-known in convex optimization that those algorithms based on proximal stochastic gradient are *unable to identify the manifold within finite iterations*".
    —> This statement needs more references.
summary_of_the_review: Overall, my vote for the paper is a (weak) reject. I think the paper has some strong points and the general results are meaningful. On the other hand, I think the technical writings of Section (Applications to deep learning) are less rigorous and lack important information. Finally, I feel the paper overstates the significance and implications of its results in its presentations.

Update after author's responses and revision: Most of my concerns have been addressed in the revision, with (1) a more rigorous reframing if the significance and importance of the work, and (2) experiments to validate the efficiency of the approach. I think this is a good paper in its current state.
review_title: null

Meta-review: The paper develops optimization algorithms for fitting structured neural networks. It focuses on the manifold identification property, which guarantees after finitely many iterations, all iterates have the same sparsity structure as at convergence. The proposed method extends dual averaging to include momentum. The paper’s analysis shows that if the proposed method converges, it converges to a stationary point, and identifies the sparsity pattern of the limit in finitely many iterations. Experiments show improvements in sparsification compared to existing two-step sparsifiers, without a degradation in accuracy. 

The initial review raised concerns about clarity, as well as some of the claimed significance of the results: the paper does not prove that an optimal, or even good sparsity structure is obtained — rather, it proves that the sparsity structure at convergence is obtained after finitely many iterations. The reviewers also raised a number of detailed concerns about the paper’s mathematical exposition. 

After considering the authors response, and a revision which significantly clarified both the paper’s notation and its main claims, the reviewers converged to a recommendation to accept. The paper provides a principled approach to sparsification, with supporting theory (albeit about finite identification, rather than optimality). The proposed algorithm appears quite practical and is supported by experiments demonstrating improvements over existing sparsification methods.
Decision: Accept (Poster)