This paper explores an interesting question: if we are allowed certain control over the input to a pre-trained language model, can we get it to return an arbitrary sentence? The control given is a vector z associated with the sentence, which is added as a bias to the hidden state at each timestep. In forward estimation, gradient descent is used to find the optimal z to "bias" the decoder towards a given sentence. In backward estimation, a given z is decoded to find the MAP sentence it encodes (which is intractable in general, so the authors use beam search). The authors analyze the "effective dimensionality" of a sentence space given a recoverability threshold tau; that is, what's the smallest dimension such that at most a tau-fraction of sentence fail to be encoded?

The paper proposes a simple algorithm for L_p regression problems and justifies its efficiency both theoretically and empirically. Major concerns: 1) Related work: The comparison with related works is not sufficient. In Section, it only compares with the polynomial dependence. What are the advantages of the proposed one? Furthermore, the lack of sufficient baselines (at least Bubeck et al. [BCLL19] or Adil et al. [AKPS19]) in the numerical experiments weakens the superior of the proposed algorithm.

This paper proposes a modified IRLS algorithm and presents empirical experiments and theoretical analysis. The reviewers viewed the contribution as a combination of existing methods, and the combination is novel. Most reviewers thought the paper was well-written. The ability of the authors to compare to existing methods is limited because of the complexity of other methods and lack of public implementations. The reviewers' scores place this paper above the bar for acceptance.

Originality: the paper lacks a sound and novel contribution. Theoretically, there is only one minor result as stated above. Technically, there is not a systematical experimental study on real deep networks. The main contribution is on discussing two different formulations of the Fisher matrix. The main trick on making these two formulations different (despite that the authors took a sophisticated approach going though GGN) is that the so called empirical Fisher relies on y_n (target of neural network output), and if one consider y_n to be randomly distributed with fixed variance based on the neural network output, the two formulations are equivalent, otherwise there is a scale parameter in eq.(3) which is shrinking making the two formulations different because of the shrinking and damping.

All reviewers were positive about the paper. The paper corrects several common incorrect assertions and misleading derivations in the natural gradient algorithms literature. The exposition is remarkably clear, with a potential to serve as a reference paper on the topic. The paper is clearly of broad interest to the machine learning community. We recommend to take the reviewers' comments and suggestions into account while preparing the camera ready final version of the paper.

Summary and Contributions: This paper introduces a new class of algorithms for local graph clustering, based on Lp objectives (for p 2) rather than the standard L2 (used in reference works like Anderson-Chang-Lang), or L_infinity (which corresponds to minimum cut). The authors make a clear point that the p 2 regime corresponds to the primal objective which optimizes in the space of flows, whose dual problem corresponds to optimizing an Lq norm (1 q 2) in the space of cuts. For the purpose of this paper, they stick to the cut problem, since it is more naturally connected to the algorithm described here. Essentially, the presented algorithm is a generalization of ACL for Lq norms. It performs a sequence of steps, in each step, it picks a node with excess residual and performs "push" operation.

The authors propose a new algorithm for local graph clustering in general Lp norms. The paper introduces new theoretical results and some interesting new tool as the Cheeger inequality specialized to Lp/Lq. The main limitation of the paper is in the additional assumption made in the paper that are not well-motivated.

In particular, the additional experiment on optimizing the dimensionality reduced functions for the real-world example looks quite persuasive, and the explanation about adding a dummy variable to address odd dimensional functions is also super valid. I also appreciate the authors for providing the detailed content of the modified paragraphs that they will include for the mathematical examples. The only small remaining issue is that for my point 6, the authors didn't seem to understand that the issue with Section 4.1 is that some of the sample points in the validation set may (almost) coincide with those in the training set, and the authors should make sure that they have excluded points that are sufficiently closed to the training set ones when generating the validation set, and clearly state this in the main text. That being said, I have decided to improve my score to 7 to acknowledge the sufficient improvement shown in the rebuttal. This paper considers the problem of dimensionality reduction for high dimensional function approximation with small data.

The paper proposes an interesting dimensionality reduction method for function approximation by generalizing linear level set learning methods to non linear level sets using the RevNet model structure and by introducing a loss function designed to give preference to functions that are sensitive only to few non linear coordinates. The paper is well-written and easy to understand. The methodology is clearly described and the experimental results are convincing.

Additional Feedback: This paper presents that different time intervals at which they deploy models trained with stochastic gradient descent in performative prediction leads to qualitatively different algorithms. Moreover, a series of experimental results confirm the result of theoretical analysis of greedy and lazy deploy. Although the paper is theoretically sound, there are still some questions need to be discussed in this paper: 1. This paper uses stochastic gradient methods to solve performative prediction, which is similar to the previous work [R1]. In addition, the proof in this paper seems an extension of the prior work [R1] on performative prediction. The authors should give the key contribution of this paper and discuss the difference between them.