Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper shows that under several assumptions, online mirror descent for convex losses can be written as a perturbed version of online gradient descent for possibly non-convex losses with an $O( T^{2/3} )$ regret, up to a reparameterization. By a similar understanding, this paper also discusses when online gradient descent for non-convex losses is provably no-regret by the reparameterization argument. 
strengths_and_weaknesses: **Strengths**
1. The argument is very simple yet reasonable and actually novel, as far as I know. 

**Weaknesses**
1. The first example in Section 3.1 seems to be wrong. That example considers online exponentiated gradient descent on the probability simplex, arguably the most representative instance of online mirror descent. As relative entropy is not Lipschitz on the probability simplex, violating Assumption 2, the smoothed simplex is proposed to be a fix. However, then points close enough to the origin should be removed from the set $\mathcal{K}'$, meaning that $\mathcal{K}'$ is non-convex and the theory in the paper does not apply. 
2. The other two examples in Section 3.1, online mirror descent with the log barrier and the tempered Bregman divergence, are much less representative compared to exponentiated gradient descent. 
2. Section 5, which provides conditions when online gradient on non-convex losses may be viewed as online mirror descent on convex losses and hence is no-regret, should be the most useful part. Unfortunately, no relevant example is provided. 
2. There are some typos. 
    - Ln. 95: $\Vert x \Vert_p$ instead of $\Vert x \Vert p$
    - Ln. 105: $\nabla^2 R$ instead of $\nabla^2_R$
    - The equality following Ln. 205: $\nabla f_t ( x_t )$ instead of $\nabla f_t$
    - The article "the" is missing in several places. 
questions: 1. Please check the correctness of the first example in Section 3.1. 
2. Is there any relevant application of Theorem 7 in Section 5? 
limitations: Assumption 2 basically assumes that everything should be Lipschitz. This assumption is violated for exponentiated gradient descent and online mirror descent with self-concordant barriers, for example. The authors also noticed that the matrix version of exponentiated gradient "is difficult to fit into this framework." The self concordance of the regularizers in these examples may a useful property to replace the Lipschitz assumption.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper studies an approximate equivalence between online gradient
descent (OGD) on non-convex losses with online mirror descent (OMD) on
convex reparametrizations of the losses. Special cases of this
equivalence were already known from [3] and [4], but the present paper
attempts to set up a general theory. Its main results are:
- Theorem 3, which gives sufficient general conditions for the
  approximate equivalence to go through, leading to an O(T^{2/3}) regret
  bound for OGD on the non-convex losses.
- Section 3.1, which provides example instances of OMD on convex losses
  which can be approximated this way by OGD on non-convex losses.
- Theorem 7 goes in the other direction: it gives sufficient conditions
  for OGD on non-convex losses to be approximated by OMD on convex
  losses.


strengths_and_weaknesses: Strengths:
* The paper is very well written, especially the introduction.
* The approximate equivalence between non-convex and convex online
  optimization is an exciting new direction, for which few results are
  yet available. It would be great to have a general theory that
  describes when such equivalences are possible.

Weaknesses:
* It is not clear that the general theory covers any interesting cases:
  1. It does not recover the previous results from [3] and [4].
  2. I do not consider the examples provided in Section 3.1 to be very
  convincing. In the first two examples, it would seem that G could be
  as large as T, so then Theorem 3 would be vacuous. For the last
  example, I am not sure how the constants play out.
  3. Theorem 7 does not quantify how the strong convexity parameter c>0
  of the regularizer R that is constructed, depends on the properties of
  q and tilde{f}. It could therefore be 

In spite of these weaknesses, the overall proof approach does seem like
the natural way forward, by quantifying the approximation error in the
equivalence. If my questions below can be answered satisfactorily, I am
therefore still mildly in favor of acceptance, even if there are no
strong examples.

Remarks:
* Theorem 3 assumes that R is 1-strongly convex. This should be stated
  explicitly in its conditions. I am also concerned that this is not
  verified in the examples from Section 3.1, so do they really satisfy
  this condition?
* In the Proof of Theorem 7: I don't understand how you get from the
  displayed equations above "solving the above formulas" to the ODE
  below.

Minor Comments:
* Line 80: equivalence between OMD and FTRL requires constant step size.
* "Euclidean" should be capitalized throughout the paper
* Line 95: p should be a subscript in p-norm
* The square on the Hessian appears to overlap with the nabla symbol
  throughout the paper.
* Line 108: Shouldn't q^{-1} be q? (Maybe I was just confused here.)
* Assumption 1: Should the Hessian be interpreted as the Hessian of R or
  the Hessian of R(q(.))
* Algorithm 1: f_t -> f_t(x_t)
* Line 147: "cab" -> "can"
* Line 205: f_t -> f_t(x_t)

questions: * Could you indicate how the G that appears in Theorem 3 scales with T,
  and verify that R is 1-strongly convex for all three examples in
  Section 3.1?
* Could you answer the remark above about the proof of Theorem 7? 


limitations: Section 3.2 provides a very good discussion of some of the limitations
of the approach.

The limitations in footnotes 1 and 2 seem sufficiently important to put
them somewhere in the main text.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper shows that for a certain class of non-convex problems, online gradient descent has a O(T^{2/3}) regret. Previous works by Amid and Warmuth show that gradient flow for minimizing a reparametrized function is equivalent to mirror flow for minimizing the original function. This work takes a step forward by showing in discrete-time, online gradient descent on a reparametrized objective has a sublinear regret.

The high-level idea is that the discrete-time online mirror descent has a O(\sqrt{T}) for the same class of problems. By carefully bounding the discrepancy between online mirror descent for the original problem and online gradient descent (OGD) for the non-convex re-parametrization, a sublinear regret of OGD can be obtained.



strengths_and_weaknesses: While the corresponding continuous-time result has been established in the previous work, the discrete-time setting seems to be left open. This work fills the gap.

In my opinion, this paper is pretty much borderline for the following reasons:

1. While I appreciate the theoretical result, I think it will be more helpful if the authors can discuss the advantage of conducting discrete-time online learning on the reprametrized functions, since the regret gets worse, i.e., one could simply use OMD for the convex problems.

2. Following the first point, I think the title should be modified and be more specific, since the technique seems only applicable to a certain class of problems and critically relies on the particular connection between OGD and OMD that has been established in the prior work by Amid and Warmuth.




Minor:
1. I don't quite understand Line 200-202. Perhaps a more detailed derivation would be helpful?
2. Line 215: "both both".

questions: N/A
limitations: N/A
review_title: null

Meta-review: metareview: The main result of the paper is on establishing an approximate equivalence between online gradient descent (OGD) on non-convex losses with online mirror descent (OMD) on convex reparametrizations of the losses. In a previous result by Amid and Warmuth, which applies to the the continuous-time setting, we have exact conditions where the gradient flow with this reparameterization is exactly equivalent to continuous-time mirror descent. However, the current paper focuses on providing discrete time algorithms. The main theoretical contribution of the paper is to provide sufficient general conditions for the approximate equivalence to go through, leading to an O(T^{2/3}) regret bound for OGD on non-convex losses.

The paper was discussed to a good extent between the authors and the reviewers, and among the reviewers. The reviewers (and the AC) agreed that the paper provides a novel analysis which is based on a simple, elegant, and novel algorithmic equivalence method. Most of the concerns of the reviewers were addressed during the discussion phase. However, the reviewers still felt that the paper lacks relevant and important applications where the approximate equivalence (and reparametrization) would apply to and would lead to non-trivial results. All in all, the reviewers agreed on the decision that the paper lies on the acceptance border (with inclination towards acceptance). 

confidence: Less certain
Decision: Accept