Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes moving along the level set during an optimization problem. Doing so may lead to faster gradient iterations, and is proven and shown empirically. A few examples of symmetries are discussed (modifications to the parameters that leave the output of the network invariant). For a nonlinear MLP, only an input-dependent symmetry is discussed. Runtime analysis is also performed.
strengths_and_weaknesses: Pros:
  - Paper is well-written.
  - Problem setting (optimization of MLPs) is relevant.
  - Proposed solution is simple to understand.

Cons:
  - Runtime complexity is not fully reconciled / transparent.
  - Some details of the symmetry teleportation is not completely clear to me.
  - In practice, symmetries must be known for a particular optimization problem, and even when known, in many cases I imagine optimizing within this group can be very difficult. 
questions:  * Does the theory behind convergence take into account the extra steps needed to solve for the symmetry teleportation problem? I'm wondering if the symmetry teleportation problem itself has a different convergence rate, and the real convergence rate would be worse?

 * Practically, how would Figure a look if it is plotted against number of gradient computations or even wall clock time? The runtime analysis per teleportation is great to have, but since this cost of teleportation is amortized (done only every so GD iterations), it isn't completely clear to me how this actually affects practice.

 * Since only a first order approximation is used for exp(x), the output of the neural network isn't invariant anymore right? Moreover, if you take more teleportation steps, this should actually diverge or at least cause the parameters to be arbitrarily far away from the level set. What's the intuition behind this not occurring in practice; is it due to the fixed number of steps for optimizing the teleportation?

Minor:

 * How did you settle on 10 steps for teleportation? How important is it to tune this number?

 * Given your expertise, would you use symmetry teleportation as a default when you run optimization problems with known symmetries? Why or why not.

 * Small suggestion for Figure 2 b and f: draw the symmetry teleportation trajectory. Right now some of the blue lines are gradient descent while others are teleportation + GD which makes it difficult to parse the details.

 * Type (line 62): dt -> dw
limitations: .
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: Authors consider the class of optimization problems having group of symmetry G, which is simple enough to optimize norm of the gradient over its orbits, and propose technique of "teleportation" from current point to the more suitable one on the same orbit before every gradient step. They present the examples of problems having symmetries, including simplest NN, and numerically show the competitiveness of proposed technique in these simple cases and more complicated test problems (MNIST). New technique is provided with sketchy theoretical justification of acceleration effect.
strengths_and_weaknesses: The idea of using group theory in optimization for solving problems with known symmetries is not new (I've found review with DOI:10.1007/978-1-4614-1927-3_9 almost immediately, but it is hardly the earliest), but this topic was not well discovered for continuous convex case. The first strength of the paper is that it attracts attention to this blank space. The reason why it is blank is the unnaturalness of group of symmetry oracle — symmetries that cannot be used to simplify the model itself are often too complicated to be used in auxiliary problems as well. This is related with first weakness — paper does not consider question of automatic symmetry detection and does not say anything about practical NN architectures, but this is very important to show that this technique at least can be applied to any practical task. The second weakness is that sketch of theoretical analysis is too sketchy, there are no explicit convergence rate estimations in the paper, so the effect of teleportation cannot be appreciated.
questions: Regarding second weakness — it would be good to find at least one case (class of functions + class of symmetries) when GD with teleportation is competitive with GD/Conjugate gradients method/Newton method with explicitly expressed effect of teleportation in final convergence rate. It seems to be possible.
limitations: Limitations seem to be obvious for the readers of the paper, and authors do not pretend to propose the panacea.
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: Using teleportation of parameters to a new point at the same loss value but with a larger gradient norm, the authors offer a new approach for accelerating the convergence of gradient-based optimization methods. This new scheme can accelerate the convergence of gradient-based optimization methods. An intuitive understanding of the connection between such a scheme and second-order methods is demonstrated by the authors. The major application discussed in the paper are deep neural networks and two rather simple classical functions. An empirical evaluation of the effectiveness of the authors' approach to solving these problems was provided, along with a comparison to gradient descent and AdaGrad.
strengths_and_weaknesses: The symmetry teleportation technique is the main idea and contribution of the paper. It is based on the fact that after teleportation, the loss will be the same, but the landscape can be much better, and hence we will get faster convergence to the local minima. I liked the presented method's relations with second-order methods both theoretically and practically on Booth function. The idea is interesting and original. Some proofs are presented, and they seem to be correct. The authors show some experiments for small feed-forward networks with leak-relu activations on MNIST. The paper is well-structured and well-written. I have some concerns about the correctness and effectiveness of the teleportation technique presented in the paper. I will address them in the questions section.  
questions: 1) There are two main assumptions for unconstrained optimization problems: $L$-smoothness (Lipschitz-continuous gradient) and $M$-Lipschitz-continuous function. Both are defined globally but we are actually using them locally on the set around the starting point $x_0$ and the solution $x_{\ast}$. The reason why we can do it is the monotonicity and compactness of gradient-based methods. With that local approach, we can make our function class much broader. For example, x4 is not $L$-smooth or $M$-Lipschitz, but we can constrain $L$ locally by some constant dependent on $x_0$, and the gradient method will converge for such a $L$. Note that the presented Rosenbrock function is not $L$-smooth or $M$-Lipschitz globally. The same problem arises for neural networks. Additionally, level sets can be unbounded. This leads us to the question of the existence of such teleportation because the maximization problem will also be unbounded. For example, one of the simplest examples of neural networks is a linear 2-layer network without activations for one data-point $(1,1)$ with MSE-loss.  $\min (x \cdot y - 1)^2$. All points $x = 1/y$ are local minima. Let us start from parameters $a = (2,1) $. The gradient norm at $b = (1000, 0.002)$ is bigger than the gradient norm of $a$. So, we'll teleport to $b$, but why is this location superior? Furthermore, because of smoothness, the learning rate at $b$ should be less than $1/(1000^2+0.002^2)<10^{-6}$, whereas the learning rate at $a$ is around $1/5$. So, my main concern is that this teleportation technique can actually make convergence worse and much slower. Because of that, the method should be used much more carefully and with clear limitations to its applicability. 

2) It is unclear to me, how complex the process of teleportation is in general. 

3) Some of the notations and objects were unclear to me. So, I would recommend adding a notation section to the appendix to clarify the introduced notation. For example, what does $g \cdot w$ mean? Why are you using $dL/dt$ and not $dL/dw$? Some definitions of used groups or links to the literature where the reader can be educated about them will also be helpful. 

4) In experiments,
a) Figure 4: Why are SGD and AdaGrad starting from different points?
b) How do you tune learning rates for gradient descent? Do 
c) Figure 5: It seems that the fact that teleportation has bad validation accuracy proves my claim from question 1.
d) Figure 3 and 8: It seems that the gradients of the teleported version of AdaGrad are smaller than regular AdaGrad. Despite this, the teleported loss is smaller than regular. How does it correspond with the dependence "bigger gradient -> faster convergence"? 

5) The authors showed intuition about two-dimensional quadratic problems (ellipsoid). It will be interesting to understand what will happen with d-dimensional quadratic problems.

#######################
During the rebuttal, the authors addressed most of my concerns and questions. They improved the paper. Special thanks for the new Section D.1 about quadratic problems. I increased my overall score to 6.
limitations: The authors adequately addressed the limitations.
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: Existing gradient-based optimization methods update the parameters locally, in a direction that minimizes the loss function. The author proposes a different optimization method to improve the convergence speed by teleportation which transforms parameters while making the loss invariant. The author gives theoretical proof and experimentally shows that teleportation improves the convergence speed of GD and AdaGrad for several optimization problems.
strengths_and_weaknesses: Strengths:
1. The teleportation improves the convergence speed of subsequent steps by transforming parameters to another point with steeper gradients.
2. The symmetry teleportation takes advantage of higher-order landscape geometry but uses only gradient information.

Weaknesses
1. It does not guarantee that the transformed parameters lead to a faster convergence rate throughout the entire training.
2. It takes time to find g.
3. When the number of weights and data is large, it may increase the complexity.

questions: 1. The meaning of ‘Acceleration’ should be stated clearly in this paper.
2. Does the initialization have an impact on the convergence and the final result through teleportation? How and why?
3. The proliferation of saddle points can slow down convergence. Can Symmetry Teleportation effectively escape saddle points?
4. Is there any general guideline for designing symmetry groups?
5. In some scenarios, GD with a learning rate schedule can also achieve a similar loss curve in Fig. 2(c). What advantages do you think GD with teleport has over GD with a learning rate schedule?
6. As far as I can see, GD in deterministic settings is slightly different from GD in stochastic settings. How do you guarantee that SGD+teleport can accelerate convergence over SGD?
7. There is a little abuse of notations. The learning rate, $\eta$, and the learning rate matrix, $\eta$. The steps, T, and the transformation matrix, T.

Typos

Line 73 leads -> lead

Line 88 flow -> flows

Line 130 are -> is

Line 227 reduces -> reduce

Line 272 has -> have

Line 285 has -> have

Line 315 minima -> minimum

etc.
limitations: Yes
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 work proposes an accelerated gradient-based optimization algorithm, symmetry teleportation, which exploits symmetries in the loss landscape. It improves current neural teleportation methods by searching for teleportation destinies that lead to the largest improvement in the magnitude of gradient. This work also provides empirical evidence showing the improved convergence speed of gradient descent and AdaGrad in different optimization problems.
strengths_and_weaknesses: Strength: 
1. This work proposes a novel optimization algorithm that applies symmetric teleportation to accelerate the convergence of gradient descent.
2. The problem is well-motivated, and the work also provides an intuitive illustration of the ideas behind the proposed algorithm.

Weakness:
1. It would be better if the work could explain more about how to exploit symmetries for different loss functions.
questions: How to exploit symmetries for different loss functions？
limitations: There are no potential negative societal impacts of the work.
review_title: null

Meta-review: metareview: This paper proposes a novel, symmetry teleportation approach to optimize the parameters of ML models.
The proposed approach allows iterates to move along the loss level set and improves the convergence speed. The teleportations also exploit the symmetries that are present in the optimization problem. 
The paper also includes very encouraging numerical experiments.
I believe that the paper brings more insides and techniques that have been mostly overlooked in the community when training ML problems.
confidence: Certain
Decision: Accept