Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper gives a proximal gradient method for optimizing nonsmooth and possibly nonconvex regularizers. It could be applied to impose structure on neural networks such as binary quantization.
main_review: The papers reasonably propose proximal methods to handle these regularizers. As proximal mapping is more progressive than subgradient descent, so it should be straightforward.

One of my questions is about the technical difficulty in developing the theory of proof, as to determine whether it qualifies to be in Neurips. The paper is more of an experimental study overall.
limitations_and_societal_impact: Some additional questions: Figure 2 shows the constant factors in the assumptions C1-C4, is it possible to compare with the convergence, i.e. |\nabla F| side by side to show whether the convergence theory is tight?
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes adaptive proximal gradient methods for nonconvex optimization where the regularizer can be nonsmooth and nonconvex. The paper also provides extensive experiments to show that the proposed approach outperform existing SGD methods for stochastic optimization.
main_review: I feel that the theoretical contribution as well as the novelty of this paper is quite limited, and this paper did not broaden our understanding of adaptive methods for sparse optimization. The main weakness of this paper is that the convergence analysis is not technically sound. A potential limitation is that the stepsize of the proposed algorithm  virtually has nothing to do with the adaptive metric. In fact, by using some nonstandard assumption C3, C4, the convergence analysis is nearly identical to the standard analysis of stochastic PGD. 

Furthermore, I feel that some of the theoretical results are incorrect or at least have obvious limitations. 
- The stepsize is the main tuning parameter for ProxGen.  A close look at the convergence analysis reveals that the tuning parameter has nothing to do with the adaptive metric at all. It is somewhat strange that the stepsize solely depends on the free parameter $\delta$ which is only a small to term to ensure the posititive definiteness of the metric. So how should the algorithm choose $\delta$?
- Line 236 the paper claims the advantage of ProxGen. However, this bound on $1/\gamma$ is different from the bound derived in appendix line 733. Is there a typo? It is also bothering that  $1/\gamma$ depends on $1/\delta$, which can be arbitrarily small, this goes back to the previous question on how to select $ delta$.
- This paper considers $\ell_0$ penalty as a motivated example. However, it seems inappropriate for the theory. Specifically, Definition 1 (Frechet subdifferential) is not well-defined for the proposed $\ell_0$ regularizer. Taking $R(\theta)=\||\theta\||_0$ in the 1-d case, if $\theta=0$, then  $\partial R(0)=\[\theta^*, |\liminf  \frac{1-\langle \theta^*, x-0\rangle}{|x|} \ge 0\]=\mathbb{R}$. Therefore, the subdifferential of the objective always contains zero. 
- The author proposes C3 in which the difference between iterates is bounded by $D$. This appears to be unnecessary. In the proof (line 763) one can subtract $(L+\rho_0G)\||\theta_{t+1}-\theta_{t}\||^2$ on both sides. Then using quadratic bound, one can easily remove the term $\||\theta_{t+1}-\theta_{t}\||$. It suffices to impose a slightly tighter bound on $\alpha_0$.
limitations_and_societal_impact: The choice of stepsize is unclear.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work introduces a proximal algorithm for training neural networks. Specifically, the method allows the use of non-convex regularization functions and general PSD pre-conditioners  in the objective, while guaranteeing convergence to a stationary point. Empirical results are provided for training sparse neural networks on CIFAR and ImageNet.
main_review: ### Summary
This is a well-motivated and well-executed work that demonstrates the effectiveness of its proposed proximal algorithm when employing  non-convex regularizers to train sparse or quantized neural networks.

### Strengths
1. This work is well-motivated, and provides an interesting method especially in the context of training sparse or quantized neural networks.
2. The convergence analysis provided in Theorem 1 seems to provide powerful results. The proof looks correct to me, although I have not checked all details.
3. The assumptions made for the theoretical results are diligently checked in practice through dedicated experiments.
4. The submission conducts convincing experiments that demonstrate the usefulness of the approach, including on the large-scale task of training a binary ResNet-18 on ImageNet.

### (Minor) Weaknesses
1. The paper is not easy to read and follow, perhaps due to its high density throughout.
2. Experiments are "only" conducted for training quantized / sparse neural networks, which are interesting topics by themselves, but perhaps special cases only compared to what the reader might expect from the generality of the method suggested by the title and abstract. 

### Comments
1. In the proof of Theorem 1, L.777 should be an inequality rather than an equality (distance from set to 0 is $\leq$ norm of one element of the set).
2. Can the authors detail why the method converges with constant mini-batch size? It is not obvious how the the first term of the RHS (from Theorem 1) converges to zero when the batch-size is constant?

### Typos
1. L.44 Strategic -> strategy
2. l.64: arbitrat -> arbitrary
3. l.72 approachstygh
4. in caption of Table 4, “first” misspelled

----

### Updated Review

Thanks for the authors for engaging in a detailed discussion. It is slightly disappointing that Corollary 1 ends up requiring the assumption $b = \Theta(T)$ since it is less elegant than the initial assumption $b = \Theta(\sqrt{n})$, but that is not a major issue.

I am keeping my initial rating of 7. Whether the submission gets accepted or is resubmitted to other venues, I would encourage the authors to take the time and effort to improve clarity of the submission (potentially making space for expanding on the most important points by deferring lower level-details to the appendix).
limitations_and_societal_impact: No need for societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents a framework for adaptive proximal stochastic methods. The general algorithm provided, ProxGen, is a variation on traditional proximal gradient descent in which the gradient is multiplied by the inverse of some $C_t+ \delta I$, and the norm in the prox operator is given by $\|x\| = x^{\top} (C_t+ \delta I) x$. They give a convergence result which matches the optimal rate for SGD, and they show experiments with sparse, group-sparse, and binary neural networks in which they show improvements over existing algorithms.
main_review: The algorithm presented is not that novel in itself, as it is very close to Prox-Quant (differing only in the norm used for the prox-operator), and to Prox-SGD (differing on the fact that Prox-SGD is a two step algorithm, so it seems that ProxGen is a “simplification” of Prox-SGD). Despite that, the authors generally do a good job in arguing the empirical and theoretical advantages of the proposed method w.r.t. the existing two. 

Question: In lines 93-94, there is the statement that Adagrad is an instance of ProxGen with a certain choice of $C_t$ and $\mathcal{R}(\theta) = \|\theta\|_1$. Is that accurate? To my understanding, “vanilla” Adagrad does not include any proximal step. Should it say “proximal” Adagrad instead?

As to the proof of Theorem 1, is the proof structure based on any previous work, or is it completely new? I think it would be useful to give some pointers. 
Although the steps to get Corollary 1 from Theorem 1 are not too involved, they are not a one-liner, and should be included either in the main text or the appendix. Also, add citation for the $O(1/\epsilon^4)$ optimal rate: this is relevant.

Regarding the experiments, the plots in Figure 2 should be uniformed: Why is Prox-SGD only in some plots (it does not look good)? Some plots have legends, some do not, and the legend for the last one is cryptic. 

Typos: The paper needs to be proofread for typos. Line 64: “arbitrat”. Line 72: “approacwstygh”.
limitations_and_societal_impact: The limitations are discussed. There is no potential negative societal impact.
review_title: null

Meta-review: Reviews were initially highly polarized: while Uvqk and REN2 give a positive score and qualify this as "well-executed" and "authors generally do a good job in arguing the empirical and theoretical advantages of the proposed method", reviewer 3MNN argues that "the convergence analysis is not technically sound". The authors provided a strong rebuttal that increased the score of reviewer 3MNN. 

After the discussion period, the reviewers agree that this is a contribution that can be of high interest to the NeurIPS community, and as such my recommendation is to accept for publication. However, reviewer 3MNN raises some valid points regarding comparison of constants with existing results and regarding clarity of the statements that I encourage the authors to incorporate into the final version.
Decision: Accept (Poster)