Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This work further investigates the use of stochastic Polyak stepsizes (SPS) first proposed in Loizou et al. (2021). The prior work had several limitations, essentially requiring that the global optimum is 0 (known) and that all minibatch samples are also minimized by the global minimizer. This work lifts this restriction and extends the analyses to the case where only a lower bound of the global optimum is known and when interpolation does not happen. The use of Polyak-type stepsizes in stochastic optimization is a relatively new direction, so many basic foundational questions about the setup need to be addressed. The discussion of section 4 provides insight into the bias in the SPS dynamics via a simple counter-example, and this nicely and clearly illustrates the difference between the SPS dynamics and that of the usual SGD dynamics. The newly proposed DecSPS is tested with some brief convex experiments, but no experiments on deep learning are done.
strengths_and_weaknesses: This work has some nice contributions, as it addresses some of the clear limitations of the prior SPS by Loizou et al. (2021). The line of research on SPS is new and, in my view, quite promising, so this work provides some clear value to the field

Overall, however, I feel that this work is a necessary, natural, but an incremental follow-up to Loizou et al. (2021). The analysis is not highly distinct or novel compared to the prior work. While there are certainly some new and interesting insights, the resultant rate is not really strong; under the interpolation assumptions, Loizou et al. (2021) established nice fast rates, but by lifting such assumptions, it seems that the rates are no longer surprising or impressive compared to the SGD rates. I found the results interesting, and I think this paper will serve as a good step forward in the SPS line of work, but I am not sure if these results are strong enough to be published in NeurIPS.
questions: In what way are the rates for DecSPS stronger compared to the prior rates on SGD?
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: This paper presents a method called DecSPS, which is based on a modification of stochastic Polyak stepsize (SPS). The proposed DecSPS method provides an exact convergence to the optimum value and is not dependent on prior knowledge of problem parameters. As a result, DecSPS achieves an exact solution without any restrictive assumptions such as bounded gradients and is the first stochastic adaptive optimization method. 
strengths_and_weaknesses: ## STRENGTHS

- The modification performed on top SPS is minor and can be easily implemented. 
- The paper is well written, structure is easy to follow.

## WEAKNESSES
- In figure 2, the example consists of 2 variables. It might be a good starting point but it is essential to have a model which can be adapted to larger scale experiments. Now we can run the experiments in a cloud system,..
- Minor typo :
... is bigger that the one for SPS_{\max}...
... is bigger **than** the one for SPS_{\max}...
- In Figure 3. sensitivity analysis could be performed for more seeds, 3 might be too less, it would be nice to see an error bar.
- The overall contribution is not too effective.


questions: - How about the time complexity? Does it take more time than the existing algorithm?
- Should we directly start using SPS, or present the algorithm DecSPS instead of other methods like SGD with diminishing step sizes?


limitations: The limitations are briefly discussed within the paper, both in Introduction and conclusion. There is no negative societal impact of work.
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: This paper presents a novel variant of Stochastic Polyak Stepsizes (SPS) providing adaptation when the usual interpolation assumption does not hold, as soon as a lower bound of the loss is known.

The authors explain first that traditional SPS methods 
- (1) require the knowledge of the optimal loss on any batch which is often not the case and 
- (2) only converge theoretically to a neighborhood of the solution 

Authors provide a practical fix which is to replace the optimal loss on any batch by a lower bound of the loss (often 0 as many losses are non-negative) and call this algorithm SPS_max^l as it is a variant of SPS_max proposed in [Loizou et al, 2021]. Moreover, to enforce convergence to the solution, they make the upper bound of the adaptive step size decrease at each iteration in O(1/sqrt(k)) and provide convergence guarantees in O(1/sqrt(K)) of this new algorithm call DecSPS:
- for convex and smooth losses with a lower bound and bounded iterates
- for strongly convex and smooth losses with a lower bound (thus removing the bounded iterate assumption)
Finally, they extend their method to the non-smooth setting by enforcing a lower bound on their SPS version leading to DecSPS-NS and prove also O(1/sqrt(K)) convergence for
- convex non-smooth losses with a lower bound, bounded iterates and bounded subgradients  

Finally, authors run experiments on regularized logistic regression on 3 datasets
- one small synthetic
- two small real datasets A1A and Breast Cancer
 for which interpolation is not met. They compare the performance of DecSPS with AdaGrad-Norm and SGD with decreasing 

They also give elements indicating that their method is not too sensible to \gamma_b : the upper bound of DecSPS and that the decrease of the step size thus computed is faster than O(1/sqrt(k)) which shows real curvature adaptation.

~~~~
Score updated to 8 to support the paper after the answer of the authors to the question "What would be the downsides of using DecSPS or SPS instead of SGD?" (by reviewer 98CJ).
strengths_and_weaknesses: Strengths: 
- Problem and interest of the paper well posed
- Good review of existing methods (in the appendix for more details) in the interpolation case
- Solid theoretical guarantees (I went though all the proofs and everything looks correct)
- The paper is particularly well written, good intuition is given in the proofs which are easy to follow and makes the intentions clear to the reader


Weaknesses:
- The experimental section is very light. I know it's a common (and sometimes easy criticism) but I was a bit disappointed by the experiments which are focusing on regularized logistic regression on 3 small datasets. See experiments on CIFAR-10 or CIFAR-100 of [1], [2] and [3]
- the regularization in the experiments is way too large in my opinion. Makes the problems solved way too simple... 
- A paper proposing a new SPS methods without comparing it *numerically* to previous variants (SPS_max [1], Ali-G [2], SPSL1 from [1] and maybe other) is a bit problematic. I would have expected experiments on a "gradient" of experiments from non interpolated to interpolated like done in the motivational plot (but on a larger problem) by playing on the regularization.
- It looks like the price to pay for "adaptivity" is to tune 2 parameters (c_0 and \gamma_b) or 3 (additional \gamma_l) in the non-smooth case. The authors try to show numerically that numerical results are not too sensitive to these values but as in previous points, Imo experiments are not exhaustive enough to conclude.

[1] Loizou et al, Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2021)
[2] Berrada et al, Training Neural Networks for and by Interpolation (2020)
[3] Gower et al, Cutting Some Slack for SGD with Adaptive Polyak Stepsizes (2022)
questions: The paper is very clear, reasoning is easy to follow and going though the proofs was a pleasure.

Let me start with typos and nitpicking:
- A1) Only cited equations should be numbered. Useful cited equations are flooded in all the numbered equations (makes it harder to navigate in the proofs)
- A2) line 68 : "Dependency on f_{S_k}^*" star is missing
- A3) lines 102-105 : precise "in section 4"
- A4) line 167 & 172 : strange too read "$f_i$s"
- A5) line 171 : "linear rate" right ?
- A6) line 229: gamma is decreasing not increasing (this typo appears several times eg in E.1)
- A7) line 232: "appendix E.1" to simplify the reading
- A8) line 240: Strange way of calling both terms in (4) : both are deterministic. Better to say "distance-to-the-solution term"  and a "noise" term
- A9) line 243 : strange "distance initialization-solution" -> instead initialization-solution distance ?
- A10) line 254 : "regularizer is added" and then interpolation is thus lost, right ? 
- A11) line 273 : better to stick with notations with c_k and c_{k-1}. There is no point changing this only here
- A12) Footnote 3 page 7 : miscitation. [31] should be cited here. No RUIG inequality in [30]
- A13) In Lemma E.1, I do not think $a \leq 1$ is required. If it were, then it would imply that one would need to set $\gamma_b$ such that $\mu_{\min} \gamma_b \leq 1$ in (114)
- A14) Eq 107 Minus sign missing and I would put a $\leq$ at the RHS 
- A15) Same typo : step sizes are decreasing not increasing
- A16) line 762 : \alpha_k are non-negative
- A17) eq (126) I think a constant 2 is lost on the left-hand side. It would give a sharper result, nothing important asymptotically
- A18) line 783 : J*E*nsen not Jansen
  

More major questions :
- B1) I am not sure to be aware of all results in adaptive and SPS methods so I wonder what are the known classical results in the domain. A small table like in A.1 would have helped summarizing assumptions and known results for methods cited in the second paragraph of 1.1. I hope the other reviewers will have a clear opinion whether this convergence result without bounded iterates nor gradients nor using the smoothness constant nor the strong convexity value is novel or not. If not, it would worth citing relevant works.
- B2) line 325 : Could you precise why you say that \gamma_b = 10 is "theoretically inspired" ? I find it a bit incorrect.
- B3) line 334-335 : Could you provide a reference or a quick explanation why the local gradient Lipshchitz constant increases near the solution ?
- B4) As pointed out in weaknesses, the regularization parameters used are way too large. The problems become very simple too solve and as we are talking about optimization methods for Machine Learning than we should keep in mind that our goal is to have good generalization of our model and I doubt that this is the case here. I would like to see the results for \lambda = 1e-4 and 1e-6.
- B5) Lack of consistency in the setting of hyperparameters depending on the methods: DecSPS parameters are set on the real datasets A1A and Breast whereas the b_0 for Adagrad-norm is set on the synthtetic data set... Why ?

limitations: We would definitely need to see how pratical this new methods are in practice on large models or at least on difficult logistic regression problems (easy to find real-sim or rcv1.binary dataset on LIBSVM Data: Classification (Binary Class) website)

I already mentioned this in weaknesses but the DecSPS method comes with 2 or 3 hyper-parameters to tune which I think is not in fact taking us away from "adaptivity".

Not really a limitation but potential extension: as the authors point out in their conclusion:
- they still unable to prove O (1/K) convergence for strongly convex objective
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 proposes DecSPS, which aims at improving the convergence of SPS in two aspects: (1) removing the optimal minibatch loss in the step sizes by replacing it with a lower bound, and (2) proving that DecSPS converges to the exact minimizer in the strongly convex setting by showing that the iterates are bounded in the strongly convex setting. 
strengths_and_weaknesses: 
Strengths:

1. The overall writing is clear and easily understandable, and the proof is also well-organized.
2. The contributions of this work are also clearly stated.

Major concerns:

1. Overall, the theoretical contributions are not very significant. The proof of the almost sure boundedness of iterates (Proposition 5.4) is novel, which helps establish that DecSPS can reach the exact minimizer under strong convexity. On the other hand, removing the optimal minibatch loss in the step sizes by replacing it with a lower bound is nice in practice, but does not need a complicated adjustment in the proof. 

More results can be added to this work if possible. For example, does DecSPS have similar properties as in Theorem 3.1 and 3.8 of [22] for strongly convex and nonconvex settings?

2. In the numerical results, comparisons with other adaptive methods such as Adam and RMSProp should also be added. 
3. Also, more numerical results on benchmarks of deep learning can be added, e.g. ResNet56 on Cifar10, which nearly satisfies the interpolation condition. Does DecSPS have an advantage over other adaptive methods?

Minor concerns:

1. It would be better if Table 1 can be put in the main text, as it provides a succinct summary of the main results.
2. The role of parameter $\gamma_b$ in SPS and DecSPS should be explained. This parameter follows from [22], but it should still be introduced and discussed here.
3. The fonts of legends and x, y axis should be larger in the figures.
4. In line 227, the $k$ in the formula should be $0$
5. In line 282, and or should be and/or

questions: 
Please see above.
limitations: Yes
review_title: null

Meta-review: metareview: As the reviewers have pointed out, it is a well-written paper with solid contribution.
confidence: Certain
Decision: Accept