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 work establishes a link between minimizing a loss function using continuous-time mirror descent (i.e. mirror flow) and minimizing a reparameterized version of the same loss function using continuous-time gradient descent (i.e. gradient flow) to explain the implicit bias of gradient flow in reparameterized models. The authors introduce a class of reparameterization mappings named commuting parameterizations which satisfy certain commutativity conditions of the Jacobian. The authors show that for any commuting parameterization, there exists a mirror function in the original domain such that the trajectory of gradient flow of a loss function with that parameterization coincides with the trajectory of mirror flow of the same loss function in the original domain with the associated mirror function. Furthermore,  they also give a converse result by showing the existence of a commuting parameterization for any mirror function such that gradient flow in the reparameterized space is equivalent to mirror flow in the original space. The authors also show that several past works on implicit bias/regularization can be considered as specific cases of different commuting parameterizations. 

strengths_and_weaknesses: Strengths:
1. The authors give a sufficient condition to check whether gradient flow for a given reparametrization can be written as a mirror flow for some mirror map in a possibly smaller dimensional domain. The condition simply relies on checking commutativity of the row vectors of the Jacobian of reparametrization map $G:M\subset \mathbb{R}^{D} \to \mathbb {R}^d$, i.e., $[\nabla G_i, \nabla G_j] (x)=0$ for any $i,j\in[d]$ for all $x \in M$. They also show that several examples of reparameterization satisfy this condition.

Weaknesses:
1. The nature of the proof of Theorem 4.4 seems to be existential rather than constructive. It doesn't seem to be straightforward to construct a commuting reparametrization $G$ given a mirror map $R$ and vice versa.
2. Although the analysis is valid for continuous-time flows, the authors do not address the fidelity of this equivalence in discrete-time setting which is more practically relevant. 
3. The theoretical analysis in this paper could have been supported with extensive simulations on certain benchmarks. 


Although the paper is well written and easy to understand, it mostly builds on Amid and Warmuth (2020) by generalizing to non-injective parametrizations. This makes it an incremental contribution as there is neither much technical novelty nor extensive simulations to show practical relevance and to draw more insights. 
questions: I would appreciate it if the authors clarify the following points:

1. Is it possible to provide an order-wise relationship between $D$ and $d$? More explicitly, given mirror function $R$, can you tell how large the dimension of the reparameterization space $D$ must be with respect to $d$?
2. Given a mirror function $R$, how easy and feasible is it to construct a commuting parameterization $G$?
3. Does it make a difference in terms of finite-time (i.e. early stopping) convergence rate if one performs the training in x-space with gradient flow or w-space with mirror flow?

limitations: The authors could make this paper more impactful if they can provide a discrete-time analysis or a finite-time (i.e. early stopping) convergence rate analysis. It would also be interesting to know the order-wise relationship between dimensions $d$ and $D$. The authors could also support their results by simulations performed with practically relevant models (deep nets, kernel models, etc.) to show efficiency of using (possibly sparse) parametrizations in optimizing these models.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: For a reparametrisation $w = G(x)$ where $x_t$ follows a gradient flow on some loss $L \odot G$, the authors give a sufficient condition on the parametrisation (i.e. commuting parametrisation) so that $w_t$ to corresponds a mirror flow on $L$ and with a related mirror map.  They then show that any mirror flow can be seen as the commutative reparametrisation of a gradient flow.
strengths_and_weaknesses: Overall I think this is a very good paper.  It is very well written: 
- the motivations are clear and relevant as it sheds light on when we can hope to obtain implicit regularisation results using mirror flow type of analysis
- the setup and preliminaries are very clear
- All the results are introduced and commented, examples are also provided
- though I am not familiar with all the mentioned notions, they all seem well defined and the math seems rigorous

The paper is very well written and I believe the general framework they introduce as well as the lemmas / tools they provide are relevant: as they help understand the link between gradient flow, reparametrisation and Mirror flow.


Minor comments: 
- in the main contributions in the intro: "we also five new convergence analysis in such settings, filling the gap in previous works [22, 57, 8] where parameter convergence is only assumed but not proved." is an overclaim as the convergence of mirror descent / flow is well understood and has been investigated for years (though I agree that the mentioned works seem to have overlooked them. 
- I would have appreciated an example illustrating Lemma 4.5 and Lemma 4.6 , for the $u^2 - v^2$ parametrisation (or even simply $G(x) = x$)  for example: what is $\Psi(x, \mu)$ in this case ? and $\mu_t$? and $G(\Psi(x_{init}, \mu))$ ? this would help the reader gain more intuition / understanding
questions: - for a fixed commutating parametrisation $G$, is it possible to understand the effect of $x_{init}$ on the associated mirror map $R$
- you provide sufficent conditions, do you think they are necessary ? or not ? 
- is Nash's embedding constructive ? can we know F, G, or the dimension D ?
- do you think the claim in Remark 4.7 still holds if we restrict ourselves to losses which are non time-dependent ? 


limitations: N/A
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: This paper focuses on implicit bias of gradient descent for reparametrized models.
In this setting, a loss L over parameters w (eg weights of a neural network) is minimized, where these parameters w write w=G(x).
Hence, they consider the gradient flow of L in the x space. In the weight space, the gradient flow writes with a preconditioner (partial G(x) partial G(x))^T.
It is known that if the latter preconditioner is equal to a Hessian map nabla^2 R(w)^-1 where R is strictly convex, then the latter flow is a Riemannian gradient flow (RGF) with respect to this metric tensor nabla^2 R.

In this paper, the authors tackle the question of characterizing the gradient flow , i.e. when given a parametrization G, we can consider the assocciated 
RGF with mirror map R; and conversely, for what R does one have a corresponding parametrization G.

The main class at study are commutative parametrizations, that holds for instance when each coordinate of G depends on different subsets of coordinates (separable case). Th 4.4 is the first main result of the paper and states that if G is commutative, then there exists a mirror map R (depending on xinit and G) such that the dynamics of w is a mirror flow. The proof relies at some point on some sufficient condition (given in Lemma C.1, already highlighted in [42]) under which a vector field is the gradient of a convex function. Convergence of the flow is proved if G is a linear reparametrization (G(x)=xAx) in Corollary 4.10. To characterize implicit bias of gradient descent, the authors use Th 3.6 which characterizes implicit bias (ie properties of the solution) of a mirror flow.
Finally the authors study the reciprocal question, i.e. for a mirror map R, does there exist a corresponding commutative reparametrization G, and provide a positive answer in Theorem 5.3 that holds generally.

strengths_and_weaknesses: Strengths

The paper brings interesting contributions to the growing literature on implicit bias of optimization algorithms, an important problem in the machine learning literature nowadays. I think the characterization of implicit bias of gradient descent through the mirror map R in the reparametrization setting at study, explicitly when it is more explicit in Th 4.11 and Cor 4.12, is novel and interesting. 
The paper is quite well written and the results appear technically sound (I read the proofs in the main, but I did not read the proofs in detail in the appendix).

Weaknesses: I think that the paper lacks clarity in its current state. It would be better with more interpretation and discussion of the results, see questions below. Moreover, due to the limitations of the reparametrization model at study and the lack of empirical support, the impact of the paper may be limited. 
questions: - to what extent the models at study (ie commutative parametrizations) are restrictive. Could the authors clarify this point and the limitations of this hypothesis ? how large is the class of models considered?  is it limited to diagonal neural nets? are more complicated architectures ruled out because of the negative result of Remark 4.7?
- th 4.4: intuitively, why the mirror map nabla R should depend on xinit?   
- th 4.11: while the result is interesting, since it says that the solution is a minimizer of the convex regularizer R, this function R remains implicit/is not known if I understood well ? in corollary 12 it is explicit.
- l295: the proposed formula for nabla^2 R (with the inverse of G = F) look quite different from the one in Lemma 4.6 involving psi (hence gradient flows of G ), could the authors clarify the link between the mirror map in section 4 vs section 5? 



limitations: Limitations are too briefly evoked (e.g. in the conclusion) but they should be discussed more extensively in my opinion.
review_title: null

Meta-review: metareview: The paper characterizes how reparametrized/overparametrized models can be understood as a version of mirror descent on a different objective through a notion they call commuting parameterization. The reviews are all positive and agree that the paper improves our understanding of this phenomenon.
confidence: Certain
Decision: Accept