Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: ##########################################################################


Summary:

This paper shows a “generalized mirror descent“ converges linearly if the objective function is smooth and satisfies the Polyak-Lojaciewicz condition. 


##########################################################################


Reasons for score: 
 

The novelty seems to be very limited. This paper does not actually show the benefit of replacing the gradient of the Bregman function by a general mapping in mirror descent. The analyses are standard and do not actually get more difficult with the generalization. The theorems require the derivatives of the Bregman function to be bounded, making the result not even applicable to entropic mirror descent, arguably the most notable instance of mirror descent. 


##########################################################################Pros: 
 

Pros: 

1. None. I have not seen a proof showing mirror descent converges linearly with the Polyak-Lojaciewicz condition in literature, so this could be a novelty. But the analyses in this paper are just standard and very restrictive because they require the Bregman functions to have bounded derivatives. 
 

##########################################################################

Cons: 

1. I do not see the benefit of replacing the gradient of the Bregman function by a general mapping \phi. The authors use gradient descent, mirror descent, and AdaGrad as examples of the “generalized mirror descent” in Section 5. However, it is already known that gradient descent is a special case of mirror descent and AdaGrad is mirror descent with a time-varying Bregman function. All three do not need the notion of a “generalized mirror descent.” 

2. The proposed “generalized mirror descent” is not actually more general than mirror descent. The assumption on \phi in Theorem 1, for example, coincides with the standard assumption in mirror descent literature that the Bregman divergence is strongly convex. Moreover, the condition that \phi is Lipschitz is restrictive (for example, it does not hold for entropic mirror descent) and does not appear in standard mirror descent literature. The conditions on the derives of \phi are even more restrictive in Theorem 2 and Theorem 3.  

3. The theorems in this paper only states that the algorithms converge linearly. Please make an optimal choice of the step sizes and make the dependence of the convergence rate on the problem and algorithm parameters explicit. Also please make sure that the exponent in the linear convergence rate does not depend on the iteration counter, as opposed to those shown in the appendix.  

4. The paper starts with a discussion on overparameterization. However, I do not see the connection of this paper with explaining the benefit of overparameterization. Indeed, the analyses in this paper has nothing to do with overparameterization, unless the authors connects the PL condition with overparameterization.  

5. Isn’t the PL^* condition simply the PL condition with the objective function shifted by -f(x^*)? As long as f(x^*) is finite, without loss of generality, one can always do such a shifting and the sequence of iterates does not change. I do not think PL^* is a new condition. 
 

##########################################################################

After reading the rebuttal: 

I keep the score. 

- In my view, the Taylor-series analysis is a very straightforward approach such that existing frameworks apply to the setup considered in this paper. Such a straightforward approach renders the results restrictive and hence I do not consider it a significant novelty. 

The proof of Theorem 1 just rewrites the existing proof with minor modifications for the considered setup and hence do not require any additional restriction. Emphasizing Theorem 1 is not very appropriate for the rebuttal. 

- The "generalization" I mentioned is for the \phi function. There are already several works on mirror descent/FTRL with a time-varying regularizer (Orabona et al. (2015) is for FTRL, as clarified in Orabona's lecture notes on online learning). Without an example where the \phi function is not the gradient of a potential function, I do not see the necessity of this generalization. 

For the same reason above, emphasizing Theorem 1 is not very appropriate for the rebuttal. 

- My point is to clarify the dependence of the convergence rate on the problem parameters. I do not think the proofs in the appendices provide explicit characterizations of such dependence. To make such explicit characterizations, I think specifying *a* step size instead of *a range* of step sizes is perhaps necessary. 

- I suggest the authors rewrite the first two paragraphs to make the motivation of the problem setup clearer there. Section 2 is OK. 
 

#########################################################################
review_title: Analyses are standard and very restrictive

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper studies 1) the convergence rate; and 2) the implicit regularization of (stochastic)GMD, a generalization of (stochastic) mirror descent where mirror maps can be time dependent. The contributions are as follows: 1) Theorem 1: for PL+smooth functions, the paper presents a linear convergence result for GMD; 2) Theorem 2, 3: they provide sufficient conditions on the Jacobian of the mirror map, under which (stochastic)GMD converges linearly; 3) Theorem 4: argues for an “approximate implicit regularization” effect of GMD, by showing that GMD converges to a point, “close” to the initialization, where closeness is measured in terms of the \ell_2 distance in the mirrored space.

- Correctness: I have a problem understanding the proof of Theorem 3. In the fifth line of the proof of theorem 3, page 15 of the appendix, I’m not sure how you upper bound the quantity - < \nabla f(w^(t)), J_\phi^-1 \nabla f_{i_t}(w^(t)) > by the right hand side. Of course, the Jacobian is assumed to be positive definite, but how does this upper bound follow? Besides, I found the claim in Theorem 3 quite interesting, and even surprising. It seems to me that SGD, which is SGMD with mirror maps equal to identity, satisfies the conditions of Theorem 3, simply because the mirror map is the identity. Then, the result claims an exponential convergence rate for SGD to the global optima. Can you clarify this, in light of the minimax lower bounds for SGD in smooth and strongly convex setting, e.g. the recent work: https://papers.nips.cc/paper/8624-tight-dimension-independent-lower-bound-on-the-expected-convergence-rate-for-diminishing-step-sizes-in-sgd.pdf

- Novelty/Significance of the results: Theorem 3 is novel and seems very interesting, if the authors clarify the issue above, as well as clarify the generality of the assumption, i.e. the conditions required for the Jacobian of the mirror map. Can you clarify what are the technical challenges in proving Theorem 1, and what are the novelties with respect to several related work, including the work of Karimi et al., 2016?

- Clarity: In my humble opinion, Theorem 4 cannot be interpreted as an “approximate implicit regularization” effect, simply because the distance to the optimum measured in the mirrored space can be very large, and the authors do not provide examples when this can actually be small. In the remarks, you point out “Hence provided that R is small (which holds for small f(w(0))), GMD selects an interpolating solution that is close to w*  in \ell_2-norm in the dual space”. But why should one expect f(.) to be small at the initialization? Specifically, this theorem is proved under the assumption that f(.) is non-negative, therefore, f(w^(0)) being small simply means that w^(0) is already an approximate global optimum.

- Presentation: I think there is room for improving the writeup. Here are some examples:
   + The presentation of MD-type updates in Equation (1) is quite abrupt, without providing the motivation/context.
   + All of the main theorems guarantee linear convergence without actually characterizing the rate of convergence. I found it very confusing as it hides the dependence on important parameters.
   + The presentation of the PL* condition in section 3 is very confusing as none of the main results (Theorems 1-3) requires this condition. What is the motivation? It seems that this condition is not preserved under simple transformations such as translation, i.e. if f(X) satisfy PL* then f(x) + 1 will not. What are some interesting function classes that satisfy this property?
   + Do the assumptions of Lemma1 (PL*, smoothness, non-negativity) imply existence of x* such that f(x*) = 0?
   + Can the monotonicity condition in Theorem 4 be restated in terms of strong/strict convexity of the potential function associated with the mirror map?
   + The sufficient conditions in theorems 2 and 3 are not discussed at all. What are some examples of interesting potential functions / Bregman divergences that satisfy these conditions?

For the reasons listed above, I don’t think this paper is ready to be published at ICLR. Of course, I will happily reconsider my evaluation and increase my score if the authors clarify the issues raised above.

****************************************Post-rebuttal comments****************************************
***************************************************************************************************
After reading authors feedback, I've increased my score from 3 to 5; however, the paper in its current form is still a borderline. 
***************************************************************************************************

review_title: Needs further clarifications

final_score: rating: 4: Ok but not good enough - rejection
review_content: [Summary]
This paper studies the interesting property of generalized mirror descent (GMD) and its stochastic variant for nonconvex optimization problems. First, for GMD this paper shows the linear convergence under PL* condition (in Lemma 1) and finds out a new sufficient condition for the linear convergence (in Theorem 2). Next, this work tried to extend this result to a stochastic setting (in Theorem 3). Moreover, the implicit regularization of GMD is studied, which is an extension of the previous studies by [Azizan et al.].

[Strength]
This paper is easy to read. I think this line of research is very interesting and important to explain the reason why the overparameterized models work well. 

[Weakness]
A major concern is the correctness of the statement. There seems to be a technical flaw in the proof of Theorem 3 which is one of main contributions. Indeed, since learning rates $\eta^{(t)}$ depend on $\|f_{i_t}(w^{(t)})\|$, $\eta^{(t)}$ should be also random variable depending on $i_t$. Hence, the equation $E_{i_t}[ \eta^{(t)} \|\nabla f_{i_t}(w^{(t)})\|] =\eta^{(t)} E_{i_t}[\|\nabla f_{i_t}(w^{(t)})\|]$ is invalid. However, this equation is used in the first expression in page 16 in supplementary.
Moreover, it would be better to specify the explicit convergence rate in the main theorems to verify certain linear convergence.

Another concern is the significance of Theorem 4. The property of implicit regularization of GMD is stated in Theorem 4, but this theorem seems not to be a proper extension of the result obtained in [Azizan et al. (2019)].
- The orders wrt R of the ball $\tilde{\mathcal{B}}$ and $\| \phi(w^*)- \phi(w^{(\infty)})\|$ are the same, hence, the convergence of the order $o(R)$ as shown in [Azizan et al. (2019)] does not hold.
- The domain of $w^*$ is restricted in $\tilde{\mathcal{B}}$, but there is no such restriction in [Azizan et al. (2019)].
- If we consider $\phi(w)=w$ which corresponds to the gradient descent, the result (3) is obvious from the triangle inequality. Hence, I am concerned about the importance of this result.

[Improvement]
It would be nice if the authors could mention the above weakness.
review_title: This line of research is interesting, but I have some concerns.

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper studied an algorithm for solving unconstrained smooth finite-sum optimization, called stochastic generalized mirror descent (SGMD). The algorithm SGMD is a generalization of several existing, popular algorithms, including stochastic gradient descent, mirror descent and Adagrad. 

The main contribution lies in the convergence rate analysis of the algorithm SGMD based on the Polyak-Lojasiewicz (PL) inequality, which in turn yields linear convergence rate results for some existing methods such as Adagrad. Specifically, the author(s) showed in Theorem 3 that if the objective function satisfies the PL inequality and has a Lipschitz gradient and if the potential function (or called the mirror function) satisfies certain technical assumptions, then SGMD converges linearly to a global minimum. If the PL inequality is satisfied only locally, then local linear convergence result for the GMP (the deterministic version) was also proved. As another contribution, the paper showed that the GMD exhibits an implicit regularization phenomenon in the sense that it converges to a particular optimizers among others. 

The Taylor-series-based analysis for stochastic algorithms seems to be new and deserves some merits. However, I do have some doubts about the main results. 

First, I'm not sure if one can obtain new, useful algorithms from the general algorithmic framework in the paper and/or deduce new convergence rate results for existing algorithms. If yes, the paper should point it out explicitly, discuss such consequences and compare with the related algorithms/theoretical results. These are not clear from the current presentation of the paper.

The practical implication of the implicit regularization result is also not clear. More efforts should be spent on discussing the meaning or interpretation of the interpolating optimal solution SGMD prioritizes, especially in the context of machine learning problems (e.g., when the optimization problem is the training of neural network or some supervised learning tasks).
review_title: Review of Paper2008

Meta-review: The paper shows linear convergence for generalized mirror descent on smooth function under the PL assumption. It extends the result to stochastic generalized mirror descent under an additional assumption on the Jacobian of the mirror map. Reviewers pointed out several technical issues with the submission. While some of the problems have since been resolved in the updated version, the paper still lacks sufficient novelty, and some concerns regarding the correctness/clarity of the claims remain. Unfortunately, I can not recommend acceptance at this time. 
Decision: Reject