Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors propose an algorithm that they call mini-batch normalized gradient descent with momentum. This algorithm can find an \epislon-first-order stationary point under O(\epsilon^{-4}) gradient complexity, even though the objective function is non-convex and non-smooth and has unbounded gradient noise. Their work is limited to where all loss functions are G−Lipschitz and L−smooth in x and conjugate function of a divergence function is M−smooth. Their main algorithm goes like: get a mini-batch gradient estimator (using mini-batch to ensure convergence) and update momentum using that estimator and update their variable w using normalized momentum. They presented two numerical results: one classification, the other regression. They compared their algorithm with vanilla SGD regarding convergence speed.
main_review: This is a high quality paper that appears to give the first non-asymptotic convergence results for DRO problems with general smooth *non-convex* losses and general divergence functions. The paper is well-written, clear, and the results (to the best of my knowledge) appear to be sound and mathematically correct. The contribution is clearly significant due to the importance of non-convex optimization and DRO. I have no major criticisms and am happy to see this paper accepted. 
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper studies the distributionally robust non-convex optimization for non-convex objectives. Authors provide a theorem for the convergence rate based on alternative assumption.
main_review: I would like to say that the paper is well-written and it is easy to follow; however, I have the following concerns:

(1) In general optimization theory it is known that bounded gradient assumption does not hold in practice and it grows with the size of input unless the updating rule involves projection to a certain set to keep the size of gradient bounded. Therefore, I think the provided example 3.1 (while being insightful) is a known fact in optimization theory.

(2) To deal with the issue (1) the reference [1] suggests the bounded variance assumption which is very similar to the assumption 3.2 in this paper. And using this assumption and careful choice of learning rate they can eliminate the effect of the growing norm of gradient. I believe this paper also follows the same approach and I found the results to be not surprising. 

[1]: Bottou, L., Curtis, F. E., & Nocedal, J. (2018). Optimization methods for large-scale machine learning. Siam Review, 60(2), 223-311.

Given (1) and (2) I am struggling to support the acceptance of this paper, and while having an interesting direction and problem in hand, I think authors can improve the results further.

I also mention that I can be considered knowledgeable in optimization theory in general but I am totally new to the distributionally robust optimization area.
limitations_and_societal_impact: See the above comment!
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper bridges the gap by studying DRO algorithms for general smooth non-convex losses. By carefully exploiting the specific form of the DRO objective with $\psi$ divergence, this paper provides non-asymptotic convergence guarantees even though the objective function is possibly non-convex, non-smooth, and has unbounded gradient noise. In particular, the authors prove that a special algorithm called mini-batch normalized gradient descent with momentum can find an $\epsilon$-first-order stationary point within $O(\epsilon^{-4})$ gradient complexity. Furthermore, for the conditional value-at-risk (CVaR) setting, this paper proposes a penalized DRO objective based on a smoothed version of the CVaR and obtains better complexity. The theoretical results are verified in several tasks, and the proposed algorithm can consistently achieve prominent acceleration.
main_review: Compared with the existing works, this paper provides the first non-asymptotic analysis of optimization algorithms for DRO with general smooth non-convex losses $\ell(x,\xi)$ and general $\psi$-divergence. In this setting, there are two major difficulties : (i) the DRO objective $\Psi(x)$ is non-convex and can become arbitrarily non-smooth, causing standard techniques in smooth non-convex optimization to fail to provide a good convergence guarantee; (ii) the noise of the stochastic gradient of $\Psi(x)$ can be arbitrarily large and unbounded even if the gradient of the inner loss $\ell(x,\xi)$ is assumed to have bounded variance. Therefore, the core technique of this paper is to exploit the specific structure of $\Psi(x)$, which shows that (i) the DRO objective satisfies a generalized smoothness condition [Zhang et al., 2020a,b] and (ii) the variance of the stochastic gradient can be bounded by the true gradient. This motivates the authors to adopt the special algorithm that combines gradient normalization and momentum techniques into SGD, by which both non-smoothness and unbounded noise can be tackled, finally resulting in an $O(\epsilon^{-4})$ complexity similar to standard smooth non-convex optimization.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies distributionally robust optimization with the loss function being nonconvex and the uncertainty set defined by a divergence function. Particularly, this paper gives a very interesting generalized smoothness condition, shows the connection of the normalized gradient descent with this smoothness condition, and gives a non-asymptotic convergence rate. Finally, experimental results verify the theory. 
main_review: I believe that this is a good paper in this area. Both the theoretical and experimental results are good. My main concern is that this paper can only address the soft constrained case. For the CVaR case or the hard constrained case, can we still apply the technique in this paper, such as the generalized smoothness condition? For instance, for the hard constrained case, we can get a similar reformulation about $(x,\eta)$ and $\lambda$ (see Namkoong & Duchi, 2016).  When $\lambda$ is also changing, can the generalized smoothness condition still hold? 

The O(\epsilon^{-4}) may be further improved if we use some variance reduction approach based on SARAH/SPIDER. 

Does the mini-batch setting really necessary? Can we only use one sample and get the same rate by decreasing the step size? 


Some minor comments: 

1. In Lemma 3.4, we may use $x', \eta'$ to replace $x_2, \eta_2$.

limitations_and_societal_impact: No Societal Impact
review_title: null

Meta-review: The paper provides convergence guarantees for a stochastic method on a family of non-convex DRO problems, getting around the non-trivial challenge of lacking global smoothness and variance bounds. The reviewers appreciated the quality of the writing, relevance of the topic, and the technical novelty of the results, and from my own reading of the paper I received a similar impression. When revising the paper, please take care to thoroughly address the comments provided by the reviewer and myself. In particular, it is crucial to provide test performance of the model you train, in order to show that the problems and hyperparameters for which you solve DRO are such that it really provides an improvement in robustness.
Decision: Accept (Poster)