SP2 : A Second Order Stochastic Polyak Method
Authors: Shuang Li
William Joseph Swartworth
Martin Takáč
Deanna Needell
Robert M. Gower
Venue: ICLR 2023 poster (2023)

Abstract: Recently the SP (Stochastic Polyak step size) method has emerged as a competitive adaptive method for setting the step sizes of SGD.  SP can be interpreted as a method specialized to interpolated models, since it solves the interpolation equations. SP solves these equation by using local linearizations of the model.  We take a step further and develop a method for solving the interpolation equations that uses the local second-order approximation of the model. Our resulting method SP2 uses Hessian-vector products to speed-up the convergence of SP. Furthermore, and rather uniquely among second-order methods, the design of SP2 in no way relies on positive definite Hessian matrices or convexity of the objective function. We show SP2 is competitive both in experiments and in theory. 
We show SP2 is very competitive on matrix completion, non-convex test problems and logistic regression. We also provide a convergence theory on sums-of-quadratics.

Published as a conference paper at ICLR 2023
SP2: A SECOND ORDER STOCHASTIC POLYAK METHOD
Shuang Li William J. Swartworth ', Martin Takáe Deanna Needell', and Robert M. Gower
Department of Mathematics, University of California, Los Angeles, USA Mohamed bin Zayed University of Artificial Intelligence, Abu Dhabi, UAE
CCenter for Computational Mathematics, Flatiron Institute, Simons Foundation, New York, USA
ABSTRACT
Recently the SP (Stochastic Polyak step size) method has emerged as competitive adaptive method for setting the step sizes of SGD. SP can be interpreted a method specialized to interpolated models, since it solves the interpolation equations. SP solves these equation by using local linearizations of the model. We take a step further and develop a method for solving the interpolation equations that uses the local second-order approximation of the model. Our resulting method SP 2 uses Hessian-vector products to speed-up the convergence of SP. Furthermore, and rather uniquely among second-order methods, the design of SP2 in way relies on positive definite Hessian matrices or convexity of the objective function. We show SP2 is very competitive on matrix completion, non-convex test problems and logistic regression. We also provide convergence theory on sums-of coms-of-quadraties.
INTRODUCTION
Consider the problem
(w) R
"² arg min wER'
Σ
where f is twice continuously differentiable, and the set of minimizers nonempty. Let the optimal value of equation| be f IR, and w be given initial point. Here each f((w) is the loss of a model parametrized in w E Idd over an i-th data point. Our discussion, and forth coming results, also hold for loss given an expectation [(w) = Eg-D [J]]. where { D is the data generating process and fe( (w) the loss over this sampled data point. But for simplicity we use the fe(w) notation.
Contrary to classic statistical modeling, there is now growing trend of using overparametrized models that are able to interpolate the data Ma et al. (2018); that is, models for which the loss is minimized over every data point as described in the following assumption.
Assumption 1. We say that the interpolation condition holds when the loss nonnegative, f((w) 2
and there exists w" E Rd such that f(w") = O.
(2)
Consequently, f((w))= =0 for i I,...,
Overparameterizzed deep neural networks are the most notorious example of models that satisfy As- sumption I Indeed, with sufficiently more parameters than data points, we are able to simultaneously minimize the loss over all data points.
If we admit that model can interpolate the data, then have that our optimization problem equa- tion is equivalent to solving the system of nonlinear equations
f((w) 0. for 1.....P. n
(3)
Since we assume (w) 2 0 any solution the above solution to our original problem.
Recently, it was shown in Berrada et al. (2020); Gower et al. (202lb) that the Stochastic Polyak step size (SF) method Loizou al. (2020) Polyak (987)
JF V((ww')
(www))
(4)

---

Published as a conference paper at ICLR 2023
directly solves the interpolation equations. Indeed, at each iteration SP samples single i-th equa- tion from equation
3 then projects the current iterate w" onto the linearization of this constraint, that is
arg min | wwww" s.t. fi(w") (Vii(w"), ), w²) 0.
(5)
weRd
Here we take one step fürther, and instead of projecting onto the lincarization of fi(w) the local quadratic expansion. That is, as a proxy of setting fi(w) = we set the quadratic expansion of f(( around w' to zero
f((w") (VS((w)), w- w²) + (V (Wwww("(( w ). w²)
The above quadratic constraint could have infinite solutions, unique solution or no solution at al" Indeed, for example if V2 fww") is positive definite, there may exist no solution, which occurs when fi is convex, and is the most studied setting for second order methods. But if the loss is positive fi and the Hessian has at least one negative eigenvalue, then equation Galways has a solution.
equation 6 has solutions, then analogously to the SP method, we can choose one using a projection step
E arg argmin 1| w01l WERd
s.t. fi(w0) + (V.i(1o"), w w²) ( - ww,
We refer to equation 7 as the SP2 method. Using a quadratic expansion has several advantages. First, quadratic expansions more accurate than linearizations, which will allow to take larger steps. Furthermore, using the quadratic expansion will lead to convergence rates which are independent on how well conditioned the Hessian matrices are,
show later in Proposition T
Our SP2 method occupies a unique position in the literature of stochastic second order method since it is incremental and in no way relies on convexity or positive semi-definite Hessian matrices. Indeed, as we will show in our non-convex experiments in 66.1 and matrix completition B the SP2 excels at minimizing non-convex problems that satisfy interpolation. In contrast, Newton based methods often converge to stationary points other than the global minima.
We also relax the interpolation assumption, and develop analogous quadratic methods for finding w and the smallest possible E IR such that
fw( S for 1,...,
We refer to this as the slack interpolation equations, which were introduced in Crammer et al. (2006)
for linear models. If the interpolation assumption holds then 8 = and the above equivalent to solving equation 3 When interpolation does not hold, then equation g is still a upper approximation
of equation D as detailed in Gower et al. (2022).
The rest of this paper is organized as follows. We introduce some related work in Section 2 We
present the proposed SP2 methods in Section and corresponding convergence analysis in Section 4
In Section 5] we relax the interpolation condition and develop a variety of quadratic methods to solve the slack version of this problem. We test the proposed methods with a series of experiments in Section 6 Finally, we conclude our work and discuss future directions in Section 7
2 RELATED WORK
Since it became clear that Stochastic Gradient Descent (SGD), with appropriate step size tuning, was an efficient method for solving the training problem equation I there has been a search for an efficient second order counter part. The hope being, and our objective here, to find second order stochastic method that is incremental; that is, it can work with mini-batches, requires little to no tuinng since it would depend less on how well scaled or conditioned the data is, and finally, would also apply to non-convex problems. To date there is vast literature on stochastic second order methods, yet none that achieve all of the above. The subsampled Newton methods such as 2018
& Mahoney
2019
Bollapragada et al.
Liu & Roosta 2021 Hrdogdu & Montanari 2015 Kohler & Lucchi| 2017
Jahani al. 2017)
Or even two solutions in case.
Note that there could be more than one solution to this projection and we can choose one either with least arbitrarily.
2

---

Published as a conference paper at ICLR 2023
require large batch sizes in order to guarantee that the subsampled Newton direction is close to the full Newton direction in high probability. As such are not incremental. Other examples of large
sampled based methods include the Stochastic quasi-Newton methods (Byrd et al. [201] Mokhtari & Ribeiro 2015; Moritz et al. 2016; Gower et al. 2016 Wang et al. 2017; Berahas et al.) 2016).
stochastic cubic Newton Mimoon/Trrpe Tripuraneni al. (2018). SDNA (Qu al. 2016), Newton sketch (Pilanci & Wainwright 2017) and Lissa (Agarwal et al. (017)) since these require a large mini-batch or full gradient evaluations.
The only incremental second order methods we aware of are IQN (Incremental Quasi- Newton) (Mokhtari et al. 2018),, SNM (Stochastic Newton Method) (Kovalev et al. 2019 Rodomanov & Kropotov| 2016) and very recently SAN (Stochastic Average Newton) Chen et al. 2. IQN and SNM enjoy a fast local convergence, but their computational and memory costs per iteration, is of (dd) making them prohibitive in large dimensions.
Handling non-convexity in second order methods is particularly challenging because most second order methods rely on convexity their design. For instance, the classic Newton iteration is the minima of the local quadratic approximation if this approximation is convex. If it is not convex, the Newton step can be meaningless, or worse, a step uphill. Quasi-Newton methods maintain positive definite approximation of the Hessian matrix, and thus are also problematic when applied to non-convex problems Wang et al. (2017) for which the Hessian is typically indefinite. Furthermore the incremental Newton methods IQN, SNM and SAN methods rely the convexity of fa in their design. Indeed, without convexity, the iterates of IQN, SNM and SAN are not well defined.
In contrast, our approach of finding roots of the local quadratic approximation equation in no way relies on convexity, and relies solely on the fact that the local quadratic approximation around wf is good if we are not far from wt. But our approach does introduce new problem: the need to solve a system of quadratic equations. We propose series of methods solve this in Sections 3 and [ Solving quadratic equations has been heavily studied. There are even dedicated methods for solving
w" = argmin 1/2 ||w ww w|? s.t. (ww) = O, where ((w) = 1/w' Hw + b WER'
(9)
for given W. where H is nonzero symmetric (not necessarity PSD) matrix, and the level set {w Q(w) = 0} is nonempty. Note that since Q(w) is a quadratic function, the problem equation nonconvex. Yet despite this non-convexity,
long as there exists a feasible point, the projec- tion equation can be solved in polynomial time by re-writing the projection as semi-definite program, or by using the S-procedure, which involves computing the eigenvalue decomposition of H and using line search as proposed in Park & Boyd (2017). and detailed here in Section A But this approach is too costly when the dimension d is large.
An alternative iterative method is proposed in Sosa & MP Raupp (020). but only asymptotic conver- gence is guaranteed. In Dai (200)), the authors consider similar problem by projecting a point onto a general ellipsoid, which is again a problem of solving quadratic equations. However, they require the matrix H to be a positive definite matrix.
The problem equation and equation 9 are also an instance of a quadratic constrained quadratic program (QCQP). Although the QCQP in equation 7 has no closed form solution in general, we show in the next section that there a closed form solution for Generalized linear models (GLMs), that holds for convex and non-convex GL.Ms alike. For general non-linear models we propose in Section 3.2 an approximate solution to equation by iteratively linearizing the quadratic constraint and projecting onto the lincarization.
3 THE SP2 METHOD
Next we give a closed form solution to equation 7 for GLMs, We then provide an approximate solution to equation 7 for more general models.
3.1 SP2- GENERALIZED LINEAR MODELS
Consider when f/ is the loss over linear model with
fi(w) (x w v:).
(10)
where di : R + IR is a loss function, and (ax, v1) E Rd++1 is an input-output pair. Consequently
(w) = (1, y;)x, a
filw)) = of (अ) w vi T.
(11)
3

---

Published as a conference paper at ICLR 2023
The quadratic constraint problem equation can be solved exactly for GLMs equation 10 next.
show
Lemma 1. (SP2) Assume (ww is the loss of a generalized linear model equation 10 and is non-
negative. Let fi = fs(w") ).ror short. Let = (1 w 1/5 and h := of (x, w Vi). ff
a 2 f 2
(12)
then the optimal solution of equation 7 is as follows
#+1 w²
a1 hr
Vo² -2
(13)
122
|.
Alternativeyy if equation 12 does not hold, since fi 2 O we have necessarily that h4 > 0, and consequently a Newton step will give the minima of the local quadratic, that
w ++1
= w²
81
(14)
The proof to the above lemma, and all subsequent missing proofs can be found in the appendix. Lemma [ establishes a condition equation [2] under which we should not take full Newton step. Interestingly, this condition equation 12 holds when the square root of the loss function has negative curvature, as we show in the next lemma.
concave funcs
Lemma 2. Let & be a non-negative function which is twice dif- ferentiable at all with Φ(t) # O. The condition equation 72 in other words
21)2² 2 (1)
0.5
tanh?
Reja
holds when ((()) is concave away from its roots, i.e. when & de Vo(l)= < 0 for all I with ((1) + 0.
0.0
Examples of loss functions include @(t) = tanh² (t) and (tt) = Figure (a) Non-convex loss func. for which condition equation squation[2]holds, In conclusion this section, SP2 has closed form solution for GLMs, and this closed form solution includes many non-convex loss functions.
8 with 0 S p s 2 (see Figure (a)).
3.2 SP2+ + LINEARIZING AND PROJECTING
In general, there is no closed form solution to equation Indeed, there may not even exist solution. Inspired by the fact that computing Hessian-vector product can be done with a single backpropagation at the same cost as computing a gradient Christianson (1992). we will make use of the cheap Hessian-vector product to derive approximate solution equation 7
Instead of solving equation 7 exactly, here we propose take steps towards solving equation by projecting onto the linearized constraints. To describe this method let
((w)= (w²) + (V'(("") w²) (V")i(""( w²), w²)
(15)
In the first step we linearize the quadratic constraint equation 15 around wt and project onto this linearization:
w 112 arg min || w'|l s.t. f((w') + (Vf((w'), w- -ww) = o.
(16)
wERd
The closed form update of this first step given by
w 1+1/2
w²
f((w=) [V Vf(ww),
(17)
which is Stochastic Polyak step equation For the second step,
again linearize the quadratic constraint equation 15| but this time around the point (+11/2 and set this linearization to zero, that
w 112 s.t. +122+ + (Vg(w'+1/2) w
- w -/ 0. (18)
w arg min wERd
2
w
We use corch.autograd functi fuactional... hvp in our eode compute this Hessian-vector product.
4

---

Published as a conference paper at ICLR 2023
The closed form update of this second step is given by
w [++
w ++/2
q(w [atut+] Vg(w(+1/3).
(19)
We refer to the resulting proposed method as the SP2 method, summarized in the following.
Lemma 3. (SP2+) Let 9t = Vf((w") and H, = vil(()). Update equation and equation 19 is given by
w ++ w²
fi(w")
10:11 St
f2(w")2 (H.ge.9))
11 || 1
u (+1 where ol
H.
f(ww)) aa
gt.
(20)
In equation 20 we can see that SP2+ applies a second order correction to the S2 step.
SP2+ is equivalent to two steps of a Newton Raphson method applied to finding a root of (w). If we apply multiple steps of the Newton Raphson method, as opposed two, the resulting method converges to the root of q, see Theorem (2 in the appendix. Theorem shows shows that this multi-step version of SP2+ converges when q belongs to a large class of non-convex functions known as the star-convex functions. Star-convexity, which is generalization of convexity, includes several non-convex loss functions Hinder al. 22199.
CONVERGENCE THEORY
Here we provide convergence theory for SP2 and SP2+ for when f(w) is an average of quadratic functions. Fix w' E Rd and let the loss over the i-th data point be given by
Se(w) = (H. - w²), w -w))
(21)
where H, E Rdxd symmetric positive cenindefinite matrix for 1,..., n. Note that we assume that our algorithms have access to the second order terms H;, but not to the minimizer w". Consequently (ww") = 0 = f(w") = mil f(w), thus the interpolation condition holds.
Proposition 1. Consider the loss functions given in equation 21 converges linearly"
The SP2 method equation
E
wOll S s Bl|w" w=1 where p Amax I
H 11
(22)
The rate of convergence of SP2 in equation 22 can be orders of magnitude better than SGD, Indeed, since equation is convex, smooth and interpolation holds, we have from Needell et al. (2016) that
SGD converges rate of
PSGD
2t mia
(23)
To compare equation 2.3 to p rate in Proposition [ consider the case where all H; are invertible. In this case H, = and thus p = and SP2 converges one step. Indeed, even if a single H, invertible, after sampling i the SP2 method will reach w*, solving the system exactly. Of course the method is more interesting when the H, 's are low rank contrast, the SGD method is still at the mercy of the spectra of the H. matrices and depend on how well conditioned these matrices are. Even in the extreme case where all H; are well conditioned, for example H; = x I, the rate of convergence of SGD can be very slow, for instance in this we have PSGD
Proposition 2. Consider the loss functions in equation 2/ The SP2+ method equation 20 converges linearly
E w w01 < P5 B| 10 w0l where PSP2+
Aanin (H.) Xmax (H.)
(24)
2n
i
The proof of Proposition 2 follows from Corollary 5.7 in Gower et al. (2021a).
The rate of convergence of S now depends on the average condition number of the H, matrix. The rate in equation 24 can be greater smaller than the rate of SGD in equation 23 For instance, if one H,; has condition number that is much greater, then equation 24 will be smaller than equation On
'Thanks to an anonymous reviewer, the proof technique used for the Block Kaczmarz method Needell & Tropp (2014), see Remark
for Proposition is the same proof technique
5

---

Published as a conference paper at ICLR 2023
the other hand, if all the Hy's are such that max;=1..... Amax (H;) Amax (H2), for j 1, 1........
then equation 23 is a smaller rate as compared to equation 24
Note also that the rate of SP2+ appears squared in equation 24 and the rate PSGD of SGD is not squared. But this difference accounts for the fact that each step of SP2 at least twice the cost of SGD, since each step of SP2+ + is comprised of two gradient steps, see equation 17 and equation 19 Thus we can neglect the apparent advantage of the rate PSP2+ being squared.
5 QUADRATIC WITH SLACK
Here we depart from the interpolation Assumption and design a variant of SP2+ that can be applied models that are close interpolation. Instead trying to set all the losses zero, we now will try to find the smallest slack variable > 0 for which
f1ww) 8, for 1,
interpolation holds, then 8 = is a solution. Outside of interpolation, 8 may be non-zero. There two natural ways of translating the slack constraint above into penalty term. Namely one can consider either the associated l or & loss. We explore both of these in turn.
5.1 L2 SLACK FORMULATION
To make s as small as possible, we consider the following problem
min wE 2
subject to fi()) S 8, for = 1,...,
(25)
which is called the L2 slack formulation. This type of slack problem was introduced in Crammer ct al. (2006) to derive variants of the sesive-agggessive method that apply to linear models on non-separable data; in other words, when the models cannot interpolate the data.
To solve equation 25 we will again project onto a local quadratic approximation of the constraint. Let
(w) = f((w") (VJi(w'), w w²) + 2 (V² f.(w") w'), w w²)
(26)
and let A, = |10- w011 (s 2²2 Consider the iterative method given by
w' +1 3 1+1 arg min
1 A. + 2 s.t. (.e(ww) S.
(27)
#20, EE
where X E [0, 1] is regularization parameter that trades off between having small 8, and using the previous iterates as regularizer. The resulting projection problem in equation 27 has quadratic inequality, and thus most cases has no closed form solution, despite always being feasible
So instead of solving equation 27 exactly, we propose an approximate solution by iteratively linearizing and projecting onto the constraints. Our approximate solution has two steps, the first step being
w
+1/2 s ++1/2 arg min
1- A. + s²
s.t. qle(w") (Vg,,(w'), (V w pou-w" w²) S.. s.
(28)
+20. wERd
2
The second step is given by projecting w 2+1/2 onto the linearization around 1-12 as follows
w 1+1 (+1 arg min
1-λ
+
5² s.t. (w ( (V w- w- Ss. (29)
X
$20, wERd
2
2
The closed form solution to our two step method is given in Lemma 7 of Appendix C.7 We refer to this method as SP212
5.2
LI SLACK FORMULATION
To make s as small as possible, we can also solve the following slack formulation s.t. f:( < for i = 1,...,n.
min 2R
We can again project onto a local quadratic approximation of the constraint. That is, let E [0, 1] be regularization parameter that trades off between having small and using the previous iterates as
For instance w0' and f((w") is feasible

---

Published as a conference paper at ICLR 2023
regularizer, and consider the iterative method given by
1
w g
arg min +20, wERd
A +
s.t. qu((w) S s,
(30)
2
2
To approximately solve equation 30
we again propose an approximate two step method similar to equation 28 and equation 29 The closed form solution to the two step method is given in Lemma
of Appendix C.8
We refer to this method as SP2L1
5.3 DROPPING THE SLACK REGULARIZZTION
Note that the objective function in equation 30 contains a regularization term (s - s²)² which forces to be close s². If we allow s to be far from s", we can instead solve the following unregularized problem
w 1+1 g41
arg min 1-A #20, WERd
w'll f
s.t. (w,) S
(31)
2
where À E [0, 1] is again a regularization parameter that trades off between having a small 8, and using the previous iterates as regularizer. We call the resulting method in equation 31 the SP2max method since it is second order variant of the SPmax method Loizou et al. (2020); Gower et al. (2022). The advantage of SP 2max is that has closed form solution for GLMs in the form of equation TO We give the closed form in the following lemma which is proved in Appendix C.10
Lemma 4. (SP2max) Consider the GLM model given in equation 70 and equation 77 If the loss f((w)) non-negative, then the iterates of equation 31 have a closed form solution given by
0.
if f: 0
#1 w² + xx
++1 max {8, 0}, 6
if F > and 3 2 0,
1+hh,
-a /22-2//--00 -2.
otherwise.
and where x =
Nall
o. 2(1+
and l = 1|0.11? 2
1+Ah,
21-
To approximately solve equation 31 in general, we again propose an approximate two step method. The closed form solution the two step method is given Lemma [0 of Appendix C.9 We refer this method as SP 2max
6 EXPERIMENTS
6.1 NON-CONVEX PROBLEMS
To emphasize how (blue curve). SP2+ equation 20 (green curve) on the non-convex problems PermD33+ Rastrigin and Figures 1 2 in the main text, and Figures 6and)
SP2 methods can handle non-convexity, have tested SP2 equation
Levy N. 13, Rosenbrock Jamil & Yang 2013
in the appendix. For baseline we compared against SGD (yellow) ), Adam (pink) and Newt on (red).
The experiments with the function Levy N. 13 and Rosenbrock are detailed in the appendix in Section D.1.2
All of these functions are 2D sums-of-terms of the format equation 1 and satisfy the interpolation Assumption [ To compute the SP2 update we used ten steps of Newton's Raphson method as detailed in Section C.4 We consistently find across these non-convex problems that SP2 and SP2+ are very competitive, with SP2 converging in under 20 epochs. SP2 also converges faster in terms of time taken (see middle of Figures and 2 Here precision solution (like most second order methods), and different than other second order methods is not attracted to local maxima saddle points. In contrast, Newt.ns method converges local maxima on all problems excluding the Rosenbrock function in Figure 7 in the appendix. For instance on the right of Figure we can see the red dot of Newton stuck local maxima.
and
clearly see that SP2 converges to high
We used the Python Package wwrbenchfuncc ion available on github Python Benchmark Test Opt imi zat oo_______ Funct on__sn______ 1 ee_ ject i We also note that the PermDiT implemented in this package a modified version of the Permibi function, we detail in Section D.I.1

---

Published as a conference paper at ICLR 2023
37
Figure 1: The 2D PermD function with = 0.5 we plot Left: f(x) vs epochs, Middle: f(x) vs time, Right: level set plot, Right: Surface plot.
80
Figure 2: The 2D Rastrigin function where Left: we plot fxx across epochs Middle: level set plot, Right: Surface plot.
59
Figure 3: Function value vs time (seconds) for the PermD3+ (d= 10) function with 8 = 0.5 (Left), the Rastrigin function (d 100) (Middle) and the Rosenbrock function (d 100).
When increasing the dimension to 100, these non-convex problems become very challenging, see Figure i|l and often only SP2, SP2+ and SP are able to find the global minima. Note that we no longer compare to Newton's 's method because it was exceeding our maximum allocated time.
6.2 MATRIX COMPLETION
Assume set of known values (s.jen where Q is set of known elements of the matrix, and we want to determine the missing elements. One approach is solving the matrix completion problem
min U.V.
a
(32)
where A = [a: E Rmxn U= [us]i=1,..... Rexm and V = ["ylj=1,.... E Tx'"_ After
solving equation 32 we then use the matrix U as an approximation to the complete matrix A. De- spite equation 32 being non-convex problem, if there exists an interpolating solution to equation 32] one where uf "/ di.j. for (i,j) Ω then the SP2 method can solve equation 32 Indeed, SP2 can
be applied to equation by sampling single pair (i. E uniformly, then projecting onto quadratic (the solution which is detailed in Theorem in Appendix B
k+1 k+1
arg min 1 |/ue 1/ +
" subject to u To == az
(33)
0.v
We compared our method 33 to specialized variant of SGD for online matrix completion described in Jin et al. (016)), see Figure To compare the two methods we generated a rank r = 2 matrix A E I. 100x00 We selected subset entries with probability p = 0.1, 0.2 or 0.3 to form our set D,nit that was used to obtain an initial estimate Uo, Vo using rank-k SVD method as described in Jin et al. (2016). We extensively tuned the step size of SGD using a grid search, and the method labelled Non-convex SGD is the resulting run of SGD with the best step size. We also show how sensitive SGD is to this step size, by including the run of SGD with step sizes that were only a factor of to away from the optimal, which greatly degrades the performance of SGD. In contrast, SP2 worked with no tuning, and matches the performance of SGD with the optimal step size in the = 0.1 experiment, and outperforms SGD when more measurements are available in the p 0.2 and p 0.3 figures.
See Figure for comparison with respect epochs.
8

---

Published as a conference paper at ICLR 2023
D. 0.10
16
'6
16
Non Cornoo
melloc
melbac
Correck BCD
10'
Non
mellhdd
[|A UV7(
SP2
SGD xap-sbze
5GD
10
10
10
Itorations (tousandds)
Iterations (tousandss)
Iterations (thousands)
Figure 4: Recovery error for matrix completion. Leftt: Using 10%, Middle: using 20% and Right: using 30% of the entries to form Q respectively. Shaded region corresponds to repeated runs.
colon grdd iter (00
oolen-anneee Begrad-tnnenng- D0w03
colencanoeen 0 Begersh ten-nne 00
SCONLS
SPM00
SPAR23
16"
SPALL ML.5
SGOMC3
1.10
SPSL11 1W0
IMM
SPM40
Si
Sittwaae Mab
SPOTM13
ADAM
ADAM
10
10"
ADAMM
J0C:
201
.00
2000
Eflective Pasem
Offective Passes
Effective Posses
Figure Colon-cancer: gradient norm at each epoch with momentum set at 0.3. Left: a = 0, Middle: σ 0.001 and Right o 0.008.
6.3 CONVEX CLASSIFICATION
Here compare our proposed methods logistic regression problem to SGD, SP, and ADAM. In particular, we consider the problem of minimizing the following loss function fww) = 1 E [i(w) + + where f((w) = w) with (x(() = In(1 + e - Here, {(x,, yt) E
[ )==1 stands for the feature-label pairs and a > is the regularization parameter. We control how far each problem is from interpolation by increasing a. When a > 0 the problem cannot interpolate, and thus we expect to see a benefit of the slack methods in Section 5 over SP2+. We used two data sets: colon-cancer ((n,d) d) (62, 2000)) Alon et al. (1999) and mushrooms ((n, d) = (8124, 112)) West et al. (2001). both which interpolate when o = 0. We compare the proposed methods SP2+ equation 20 SP2L2 (Lemma 7). SP2L1+ (Lemma 9) and SP 2max (Lemma 10) with SGD, SP equation and ADAM on both data sets with three reg- ularizations a {0, 0.001, 0.008} and with momentum set to 0.3. For the SCD method, we use learning rate / Vt in the t-th iteration, where Lmax = max;=1...... || denotes the smoothness constant of the loss function. We chose À for SP2L2 + SELLL*$$P220 SP2L1+ and SP SP2max using a grid search of X E 0.2., 0.9). the details are in Section D
The gradient norm evaluated at each epoch is presented in Figures and see that SP2 methods converge much faster than classical methods (e.g., SGD, SP, ADAM) and need fewer epochs to achieve the tolerance when is small (left and middle plots). However, they can all fail when the problem is far from interpolation, e.g., when a = 8 x 10-3, The running time used for each algorithm to achieve the tolerance for both data sets is presented in Figure 17 (sce Appendix D)
and 16 (see Appendix D). We
7 CONCLUSION
We have proposed new second order methods aimed overparameterized models that can interpolate (or nearly interpolate) the data. In contrast to previous incremental second order methods, ours do not rely on convexity. Quite the opposite, the SP2 method can benefit from the Hessian having least one negative eigenvalue. Consequently the SP2 method excels at optimizing non-convex models that interpolate, as we demonstrated in Sections 6.1 and We also provided a convergence result in In
Theorem
2 showing that SP2 can converge significantly faster than SGD for cums-of-quadratie Section we then developed second order methods that solve a relaxed version of the interpolation equations by allowing some slack. We showed that these methods still perform well on problems that are close to interpolation in Section 6.3 In future work, it would be interesting to develop specialized variants of SP2 for optimizing Deep Neural Networks (DNNs). DNNs are particularly well suited since modern deep models often interpolate, are non-convex, and enjoy fast gradient and Hessian- vector computations via propaproo.g

---

Published as a conference paper at ICLR 2023
REFERENCES
Naman Agarwal, Brian Bullins, and Elad Hazan. Second-order stochastic optimization for machine learning in linear time. Journal of Machine Learning Research, 18(116):1 -40, 2017.
Uri Alon, Naama Barkai, Daniel A Notterman, Kurt Gish, Suzanne Ybarra, Daniel Mack, and Arnold J Levine. Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays. Proceedings of the National Academy of Sciences, 96(12)6745-6773 1999.
Albert S Berahas, Jorge Nocedal, and Martin Takáč. A multi-batch 1-bfgs method for machine learning, The Thirtieth Annual Conference on Neural Information Processing Systems (NIPS), 2016.
Leonard Berrada, Andrew Zisserman, and M. Pawan Kumar. Training neural networks for and by interpolation. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 799-809, 13-18 Jul 2020.
Raghu Bollapragada, Richard H Byrd, and Jorge Nocedal. Exact and inexact subsampled Newton methods for optimization. IMA Journal of Numerical Analysis, 39(2):545 578, 04 2018.
Richard Byrd, Gillian M Chin, Will Neveitt, and Jorge Nocedal. On the use of stochastic Hessian information in optimization methods for machine learning. SIAM Journal Optimization, 21(3): 977-995, 2011.
Jiabin Chen, Rui Yuan, Guillaume Garrigos, and Robert M. Gower: San: Stochastic average newton algorithm for minimizing finite sums, 2021.
Bruce Christianson. Automatic Hessians by reverse accumulation. IMA Journal of Numerical Analysis, 1252)133-- 1992.
Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, and Yoram Singer. Online passive-aggressive algorithms. J. Mach. Learn. Res., 7:551-585, 2006.
Yu-Hong Dai. Fast algorithms for projection on an ellipsoid. SIAM Journal on Optimization, 16(4): 986-1006, 2006.
Murat A. Erdogdu and Andrea Montanari. Convergence rates of sub-sampled Newton methods. In Advances in Neural Information Processing Systems 28, pp. 3052-3060. Curran Associates, Inc., 2015.
Robert M. Gower, Donald Goldfarb, and Peter Richtárik. Stochastic block BFGS; Squeezing more curvature out of data. Proceedings of the 33rd International Conference on Machine Learning, 2016.
Robert M. Gower, Othmane Sebbouh, and Nicolas Loizou. Sgd for structured nonconvex functions: Learning rates, minibatching and interpolation. arXiv:2006.1031 10311, 2020.
Robert M Gower, Aaron Defazio, and Michael Rabbat. Stochastic polyak stepsize with a moving target. arXiv preprint arXiv:2106. 1151, 2021a.
Robert M. Gower, Aaron Defazio, and Mike Rabbat. Stochastic polyak stepsize with a moving target. arXiv:2/06. 1851, 2021b.
Robert M. Gower, Mathieu Blondel, Nidham Gazagnadou, and Fabian Pedregosa. Cutting some slack for sgd with adaptive polyak stepsizes. arXiv:2202.12322 2022.
Oliver Hinder, Aaron Sidford, and Nimit Sharad Sohoni. Near-optimal methods for minimizing star-convex functions and beyond. arXiv preprint arXiv: 1985, 2019.
Majid Jahani, Xi He, Chenxin Ma, Dheevatsa Mudigere, Aryan Mokhtari, Alejandro Ribeiro, and Martin Takac. Distributed restarting newtoneg method for large-scale empirical risk minimization. 2017.
10

---

Published as a conference paper at ICLR 2023
Momin Jamil and Xin-She Yang. A literature survey of benchmark functions for global optimization problems. CoRR, abs/ toos//308..chh 1308.4008, 2013.
Chi Jin, Sham M Kakade, and Praneeth Netrapalli. Provable efficient online matrix completion via non-convex stochastic gradient descent. Advances in Neural Information Processing Systems, 29, 2016.
Jonas Moritz Kohler and Aurélien Lucchi. Sub-sampled cubic regularization for non-convex opti- mization. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pp. 1895-1904, 2017.
Dmitry Kovalev, Konstantin Mishchenko, and Peter Richtarik. Stochastic Newton and cubic Newton methods with simple local linear quear-- rates. arxiv:111..01597, 2019.
Yang Liu and Fred Roosta. Convergence of newton-mr under inexact hessian information. SIAM J. Optim., (1(15:99-90, 2021.
Nicolas Loizou, Sharan Vaswani, Issam Laradji, and Simon Lacoste-Julien, Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence. arXiv:2002.10542 2020.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of SGD in modern over-povvee weer-parametrized learning. In ICML, volume 80 of JMLR Workshop and Conference Proceedings, pp. 3331-3340, 2018.
Aryan Mokhtari and Alejandro Ribeiro. Global convergence of online limited memory BFGS. The Journal of Machine Learning Research, 16:3151-311
2015.
Aryan Mokhtari, Mark Eisen, and Alejandro Ribeiro. Iqn: An incremental quasi-newton method with local superlinear convergence rate. SIAM Journal on Optimization, 2802)1670-1168, 2018. doi: 10. 00.1137/17M1122944
Philipp Moritz, Robert Nishihara, and Michael Jordan. A linearly-converge stochastic L-BFGS algorithm. In International Conference on Artificial Intelligence and Statistics, volume 51, pp. 249-258, 2016.
D. Needell and J.A. Tropp. Paved with good intentions: analysis randomized block Kaczmarz method. Linear Algebra and its Applications, 441:199 221,,2221221102 2014.
D. Needell, N. Srebro, and Ward. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. Mathematical Programming, Series A, 155(():5499555 573, 2016.
Jaehyun Park and Stephen Boyd. General heuristics for nonconvex quadratically constrained quadratic programming. arXiv preprint
2017.
Mert Pilanei and Martin Wainwright. Newton sketch: A near linear-time optimization algorithm with linear-quadratic convergence. SIAM Journal on Optimization, 27(1):205 245,,,,, 2017.
Borist Polyak. Introduction to optimization. New York, Optimization Software, 1987.
Zheng Qu, Peter Richtárik, Martin Takáč, and Olivier Fercoq. SDNA: Stochastic dual Newton ascent for empirical risk minimization. In Proceedings of the 33rd International Conference on Machine Learning, 2016.
Anton Rodomanov and Dmitry Kropotov. A superlineatly for the optimization of finite sums. In Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 2597-2605. PMLR, 20-22 Jun 2016.
proximal newton-type type method
Farbod Goosta-KKorasee and Michael W. Mahoney. Sub-sampled newton methods. Math. Program., 174(1-2):293-326 2019.
Wilfredo Sosa and Fernanda MP Raupp. An algorithm for projecting a point onto a level set of quadratic function. Optimization, pp. 1-19, 2020.

---

Published as a conference paper at ICLR 2023
Nilesh Tripuraneni. Mitchell Stem, Chi Jin, Jeffrey Regier, and Michael I Jordan. Stochastic cubic regularization for fast nonconvex optimization. In S. Bengio, H. Wallach, H. Larochelle, and R. Garnett (eds.), Advances in Neural Information Processing
K. Grauman, N. Systems, volume 31, 2018.
Xiao Wang, Shiqian Ma, Donald Goldfarb, and Wei Liu. Stochastic quasi-newton methods for nonconvex stochastic optimization, 2017.
Mike West, Carrie Blanchette, Holly Dressman, Erich Huang, Seiichi Ishida, Rainer Spang, Harry Zuzan, John A Olson, Jeffrey R Marks, and Joseph R Nevins. Predicting the clinical status of human breast cancer by using gene expression profiles. Proceedings of the National Academy of Sciences, 98(20):1 11662-1167,, 2001.
S. Wright and J. Nocedal. Numerical optimization. Springer Science, 35(67-68):7, 1999.
A PROJECTING ONTO QUADRATIC
This following projection lemma is based Section B in Park & Boyd (017)). What do in addition to Park & Boyd (011)) is to clarify how to compute the resulting projection, and add further details on the proof.
Lemma 5. Let w E R& and let P E Raxd is symmetric matrix. Consider the projection
w' E arg aargmin / ||w 2|| WERd
s.l. r (1, - =) + (P(w - 2), w 2) = =0
(34)
Let
A1 S S...
be the eigenvalues of P and let QAQ = P be the eigenvalue decomposition of P. where A
diag(A; (>i) and QQ = T. Let q = Q q. If the quadratic constraint in equation 34 is feasible, then there exists solution equation 34 Now we give the three candidate solutions.
1. r = 0, then the solution is given by
w
2. Now assuming + O. Let
V max
(35)
:: X,
A
Xd
1
arg max
(36)
i: A:700
A1
Ad
N {i X * A1.
(37)
Let
x² --(I+ vA)tVa
(38)
If
22
2vr + x²) -1xx112
Σ
c
0
(39)
then the solution is given by
w = = Q(x"" +n),
(40)
where I2d and
-
V/
+
1
2ur + 11
- 1|2+1|2 - 2
v2
Σ gf
f N
VINI
4
VEN
n4 for & N.
12

---

Published as a conference paper at ICLR 2023
3. Alternatively if equation 39 does not hold, then the solution is given by
w' 2 (I vA ug
(41)
where is the solution to the nonlinear equation
(2+
r. (1+
(42)
Proof. First note that there exists a solution to equation 34 since the constraint is closed feasible
set.
Let QAQ P be the SVD of P. where QQT = By changing variables x = QT - 2) we
have that equation 34 is equivalent to
min 1 2 ||a:||
SER2
s.t. + x) + (Ar, x) 0,
(43)
where 2 = Qw - 2) and Q q. The Lagrangian of equation 43 is given by
M(,, v) = 1/2 ||:|| + v(r + (0,0) + 1/2 (Az,x)
= 1 T (I + -1) + v(r (g.z))
(44)
Thus the KKT conditions are given by
v_L(r, (I vA) x Vr =
(45)
V,L(I,v)=1) - (á. x) (Az, 0.
(46)
Since we are guaranteed that the projection has a solution, we have that as a necessary condition that the solution satisfies
((,,v) (I+ vA) ž 0,
see Theorem 12.5 in Wright & Nocedal 1999). Consequently either (I vA) > or + (I+DA) has zero eigenvalue.
Consider the case where (I + vA)
0. From equation 45 we have that
x -I vA) 9.
(47)
Now note that if then and by the constraint we must have 0. Otherwise, if # 0, then * O. Assume now * 0 and substituting the above into equation 46 and letting A = diag Ax:) gives
V voL(z,))= = x) + 2v (vAz, x)
1 2v
<), (II UA)
||0/|/
1
(á. x))
||0||/
Using equation 45
2
2v
(á. (I + vA) -11)
1/
-I++
Using equation 47
2
of
of
Σ
1 1+ v\:
(1 + v2
Thus
(2+ (1+
r.
(48)
Upon finding the solution / to the above, we have that our final solution is given by w' = 2 Qx that is
Q(I DAtivG w/
= =I+++ uQu
=- vA)ta
(49)
13

---

Published as a conference paper at ICLR 2023
Alteratively, suppose that (I + PA) = 0 is non-singular. The positive definiteness implies that
for i = ,.....d.
(50)
For (I + vA) to be non-singular, least one of the above inequalities will hold to equality. To ease notation, let us arrange the eigenvalues increasing order so that
A1 )2 S S Ad-
For one of the equation 50 inequalities to hold to equality we need that
(-1--1]
V/ max :: A;70
max A :: A:70
x X x=>
Since (I + vA) is now singular with this u, we have that the solution to equation 45 is given by
x = (I vA) vq + = x² + n, where (x", n) = 0,
(51)
where i denotes the pseudo-inverse and where is in the kernel of (I + vA), in other words (I DA)n m 0. It remains to determine n, which we can do with equation 46 Indeed, substitut-
ing equation 51 into equation[46 gives
1
v.L(r, = + (q. 2v
||0/|
Using equation 45
2
1
= 2 (0, x n)
||m|12
1,001
Using equation 51
2y
2y
Setting and completing the squares in we have that
1
12
2 = r (g. x²)
|
112
V 8 11112
(52)
2v
2
2v
To characterize the solutions in n of the above, first note that will only have few non-zero elements. To this, let i' arg max; Ax - xha and note that (I vA) has many zeros the diagonal as the multiplicity of the eigenvalue Açe. That is, has zeros elements on the indices in
(i A = }=
Thus the non-zero elements of are in the set
N
{i A + A,-
Because of this observation we further re-write equation
52 as
14 00:
V
2vr + 1/ (g,
||x011
y2
||
12
9
N
iE!
2
2ur + u x") - -1|a"
(53)
iEN
Consequently, the above positive, then there exists solutions the above of which
V/ n. =
9i +
2ur + (g. x²) - || 11
2/2
for e N.
(54)
2
VINY
4
iEN
is Consequently, the final solution is given by = by equation 51
Qx (x + n) where x" is given in
Corollary 1. Ifr > 0 and has at least one negative eigenvalue, there always exists a solution to the projection equation 34
Proof. We only need to prove that there exists a solution to the quadratic equation in equation 34 after which Lemma guarantees the existance of a solution.
14

---

Published as a conference paper at ICLR 2023
B MATRIX COMPLETION
The projection equation 33 can be solved as we shown in the following theorem.
Theorem 1. The solution to equation 33 is given by one of the following cases.
1. If (f ot di then u and vf.
2. Alternatively uuu vř and
(ul) of 2 Aais
then
2
V. =
2 3
+
2 1
V | 4aij
(55)
1
V /|
4ai,
(56)
Ju
3. Finally, if none of the above holds then
" 703
(57)
72
1 7
(58)
where E (-1,1) and is the solution to the depressed quartic equation
(1 + ( (u),
> (1| + |103113) = (1 - 2
(59)
Proof.
The Lagrangian of equation 33 is given by
L(u, u, 7) - w b ||00 uf'l + +(u a;,});
where 7 E IR is the unknown Lagrangian Multiplier. Thus the KKT equations are
u yv
(60)
vj k + yuu =
(61)
u at,j
(62)
Subtracting y times the the second equation from the first equation, and analogously, subtracting the first equation from the second gives
22²2 ui ruf =0 (1 y - 14t + yu = 0.
(63)
(64)
If 1, then necessarily uf u/ and furthermore from the first equation in equation 62 we have that
(65)
Substituting u out in the original projection problem equation 33 we have that
min || of subject to u oz |||||
ai.i
(66)
Consequently, for every v that satisfies the constraint we have that the objective value is invariant and equal -as.j. Consequently there are infinite solutions. To find one such solution, we complete the squares of the constraint and find
||0 10
|
Oijj-
(67)
The above only has solutions if || aiij 2 0. One solution the above is given by equation 55
15

---

Published as a conference paper at ICLR 2023
Alteratively, if y + then by isolating u and y in equation 63 and equation 64
respectively, gives
u yoj
(68)
1 72
j yu
(69)
1 72
To figure out 7, we use the third constraint in equation and the above two equations, which gives
u e (u yu.)) T 2 y
722 1 72
(1 + 72) (ut, 015)
>( 11 + | ai.
72-9
Let
<6)) = (1+ ?2) (u,, uf) - >[1 (|| ||
(1 - 2
Can we now find an interval which will contain the solution 7? Note that
Φ 2 (u, uf) || ||
||
|/u + || 0 0
(11) = 2 ( (u. .u5) -|| -- S.. 0.
Thus suffices to search for y (-1, 1), which can be done efficiently with bisection.
C PROOFS OF IMPORTANT LEMMAS
C.I PROOF OF LEMMA
I
Let us first describe the set of solutions for given constraint. We need to have
ft a. A A xnze A = O,
(70)
where w w is unknown. we denote by TÚ = x!. A then equation 70 will reduce to
1
ft + a,T; + - 11,77 0.
(71)
2
This quadratic equation equation 71 has solution if
af 2/, 2 0.
(72)
the condition above holds then we have that the solution for T is in this set Recall that the problem equation 7 now reduces into
T a4 a 2h.S.
0g
v a 2h
(73)
h
h;
min { ?| such that T.AET
(74)
Note that because want to minimize ||| ? want to choose the constraint with smallest possible absolute value, hence the problem equation 74 is equivalent to
min [|| such that x A T²}
(75)
where
a, +
a
2h;
if a; > otherwise.
0 of
2h
h,
16

---

Published as a conference paper at ICLR 2023
In other words,
ai h
Vag
2h,
ai
(v
2h
-11
+ (a)
hi
h4
ag
The final solution is hence
Ti
+
|| 112
24
and therefore
w² = wº + T
T2
|
In case when equation 72 is not satisfied, and because we assumed that the loss function is non- negative, we necessary have h2 Then natural choice of TÜ the one that would minimize the
f a.T + h,T
From first order optimality conditions obtain that
h;
which leads to equation 14
C.2 PROOF OF LEMMA
Proof. If (tt)) then the condition holds trivially. For such that ((t) + 0, o(t) is differentiable. and we have
d2
dta @(t)
("00000000"00000000"00000000"010 (0())))))))))
which is negative precisely when o'(1)² 2 20())=(()
C.3 PROOF OF LEMMA 3
Note that
fe(w')
1122) equation equation
15 fi(w*)
V((w()),
Vi((w")
[
1 v2
f((w**
fi(w')
((w'(
Vli(w'))
[V Vii(w))
2
[
1
fi(w*)2
vf((")).
2
[[(
Furthermore
Vg(w++1/23
equction
vi(ww") + fe (w) -w²)
fi(w")
equation
1- (-v2f((w") [
V(((w').
Thus the second step equation
19 is given by
f((w))2
V2 Vfl Vf((w())
f((w²)
w 1+1 = =
I v2f((w)
Vf((w").
2 ([((w))ll
11
[[1 (2
V fi(()) [AA(w
fetwe)
| [V
(76)
Putting the first equation 17 and second equation 76 updates together gives equation 20
This gives second order correction of the Polyak step that only requires computing single Hessian- vector product that can be done efficiently using an additional backwards pass the function. We call this method 5P2.
17

---

Published as a conference paper at ICLR 2023
C.4 CONVERGENCE OF MULTI-STEP SP2*
If we apply multiple steps of the SP2*, as opposed to two steps, the method converges to the solution of equation 15 This follows because each step of SP2+ is step of NR Newton Raphson's 's method applied to solving the nonlinear equation
(w)) = f((w²) + (Vi(("),, w w²) (V - w²).
Indeed, starting from w w², the iterates of the NR (Newton Raphson) method are given by
g(w")
wd+1 w (Va(w()) q(w=) = w
[[Vg(=)]]* Vg(w*),
(77)
where Mt denotes the pseudo-inverse of the matrix M.
The NR iterates in equation 77 can also be written in variational form given by
arg min || - w0'l
w
wERd
s.t. q(w") Vq(w") w')= =0
(78)
Comparing the above the first equation 16 and second step equation 18 indeed two steps of the NR method. Further, we can see that equation 78 is indeed the multi-step version of SP2+.
This method equation 77 is also known gradient descent with Polyak Step step size, SP for short. It is this connection we will use to prove the convergence of equation 77 to root of (
IRd be a least norm root of q(w), that is We assume that (w)) has least one root. Let wy
W arg min ||]
subject to ((w) 0.
(79)
It follows from Theorem 3.2 of Sosa & MP Raupp has solution if and only the following matrix
2020) that the above optimization equation 79
B (Vf((w") v f(("))"")) - f((w)) + V((w')) Two wt w¹ T V22 vil'"")) V2 vi((("))
v vill(w")"))
(80)
has at least a non-negative eigenvalue. Theorem 2. Assume that the matrix B defined in equation 80 has at least a non-negative eigenvalue. !f q(w) star-convex with respect w/ that is if
(w' wi)) T 2 few -wr) 2 0, for all i,
(81)
then it follows that
(V(i((w))) 2T
min q(x") mmax O......
|| 1/00 aon-wwlll will?
(82)
Proof. The proof follows by applying the convergence Theorem 4.4 in Gower et al. (2020) or equivalently Corollary D.3 in Gower et al. (2021b). This result first appeared in Theorem 4.4 in Gower al. (202)), but we apply Corollary D.3 in Gower al. (2021b) since a bit simpler.
To apply this Corollary D.3 in Gower et al. (20216). we need to verify that is an L-smooth function and star-convex. To verify if smooth, we need to find I. > such that
L ||w yl² 2
((w)
q(v) (V y)
(83)
which holds with L = max 2 q3)) = a max 2 f((w)) since is quadratic function. Furthermore, for q be star-convex along the iterates w', we need verify if
((w))) 2 q(w") (Vq(w"), w0 w
(84)
18

---

Published as a conference paper at ICLR 2023
Since q is quadratic, have that ((wr)) g(w") + (Vq(w"), w0 - w²) + (V2g(w))(" w²), w w²)
Using this in equation 85 gives that
2 V (g (w w w w²) = fi (w" - w'), w= w')
(85)
which is equivalent to our assumption equation 81
We can now apply the result in Corollary D.3
Gower al. (2021b) which states that
t T' ( (w I
min
27 w - n "ll
Finally using g(wa)) and that L mmax
(V2 (V2 f((w")) gives the result.
To simplify notation, we will omit the dependency on wf and denote = f((w)), Vf((w") and H f(w"). thus
((w) = c + (g, w w²) + (H(w w²), w - w²
Vq(w)= = + H(w - w²)
(2q(w)= =
(86)
Lemma 6. If g E Range(H) and w E (RangeHH) then w', Vg(w") E Range(H) for all i and wy Range(EF (H).
Proof. First, note that since g E Range(H) and since Vg(w)= = q H(w w²) (see equation 86) we have that Vg(w) E Range(H) H) for all w. Consequently by induction if w Range(H) then by equation 77 we have that ++1 E Range(HH) since is a combination Vq(w") and w'.
Finally, let w = w' WH + WH where wH E Range H) and WH Raage H) It follows that
(ww)) q(w" wH).
Furthermore, by orthogonality and Pythagoras' Theorem
|لmi||| ||' + wH + [|
Consequently, since wy is the least norm solution, we must have that WH = and thus wy E (H).
C.5 PROOF OF PROPOSITION I
First we repeat the proposition ease of reference.
Proposition 3. Consider the loss functions given in equation 27 converges according to
The SP2 method equation
E - - -w²l S Blllw* w² w=1
(87)
where
1 n n
Σ H.H.
p Amax
I
(88)
Proof. First consider the first iterate of SP2 which applied to equation 21 are given by
++ arg min
w
wERd
S.t. ||w w0 IH, 0.
Thus every solution to the constraint set must satisfy
E " N
(89)
19

---

Published as a conference paper at ICLR 2023
where N, E R is basis for the null space of H. where Substituting into the objective we have the resulting linear least squares problem given by
min E
I + N₂a w²11
The minimal norm solution in is thus
N (w² w²)
which when substituted into equation 89 gives
N,N (w' w²)
(90)
Note that P; N is the orthogonal projector onto Null(H.). Subtracting w" from both sides
of equation 90 and applying the squared norm we have that
I w='+1 w" w²Il
P& (w- - w²)l [1w===")'"" (P:(w' -o--ww), (w' (w'-ww") w²))
(91)
where we used that P,P; = P. because is a projection matrix. Now taking expectation conditioned on w" we have
R fll - w0
w²
EPi (w - w0)) vo"), (w² w²²)) Amax (BP;) |w -w"ll
Since the null space is orthogonal to the range of adjoint, we have that
P. = H.H
Thus taking expectation again gives the result equation
87
Finally, the of convergence p in equation 88 is always smaller than because, due Jensen's inequality and that Amax is convex over positive definite matrices we have that
0 max HHH I EAmax (H,H;) 1,
(92)
where the greater than zero follows since there must exist H. * 0, otherwise the result still holds and the method converges in step (with p 0). Now multiplying equation 92 by -1 then adding 1 gives
Amax [I EHH 0.
(93)
Remark (Connection to Block Kaczmarz proof). The proof of Proposition follows the same proof technique of the Block Kaczmarz method Needell & Tropp (2014 To see this, first note that since interpolation holds, to find the minima we can solve the equations
Find w E I :
Vf((w)= =0 for i = 1....,n.
(94)
Since each fi(w) function is quadratic, this is equivalent to
Find w E Rd
( ww) = 0. for 1....
(95)
We can now interpret the above as one big linear system that we need to solve. we we sample one of the block of rows, say H,(w-w" )=")= for one i, and project w onto this smaller system, the resulting method the block Kaczmarz method equation 995 This also coincides with the SP2 method. F Furthermore, our convergence analysis is now equivalent to applying the convergence analysis of block Kaczmarz to solving equation 95
Thanks anonymous reviewer ICLR for pointing this connection.
20

---

Published as a conference paper at ICLR 2023
C.6 PROOF OF PROPOSITION 2
For convenience repeat the statement of the proposition here.
Proposition 4. Consider the loss functions given in equation 21 The SP2 method equation 20 converges according to
E B w0' S PSP2+
Bllw² w w=1?
(96)
where
Amin (H:)
PSP2+ =
(97)
2n
Amax (H₂)
Proof. The proof follows simply by observing that for quadratic function the SP2 is equivalent to applying two steps of the SP method equation [ Indeed in Section 3.2 the SP2* applies two steps of the SP method to the local quadratic approximation of the function wish minimize. But in this case, since our function is quadratie, is itself equal to it's local quadratic.
Consequently
apply the convergence theory of SP for smooth, strongly convex functions that satisfy the interpolation condition, such as Corollary 5.7.1 in Gower et al. (202Ib), which states that converges at rate of equation 97
C.7 PROOF OF LEMMA
The following lemma gives the two step update for SP2L2*
Lemma 7. (SP2L2*) The w and s1+1 update of equation 28 equation 29 is given by
w [+1 = w² (TT,+ + 1'2) V()'"( + V
g++ = (1 - -1 ((1 () +T))
where
T1 (fi(w*) (1 ))s²)
1- + V 11
[(ww)) ((s(1a) -1--0 1-A+|V/i(u0 TT "T -
12 =
where we denote (z)+ for 2 0 otherwise
We will use the following lemma to prove Lemma which has been proven in Lemma C.2 of Gower et al. (022).
Lemma 8 (1.2 Unidimensional Inequality Constraint). Let 8 > 0, c E R and w, wo Rdd The closed form solution to
w', s' arg min || w w011 + +8||s - 2012 E .EEt
s.1. a (w- + 5
(98)
given by
(c 50)
w/ = 0
(99)
1 8
(c +
0
(100)
1 ||l| 2'
xx
if otherwise
where we denote (x)+
0
21

---

Published as a conference paper at ICLR 2023
We are now in the position to prove Lemma 7
Note that
1- X (s
s²
+
2²
X
1-
x
s² (1
-)sss*
+
A 2
1 x
(s
2
2
2
2
1 8²
1- X
(1 (1- -11-))s8*
+
(5
2
2
1
+ A- 12
70 (1 -))st)2
2 (5
(101)
Consequently equation 28 is equivalent to
w ++/2 12 8 1/2
arg |/00 w²1 w²12+ +
1 (s (1 - A)s²)²
200 wERd
(i,r(w') + (Vw))(""), w²) S S. s.t.
(102)
It follows from Lemma & that the closed form solution is
w +122 w² 1 (0h,(w")) - (1 (1-)) Ver,((w'),
(103)
1 X 1+ I=x (q,e(w)))] )|1
s/+1/2 = (1- A)s² + (g:,(w") - (1 ))s²)+
(104)
1+ 1-x [V],,(""'|1
where we denote
(x)+ {0 x 2
otherwise
Note that (w*) fe(w') and (g V.((w").. To simplify the notation, we also denote
(fi(w²) - -11-)ss)
r 1+ T-x 11 [V
With this notation we have that
w 1+12 w² 1 (fi(w))) (1 N))*)+
Vf((w')
(105)
X 1+ - \f'((())ll ?
u 11 Vi(''(
(106)
+1// (1 - \)s² + (fi(w*) (1- -))+)+
(107)
1+ T [V((w'))1
= (1 ()* + (T).
(108)
In completely analogous way, the closed form solution to equation 29 is
(q, 1/2) - (1 A)s 1/2)
w t+ = +1/21/2
--X 1 + - /v.,(u++1//3)
se1 = (1 (1- -1)) (que
(1 - 2)
(109)
(wo,((w
Note that
(1e(w++1/2) = fi(w') - -V ( (/
= - + +
and
/ = Vfi(w') -/aa)\+
= -Vi((w') -
22

---

Published as a conference paper at ICLR 2023
Denoting 12 as in the statement of the lemma conclude that
w ++ =w 1/2 1 (q.,((u+1/2 - (1- -)s +1s)+1122++
(w
1 1+ 1-x [g.c(wut1/2]]1
w² -IiV)((w') T2 (Vf((w") - I'2 V2 (i
(110)
g+1 (1 1) + (1,, (v. (1/2) - (1
1+ T-x [gh, 1)s
(1- ((1 2)(s +T))
(111)
C.8 PROOF OF LEMMA 9
The following Lemma gives a closed form for the two-step update for SP2L1
Lemma 9, (SP2L1*) The w and s++2 update is given by
w ++ w² -(T4 oo4+To)VSi(u') + + f(l")
g41 (s' 2(1 A)
+ rs) 2(1 (1--)) X)
+ Iss
where
f((w()- - (s' -
fs(wo)
L'3
14= min I'' [V
1+ (V(((" 1|2
A1 (s' 3 -
T3 = 1+ -
-
A
T6 = min
Iss
- l'y ((V""
A = -a
+ + (V Vl(w')).
To solve equation 30 tion
we consider the following two-step method similar to equation 28 and equa-
1- X A, + 2.
A
w 1122 g//1/22
arg min
(112)
220 WERd
2
s.t. q.((w") + (V,,((w)), w -w')=
1-
w [1 s 1+
arg min
+ 2
(113)
420. WERd 2
s.t. Cur (1t +
(Vgie( w 41122) Ss.
Note that
1
X
1->
2(1 -x,)) )) + constants w.r.t. w and s.
A
(s
5/2
8 (s-
s²
2
2
Then, equation 112 is equivalent to solving
arg min w|l w|w/ 111 (s S- (s' +20, wERd
2 2(1 - x1 )
2 f/+1/2=
(114)
s.t. (w"(")) + (Va.c(""), w²) S
23

---

Published as a conference paper at ICLR 2023
It follows from Lemma C.4 in Gower et al. (2022) that the closed form solution to equation 112
(ile(w")) - ss x(1>x
w/+1/2 w² min
Vgr,((w"),
1+ (
s/11/2 (1 2(1 - 2)
+ (rre(ro")) -(s- s² -
2(1 2(1-1))
1 (Qq,((w)) )|2
+
x i 2 0
where we denote (x)+
10
otherwise
Note that qr,((w)) f((w)) and (gn V.((w")). To simplify the notation, denote
(Ji(w*)
(s' -
I'3
1 [i
and
fe(w*)
T4 min T3:
Then, we have
w 1-12 w0. -)w's(
1// ((0 2(1
A
[33
In similar way, we can get the closed form solution equation 113
which given as
(anuluo (/2) - (st (st11/22(11
2(1-
Fi (wx(22+)22)
w+1 w11122 min
1 Vot,e
Vi V (12++/2)112
+ (1a(wu+1/22- ((s (s'-Z(1X)) 2(1-1)
(5'
(141//2
g441
2(1 - 2)
1 (9:
Note that
11/( = - (
= 110HH//11177A40001......1..11111
A A
and
Voir(wt1/22) = + w²)
Again, to simplify the notation, we denote
((..(w((1/2) 55 (1-2\(x))
T3
1+ [V
x 1+ Vf((w*) f(("') (F(
A1 8"
24

---

Published as a conference paper at ICLR 2023
and
11122)
F6 min
A1 Ts
(
min
Tss
Vff(w()) - V
Then, we have
w w1 = w Te Vv.
= w² - I44 f. - To (Vii((") - (V
w' -IT' + 1T) ff(((')) +
(/41/2 A
5 (+1
+1's
2(1 A)
A
+1'3
+ +1's
2(1 - X)
2(1 - x1
C.9 PROOF OF LEMMA 10
The following lemma gives a closed form for two step method SP 2maax Lemma 10. (SP 2max+) ) The wt+1 and g update is given by
c+ = w² (T1 + 13) V(((w)))))))) +
A
841 = -max
I2 - 2(1 - A)
where
fi(w")
x
Ii min
2(1 A) S [|V
12 = Si(w")
-T, // )12 + !r (V> V(i(w")),
T2
A 2(1 2
r3 min
1) S)
To solve equation
31
we again consider two step method similar to equation 112 and equation 113
1- A
||0 - w + A
w 1+/2 s/1122=
arg min +20, WERd 2
(115)
2
s.t. (w') + (V)):(("),, w - w²) S 8.
w ++ 1+1 arg min 1-1 w w w
+ X
(116)
220, wERi 2
2
s.t. gi ( (1/2) + (V)nr(u(t1/2), w - w +1122 S s.
Note that equation 115 is equivalent to solving
1 w w/1 + 2(1 - 2) s
" 1+1/ g/+1/2=
arg min 220 w 2
(117)
s.t. (w'(w") + (Vg,,((w)), w²)
25

---

Published as a conference paper at ICLR 2023
It follows from Lemma D.2 in Gower al. (2022) that the closed form solution equation 117
gs,(w*))
A
w 4112 w² min
Vgni(w")
"/2"))))22000""0"0"0"00 2(12(11110 21
Si(w0
A
w min
Vf(((())11 111222(111)) 2(1-1} Vfi(w()
w. E, Vivl'
2(1 2) [V .0} .03
//11/2 max
(1,((10))
{Fi(ut)
X
[[ii(=+)|| 00)
max
2
where we denote
Si(wx)
T1 = min
[VV 2'2 "2(1 - A)
Note that
(1/(2 = fi(w") - || ( Vf(w'')
12,
and
Wel (l((w++1/3)= V.i(w')) + V ( w²)
- - V
=
Similarly, we have the closed form solution to equation
116 given as
(11(2
211 =w'11/2 min
V
2(1 -
Xj
14122 min
I'2
2(1 - -1 (V/((w)) "V
- - (w
w/ 1/12 I' (v -
w' (T) (3) Vi((w') + rar V2 S.
2(1 A) Vg.r(w .00
111 max (/ +1/
A
of
max I'2
Vfi(w") v f
2(1 X)
C.10 PROOF LEMMA
In GLMs, the unregularized problem equation 31 becomes
1+1 1+ = arg min 1
s20, wERn? 2 ||w - w0'l + Ās
s.t. fi + (a,3,, w w²) + (hazta) (w - -ow-ww), , w w()=
S s,
(118)
where N == A X[-x]. and we denote fi = f,(w0), az = (( To vi). h == (x. w - 9:) for short.
Denote A = wt. Then, problem equation 118 reduces to
min $20, AER 2 || + As
s.t. ft a. A + TT A S..
TA.
(119)
26

---

Published as a conference paper at ICLR 2023
Note that want to minimize |A|| Together with the above constraint, conclude that A must be a multiple of 2; since any other component will not help satisfy the constraint but increase ||||2 Let A cæ, and & ||, 13, then problem equation 119 becomes
min c $20, CER2
s.t. Ji + a,ec + 11 <
(120)
The corresponding Lagrangian function is then given as
L(s,C,VI, = 2 e As + vs + aalc 11 é -)) 128,
where 02 2 0 are the Lagrangian multipliers. The KKT conditions are thus
fi + aalc e - 0,
8 820, M 200, 1/2 2 0, msffi + a + h
5) 0, V25 0,
X 11 1/2 = 0, tc + via,& + vn h4 O. By checking the complementary conditions, the solution to the above KKT equations has three cases, which are summarized below.
Case I: The Lagragian multiplier 1/2 O. In which case vs = X, 1/ 0, c*
Āo and
1+Ahee"
8* Si alle 1 hn =2 + Auel
Xafe 1222af62
2(1 + Xh;
which is feasible s* 2 0. The resulting objective function is c + Äs* which is 2 0.
Case II: The Lagragian multiplier 111 = 0. which case 1/ = 0. vo = X, c* = 0, s* = 0. which is feasible if f. 0. The objective function is 0 in this case and the variable is unchanged since w
c* x; 0.
Case III: Neither Lagragian multiplier is zero. which case there are two possible solutions for given by e² -a 2b
V t,th VS = X acthato 8* = 0. Note that a, + h,lbe = +
h,t
2h,fe-
Consequently to guarantee that the Lagrangian multipliers and D2 are non-negative, we must have c* -a: + u 2h and in this the objective function equals J/²² 0.
h,t
As summary, if 0, Case II is the optimal solution. Alternatively if >> 0 and
Xaze
x= S.
1 Xh,
2(1 + Xhzl)2
is non-negative then Case is the optimal solution. Otherwise, Case III with c* -aity the optimal solution. Therefore, the optimal solution equation 118 is then
/a - 2h: h,d
is
w 1+1 w² + c Fis
(+1 max {3, 0}
where
0,
if ft
c²
1+ Xh,!
Xo.
if f. > 0 and 3 0, otherwise.
y a² 2h:
h,t
27

---

Published as a conference paper at ICLR 2023
D ADDITIONAL NUMERICAL EXPERIMENTS
D.I NON-CONVEX PROBLEMS
For the non-convex experiements, used the Python Package pybenchfunction available github Python Benchmark Bettaaaarr___tt_____e- Opt Function, Funggion_Siiggle See__ojjeeiivte
We compared SP2 equation 7
(blue curve). SP2+ equation 20
(green curve) on the non-convex
problems P Rastrigin and Levy N. 13, Rosenbrock Jamil & Yang 20013 For a baseline
we compared against SGD (yellow) Adam (pink) and Newton (red).
For the implementation of Newton. 's method, we found that the regularized Newton methods was best suited for these non-convex experiments where
1 = w² 7(1e +
(w"(")
where is the regularization parameter which we set to = 10 10ma, and y is learning rate which we tuned.
Specifically, for all the experiments in this section we set learning for all methods to 0.25 except for SGD and ADAM, both which had to be tuned by doing grid search on the first 100 epochs over the grid
[0.0001, 0.0005, 0.001, 0.005, 0.01,, 0.05, 0.25,
proving much harder tune.
D.1.1 PE INCORRECT IMPLEMENTATION PERMD8.
We note here that the P implemented is given by
(1))))
FermD (x)
(f B)
2
-11
i= j=
which is different than the standard PermDB function which is given
2
6 -1 (()
PermD3(x)) Σ
Σ G + 3)
We believe this is a small mistake, which is why we have introduced the plus PermD to distinguish this function from the standard Pe rmD3 function. Yet, the PermD3 is still an interesting non-convex problem, and thus we have used it in our experiments despite this small alteration.
D.1.2 THE LEVY N. 13 AND ROSENBROCK PROBLEMS
Here we provide two additional experiments on the non-convex function Levy N. 13 and Rosenbrock that complement the findings in 6.
For the Levy N. 13 function in Figure 6 we have that again SP2 converges in 10 epochs to the global
minima. contrast Newton's 's method converges immediately local maxima, that can be easily seen on the surface plot of the right of Figure 6
The one problem where SP2 was not the fastest was the Rosenbrock function, see Figure Here Newton was equally fast. But note, this problem was designed to emphasize the advantages of Newton over gradient descent. For completeness, we also give the function value versus time plot in Figure g
We used the Python Package pwbench funct iin available on github Python Benchmark Test Opt mi zat on__ Funct on__s_____ ngle_ 1ee_ll______ ject i We also note that the PermDiT implemented in this package modified version of the Permij function, detail in Section D.I.1
28

---

Published as a conference paper at ICLR 2023
3.50
SPRA
SF2
111
33
33-1
99
277
2.2
3.5
1125
22-5
155
1.00
13"77
0.08
170
Figure 6: The Levy N. 13 function where Left: we plot f(x) across epochs Middle: level set plot, Right: Surface plot. SP2 is in blue, SP2 is in green, SGD is in yellow and Newton is in red.
165
3.00
SF2
SF2
Aecm new.
0.72
04
0.50
0.4
2
13-a
236 ap4da
00
255
75
6-30
Figure 7: The Rosenbrock function where Left: plot f fxx) across epochs Middle: level set plot, Surface plot. SP2 in blue, SP22 in green, SGD is in yellow and Newt is in red.
Right:
D.1.3 LARGER DIMENSIONS
Here increase the dimension of the problems appraise the effect dimensions has the convergence of the methods, see Figure comparison in terms of epochs, and Figure i the main text for comparison in terms of time taken. We no longer compare Newton's method because it was exceeding our maximum allocated time. We find that when increasing the dimension, these problems become extremely challenging. To select the learning rate of each method, we used grid search over the first 100 epochs. For the SP2, 2, SP2 and SP methods we used the grid
[0.005, 0.01, 0.05, 0.1].
For Adam and SGD we used the larger grid
[0.00001, 0.00005, 0.0001, 0.005, 0.01, 0.05, 0.1].
Thus gave competitive advantage to SGD and Adam.
D.2 ADDITIONAL CONVEX EXPERIMENTS
We set the desired tolerance for each algorithm to 0.01, and set the maximum number of epochs for each algorithm to 200 in colon-cance, cion-cancer and 30 in mushrooms. To choose an optimal slack parameter À for SP 2 SP2 and SP 2 we test these three methods on uniform grid 0.001. The gradient norm and loss evaluated each epoch are presented in Figures 10 13 (see Appendix D). It can be seen that SP212 performs best when 0.9 in colon-cancer and À = 0.1 mushrooms, SP211 + and 2m2max perform best when 0.1 in both data sets. Therefore, set À 0.9 for SP2L2 + in colon-cancer and fix À 0.1 in other cases.
{0.1. 0.2, 0.9) with
Under the same setting in Section 6.3 grid = [0.001 0.01 0..1 0.055 with o 0. The gradient norm and loss evaluated at each epoch presented in Figures 14 15 (see Appendix D As observe, SP2max" always outperforms the
we also compare the SP 2max and SP 5m2max methods
SP 2m2aa x method.
29

---

Published as a conference paper at ICLR 2023
5P2plus
10
SP2
SPastus
107
Adam
Adom
10-4
Suncion
10-31
10-1
3000
Figure 8: The time plots for the Rosenbrock function (Left) and Levy N. 13 function (Right). SP2 is in blue, SP2 is in green, SGD is in yellow Adam and pink.
39.
20.11
130 200 180
200g
3300
Figure 9: Function value epochs for the P + (d 10) function with 0.5 (Left), the Rastrigin function (d 100) (Middle) and the Rosenbrock function (d 100).
colon-sancer-00 rew.d-ttterer---000000 1.000000-
grad-iter--re--11
colon-sancer D. reg
SP2L2"
SP2L2'
SP2.2"
10
SP2L1"
10
SP2L1*
10P
SP2L1*
SPmmox
5P2mox
SP2nax
10-1
10-11
10-2
10
2
10
100 Effective Passes
200
50
100
20
60
Effective Passes
Effective Passes
(a) À = 0.1 gradditer-rg--...
(b) 0.2
(c) À = 0.3
colon-cancer- A-grrrd-itee waddiit--rrg-----
SP2L2'
SPIL2'
10
10
SP2max
SP 5m2mx
1100
10--
101
SP2L1
10
10-2
SP2max
20
801
0
10
200
30
20
301
Effective Passes
Effective Passes
Effective Passes
(d) À 0.4
0.5
(f) A = 0.6
colon-cancen-O De gea---ter---- 03
colon-cancen-l De..rad--tee---geg 00w-03
colon-cancen-0 De gagrrditte--rge--- 00e-03
10A
10
10
10-1
10-1
SP2.2"
SP2L2
SP2.2'
SPoL11
10
SPOmax
10-2
SP2maxx
10:2
SP2max
100
200
0
100
2001
100
200
Effective Passes
Effectivve Passes
Effective Passes
(g) A = 0.7
(h) À 0.8
(i) A 0.9
Figure 10: Colon-cancer: gradient norm each epoch with different
30

---

Published as a conference paper at ICLR 2023
colon-cancer-D 0-loss-iter-reg-- 1.00e-03
colon-cancer-O lo-so-tter-reg-111111 000e-3
colon-cancer-D 0-loss-iter--eg- 00e-03
10
SP2L2*
SP2L2*
SP2L2
SPIL1"
10
SP2L1'
SPIL1"
5P2max*
5P2max
5P2max*
10-1
10-)
10
100
200
50
100
20
10
60
Effective Passes
Effective Passes
Effective Passes
(a) À = 0.1
(b) À 0.2
(c) A = 0.3
colon-cancen.0 0.0-loas- rew.rree--1.00
1.00
Calon-canee--oe 0.O. wew.erree-..00000
1.000-0000000 03
colon-cancee caom-ccnnen--0 0.0 0.0-loos iter 1.00e
SP2L2'
SP2L2'
10
SP2L1*
10%
SP2L1*
SP2mwx
10
111-
5P2L2"
SP2max
10
10
20
23
40
Effective
Effective
Effective
(d) A 0.4
(e)
0.5
(1 A 0.6
colon-cancer-D les-- 03
colon-cancer 0.0 O-loos-iter--ess reg-eer-re---eee 1000-03
colon-cance--e lol-oos--te -ter-rteerr--- reg- 00e
10
10
10
105
104
10
10
10
SP212"
10-1
SP212
10
5P212"
SP2L1
SP2L11
SP2L1'
SP2exx*
SP2max
10
10-
100
200
Effective Passes
Effective Passes
Effective Passes
g
0.7
(h) 0.8
(i)
Figure 11: Colon-cancer: loss at each epoch with different X.
31

---

Published as a conference paper at ICLR 2023
mushrooms --grad--ter---e-- 1eaerrre--1-0-ee- 1.00e-03
mushrooms-D 0.C C-grad-iter--ee-- 000e-03
mushrooms 0. (-grad-iter--ee-- 1.0e-03
SP2L2"
SP2L2"
SP2L1"
SP2L1"
SP2max
SP2max
[|
10-1
SP2L2"
SPOI
SP2max
10-3
10
0.0
2.5
5.0
1.5
20
10
Effective Passes
Effective Passes
Effective Passes
(a) À = 0.1
(b) A 0.2
(C) A 0.3
mushrooms-O 0-pad--te--------------1- 00e-03
mushrooms-0 D-grad-iter--re:: 000-03
mushrooms- D-grad-iter--eg--
SP212"
SP212"
SP2L1'
SPaL1
SP2max
WO MA
SP2max"
100
5P2L2
10-
10-2
10
SP2mas
d0
40
Effective Passes
Effective Passes
Effective Passes
(d) À 0.4
0.5
X
0.6
mushrooms. 1...praditee---e.
00c-03
mushrooms-O O C-grad-iter wedddd---eeeeeee regr--e--1------ 00
mushrooms O-grad-iter--ee 00e-03
10P
106
SP2L2*
SPOI1*
A Mom
MN
10-1
10
SP2L2
SP2L1"
10-3
SP2L1"
10
SP2max
SP2mas
10
40
20
20
40
Effective Passes
Effective Passes
Effective Passes
(g) A = 0.7
(h) 0.8
(i) X 0.9
Figure 12: Mushrooms: gradient norm each epoch with different X.
32

---

Published as a conference paper at ICLR 2023
mushrooms- 0.0 1-0--oss-ite----ee 1.00e
mushrooms 0.0- loss iee-iiterrrrlllee 1.00e
mushrooms 0.0-loss Dose-iter-reg 1 0.000
10a
10
SP2L1
SP2L1
SPaL1
SP2max
5P2max
SP2max
10-1
10-2
10-1
0.0
2.5
5.0
7,5
40
Effective Passes
Effective Passes
Effective Passes
(a) À = 0.1
(b) A 0.2
(c) A = 0.3
mushrooms-D O-loss-iter--ee- 00e-03
mushrooms- O-loss-ite---eg- 000-03
mushrooms- O- 00e-03
10a
10
10
SP2L2"
5P2L2*
SP2L1
SP2L1
SP2max
SP2max
Faa"))aa")
SPa1 2
SP2L1 5P2max
Me Mally
10-1
10-2
10
10
20
d0
10
Effective Passes
Effective Passes
Effective Passes
(d) À 0.4
(e) 0.5
mushrooms-- O-loss-iter-reg-1111 00e-03
mushrooms- 0.0-000-00--0 --t-s---ite-------1-1 00e-03
mushrooms-O 0.0---os--tte---re------- 100e-03
SP2L2*
SP2L2'
10a
SP2L21
SP2max
SP 5P2mmxx
SP2mac
109
10
10-7
20
40
201
40
20
40
Effective Passes
Effective Passes
Effective Passes
A 0.7
(h) 0.8
(i) A 0.9
Figure 13: Mushrooms: loss at each epoch with different X.
33

---

Published as a conference paper at ICLR 2023
colon-cancer-O O-grad-iter--eg 00++00
colon cancer- O. grad-iter.rge. reg. 00e
colon-cancer- cancer grad reg. 0
SP2nxx
5P2max
5P2max"
10
5P2max
101
5P2max
10M
[|//
1
10
10
10
20
60
40
20
60
Effective Passes
Effective Passes
Effective Parses
(a) 0.001
(b) À 0.01
(c) À 0.02
colon-cancer--.. O- grad. reg-- D 00
cplon-cancer-B0 O O g-gad-iter--ep- wew. 0.000..000 000
oplon-cancer-1 - wra.d--ttt-rgegeea.. 00
SP2mas
109
SP2max
10P
10
fillee
10-1
10-1
5P3mas
SP2mas
10:2
5P2max
10
5P2max
201
60
0
20
801
60
60
60
Eflective Passes
Elfective Passes
Effective Passes
(d) À = 0.03
(c) À = 0.04
(f) A = 0.05
Figure 14: Colon-cancer; gradient norm at each epoch with different A.
colon-cancer-- D-loss-tter-re-- 00e+000
colon-cancer-O (-lost-iter-ep.-
colon-cancer-- f--oos- koss-iter--eg-D
5P2max
10"
SP2max
10
SP2max" SP2max
SP2nax
SP2max
//
10-1
10
10
20
10
60
20
60
Effective Passes
Effective Passes
Effective Passes
(a) 0.001
(b) À = 0.01
(c) À 0.02
0olon-cancer-00--oooo 0-los--tte----ge 0 -0
colon-cancer-00 -------tee--re---ee-- 1e00:----eerr--0000000.00000.00. 00
colon-cancer-- 0.ee--000---0 --los---ter--reg-eee-e-- -ee-- 0.00e-000
SPanas
10
SP2max
109
104
201
10-1
10"
10-1
10-1
SP2max" SP2max
10
10-2
SP2max
20
40
60
0
20
40
60
20
40
60
Effective
Passes
Effective Passes
Effective Passes
(d) A = 0.03
(e) X = 0.04
(f) A = 0.05
Figure 15: Colon-cancer: loss at each epoch with different X.
34

---

Published as a conference paper at ICLR 2023
mushroomm-- 3-grad-iten-re--- 00
mushrooms 3-grad-iter--eg-1 000=-3
3-grad--teer--e---
5GDM0.3
SGDM0.3
5PM0.3
10-1
SP21 M0.3
SP2nixx M0.3
5P2-M0.3
SP2L1 M0.3
IV
10-1
SPMO
SGDMO.3
10
SP2 M0.3
SP2L2 M0.3
SP3mee MM.
1M0
10-2
ADAM
SP2L21M0.3
ADAM
SPoI MM0.3
ADAM
10
10
0.0
2.5
5.0
7.5
30
20
Effective Passes
Effective Passes
Effective Passes
mushhooam--O www.p/amm-.....ss------o..... 3-
mushrooms-D 3-loss-iter--ree 00e-03
mushrooms-O 3-loss-iter-reg-- 00e-03
10y
SPMD
SCDM0.3
10
SPMM0
SGDM0.3
10
SGDMola
SPM00.
SP2
SP7 MMh3
1624/1199
SP2L2' M0.3
SP2L2 Mo.3
SP2L2 MM0
SP2L1"M0.3
SP2L1 M0.3
SP2mas
SP2iax M0
SP3
ADAM
ADAM
ADAM
10-2
10-3
0.0
2.5
5.0
755
10
20 Passes
10
20
Effective Passes
Effective
Effective
Passes
Figure 16: Mushrooms: gradient norm and loss at each epoch with momentum being 0.3.
colon-cancce-ruriime..k
mushhromms-uniimeeMM0
SGD
SGD
Bunning time
100
SP2
SP2*
SP212"
SP2
SP2max
SP2max
10a
10-1
000
0.002 0.004 0.006 0.008
0.000 0.002 0.004 0.006 0.008 Regularization
Regularization
Figure 17: Running time in seconds.
35


Reviews:
[{"review_id": "WhCvbJQPlWT", "reviewer": "Reviewer_fkL2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers the problem of solving finitely many non-linear\nequations, under the assumption that a solution exists. The key idea\nis projecting the current iterate onto the hyper-surface defined by\nthe quadratic approximation of the current equation of choice. The\nfirst proposed method (SP2-GLM) considers the case where the non-linear equation is the\ncomposition of some loss with a linear function. The second method\n(SP2+) further linearizes the quadratic approximation. Some\nconvergence theory is derived for the two methods (Section 4). Extensions to the\ncase where there is an \"approximate\" solution are considered (Section\n5). And experiments are demonstrated on several problems (Section 6).", "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\". \n\nAt this moment, I made a borderline score, \"marginally below the acceptance threshold\".\n\nNote 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.\n\n", "strength_and_weaknesses": "\n# Strength\nThe paper enjoys the following strength:\n\n- The paper considers an interesting problem of solving non-linear\nequations, which is potentially important and relevant to some\nreaders of ICLR.\n\n- The paper is written clearly, and the proposed method consists of a\n  simple idea.\n\n- The paper covers several aspects of the proposed methods, including\n  convergence theory, experiments, and extensions to the case of\n  *quadratic with slack*.\n\n- Full proofs are in the appendix in a single file, which makes the\n  the paper easy to navigate.\n\n# Weakness\nThe weakness of the paper manifests itself from several aspects:\n\n- The assumption of Proposition 1 is too strong, which makes it not very\n  interesting. First, it is a bit weird that the global minimizer\n  $w^*$ has already shown up in the definition of $f_i$ (21), which\n  is quite artificial. Second, $f_i$ is already quadratic,\n  and local quadratic approximation does not make too much sense.\n  Third, $H_i$ is positive semidefinite, which means that the\n  quadratic constraint $f_i(w)=0$ is equivalent to the linear\n  constraint that $w$ should lie in the null space of $H_i$ (if $H_i$\n  is rank-deficient). This makes the convergence analysis trivial, as\n  it is reduced to the situation that we already know (e.g., from the\n  analysis of the Kaczmarz method). Finally, the discussion on the case\n  where $H_i$ is invertible is misleading: In this case $H_i$ is\n  positive-definite, the equation $f_i(w)=0$ has a unique\n  solution, and one does not need to do a projection as solving\n  $f_i(w)=0$ directly would suffice.\n- Proposition 2 is a bit mysterious. Since it follows directly from\n  Gower et al. (2021), that should be mentioned explicitly right after\n  Proposition 2. Besides this, SP2+ itself is also mysterious and not\n  very well motivated: In (18), intuitively, what is the benefit of\n  considering a linearization of a quadratic approximation, instead of\n  a linearization of the original function? That question also applies\n  to Section 5.\n\n- The two propositions stand in contrast to the name SP2 and very\n  much also the purpose of the paper: Under the given assumptions the\n  paper is essentially analyzing first-order methods (in a trivial\n  way, based on prior works). The paper would be significantly\n  strengthen if there is some solid analysis that reveals superlinear\n  or quadratic rates of the proposed idea, as is typical for\n  second-order methods.\n\n- Section 5 would be a powerful technical contribution of the paper\n  if it were more well-motivated. For example, what is the benefit of\n  having two different slack formulations (L1 and L2)? What is the\n  reason of resorting (30) for solving the L1 slack problem? After\n  all, they seem to perform very similarly in the experiments.\n\n\n- There are several sub-optimal aspects in experimental evaluation.\n  First of all, the comparison to Newton's method is unfair, as it is well known\n  that standard Newton's method is not always globally convergent. A slightly\n  more considerate option is to compare with the damped Newton's\n  method (as described in Boyd's book), which is guaranteed to\n  converge, at least in the (strongly) convex case. Second, the\n  plots should not be *function values versus epochs*, but it should\n  be *function values versus running time*; the reason is that the\n  methods under consideration have different time complexities at each\n  iteration. Third, by just reading the paper, the reader has no idea\n  how large the dataset in each experiment is. Since Sections 1\n  and 2 make it an important point to design incremental methods that\n  can work with mini-batches, it is important to run experiments on\n  large datasets for which traditional offline methods run out of\n  memory (e.g., Newton's method), otherwise, there is no reason to believe that online methods\n  could perform better than offline methods. E.g., online methods\n  would have very large variances and could easily fail in the case\n  where some equation is far from being satisfied at the global minimizer.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LimqCYqp4D", "reviewer": "Reviewer_DF7u", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.  ", "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. ", "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. \n\nThere 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. \n\nOther comment: The detailed algorithms should be stated separately in a box to avoid any confusion for the readers. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8dn66LZPpH-", "reviewer": "Reviewer_etGz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. \n", "summary_of_the_review": "Comments: \n1- 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. \n\n2- 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. \n\n3- 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. \n\n4- It will be nice to first give the original formula of SP method before eq 4.   \n", "strength_and_weaknesses": "Empirically their proposed methods shows outperform other existing optimization methods in the literature. \nWeakness: their theoretical analysis holds just for too limiting settings. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster