Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Summary:

This paper introduces and analyzes a training algorithm for neural networks with non smooth regularization and weight constraints (such as sparsity or binarization). The analysis shows that, under assumptions, the proposed algorithm converges almost surely to a stationary point. Experimental results show that the proposed algorithm can train both sparse and binary neural networks.

Major comments:

This paper presents an interesting combination of theoretical analysis and experiments demonstrating the benefits of the proposed training algorithm. Because the setting considered is fairly general, it is likely to be widely useful in a variety of settings that have up to now been approached with case-specific algorithms (eg training binary NNs). 

It should be noted that objective functions for many NNs are not smooth (eg ReLU-based networks, which are used in the experiments) and the convergence argument does not apply directly to these. 

The paper could be improved by more extensively optimizing hyper parameters of all algorithms in the experimental evaluation. From the current experiments, it is not possible to evaluate whether performance differences are coming from differences in learning rate schedules, etc, or from the proposed algorithm specifically. For instance, the competitor algorithms are run with fixed momentum and learning rate parameters, while the proposed algorithm is run with a handcrafted decay in these parameters. Ideally, the hyperparameters should be optimized out such that each algorithm uses its best settings. At minimum, the choice of hyperparameter schedule for the algorithm should be justified. 

The paper could also be strengthened by comparing the runtime of the proposed algorithm to prior methods. Prox SGD trains faster in terms of iterations (hyper parameter differences aside), but how about wall clock time? This is particularly important in the binary case where additional optimization parameters are added and updated in each iteration.

The main theoretical result is presented with a sketch of a proof, and I did not attempt to reconstruct the argument from the named sources. It could be useful to provide a full proof (perhaps in an appendix) to allow the work to be self-contained.

The paper is clearly written and easy to follow.


Typos:
In general more care should be taken with the equations:
Eq. 7 x^t should be x(t)
Eq. 7 differs slightly from Alg. 1 step 3 because of the \mu term in step 3. I would remove \mu 
Pg 3, the indicator function is introduced as \sigma_X then put in the equation as \delta_X
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: The paper proposes a new gradient-based stochastic optimization algorithm (with gradient averaging) by adapting theory for proximal algorithms (originally developed for convex problems) to the non-convex setting. The main idea is to first use an averaged gradient plus a quadratic term to locally approximate the non-convex function with a convex smooth function before applying the proximal operator on it. As a result, the algorithm will be able to solve non-smooth (e.g., l1-regularized) and constrained non-convex problems, which will be very useful for optimization problems arising from deep learning.

I think this is a potentially good paper that proposes an algorithm for wide applicability. But I still see some issues that prompts me to ask the following questions:

1. What is the time complexity of solving the sub convex problem at every iteration? The authors did not discuss this in the experiments, but this is very important in evaluating the applicability of the proposed algorithm especially on large-scale problems.
2. The authors should provide more explanation on the term \tau (t): It seems it is only used as an auxiliary parameter in the quadratic approximation of f, and that it doesn't affect the convergence asymptotically. But I would imagine it would affect the practical convergence at the beginning of the algorithm?
3. The authors have repeatedly mentioned that using the averaged gradient v(t) is very important for the convergence analysis of the algorithm. But I did not see how this is the case from the analysis discussed in the paper (I didn't check the proof in reference Ruszczynski (1980)). As this is important in justifying the algorithm, I think the authors should include a discussion to provide some intuition on this in the paper.
4. Line (15): should vx(t) be x(t) instead? If not, where does the term come from?

review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: 
[Summary]
This paper proposes Prox-SGD, a theoretical framework for stochastic optimization algorithms that (1) incorporates momentum and coordinate-wise scaling as in Adam, and (2) can handle constraint and (non-smooth) regularizers through the proximal operator. With proper choices of hyperparameters, the algorithm is shown to converge asymptotically to stationarity, for smooth non-convex loss + convex constraint/regularizer. The algorithm is empirically tested on training binary and sparse neural nets on MNIST and CIFAR-10.

[Pros]
The theoretical framework that incorporates most of the commonly used tweaks in stochastic optimization for deep learning, and a convergence result that establishes broadly the asymptotic convergence to stationarity.

[Cons]
The result of Theorem 1 sounds rather a straightforward application of classical results; important sub-cases such as Adam violates the assumption (Adam has \rho_t = \rho so \sum \rho_t^2 = \infty) and thus are not contained in this case. From this it seems to me Theorem 1 says things mostly about the “easier” sub-cases, and thus is perhaps not very surprising and a bit limited in bringing in new messages. 

The experiments are mostly done on simple problems --- 3 of the 4 figures are on MNIST. The specific tasks (training sparse / binary neural nets with MLP / vanilla CNN architectures) considered in the experiments are all very extensively studied in prior work, and the results in this paper says at most that the proposed Prox-SGD works for these tasks.

Overall, I like the idea in this paper that we can put together a unified framework for stochastic optimization algorithms and incorporate things like momentums and regularizations that were previously treated separately. However, beyond proposing such a framework, it seems that contributions on both the theoretical and empirical side are a bit limited at this point.

***

Thank the authors for the response and the efforts in revising the paper. I am glad to see the additional experiments for training sparse networks on CIFAR-100 (a much harder task than MNIST and also CIFAR-10) in which the proposed method works well. This largely resolved my concerns on the experimental side. 

However, I'd still like to hold my evaluation on the theoretical side, in that approaches for handling constraints / non-smoothness / momentums are fairly well understood in the optimization literature. The present result (Theorem 1) conveys the message that these approaches can be combined to work (give an algorithm that converges to stationary points if it converges), but is not really a result that gives us new understandings / novel proof techniques beyond that.

I have slightly improved my rating to reflect my updated evaluation.

review_title: Official Blind Review #3

Meta-review: This paper proposes a new gradient-based stochastic optimization algorithm by adapting theory for proximal algorithms to the non-convex setting. 

The majority of reviewers voted for accept. The authors are encouraged to revise with respect to reviewer comments.
Decision: Accept (Poster)