Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This work studies the question to what extend a reparametrization of an optimization problem, i.e. representing the original parameters w to optimize for as a function of some other parameters theta, can accelerate the convergences of the gradient flow / gradient descent for nonconvex optimization problems. It studies the dynamics of the flow via eigenvectors of a matrix M formed as the expectation over the outer product of the gradient of the loss with itself to reveal 'slow' and 'fast' modes of the evolution. It subsequently derives sufficient conditions for the reparametrization (which is chosen to be linear but time varying) to balance the decay on all modes. After discussing an efficient approximation of the theoretically derived scheme, numerical results demonstrate the effectiveness of the proposed reparametrization in two exemplary applications.  
main_review: In terms of its strength, this paper contains interesting thoughts about the intriguing idea that a temporally varying linear reparametrization of the unknown can accelerate the gradient flow based optimization. The general topic, the combination of theoretical analysis and numerical experiments, and the bridge between the two by using efficient numerical approximations of what the theory demands, are strength of this paper.  And although the numerical experiments are certainly not exhaustive, there is some proof of concept of the benefit in the particular applications considered here. 

Unfortunately, the paper also has some clear drawbacks. In particular, I found the paper difficult to follow and the main idea from an optimization perspective appears to be unnecessarily hidden in a framework on "neural" reparametrizations. Unless I misunderstood the main idea significantly, the "neural reparametrization" illustrated by a neural network in Fig. 1(b), later turns out to be a linear parametrization only, i.e., considering the gradient flow for theta in $w(t) = \kappa(t) \theta(t)$ instead of in the original variable w.  Before considering this to be a graph neural network, I would have been interested in how this idea relates to other classical optimization methods: Has the idea of temporally changing but linear reparametrization not been considered in the optimization literature before? As kappa turns out to be the square root of the inverse of the Hessian, is there a relation to Newton or quasi-Newton methods? For me, the paper would have been easier to follow from this more classical optimization perspective. In particular, the considered gradient flow resulting from the linear reparametrization seems to be $\partial_t \theta(t) = \kappa(t)^T \nabla L (\kappa(t) \theta(t))$, and should be stated explicitly. If now the change in $\kappa$ is negligible slow in comparison to the change in $\theta$, and if $\kappa$ represents the (scaled) square root of the inverse Hessian, isn't that the flow arising from Newton's method? I would much rather prefer a clear motivation and presentation of the paper from such a classical perspective before delving into graph neural networks. 


Some minor aspects
- In equation (2) there is an $\epsilon_{i,j}$, but I think the way eq. (1) is written it is unclear what 'off-diagonal' elements in $\epsilon$ mean. (Of course the delta ensures there are no off-diagonals, but then I would avoid the notation). 
- "Equation 1 is also an ordinary differential equation"; I would call it a partial differential equation.
- I am sometimes not sure which quantities are random variables and which ones are not. In eq. (4), for instance, random variables seem to have been dragged out of the expectation, which I do not understand. 
- An example of why the paper was a little difficult for me to follow are sentences like "When running GD, the maximum change in w is bounded to ensure numerical stability." This sounds like a modification of GD (like gradient clipping), but it is actually meant as a condition to limit the step size you are using. Thus, isn't the reasoning flipped, i.e., in order to ensure numerical stability, we have to bound ...?
- In the entire analysis, it could be made clearer that M is time dependent. The first sentence of section 2.3 is the first time where it is really prominent. The discretization for time dependent matrices  might of course make the behavior of the actual algorithm differ from the (continuous) gradient flow. 
- Before eq. (10) it is exemplified that $w = \sigma(A\theta + b)$ would be a valid choice. $A$, $b$, and $\sigma$ are, however, not defined and if $\sigma$ refers to a (nonlinear) activation function, I do not see how this is true.
- page 2, "abounded"
- page 6, "adaptove learning rates"
- If the numerical experiments are carried out with Adam, shouldn't the theory also consider effects like (adaptively scaled) momentum?
- In Fig. 2, why does GCN-1 seemingly start with a much lower loss function value than the other methods? Does it have a sharp drop at the beginning?
- "GCN with $A^2$ as the propagation rule achieves the highest speedup". What is $A^2$? Please define. 
- "where difficult to separate the slow and fast modes" >> "where it is difficult ..."
- The numerical results are, to my mind, not a strong indication of the proposed approach being a universal way to accelerate gradient-based methods. In particular, I am wondering how specific the acceleration results are to the applications? Also, what amount of hyperparameter tuning is required for the proposed approach to work well?

summary_of_the_review: Although I like the general idea and do believe that reparametrization can balance out different convergence speeds of different modes to some extend, I found the presentation to be a little confusing. The appoach seems to reduce to a linear reparametrization, which seems to relate it to other (more classical) approaches. Along with the list of minor aspects that make the paper a little difficult to follow, I need some clarification on this aspect.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: This paper proposes a reparameterization of non-linear non-convex optimization problems. This reparameterization amounts to a linear map (i.e., "optimization params = linear operation of a different set of parameters). These linear maps are interpreted as a graph convolution network. The experimental results are validated on "Kuramoto models" and "persistent homology models".
main_review: Strengths:
* The idea of reparameterization is nice.

Weaknesses:

* The experimental evaluation consists of two problems that are not of interest to the ICLR community. I have certainly never seen either of them used in a ML paper. I have no idea how they relate to actual optimization problems I care about (i.e., training deep neural networks).
* The experimental work doesn't look thorough -- where are the learning rate sweeps, comparisons to other optimizers, etc etc?
* The paper spends a substantial of space (pg 2-4) deriving well known results (under assumptions that amount to strong convexity lambda_max to lambda_min ratio controls covergence). I strongly suggest that the authors use the results and language of optimization, rather than going from first principles for no good reason.
* The final reparameterization is not very interesting -- although much ado is made about "using a neural network parameterization", it's just a linear map at the end of the day. 
* Since the reparameterization is linear, this makes the overall idea very similar to a preconditioner. This should be touched on, and compared to e.g., KFAC, shampoo, the many other linear preconditioners that people use. As with the optimization comment above, I think this work needs to be grounded more in the literature.
* GCNs are tangentially relevant, but don't seem to be used in any really meaningful way.

Technical comment: right after eqn 15, it says that H is positive semidefinite. Where does thos come from? Isn't the base problem meant to be non-convex, in which case by definition H should have some negative eigenvalues at some point?
summary_of_the_review: This paper is clearly unready for publication. The main idea -- using a structured linear reparameterization -- is under-developed, and the experimental results are on problems that the ICLR audience don't really care about.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors derive a neural reparameterization of non-convex optimization problems in order to accelerate their convergence. They do this by deriving how the slowest components of the optimization variables can have their convergence rate improved by preconditioning with a NTK-based matrix. They make connections between this approach and Group Convolutional Networks. Experimentally, they show this approach improves upon baseline gradient-based optimization on a two datasets. 
main_review: **Main comments**

-Overall, I think the paper is quite novel and the experiments fairly convincing.

-I really enjoy how much the authors walk through the individual steps of the gradient math which derives their neural reparamaterization in 2.1 and 2.2. It is easy to follow and clear.

-However, one drawback of this approach is that it appears that it seems to only help the early stages of optimization, as this is how it is used in the experiments. I think the authors should take more care to make this point more clear. In particular, what prevents one from using this hessian approximation for $\bar{M}$ as in Section 2.3 in early stages of training when using Adam? It would be nice to see ana ablation of the different components of their method, to understand exactly what component of the approach is contributing to the improved performance.

-How does this approach compare to gradient-based optimization in terms of memory consumption? How would this scale to large-scale datasets with larger parameter spaces, e.g. deep network training? 

**Minor Points**

-The authors seem to pose the title and introduction to refer to any non-convex optimization problem, but in some parts of the paper they seem only focused on neural network optimization (e.g. Fig 1). It would be good to smooth out these inconsistencies. 

-The abstract on OpenReview and the abstract in the article do not match. 

-In the experiments, why is the term "linear" used to refer to the gradient-based baselines? I am not sure this is the best term to use and was confusing to me upon my first read. 
summary_of_the_review: Overall, I lean slightly towards acceptance. This is due to the clarity and novelty of the paper, as well as encouraging experimental results. However, I think some more experimental verification is needed for ablating the different components of the proposed approach and for demonstrating its applicability to a broader range of problems.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work proposed a neural reparametrization scheme to accelerate a large class of nonconvex nonlinear optimization problems. The proposed method is grounded on analysis that the dynamics of gradient ﬂow are related to the condition number of the system. More specifically, by reparametrizing the optimization problem with a graph convolutional network (GNN), the proposed method can modify the condition number and obtain convergence speed up, the acceleration is demonstrated on optimizing synchronization problems and persistent homology of point-clouds.
main_review: The paper introduced a new network reparametrizing method for accelerating optimization for nonlinear problems. Overall, the reviewer finds the paper is a bit hard to follow, and the presentation of the paper can be significantly improved. The experiments are interesting but the comparison is not quite comprehensive. 
First, the reviewer is not fully convinced by the benefits of reparametrizaiotn. The reparameterization using a neural network can improve convergence speed, but on the other hand, the memory cost could be higher.  
Second, it is a bit unclear to the reviewer why in Section 2.2, the authors considered the NTK. The weights for NTK require an ultrawide network and the weights barely change. It is a bit abrupt without much explanation of the motivations behind it.
Third, the speed up in Figure 2 does not seem impressive. The authors only compared with a very baseline optimizer. More comprehensive comparisons are needed to draw the conclusion. 

summary_of_the_review: Overall, the reviewer finds the paper is a bit hard to follow, and the presentation of the paper can be significantly improved. The experiments are interesting but the comparison is not quite comprehensive.
review_title: null

Meta-review: This paper proposes speeding up certain optimization problems common in physics by reparameterizing their parameters as the output of a graph neural network. The reviewers appreciate the idea, but are not convinced enough to recommend the paper for acceptance. They point out the following weaknesses:
* The method amounts to linear preconditioning, and hence it's reasonable to expect a fairly complete comparison to the many linear preconditioning approaches that have been proposed previousl. The reviewers are not satisfied with the currently provided comparison. 
* The main idea is not presented clearly enough. In particular, it's not obvious the proposed method is best described as neural reparameterization, since it seems to amount to linear preconditioning.
* The experiments are not persuasive enough: The presented problems may not be relevant to all of the target audience of ICLR, and the experimental evaluation does not seem sufficiently exhaustive.

The suggested areas of improvement provided by the reviewers seem reasonable to me: I therefore recommend not accepting the paper in its current form. To make the paper more accessible and appealing, the authors may consider rewriting the paper to more closely match the perspective taken by the reviewers, and to provide a more thorough comparison to the previous approaches and the existing literature.
Decision: Reject