Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper provides a convergence analysis for the AMSGrad algorithm for the more general class of functions that are weakly convex. The convergence guarantee is comparable to existing results for SGD, and the main advantage is that the AMSGrad algorithm does not require knowledge of the weak convexity parameter and it automatically adapts to it. The paper extends the convergence analysis to other algorithms, such as SGD with momentum and the AdaGrad algorithm with scalar step sizes.

main_review: Significance:
Adaptive methods in the AdaGrad/Adam family are widely used in practice, in both the convex and non-convex setting. Prior analyses for these algorithms in the non-convex setting assume smoothness. This paper extends this line of work by considering weakly convex functions, which are more general than smooth functions. In addition to adapting to the weak convexity parameter, another strength of the analysis is that it works for constant beta_1 and beta_2 parameters, which is in line with how Adam is used in practice.

One of the weaknesses of the analysis is that it strongly relies on the value delta used to initialize the preconditioner, which is crucial for bounding key error terms, resulting in a dependence of 1/sqrt(delta) in the convergence. This limits the applicability of the analysis approach and it does not allow for arbitrarily small initializations as used in practice.

The computational evaluation shows the benefits of using AMSGrad compared to using non-adaptive methods such as SGD. However, the experiments consider small synthetic instances and thus the experimental evaluation is limited. Overall, this is a good contribution to this line of work.

Novelty/originality: The paper builds on prior analyses of SGD for weakly convex functions as well as an an analysis of AMSGrad for convex functions that works for constant beta_1 and beta_2 parameters. The non-convexity together with the adaptive and stochastic step sizes poses some additional challenges in the analysis compared to prior work, and the main novelty in this work is to bound the new error terms that arise. Overall, there is sufficient novelty but it is perhaps somewhat limited.

Clarity: The paper is reasonably clear. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper analyzes AMSGrad when applied to a broad family of nonsmooth, nonconvex, stochastic, constrained optimization problems. Convergence rates based on the norm of the Moreau envelope's gradient (although in a rescaled norm) are presented. The rates nearly match the O(1/T^{1/4}) rate of the subgradient method, off by a logarithmic term. The primary innovation in this work is tackling technical barriers to handle first and second order moment parameters that complicate analysis.
main_review: -The terminology used for describing convergence rates is somewhat inconsistent. The abstract uses the more modest description of a O(1/T^{1/4}) rate in the gradient norm whereas the main text consistently frames itself as a O(1/\sqrt{T}) rate in terms of the near stationarity condition (5), which hides a factor of two.

-Algorithm 1 currently does not define $\xi_t$ which is presumably sampled i.i.d. at each iteration.

-The analysis implicitly uses a sum rule for nonconvex nonsmooth calculus that requires additional regularity assumptions to be assumed. Namely, it need not be the case that selecting $g_t\in \partial f(x_t,\xi_t)$ for each realization of $\xi_t$ produces an unbiased estimator of a element $q_t$ in $\partial f(x_t)$ (as is claimed in Lemma 2). Regularity conditions on each $f(x,\xi)$ are needed. It would suffice to additionally assume that each $f(x,\xi)$ is locally Lipschitz everywhere on an open set containing $X$.

-Remark 2 currently claims $\|x_t-\hat x_t\|^2_{v_t^{1/2}} \geq \sqrt{\delta}\|x_t-\hat x_t\|^2$. I believe the $\sqrt{\delta}$ should be $\delta$.

-Relaxing the $\|\cdot\|_\infty$ norm subgradient constraint to instead be a bound on the expected norm seems more difficult than the work suggests. Doing so would remove the uniform upper bound on the size of $v_t$, which would then make converting guarantees back to the original norm $\|\cdot\|$ much harder.
limitations_and_societal_impact: The convergence guarantee's given in the rescaled norm based on $v_{t}$ and based on the rescaled Moreau/proximal operator using $v_t$. As a result (and as the paper acknowledges in remark 2), extra care is needed to understand the results in the given norm $\|\cdot\|$. Particularly, the best guarantee given from the proposed analysis is worse by a non-negligible factor of $1/\delta$. Establishing some lower bounding theory for $v_t$ may overcome this current limitation.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents an adaptive gradient descent method for a convex set-constrained weakly convex (hence, nonconvex and possibly nonsmooth) optimization problem. 
main_review: The authors used AMSGrad proposed by Reddi et al. [2018] for showing their results. AMSGrad was a modification of ADAM that exhibited provable convergence. The authors also used Moreue envelop-based analysis in Davis et al. [2018] where the norm is suitably weighted for the adaptive procedure. The bounds provided in Theorem 1 are very similar to state-of-the-art results for adaptive algorithms like Adam, AMSGrad, RMSProp, etc. 
The Paper was quite easy to read and the authors did a good job in providing key insights into the proof techniques.
limitations_and_societal_impact: Boundedness assumption on the stochastic gradient, even though standard in adaptive optimization, is quite strong for unbounded domain set. Many works get around this difficulty by assuming compactness of set \mathcal{X}. Since the paper also briefly discussed bounded domains, I believe that this is not a major issue. 
Overall, I think the paper makes a good contribution. Given that this is the first paper looking into an adaptive procedure for nonsmooth nonconvex problems, the authors could have done a better job in highlighting the key aspect of the analysis which allowed for providing convergence.
review_title: null

Meta-review: The paper introduces an adaptive method for weakly convex optimization, which generalizes the setting of smooth nonconvex optimization. A particularly important aspect of the introduced method is that it automatically adapts to the weak convexity parameter, without any prior knowledge. The paper makes a good contribution to the literature on adaptive gradient methods (similar to the very popular AdaGrad) and all the reviews expressed support in seeing this paper published at NeurIPS. 
Decision: Accept (Poster)