Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes an adaptive mirror descent method for solving relative smooth optimization problems. The idea of using adaptive stepsize for first-order methods is not new in the literature, but the proposed adaptive stepsize in this paper is new. 
main_review: The paper is well-written and the obtained convergence rate in this paper is nice. My main concern is the well-definedness of the proposed algorithm. Proposition 2 proves that $x^+ \in dom  \partial h$ for all $x\in dom  \partial h$ and $g\in \mathcal V^*$. But it is not clear if $x^+$ belongs to $dom \partial f$ or not. This is crucial to guarantee the existence of the next $g$.  

Some minor comments:

1. Provide the strongly convex constant $K$ for the examples in lines 157-165.
2. Typo in (RC) (see line 171): $x\in dom \partial h, x' \in dom h$. 
3. Definition 3: it should be "relative smooth to $h$".
4. Proposition 1: provide where $x$ and $x'$ belong in each inequality. 
5. Section 4.1: is it "prox-mapping" or "prox-gradient/subgradient-mapping"? 

limitations_and_societal_impact: N.A.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposed an adaptive mirror descent for convex optimization problems where Lipschitz continuity or smoothness may be not available, both deterministic and stochastic settings are discussed.

main_review: The paper provides a detailed literature review on the considered problem. The study is well motivated and the results obtained are clearly stated and discussed. 

Please be clear about the $O(1/T^\alpha) $ convergence rates appeared in the paper. For Nesterov’s accelerated gradient, the $O(1/T^2)$ rate is on the objective function value at the last iterate, while for some other methods mentioned in the paper, $O(1/T^2)$ rate is for ergodic averaged point. 




limitations_and_societal_impact: See above for limitations and no negative societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: - In the paper, the authors propose an adaptive parameter agnostic algorithm AdaMir for online and stochastic convex optimization problems.
- AdaMir is essentially like the popular Adagrad algorithm with Bregman distances involved in controlling the step-size.
- Their setting involves non-Lipschitz gradients, contrary to the traditional Lipschitz smooth setting. 
main_review: Positives:
- The paper is well written, clear to read and the theory seems to be sound. I did not check the proofs though.
- Authors provide a good introduction to various concepts involved in the paper, for example, Bregman distances, relative smoothness and many others.
- AdaMir combines the best of two worlds, adaptive gradient methods and Mirror Descent based methods.
- In the deterministic setting, the ergodic convergence rates of AdaMir for both RC and RS settings are given in Theorem 1. Notably, optimal rates are obtained in both the settings.
- The stochastic setting is also considered, for which convergence rates are provided for AdaMir. Brief discussion on non-convex setting is also provided.


Negatives:
- The paper considers many settings which contributed to too much packed content in the paper. I wish authors focussed on just online setting itself, while relegating the stochastic setting to the supplementary material.
- No experiments were provided in the main paper. I would suggest moving the experiment from the supplement to the main paper.
- Example 1, 2, 3 can be moved to supplementary material. I think it is better to focus more on the AdaMir algorithm.
- The authors use a strongly convex $h$, which makes the definition of $\delta$ not so appealing.
- In my opinion, the main novelty lies in the definition of $\delta$ which makes use of two Bregman distance evaluations. However, I think the novelty in the rest of paper is not significant.
- More discussion on remark starting at line 118 is needed.
- A closely related work seems to be [45]. I think more discussion on this is needed preferably before just before the AdaMir algorithm. Also, discussion on regret bounds based on Proposition 3 is missing (please refer to [45]).
- What is the connection of your Definition of a Bregman function to the other standard definition using Legendre functions?
- There is no numerical evidence for the proposed method.

Other comments:
- In line 334, change "eay" to "easy".
- Typo in equation in line 229.

limitations_and_societal_impact: yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper studies convex minimization problems lacking Lipschitz continuity of the objective and compactness of the feasible set. They assume access to a standard stochastic subgradient oracle with mean-zero noise and bounded variance. The main contribution of the paper is to propose an adaptive method based on Mirror descent and a clever step-size rule that attains optimal convergence rates under several regularity assumptions beyond standard Lipschitz continuity.
main_review: The paper is well-written and easy to follow. It was a pleasure to read. The authors did a good job explaining the problem, the motivating limitations from the literature, and the connections to other methods. The use of examples and the clarifying remarks were very insightful.

The proposed method combines Mirror descent with a generalized version of the adaptive step-size rule popularized by AdaGrad. The method is simple and somewhat natural. The core innovation is the analysis of these algorithmic solutions under weaker conditions. The theoretical analysis appears to be mathematically sound. However, I did not check all the details.

Here are some points that the authors should address before publication:

- The column "Order-optimal" in Table 1 is slightly misleading. This column is not comparable among the rows because the classes of functions are different. Consider dropping the column or including the class explicitly.
- I would like to see how AdaMir performs against other methods in the literature; the paper would greatly benefit from a few numerical experiments.
- What does "partial" mean in Table 1?
- L98: adaptiving -> adapting.
- L121: Move the footnote to the previous sentence where you make the claim.
- L131: Delete one "sample."
- L134: Clarify this is the dual norm on V^*.
- L229: Typo double in the inline equation.
- L259: It is odd to present all the other statements explicitly and use the big-O notation for this one. Consider writing an explicit bound.
- L301: I cannot find (SI) defined anywhere. I am assuming you refer to (12)?
limitations_and_societal_impact: The limitations were addressed. The paper studies a theoretical question with no direct societal impact.
review_title: null

Meta-review: Overall the reviewers liked the paper and found the contributions strong enough for NeurIPS. I have read the paper, and while I have an issue with the claim of the authors that their algorithm is adaptive, while it requires the specification of the "smoothing function" h(), I still appreciate the overall technical contribution provided in the analysis and obtained results.

Decision: Accept (Poster)