Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: SP (Stochastic Polyak step size) can be interpreted as a method specialized to interpolated models since it solves the interpolation equations. SP can be interpreted as a projection into a stochastic-constrained linearization of the objective function. The main idea of this paper is that it extends this constrained linearization to a quadratic approximation of the objective (SP2). They show a closed-form solution for this minimization of some objectives common in machine learning such as quadratic loss. In general, there may not be a solution for SP2 minimization, so they introduce SP2+ that contains two steps: 1- minimizing on a linearized objective and 2- minimizing on a quadratic approximation of the objective. They provide a convergence guarantee for SP2(+) for a quadratic loss in an interpolation setting. 

strength_and_weaknesses: Empirically their proposed methods shows outperform other existing optimization methods in the literature. 
Weakness: their theoretical analysis holds just for too limiting settings. 
clarity,_quality,_novelty_and_reproducibility: Novelty: The main novelty of this paper is extending the linearized constrained into quadratic constraints and proposing closed-form solutions for various losses. 
summary_of_the_review: Comments: 
1- The empirical results are based on the number of epochs used through training. However, the iteration costs for SP2 and SP2+ are greater than SP or SGD. Therefore the right criteria would be wall clock time. So I suggest to change all x-axis changes to the wall-clock time so a fair comparison is doable. 

2- In your theoretical result, specifically Prop 1 and 2, if we assume d > n, and H_i is non-zero only in the (i,i) element. This setting satisfies your assumptions for Prop1 and 2. For this setting, \rho would be 1 and your analysis won’t show a convergence. 

3- Since your SP2 method needs a Matrix-vector product, it would be useful to show that for a simple loss how some can implement it efficiently. 

4- It will be nice to first give the original formula of SP method before eq 4.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper consider the interpolation settings. It proposes to use a similar approach as the stochastic Polyak step size (solving the interpolation equations). However, instead of using the first-order approximation, this paper uses the local second-order information of the model. The authors then listed several approaches for this, namely SP2 (closed form solution applying for generalized linear models), SP2+ with approximating the solution to subproblem, and other versions with slack formulation.  
strength_and_weaknesses: The strengths of this paper come from the nice framework to approximate the second-order function. It also proposes various different ways to solve the quadratic problem, including discussions using a generalization of the interpolation property. 

There are potentially several limitations of this method. Firstly, it is not clear whether the quadratic subproblem can be solved efficiently in a big-data machine learning setting. In addition, most proposed methods only can approximate the solution of those problems, which poses some difficulty in analyzing these method theoretically and practically. Secondly, since the convergence theory is for quadratic functions, it is unclear if this method would have theoretical guarantee in most of the ML setting with interpolation (which is the motivation for the problem). Finally, the experiment and theoretical setting does not seem to match each other. 

Other comment: The detailed algorithms should be stated separately in a box to avoid any confusion for the readers. 
clarity,_quality,_novelty_and_reproducibility: The idea of using stochastic Polyak step size and second-order approximation is not novel, but the authors did combine them relatively well. 
summary_of_the_review: This paper has some good contributions, though the practicality of this method is in question. I would like to hear from the authors regarding the limitations of this papers.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper considers the problem of solving finitely many non-linear
equations, under the assumption that a solution exists. The key idea
is projecting the current iterate onto the hyper-surface defined by
the quadratic approximation of the current equation of choice. The
first proposed method (SP2-GLM) considers the case where the non-linear equation is the
composition of some loss with a linear function. The second method
(SP2+) further linearizes the quadratic approximation. Some
convergence theory is derived for the two methods (Section 4). Extensions to the
case where there is an "approximate" solution are considered (Section
5). And experiments are demonstrated on several problems (Section 6).
strength_and_weaknesses: 
# Strength
The paper enjoys the following strength:

- The paper considers an interesting problem of solving non-linear
equations, which is potentially important and relevant to some
readers of ICLR.

- The paper is written clearly, and the proposed method consists of a
  simple idea.

- The paper covers several aspects of the proposed methods, including
  convergence theory, experiments, and extensions to the case of
  *quadratic with slack*.

- Full proofs are in the appendix in a single file, which makes the
  the paper easy to navigate.

# Weakness
The weakness of the paper manifests itself from several aspects:

- The assumption of Proposition 1 is too strong, which makes it not very
  interesting. First, it is a bit weird that the global minimizer
  $w^*$ has already shown up in the definition of $f_i$ (21), which
  is quite artificial. Second, $f_i$ is already quadratic,
  and local quadratic approximation does not make too much sense.
  Third, $H_i$ is positive semidefinite, which means that the
  quadratic constraint $f_i(w)=0$ is equivalent to the linear
  constraint that $w$ should lie in the null space of $H_i$ (if $H_i$
  is rank-deficient). This makes the convergence analysis trivial, as
  it is reduced to the situation that we already know (e.g., from the
  analysis of the Kaczmarz method). Finally, the discussion on the case
  where $H_i$ is invertible is misleading: In this case $H_i$ is
  positive-definite, the equation $f_i(w)=0$ has a unique
  solution, and one does not need to do a projection as solving
  $f_i(w)=0$ directly would suffice.
- Proposition 2 is a bit mysterious. Since it follows directly from
  Gower et al. (2021), that should be mentioned explicitly right after
  Proposition 2. Besides this, SP2+ itself is also mysterious and not
  very well motivated: In (18), intuitively, what is the benefit of
  considering a linearization of a quadratic approximation, instead of
  a linearization of the original function? That question also applies
  to Section 5.

- The two propositions stand in contrast to the name SP2 and very
  much also the purpose of the paper: Under the given assumptions the
  paper is essentially analyzing first-order methods (in a trivial
  way, based on prior works). The paper would be significantly
  strengthen if there is some solid analysis that reveals superlinear
  or quadratic rates of the proposed idea, as is typical for
  second-order methods.

- Section 5 would be a powerful technical contribution of the paper
  if it were more well-motivated. For example, what is the benefit of
  having two different slack formulations (L1 and L2)? What is the
  reason of resorting (30) for solving the L1 slack problem? After
  all, they seem to perform very similarly in the experiments.


- There are several sub-optimal aspects in experimental evaluation.
  First of all, the comparison to Newton's method is unfair, as it is well known
  that standard Newton's method is not always globally convergent. A slightly
  more considerate option is to compare with the damped Newton's
  method (as described in Boyd's book), which is guaranteed to
  converge, at least in the (strongly) convex case. Second, the
  plots should not be *function values versus epochs*, but it should
  be *function values versus running time*; the reason is that the
  methods under consideration have different time complexities at each
  iteration. Third, by just reading the paper, the reader has no idea
  how large the dataset in each experiment is. Since Sections 1
  and 2 make it an important point to design incremental methods that
  can work with mini-batches, it is important to run experiments on
  large datasets for which traditional offline methods run out of
  memory (e.g., Newton's method), otherwise, there is no reason to believe that online methods
  could perform better than offline methods. E.g., online methods
  would have very large variances and could easily fail in the case
  where some equation is far from being satisfied at the global minimizer.
clarity,_quality,_novelty_and_reproducibility: The clarity and novelty are good. 

There are some drawbacks in terms of the quality, as mentioned in "Weakness".

summary_of_the_review: I found the proposed method simple (a strength in my point of view), and some technical contributions are made (say in Section 3.1 and Section 5). But I also found Section 4 regarding convergence analysis and the experimental section unsatisfactory, as mentioned above in "Weakness". 

At this moment, I made a borderline score, "marginally below the acceptance threshold".

Note that I am not an expert in this line of research. I will re-evaluate the paper based on the comments from other reviewers and the rebuttal.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes an interpolation type update strategy that resembles the famous stochastic Polyak step while using second-order information. Several approaches were designed to implement this idea under different situations, including SP2, SP2+, and other versions with slack formulations.

The theoretical analysis is relatively weak since the proof is only provided for quadratic objective functions. However, this is acceptable since many popular step rules like BB and CG in practice works well, but their convergence is only available for quadratic functions. In terms of the practical performance. When SP2 step works, its performance is quite impressive in the experiments. 

However, we should also notice that the SP2 step may not exist in many problems. The authors also propose the SP2+ step as the surrogate of SP2 when it doesn't exist. However, from the experiments, the SP2+ does not seem to have clear advantage compared to the existing SP step. Therefore, I think this paper is only marginally above the accept threshold.
justification_for_why_not_higher_score: The surrogate methods like SP2+ does not have significant advantage against SP step. This is a weakness of the result for problems where an SP2 step does not exist.
justification_for_why_not_lower_score: When SP2 step exist, the performance is impressive, and the analysis is OK.
Decision: Accept: poster