Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Thanks for the responses and my concerns seem to be addressed. But since I do not know much about this area, I would like to stick to my initial rating 6.
==================================================================================================
This work designs a new optimization SGD algorithm named ALI-G for deep neural network with interpolation property. 
This algorithm only has a single hyper-parameter and doesn’t have a decay schedule. The authors provide the convergence guarantees of ALI-G in the stochastic convex setting as well as the experiment results on four tasks.This paper shows state-of-the-art results but I still have have two concerns.

My main concern is that the performances of other SGD algorithms may be potentially better than the results showed in section 5 because it is not easy to tune the parameter. It would be better if the authors can tune the hyper-parameter more carefully. Take figure 3 as an example. The settings where step size bigger than 1e+1 can hardly shows something, because the step-size is too big for SGD to converge. The settings where step size smaller 1e-2 can also hardly shows something, because the step-size is too small and the experiments only runs 10k steps. It would be better if authors can do more experiments in the settings where step size is from 1e-3 to 1e+0. Moreover, the optimal step size of different optimization algorithms may differ a lot. It would be much more fair if the authors can compare the best performance of different algorithms.

Another concern is that the authors only give the convergence rate of ALI-G in section 3 but haven’t make any comparisons. For example, it would be better if the authors can show that ALI-G has better convergence result than vanilla SGD without decay schedule.

review_title: Official Blind Review #4

final_score: rating: 6: Weak Accept
review_content: This paper addresses designing and analyzing an optimization algorithm. Like SGD, it maintains a low computational cost per optimization iteration, but unlike SGD, it does not require manually tuning a decay schedule. This work uses the interpolation property (that the empirical loss can be driven to near zero on all samples simultaneously in a neural network) to compute an adaptive learning rate in closed form at each optimization iteration, and results show that this method produces state-of-the-art results among adaptive methods. I can say the paper was very well written and easy to follow along/understand. Prior work seems comprehensive, and the intuitive comparisons to the prior methods were also useful for the reader. 

My current decision is a weak accept, for a well-written paper, thorough results including meaningful baselines and numerous hyperparameter searches, and a seemingly high-impact tool. Some concerns are listed as follows:
1-	Convergence was only discussed in the stochastic convex setting, which seems limiting because we rarely deal with convex problems in problems requiring neural networks.
2-	Regularization of the weights during the optimization is dealt with by projecting onto the feasible set of weights, but it seems like there are other types of losses that don’t necessarily to go 0. For example, terms in the objective such as entropy seem worrisome.
3-	One detail that I did not fully follow along with is section 3.1. How does Theorem 1 (Regarding convexity) related to the “each training sample can use its own learning rate without harming progress on the other ones” and/or “allow the updates to rely on the stochastic estimate rather than the exact”? 
4-	Unfortunately, I am not an expert in this particular area, so I’m not confident about the novelty. For example, the difference between L4 and this is stated to be the utilization of the interpolation policy (which just sets f*=0) and the maximal learning rate, and the stated benefit of convergence guarantees in stochastic convex settings seems poor since most problems will not be convex anyway. More generally, it seems like all details of the algorithm came from elsewhere, although the presented synthesis of ideas does have clear benefits.

After reading the author response: 
-I'm fine with points 4 and 3. 
-My feelings about 1 are still the same.
-My comment on 2 wasn't about cross-entopy loss, but rather other types of objectives that people are often interested in optimizing (such as max-ent RL, where we aim for maximizing rewards as well as maximizing entropy of the policy), in which case, it's not clear to me how we could apply this optimizer. 
-My decision stays as a weak accept
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: This paper proposes a new adaptive learning rate method which is tailored to the optimization of deep neural networks. The motivating observation is that over-parameterized DNNs are able to interpolate the training data (i.e. they are able to reach near-zero training error). This enables application of the Polyak update rule to stochastic updates and a simplification by assuming a zero minimal training loss. A number of proofs for convergence in various convex settings are provided, and empirical evaluation on several benchmarks demonstrates (a) ability to optimize complex architectures, (b) performance improvements over, and (c) performance close to manually tuned SGD learning rates.

I vote for accepting this paper. The approach is well-motivated, the method is described clearly and detail, and the experiments support the paper's claims well. What I would still like to see are a few additional details regarding the experimental protocol. In particular, did you train a single or multiple models for each result that is reported? Do different runs start from the exact same weight initialization? What condition was used to stop the training? The results in section 5.2. are all very close to each other, and it would be helpful to have a sense of the variability of the different methods. The graphs in Figure 4 do look like the models did not converge yet.

Generally, it would be nice to examine the behavior of the method in cases where the neural network is underparameterized or is otherwise unable to effectively interpolate the training data. Does the method lead to divergence in this case, or is it subpar to other methods? I think section 2.2. could benefit from a short motivational introduction; on the first read, I was not clear about the purpose of introducing the Polyak step size as it is not mentioned explicitly in the text leading to it.
review_title: Official Blind Review #2

final_score: rating: 1: Reject
review_content: This paper proposes a new gradient descent methods for training deep neural network which can take the adaptive step size with only one hyper-parameter to tune -- the maximum learning rate -- and achieve comparable results to stochastic gradient descent (SGD) on various tasks and models. In order to achieve that, they develop a stochastic extension of the Polyak step-size for the non-convex setting, namely the adaptive learning-rates for interpolation with gradients (ALI-G), in which the minimal value of the objective loss is set to 0 due to interpolation in neural networks and the learning rates are clipped by a chosen maximal value. The problem is formulated clearly, and the review on the Polyak step-size and related works are well done. Another main contribution of the paper is to provide the convergence guarantees for ALI-G in the convex setting where the objective loss is Lipschitz-continuous (Theorem 1 in the paper). Their theorem also takes into account the error in the estimate of the minimal value of the objective loss. In addition, they derive the connections between  ALI-G and SGD and show that compared to SGD, ALI-G take into consideration that the objective loss is non-negative and set the loss to 0 when it is negative. They perform empirical study to compare their algorithm with other methods including Adagrad, Adam, DFW, L4Adam and SGD on learning a differentiable neural computer, object recognition, and a natural language processing task. Their experimental results show that ALI-G performance is comparable with that of SGD with schedule learning rate.

Overall, this paper could be an interesting contribution. However, some points in the theory and experiments need to be verified. I weakly reject this paper, but given these clarifications in an author response, I would be willing to increase the score. 

For the algorithm and theory, there are some points that need to be verified and further clarification on novelty:

1. When there are regularization such as the weight decay regularization, the minimal objective loss will not be 0. In such cases, Theorem 1 in the paper only guarantees that ALI-G reaches an objective loss less than or equal to a multiple of the estimate error \epsilon of the true minimal objective loss. It cannot guarantee that the objective loss reached by ALI-G can converge to the true minimall objective loss. Furthermore, when training neural networks with, for example, the weight decay regularization, often times the value of the regularization loss, i.e.  the estimate error \epsilon, is not small. Therefore, the upper bound given by Theorem 1 is rather loose. 

2.  The paper mentions that when no regularization is used, ALI-G and Deep Frank-Wolfe (DFW) are identical algorithms. The difference between the two algorithms are when regularization is used. However, given my concern for Theorem 1 above, the convergence of ALI-G and advantage of ALI-G over DFW in this setting is questionable, and the claim that “ALI-G can handle arbitrary (lower-bounded) loss functions” also needs to be verified. 

For the experiments, the following should be addressed:
1. In the experiment with the differentiable neural computers, even though ALI-G obtains better performance for a large range of \eta, its best objective loss is still worse than RMSProp, L4Adam, and L4Mom.

2. Given the merit of Theorem 1 is that the convergence guarantee takes into account the estimate error of the minimal objective loss, an ablation study that compares ALI-G with other methods in the same setting with and without regularization are needed. For example, it would be more convincing if similar results to those in Table 2 or 3 but without regularization are provided and discussed.

3. In Section 5.5, given that ALI-G and DFW are related, why is there no result for DFW in Figure 
4.?

4.  As the paper mentions, AProx algorithm and ALI-G are related, why is there no comparison with AProx in the experiments?
Things to improve the paper that did not impact the score:
1. In all experiments, the performance differences between ALI-G and competitive methods are small. Thus, error bars are needed for these results.

2. In Table 3, the gap between SGD and ALI-G can be significantly different on different architectures. For example, in CIFAR-100 experiments, while ALI-G achieves the same result as SGD with the DenseNet, ALI-G’s performance on Wide ResNet is much worse than SGD. Do you have any explanation for this?

3. How is ALI-G compared with the methods proposed in the paper “Stochastic Gradient Descent with Polyak's Learning Rate” (https://arxiv.org/abs/1903.08688)


The following paper also proved the convergence of adaptive gradient methods for nonconvex optimization:
Dongruo Zhou*, Yiqi Tang*, Ziyan Yang*, Yuan Cao, Quanquan Gu. On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization.

-------------------------------------------------------------
After rebuttal:
I noticed that the authors:

1. did not compare with SGD or Adam with good hyperparameters (https://arxiv.org/abs/1907.08610)

2. did not test on the large scale datasets, e.g., imagenet

3. the proposed algorithm is not as good as SGD on most numerical experiments.

For the above reasons, I think this paper should be rejected.

review_title: Official Blind Review #1

Meta-review: This paper uses the interpolation property to design a new optimization algorithm for deep learning, which computes an adaptive learning-rate in closed form at each iteration. The authors also analyzed the convergence rate of the proposed algorithm in the stochastic convex optimization setting. Experiments on several benchmark neural networks and datasets verify the effectiveness of the proposed algorithm. This is a borderline paper and has been carefully discussed. The main objection of the reviewers include: (1) The interplay between regularization and the interpolation property is not clear; and (2) the proposed algorithm  is no better than SGD in any of the benchmarks except one, where SGD's learning rate is set to be a constant. After the author response, this paper still does not gather sufficient support. So I encourage the authors to improve this paper and resubmit it to future conference.
Decision: Reject