A Stochastic Newton Algorithm for Distributed Convex Optimization
Authors: Brian Bullins
Kumar Kshitij Patel
Ohad Shamir
Nathan Srebro
Blake Woodworth
Venue: NeurIPS 2021 Poster (2021)
Keywords: Distributed Optimization
Stochastic Optimization
Federated Learning
Newton's Method

Abstract: We propose and analyze a stochastic Newton algorithm for homogeneous distributed stochastic convex optimization, where each machine can calculate stochastic gradients of the same population objective, as well as stochastic Hessian-vector products (products of an independent unbiased estimator of the Hessian of the population objective with arbitrary vectors), with many such stochastic computations performed between rounds of communication.  We show that our method can reduce the number, and frequency, of required communication rounds, compared to existing methods without hurting performance, by proving convergence guarantees for quasi-self-concordant objectives (e.g., logistic regression), alongside empirical evidence.

A Stochastic Newton Algorithm for Distributed Convex Optimization
Brian Bullins Toyota Technological Institute Chicago bbull 1 ins@ttic edu
Kumar Kshitij Patel Toyota Technological Institute Chicago skpatel@ttic edu
Ohad Shamir
Weizmann Institute of Science ohad. shamir@weizmane ac
Nathan Srebro
Blake Woodworth Toyota Technological Institute at Chicago blake@ttic. edu
Toyota Technological
Institute at Chicago nati@ttic. edu
Abstract
We propose and analyze a stochastic Newton algorithm for homogeneous dis- tributed stochastic convex optimization, where each machine can calculate stochas- tie gradients of the same population objective, well as stochastic Hessian-vector products (products of an independent unbiased estimator of the Hessian of the population objective with arbitrary vectors), with many such stochastic computa- tions performed between rounds of communication. We show that our method can reduce the number, and frequency, of required communication rounds compared to existing methods without hurting performance, by proving convergence guarantees for quasi-self-ccocordaal objectives (e.g., logistic regression), alongside empirical evidence.
Introduction
Stochastic optimization methods that leverage parallelism have proven immensely useful in modern optimization problems. Recent advances in machine learning have highlighted their importance as these techniques now rely millions of parameters and increasingly large training sets.
While there are many possible ways of parallelizing optimization algorithms, we consider the intermittent communication setting (Zinkevich et al., 2010; Cotter al., 2011; Dekel al., 2012; Shamir et al., 2014; Woodworth et al., 2018, 2021), where M parallel machines work together to optimize objective during /t rounds of communication, and where during each round each machine may perform some basic operation (e.g., access the objective by invoking some oracle) K times, and then communicate with all other machines. An important example of this setting is when this basic operation gives independent, unbiased stochastic estimates of the gradient, in which case this setting includes algorithms like Local SGD (Zinkevich al., 2010; Coppola, 2015; Zhou and Cong, 2018; Stich, 2019; Woodworth et al., 2020a), Minibatch SGD (Dekel et al., 2012), Minibatch AC-SA (Ghadimi and Lan, 2012), and many others.
We are motivated by the observation of Woodworth et al. (2020a) that for quadratic objectives, first-order methods such as one-shot averaging (Zinkevich et al., 2010; Zhang al., 2013) a special case of Local SGD with single round of communication can optimize the objective to a very high degree of accuracy. This prompts trying to reduce the task of optimizing general convex objectives to short sequence of quadratic problems. Indeed, this is precisely the idea behind many second-order algorithms including Newton's method (Nesterov and Nemirovskii, 1994), trust-region methods
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table Convergence guarantees for different algorithms in the intermittent communication setting. Notation is as follows: H: smoothness, U: sear--order-smoohness a: stochastic gradient variance; stochastic feestorn-vector product variance; g(æ; z): stochastic gradient oracle; h(r, u; z'): stochastic Hessian-vector product oracle (see Section 2 for complete details). For the sake of clarity, we omit additional constants and logarithmic factors.
Algorithm
Assumption, Oracle Access
Convergence Rate
(Reference)
Local SGD
H
B VMKR
2 R3/3
A1 g(1; x)
(Woodworth et al., 2020a)
KR
H KR VMKR
FEDAC
A1 g z)
(Yuan and Ma, 2020)
+ min
g
///2g//2/3/2 KVAR
KVPR
Local SGD
HB²
aB
U
A3 -order Smooth)
(Yuan and Ma, 2020)
Kft
VMKR
K
g(1; z)
FRDAC
HB² VMKR
A3 -33dd-order Smooth) -order
KIS
(Yuan and Ma, 2020)
HV 9/2 g4/3
UV/ ga/3 K4/3
g =)
M-/5K1/3R
FEDSN
exp. decay +
H KR
oB
+ VKR
AB
A2 (QSC)
(Theorem 1)
VMK
g(x; 2), h(2, u,&²
(Nocedal and Wright, 2006), and cubic regularization (Nesterov and Polyak, 2006), as well as methods that go beyond second-order information (Nesterov, 2019; Bullins, 2020).
Computing each Newton step requires solving, for convex F, a linear system of the form F²F(z)Az
(z)z). Unfortunately, this may be prohibitive in high dimensional setting, and may not even be feasible if F is only accessible through stochastic oracle in a streaming fashion, as is the case in the setting we consider. To avoid these issues, we reformulate the Newton step as the solution to a convex quadratic problem, minar _ Ax F(r) + F Ar., which we then solve using one-shot averaging. Conveniently, computing stochastic gradient estimates for this quadratic objective does not require computing the full Hessian matrix, as it only requires stochastic gradients and stochastic Hessian-vector products. This attractive computationally since, for many problems, the cost of computing stochastic Hessian-vector products is similar to the cost of computing stochastic gradients, and both involve similar operations (Pearlmutter, 1994). Furthermore, highlighting the importance of these estimates, recent works have relied on fessian-vectte products to attain faster rates for reaching approximate stationary points in both deterministic (Agarwal et al., 2017; Carmon et al., 2018) and stochastic (Allen-Zhu, 2018: 8; Arjevani et al., 2020) non-convex optimization.
In the context of distributed optimization, second-order methods have shown promise in the empir- ical risk minimization (ERM) setting, whereby estimates of F are constructed by distributing the component functions of the finite-sum problem across machines. Such methods which leverage this structure have since been shown to lead to improved communication efficiency (Shamir et al., 2014; Zhang and Xiao, 2015; Reddi et al., 2016; Wang et al., 2018; Crane and Roosta, 2019; Islamov et al., 2021; Gupta et al., 2021). An important difference, however, is that these methods work in a batch setting, meaning they allow for repeated access to the same K examples each round on each machine. giving a total of M K samples. In contrast, we work in the stochastic (one-pass, streaming) setting, and so our model independently samples fresh set of M K examples per round, for total of M K R examples (see Appendix G.5 for an empirical comparison).
Our results
Our primary algorithmic contribution, which we present in Section 3 (and include sketch in Ap- pendix A), is the method SWW.AADD-SOOHSTTII--AACC (FEDSN), distributed approximate Newton method which leverages the benefits of one-shot averaging for quadratic problems. We pro-

---

vide in Section 3, under the condition of -uasisself-onneordance (Bach, 2010), the main guarantees of our method (Theorem 1). Section 4 we show how, for some regimes in terms of M, K, and R, our method may improve upon the rates of previous first-order methods, including FEDAC (Yuan and Ma, 2020). In Section 5, we compare a more practical version of our method, FEDSN-LITE (Algorithm 6) against the other methods, showing we can significantly reduce communication compared to other first-order methods.
Preliminaries
We consider the following optimization problem:
min F(x),
(1)
#ER
and throughout we use F* denote the minimum of this problem. We further use |I-Il to denote the standard & norm, we let || = vx Az for a positive semidefinite matrix A, and we let denote the identity matrix of order d.
Next, we establish several sets of assumptions, beginning with those which are standard for smooth, stochastic, distributed convex optimization. We would note that working in the homogeneous distributed setting (i.e., each machine may access the same distribution), rather than the heterogeneous setting (Khaled et al., 2019; Karimireddy al., 2019; Koloskova al., 2020; Woodworth et al., 2020b; Khaled et al., 2020). Assumption (A1).
(a) F is convex, differentiable, and H-smooth, ie., for all N.y R2, F(y) S F(x) FF()) (y 2) 2 lly 2
H
(b) There is a minimizer x² E arg min, F(x) such that || B.
(c) We are given access to stochastic first-order oracle the form of an estimator g I& x Z + Rd, and distribution D Z such that, for any IR queried by the algorithm, the oracle draws D, and the algorithm observes an estimate g(x; 2) that satisfies:
(i) g(æ; z) is an unbiased gradient estimate, i.e., Egg(1; VF(x). (ii) g(æ; z) has bounded variance, i.e., Exllg(r; =
In order to provide guarantees for Newton-type methods, will require additional notions of smoothness. In particular, we consider a-quasi--elf--cocorrde convex and three-times differentiable F is satisfied for when, for all x E dom(F). Rd.
(QSC) (Bach, 2010), which for
V F(r)(u, u, u|l s a|| F(=)(u)
where we define
ak
V ((:))(1, .2,..., wR] =
Oun Sug...., Ou. 11=00.t200....444. F(r + f1 + f2 + +.... tg
for à 2 1, i.c., the h directional derivative of F at x along the directions u1 u2...... Ug. Related to this is the condition of a-self-comcorddacee which has proven useful for classic problems in linear optimization (Nesterov and Nemirovskii, 1994), whereby for all x dom(F)) Rd.
V F( u, u|l 2a (V2 (V2F(z)) F())(u, 3/2
Though quasi-sell-conncrddance is perhaps brought its usefulness to light in the context of machine learning (Bach, 2010; Karimireddy et al., 2018; Carmon et al., 2020). Notably, for logistic regression, i.e., problems of the form
widely studied as self-concordance,, recent work has
min F F(x)
Σ log (1 +ee -e-b(...))) 1=11
N
we observe that is not self-concordant, thus highlighting the importance of introducing the notion of QSC for such problems, and indeed, neither of these conditions implies the other in general."
holds with a S max; [[baa; Interestingly, this function
For the other direction, note that F(x) In(x) is I-self-concordant but not quasi- suascsealf-ooncordantt

---

We now introduce further assumptions in terms of both additional oracle access and other smoothness notions. The following outlines the requirements for the stochastic Hessian-vector products, though we again stress that the practical cost of such an oracle is often on the order of that for stochastic gradients (Pearlmutter, 1994; Allen-Zhu, 2018).
Assumption (A2). In addition Assumption we have:
(a) F is three-times differentiable and o-quasisselfccoooordamn i.e., for all 2, u, E Rd, V F()))u, u, u|| S al]e||/V² F[)]]] ul.
(b) We given access stochastic Hessian-vecton product oracle in the form of an estimator h The x Rd x 2 + TRd,, and a distribution 'D on such that, for any pair x, u E Thd queried by the algorithm, the oracle draws z' ~ DD and the algorithm observes estimate hax, u; 2 that satisfies:
(i) h(x, u; 2/) is an unbiased Hessian-vector product estimate, i.e., Ezr((r, = (z)u.
(ii) h(x, z') has bounded variance of the form u; ==)
Meanwhile, other works (e.g.. Yuan and Ma, 2020) require different control over third-order smooth- ness and fourth central moment. We do not require this ussumption in our analysis, and include it here for comparison.
Assumption 3 (A3). In addition Assumption 1, have:
(a) F is difee-differentiable and --shirddordde--mootth i.e., for all x, Rd, F(y) s F(x) VF(x) (y - x) ( (V2 x), x) + lly z=13.
(b) g(æ; 2) has bounded fourth central moment, i.e., Eg [g(2; Fx())| sot
3 Main results
We begin by describing our main algorithm, FEDSN (Algorithm 1). Namely, our aim is to solve convex minimization problems min, F(x), subject to Assumption 2.
Algorithm 1 FEDERATED STOCHASTIC-NEWTON FEIDRATEE--SOCCCASTICCCC
a.k.a, FEDSN(
(Operating on objective F(-) with stochastic gradient ((3--) and Hessian-vector product h(::.;)
oracles.)
Input: E IR.
Hyperparameters: T: main iterations; and E: local stability (see Table 4). Output: Approximate solution to min, F(x) for t = 0, 1,.... T 1 do
See Theorem 1
D Approx. min as +f
fu 2 V2F(x
b4 = CONSTRAINED SUAEEED---AAAAAAAALIAAAIA SOLVER(Z.)
+VF(Iz)
Update: Ø1+1 = 2, + AT
Return: FT
We will rely throughout the paper on several hyperparameter settings and parameter functions, which we collect in Tables 3 and 4. Recall that M the amount of parallel workers, R is the number of rounds of communication, K is the number of basic operations performed between rounds of communication, and H, B, a, a, and p are defined in Assumptions and 2. Among our assumptions, we note in particular the condition of weweiissee--ccooonncecc under which several works have provided efficient optimization methods. For example, Bach (2010) analyzes Newton's 's method under QSC conditions, in manner analogous to that of standard self-concordance analyses, to establish its behavior in the region of quadratic (log log(1 log(1/e)) /e)) convergence. More recently, both Karimireddy et al. (2018) and Carmon et al. (2020) have presented methods which rely instead on trust-region approach, whereby, for given iterate x2, each iteration amounts to approximately solving a constrained subproblem of the form min Ax]|Se e AAx V²F(x, +
v F(xx)) T Ar, for some 2 and groblem-dependent radius 0. This stands in constrast to the

---

Hyperparameter Setting
Description
log ((1)
==
(7))
a5
Main iterations
(for Ç = 4096 + 4(80 + log K + 24log(1 + 2))))
Momentum
= min
32B 7
log (TK), 1
Trust-region radius
5
{ = exp(ar)
Local stability
A = max
2eH K-2-
2p VK
32eH log (51200)
40y 200/llog// (lo((12000)
VK
Regularization bound
220 VMK
320g
8 K-16
PVMK
N = 1 + 6 log #(B+5TF)
Binary search iterations
2 3
C log [1og2 N1 (7 [++ CH
80 B45TT)
Reg. quadratic repetitions
AF
Table Hyperparameters T. F. X, N. and C, used by FEDSN and its subroutines.
Parameter Function
Description
K $ 3 max { + X, p² k
71
Reg. quad. stepsizes
(A) =
1
K > - max
EH + X, d²
and k 2
x( max EH ) x))
(1 - Amaa + ) -
K < } max
EH + X, p²
x
K 2 max
EH + X, &/ and 1s 2
Reg. quad. weights
(A)
E X x²)
{
A max
k K
K 2 max
( EH 2) and k 2
Table 3: Parameter functions T)e (A) and wx (A), as used by FEDSN and its subroutines, where & is as defined in Table 4, and where 7/x denotes vy()) : min EH+
unconstrained minimization problem min Ar (2 VF())) Az. which, may recall, forms the basis of the standard (damped) Newton method. Carmon et al. (2020) further use their trust-region subroutine approximately implement certain ball minimization oracle, which they combine with an acceleration scheme (Monteiro and Svaiter, 2013).
These results show, high level, that long as the radius of the constrained quadratic (trust-region) subproblem is not too large, it is possible to make sufficient progress on the global problem by approximately solving the quadratic subproblem. Our method proceeds in similar fashion: each iteration of Algorithm 1 provides an approximate solution to constrained quadratic problem. To begin, we follow Karimireddy al. (2018) in defining -lr)-local (Hessian) stability.
Definition Let IR+ + R We say that a wwice-differentiable and convex function F is -loraly stable if. for any > 0 and any I, y Rd (x + y) such that | yll S and || - vllvaF(z) > we have ||x vllvar(w) S 8(r)]l - y v)(vaF(2)
As the next lemma shows, quasi-self-comcordane is sufficient to provide this type of local stability.

---

Lemma 1 (Theorem I (Karimireddy et al., 2018)). If F is c-guasi-eff--concrrtnn, then F is 8(r) exp(ar)-locally stable.
The advantage of local stability that it ensures that approximate solutions to locally-defined constrained quadratic problems can guarantee progress on the global objective, and we state this more formally the following lemma. Note that this lemma is similar to (Theorem IV Karimireddy et al., 2018), though we allow for an additive error in the subproblem solves in addition to the multiplicative error, and its proof can be found in Appendix B.
Lemma Let F satisfy Assumption 2 and 8(r)-locally stable for d To E Id be as input FEDSN (Algorithm 1). let
R Rt, let let 8 E [0,1], and define Qi(Ax) = B(5c) Ax T V2 F()(()) ( Da + (F())) Dx, where It is the t iterate of Algorithm 1. Furthermore, 3
suppose we are given that in each iteration of Algorithm 1, ||ATell S 5e and
min Qr(Ax) S (Q.00) Ar:|AAu Stc
EQ((AT;)
(,(0)) min An:|AAlls
Pe(dx) tc.
for O. Then for each T 2 0, Algorithm 1 guarantees
EF(xT) - F E ( - F*] Fx]exp[ (
Tc(1-8)
2B5(2c)d(
+
(B8(2c))((c)
c(1 (1-0)
We have now seen how to turn approximate solutions of constrained quadratic problems into an approximate minimizer of the overall objective. We next need to ensure that the output of our method CONSTRAINNED-UUADDATIIC
(Algorithm 2) meets the conditions of Lemma As previously discussed, Woodworth et al. (2020a) showed that first-order methods can very accurately optimize unconstrained quadratic objectives using a single round communication; however, here we need to optimize quadratic problem subject to norm constraint. Our constrained quadratic solver is thus based on the following idea: the minimizer of the constrained problem ming:|læe|se ((x))
the same as the minimizer of the unconstrained problem min, Q(x) + & ||>/|| & for some problem- dependent regularization parameter X*. While the algorithm does not know what X should priori, we show that it can be found with sufficient confidence using binary search. Lemma 3, proven in Appendix C, provides the relevant guarantees.
Lemma 3. Let F satisfy Assumption 2. let x be as input to CONSTRANNEDQQUADRRTTI. (Algorithm 2), let & be as in Table 4, define
č (uu = FFF(x)) + VF(x) 2
Qx(u) = 2" (CV + AIja+ VF(x) u,
" = min (u),,
r*()) = =|1
and let dr denote, for any r. > 0, the value such that r ((r)) =r. Let ús be the output of Algorithm 2 for hyperparameters F. E, X N and as Table and suppose the output ü, of REGULARIZED- QUADRATIC-SOLVER X) satisfies for all X 2 X that
[+x min Qx(u)= S c(A) = X(r X(r*(A)²+ +2)
800
Then || < 57 and
f Q(u) + ((Aar) +
RQ(
2(0) min Q(u) < 4 a 3f
min
4
We now show that using one-shot averaging (Zinkevich et al., 2010; Zhang et al., 2012) with M machines-i.e.. averaging the results of M independent runs of SGDDsuffit to solve each quadratic problem to the desired accuracy. The following lemma, which we prove in Appendix D, establishes (Algorithm 3) supplies Algorithm with an output á that
that AAA.UUAAAREEEE-QAARRAAT----- satisfies the conditions of Lemma 3.

---

Algorithm 2 CONSTRAINED-QUANN DAW.AAAEEDDTAAAAAATTSSSLLLEEEEEE
(Operating objective F()) with stochastic gradient (15-) and Hessian-vector product h(())))
oracles.)
Input: x Rd.
Hyperparameters: F: trust-region radius; &: local stability; ): regularization bound; N: binary search iterations; and C: reg. quadratic repetitions (see Table 4). Output: Approximate solution to min w:|lulls $ T F2F()
D See Lemma
A
(
n= in
while A, # do
A = Median(A,)
for 1..... do
a(t.c) = REGULARIZED SUW.LIEDDQUUARRATI-SSSLEEEERRR A()) if { (((())) [ E r }r] > & then
ū- REGULARIZED-QUI A.GU.RRZD.QQAADRNCCSSSVVRR
(0)
Return: á = min 1, Gr ü
|
else if {āluee) ||
5
>
C
then
2
A;-1 = (X E A; : X < <(0
else if {(llte); || > ]7] > C then
2
A,1 (X A X> 10)
else
Return: á =0 1 i+i1
REGULARIZED QUADRATIC-SOLLVERIIA
Return: min 1, 3F
|lll ū
Lemma 4. Let F satisfy Assumption 2, let x E Rd. X E BC be as input to REGULARIZED- QUADRATIC-SOLVER (Algorithm 3), let 3u (EV2F(((( AIJu+ VF(x) u, let Q3 = min, Qx(u), let n* == arg min, Qx(u). and let stochastic first-order and stochastic Hessian- vector product oracles for F, as defined in Assumptions I and 2, respectively, be available for (Algorithm 4), for either Case I
each call to REGULARIZED- REGULARRZZD--UUADRATTCC-C Sefferent-SSapllle or Case 2 Sample., Let ú, as output by Algorithm 3, be a weighted average of the iterates of M independent runs of SGD with stepsizes ()(A), -KK- (A), i.e.
Dmm Σk
M KK-
2k=o wauk. Then, for both Cases I and 2,
M 2=z
2max {H + X, { |1uu min K exp K+1 min
12 }}}} 1 5H++
A
2(0² (1²1)
if K < 2 max
Ell + X, 4
AMK
(Q) S
966| || exp(
K min
2 TH
2
96(a + w' 11
Kf > 3 max
EH X, 5}
Our analysis for Algorithm 3 is based on ideas similar to those of Woodworth et al. (2020a), whereby may access the stochastic oracles via REGULARIZED- DEW.ARRIIEE-QAAATTIICC. QUADRATIIC-GAADEENT ACCESS (Algorithm 4). However, additional care must be taken to account for the fact that Al- gorithm supplies stochastic gradient estimates of the quadratic subproblems Qx(u) as per the oracles models described in Assumptions and 2. Thus, the estimates based in part on stochas- tic Hessian-vector products- have variance that scales with the norm of the respective iterates of Algorithm 3 (see Assumption 2(b.ii)).
the algorithm may
7

---

Algorithm 3 SWW.AIIIZEDDQAAAAATI-SSSSSSO X)
(Operating objective F()) with stochastic gradient ((5+) and Hessian-vector product h(s))))) :)
oracles.)
Input: a Rd, AERt
dlppepaarameters: 3: momentum; a: local stability; and parameter functions 17 (A), wa (A) (see
Tables and 4).
Output: Approximate solution to min, Qx(u) = 2/"" (EV2F(x)) + 21 + (=) u
> See
Lemma 4
Initialize: uy "o...., M0g M 0
Initial iterates each machine
for Each machine m ......
..: .M in parallel do
for k = 0,.... K
do
Tuu ; 2/ 2k m) )²) REGULARIZED -
" "kt1 uk mh (A) zm =k +1 (1>00)((UT -
Return: EAST (x(A) Em=r Ex= wx( (A)
We also note two possible cases for the oracle access: Case (Different-Samples) in Algorithm requires both a call to stochastic first-order oracle (which draws 2 ~ DD and a call to a stochastic Hessian-vecte vector product oracle (which draws a different ~ D); while Case "Same-Sample both stochastic estimators to be observed for the same random sample only a small constant factor the final convergence rate, and we base our practical method on this single sample model. We refer the reader to Appendix G.4 for discussion of these settings.
allows D. These cases differ by
Algorithm 4 CEGGULARIZED-UAADRRRI CAAADRRTCC-GRDDDEENTAACCCSSCCCC u,
(Operating on objective F()) with stochastic gradient g(5-) and Hessian-vector product h(:i-.)) oracles.)
Input: 2, u E RR, A R+
Hyperparameters: E: local stability (see Table 4).
Output: 7(,; s.t. Eg 2') (u) and Eg, 11 VQx(u)]2 < o² P||l
Case 1: Different-Samplee (z, a' drawn independently for each stochastic oracle)
Query the stochastic first-order oracle at (as in Assumption 1(c)), so that the oracle draws D. and observe g(;; 2)
Query the stochastic Hessian-vecte product oracle at z and u (as in Assumption 2(b)). so that the oracle draws z' DD and observe l((,, u; =')
Case 2: Same-Sample (Same = z used for both stochastic oracles)
Query the stochastic first-order oracle at (as in Assumption 1(c)), so that the oracle draws D, and observe g( =)
Query the stochastic Hessian-vecter product oracle at æ and u (as in Assumption 2(b)) for z, and observe f(,,, u; 2')
(u; 2, =/) = Eh(x, uq z') + Au + g(x;
Return: (uu; 2,
Finally, having analyzed Algorithms 1, 2, 3, and 4, we may put them all together to provide our main theoretical result, whose proof can be found in Appendix E.
Theorem 1. Let F satisfy Assumption 2. Then, for K 175 and R > 52(1), and for hyperparameters T, F, &, X, N, C and parameter functions (A), wx(A) as in Tables 3 and 4, the output of FEDSN (Algorithm 1) with initial point 3o E Rdd, using Algorithms 2, 3, and 4 (for both Cases I and 2)
We add heavy- ballooyal/Polyyk momentum in this step with momentum parameter B. Our theoretical results do not require any momentum, and thus FEDSN is analyzed for 3 = O. For our experiments we compare the algorithms both with and without momentum, i.e., 0 optimally tuned (0.1, 0.3, 0.5, 0.7, 0.9).

---

satisfies
R + exp (-o(1) K (o0t))+00 aB
HB² KR VKR
pB²
EF S HB exp (
+
VMK
where it Ô hide terms logarithmic in R, K, and aB..
Comparison with related methods and lower bounds
In this section, we compare our algorithm's guarantees with those of FEDAC, and we include additional comparisons in Appendix A difficulty in making this comparison determining "typical" relative scale of the parameters H, o, U, and p. Drawing inspiration from training generalized linear models, we consider a natural scaling of the parameters that arises when the objective has the form F(z) = [E,((( 2)), where |e"), 1 and |e"i| are ((), and where || S D; this holds, e.g., for logistic regression problems (see (2)). In this case, upper bounds on the derivatives of F will generally scale with || So if we assume that ||=|| < D for some D, then the derivatives of F would scale as (z) S D. [ op X D2, and |V) olop S Dd, where II-Ilop denotes D² These
the operator norm. Thus, will take H D2_ o D, U = D3 parameters could have different relationships, but we focus on this regime for simplicity.
D, and
In addition to working within this natural scaling, we consider the case where we have access to sufficient machines (i.e., M Z KR D² ) and for K large enough. We explore various regimes w.r.t.
both the number of rounds of communication Rt and the "size" of the problem DB. Thus, ignoring constants and terms logarithmic R, K, and aB, our upper bound from Theorem reduces to
R DB
D² D
Dº Dd
EF F* & D² exp
DdB cxp(-K)+ K)+
KR KR
VKR
VKR
Comparison with FEDAC
The previous best known first-order distributed method under third-order smoothness assumptions is FEDAC (Yuan and Ma, 2020), accelerated variant of Local SGD, which achieves guarantee of
HB²
oB
H B4/3
U2/302/3
2F < Ô
KR
VMKR
MI/3 K//3
K1/3R4/3
For the setting as outlined above, this bound reduces to
D² EF(() - F* S KR
D5/3/5/3
K1/3
In the case where DB is not too large (DB S K2R the dominant term for FEDAC is D2/3ga/3 and so we see that our algorithm improves upon FEDAC as long as R S FEDAC provides better guarantees than FEDSN.
R1/9R473 VK
VK DB whereas for R DB
Comparison with first-order lower bounds
Woodworth al. (2021) provide lower bounds under other smoothness conditions, including quasi- self-concordance, which are relevant to the current work. Roughly speaking, they show that under Assumption 2(a), first-order intermittent communication algorithm can guarantee suboptimality less than (ignoring constant and log M factors)
HB²
aB
HB2
aB VKR.
EF F*
VMRR + min
R
VKR2
In the same parameter regime above, the lower bound reduces to
B²
D2
DB
EF K2R² + min
VKR² VKR
Comparing this lower bound with our guarantee in Theorem 1, we see that, when DB = 0(1) and the number of rounds of communication is small (e.g., R = (log K)), approximate Newton method can (ignoring log factors) achieve an upper bound of EF F S 1/ L/VK. Therefore. in this important regime, FEDSN matches the lower bound under Assumption 2(a), albeit using stronger oracle. No prior work has matched this lower bound, and so we do not know whether such an oracle is necessary in order to achieve it, or if perhaps the stronger oracle allows for breaking it.

---

Wour
Fod (Sptimally Regu brood
Local
hadhC (Cptimally fagge arrows)
Local
0.0
+0.2
135
Mumber of Darmuniiatioo Rlonnd
Namber of Conmuniintie Rounds
(a)
(b)
Figure 1: Empirical comparison of FEDSN-LITE (Algorithm to other methods (see Appendix G.I) on the LIBSVM a9a (Chang and Lin, 2011; Dua Graff, 2017) dataset for minimizing: (a) in-sample, and (b) out-of-sample unregularized logistic regression loss using M E (100, 200) machines. We vary the frequency of communication (horizontal axis of cach plot), while keeping the total number of steps on cach machine (thcoretical parallel runtime) fixed at KR 100. Thus, every point in the sub-plot is separately tuned instance an algorithm, where each algorithm besides FEDAC solves an unregularized ERM problem and reports (a) the best relative sub-optimality w.r.t. the optimal minimizer and (h) the hest validation loss on a held-out dataset. All results are averaged over multiple runs (see Appendix G.3 for full details).
5 Experiments
In Appendix G.1 we present more practical variant of FEDSN called FEDSN-LITE (Algorithm 6), which does away with the search over the regularization parameter as in Algorithm 2. We compare FEDSN-LITE against the two variants of FEDAC (Algorithm 7, Yuan and Ma (2020)), Minibatch SGD (Algorithm 9, Dekel et al. (2012)), and Local SGD (Algorithm 8, Zinkevich et al. (2010)). We also study the effeet of adding Polyak's momentum, which denote by B, to these algorithms (see Appendix G.1). FEDAC is mainly presented and analyzed for strongly convex functions by Yuan and Ma (2020). In fact, they assume the knowledge of the strong convexity constant to tune FEDAC, which is typically hard to know unless the function is explicitly regularized. To handle general convex functions, Yuan and Ma (2020) build some internal regularization into FEDAC (see Appendix E.2 in their paper). However, their hyperparameter recommendations in this setting also depend on unknowns such the smoothness of the function and the variance of the stochastic gradients. This poses a difficulty in comparing FEDAC to the other algorithms, which do not require the knowledge of these unknowns.
To overcome this we take the more carefully optimized version of FEDAC for strongly convex functions and tune its internal regularization and learning rate. This emulates the setting where the objective is assumed to be just convex but FEDAC sees strongly convex function instead. In our experiments in Figure 6, we notice that FEDSN-LITE is either competitive with or outperforms the other baselines. This is especially true for the sparse communication settings, which are of most practical interest. more comprehensive set of experiments can be found in Appendix G.2 along with full implementational details in Appendix G.3.²
6 Conclusion
In this work, we have shown how to more efficiently optimize convex quasi-self-concordeee objectives by leveraging parallel methods for quadratic problems. Our method can, in some parameter regimes, improve upon existing stochastic methods while maintaining similar computational cost, and have further seen how our method may provide empirical improvements in the low communication regime. It remains open whether the same guarantees achieve here can also be achieved using only independent stochastic gradients (a single stochastic gradient on each sample), or whether the distributed stochastic setting access to Hessian-vector products is strictly more powerful than access to only independent stochastic gradients.
Cooee availabe
10

---

This research was partially supported by NSF-BSF award 1718970. BW is supported by a Google Research PhD Fellowship. We also thank all the anonymous reviewers for their time and suggestions.
Acknowledgements.
References
Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approximate local minima faster than gradient descent. In Proceedings of the 49th Annual ACM SIGACT Symposium Theory of Computing, pages 1195-1199, 2017.
Zeyuan Allen-Zhu. Natasha 2: faster non-convex optimization than sgd. In Advances in Neural Information Processing Systems, pages 2680-2691, 2018.
Yossi Arjevani, Yair Carmon, John Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridharan. Second-order information in non-convex stochastic optimization: Power and limitations. In Conference on Learning Theory, pages 242-299. PMLR, 2020.
Francis Bach. Self-concordant analysis for logistic regression. Electronic Journal of Statistics, 4:
384 414, 2010.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Brian Bullins. Highly smooth minimization of non-smooth problems. In Conference on Learning Theory, pages 988-1030. PMLR, 2020.
Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal on Optimization, 28()):151-1172, 2018.
Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, and Kevin Tian. Acceleration with ball optimization oracle. Advances in Neural Information Processing Systems, volume 33, 2020.
Chih-Chung Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1-27:27, 2011. Software available at http:/ /wwww csie .nu. edu. sa/"cjlin/libss/
Greg Coppola. Iterative parameter mixing for distributed large-margin training of structured predictors for natural language processing. PhD thesis, The University of Edinburgh, 2015.
Andrew Cotter, Ohad Shamir, Nati Srebro, and Karthik Sridharan. Better mini-batch algorithms via accelerated gradient methods. In Advances in Neural Information Processing Systems, volume 24, pages 1647-1655, 2011.
Rixon Crane and Fred Roosta. Dingo: Distributed Newton-type method for gradient- optimiza- tion. In Advances in Neural Information Processing Systems, volume 32, 2019.
Ofer Dekel, Ran BachhaBa, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 13(Jan):165-20) 2012.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http: htttt::/aarchiee.ttt uci. edu/ml.
Saced Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal Optimization, 22(4): (199))1469-14992 2012.
Vipul Gupta, Avishek Ghosh, Michal Derezinski, Rajiv Khanma, Kannan Ramchandran, and Michael Mahoney. LocalNewton: Reducing communication bottleneck for distributed learning. arXiv preprint arXiv:2105.07330, 2021.
Rustem Islamov, Xun Qian, and Peter Richtárik. Distributed second order methods with fast rates and compressed communication. arXiv preprint arXiv:2102.07158 2021.
Sai Praneeth Karimireddy, Sebastian U Stich, and Martin Jaggi. Global linear convergence of Newton's 's method without strong-convexity or lipschitz gradients. arXiv preprint 1806::8806004 2018.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for on-device federated learning, arXiv preprint arXiv:1910.06377 2019.

---

Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First analysis of local gd on heteroge- neous data, arXiv preprint vrXiv:1909.04777 2019.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pages 4519-4529. PMLR, 2020.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. International Conference on Machine Learning, pages 5381-5393, PMLR, 2020.
Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Program- ming, (33(132) 3975, 2012
Renato DC Monteiro and Benar Fux Svaiter. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM Journal on Optimization, 2302):1022-1225, 2013.
Yurii Nesterov. Introductory lectures convex programming volume i: Basic course. Lecture notes, 3(4):5, 1998.
Yurii Nesterov. Implementable tensor methods in unconstrained convex optimization. Mathematical Programming, pages 1-27, 2019.
Yurii Nesterov and Arkadii Nemirovskii. Interior-point polynomial algorithms in convex program- ming. SIAM, 1994.
Yurii Nesterov and Boris T Polyak. Cubic regularization of Newton method and its global performance. Mathematical Programming, 108(1):177-205, 2006.
Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.
Barak A Pearlmutter. Fast exact multiplication by the Hessian. Neural Computation, 6(1):147-160 1994.
Sashank Reddi, Jakub Konečný, Peter Richtárík, Barnabás Póczós, and Alex Smola. Aide: Fast and communication efficient distributed optimization. arXiv preprint arXiv:1608.0688 2016.
Ohad Shamir, Nati Srebro, and Tong Zhang. Communication-effceee distributed optimization using an approximate Newton-type method. In International Conference on Machine Learning, pages 1000-1008. PMLR, 2014.
Sebastian Stich. Local sgd converges fast and communicates little. In International Conference on Learning Representations, 2019.
Shusen Wang, Fred Roosta, Peng Xu, and Michael W Mahoney. Giant: Globally improved approxi- mate Newton method for distributed optimization. Advances in Neural Information Processing Systems, 31:2332 2342, 2018.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pages 10334-10343. PMLR, 2020a.
Blake Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. In Conference Learning Theory. PMLR, 2021.
Blake E Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, and Nati Srebro. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. Advances in Neural Information Processing Systems, 31:8496-8500 8506, 2018
Blake E Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch local sgd for heterogeneous distributed learning. Advances in Neural Information Processing Systems, 33:6281 16292, 2020b.
Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent. In Advances in
Neural Information Processing Systems, 2020.
Yuchen Zhang and Lin Xiao. Disco: International Conference Machine Learning, pages 362-370. PMLR, 2015,
Distributed optimization for self-concordant empirical loss. In
12

---

Yuchen Zhang, Martin Wainwright, and John C Duchi. Communication--ffiiiei algorithms for statistical optimization. Advances in Neural Information Processing Systems, pages 1502-1510, 2012.
Yuchen Zhang, John C Duchi, and Martin J Wainwright. Communicatioon-effcccennn algorithms for statistical optimization. The Journal of Machine Learning Research, 14(1):3321-336) 2013.
Fan Zhou and Guojing Cong. On the convergence properties of k-step averaging stochastic gradient descent algorithm for nonconvex optimization. In Proceedings of the Twenty-Seveni International Joint Conference Artificial Intelligence, IJCAI-18, pages 3219-3227. International Joint Conferences on Artificial Intelligence Organization, 7 2018. doi: 10.24963/jcci.200 8/447.
Martin Zinkevich, Markus Weimer, Lihong Li, and Alex Smola. Parallelized stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 2595-2603, 2010.
13


Reviews:
[{"review_id": "vy34liMps4K", "reviewer": "Reviewer_N6s7", "summary": "The paper proposes a distributed stochastic Newton’s method which uses Local SGD as a quadratic solver to approximate the Newton steps at each iteration, leveraging recent results on the strong performance of Local SGD when optimizing quadratic objectives. An important feature of the algorithm is that it has access to two oracles: a noisy gradient, and a noisy Hessian-vector product. The authors provide convergence guarantees for the algorithm, as a function of the number of machines M, number of communication rounds R, and number of oracle queries per machine per round, denoted K. The results suggest that the second oracle can in fact lead to better convergence guarantees compared fiirst-order methods which have access only to the noisy gradients.", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "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": "Thank you to the authors for the response. It was helpful, particularly in comparing quasi-self-concordance to standard self-concordance, as well as motivating the approximate Hessian-vector product. May I suggest that the authors also discuss in the paper how using quasi-self-concordance compares to using scaled self-concordance, which is considered in DISCO (Zhang and Xiao, 2015), since it seems that both of those can be used for logistic regression. Sounds like the authors agree that the paper needs some work in making the presentation of the results clearer and more precise, so my recommendation does not change.\n\n-------------------------------\nI found the paper to be extremely dense and difficult to get through, with very complicated notation to the point where it was difficult for me to put the results into perspective. Below are the main issues I ran into with the notation:\n- First, it feels very strange that the main iterates of the algorithm are indexed by T, and yet T does not appear in the bound of the main result (Theorem 4).\n- In fact, parameter T appears both in Algorithm 1 (the outer loop) and Algorithm 3 (the inner-most loop), which makes me think one of those parameters should be called something else.\n- Parameters R and K, which seem to be the main quantities used to evaluate the convergence rate, do not appear anywhere in any of the algorithms, except in Appendix D, where they appear in the definitions of other parameters, like T.\n- The definitions of all the parameters in Theorem 7 (the full version of the main result) seem to be entangled together. For instance, T is defined using N and N is defined using T. It is not clear to me how all those equations can be satisfied at once. \n\nOther major question that is not properly addressed in the paper is: How does the noisy Hessian-vector oracle arise practically, as a natural data access model? I didn’t see this addressed in the paper, and it is not clear to me how this was done in the experiments.\n\nFinally, another definition that deserves clarification: What is the relationship between quasi-self-concordance and standard concordance? Is it a broader class, or a narrower class, or incomparable?\n\nOverall, I find the paper very confusing and  poorly written, thus it is difficult for me to even judge the merit of the contributions. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "c122rNmTGDI", "reviewer": "Reviewer_uQaQ", "summary": "This paper proposed a distributed stochastic newton algorithm for convex optimization. Each Newton update is solved using a recently developed distributed least-squares algorithm with only one round of communication. The authors analyze the convergence rate of their algorithm which outperforms the convergence rates of previous work.", "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": "This paper forms the Newton updates in quasi-self-concordant convex optimization as a quadratic programming problem. It then uses recently proposed local SGD algorithm to solve this quadratic programming in a distributed setting with single round of communication. Here are some comments: \n\n1. The paper is mainly well-written. However, the notations are confusing and wrong. The parameter T (number of rounds for local SGD) in algorithm 3 and Theorem 3 should be K in Theorem 4 and all the comparisons in this paper. It is really confusing to mix with the number of newton updates. For some key parameters like R,M,K and T, it would be much better if the authors can restate/emphasize their meaning before main theorems/algorithm comparisons. \n\n2. The authors should emphasize their contributions, on the theoretical analysis and the novelty of their algorithms. Using quadratic programming to solve Newton updates is a very standard technique in recent 10 years optimization literature. From my perspective, the algorithm is just a combination of this technique and recently proposed local SGD in Woodworth et al. (2020). The theoretical analysis is also very straight-forward. The Hessian-vector product is very important in their algorithm. I am very surprised that the authors do not give any explicit form/algorithm to compute this product. They treat it as a black box with some outputs satisfying unbiasedness and bounded variance assumption. I think we need an explicit form for that (from some literature) which satisfies the assumptions proposed.\n\n3. The Hessian-vector product is very important in their algorithm. I am very superised that the authors do not give any explicit form/algorithm to compute this product. They treat it as a black box with some outputs satisfying unbiasedness and bounded variance assumption. I think we need an explicit form for that (from some literature) which satisfies the assumptions proposed.\n\nReferences mentioned above:\n\n1. Woodworth, Blake, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan, Ohad Shamir, and Nathan Srebro. \"Is local SGD better than minibatch SGD?.\" In *International Conference on Machine Learning*, pp. 10334-10343. PMLR, 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "brKWwlAlgZa", "reviewer": "Reviewer_y5UR", "summary": "The paper analyzes a stochastic Newton algorithm for distributed convex optimization. The upper bound is shown to achieve faster convergence rates than other first-order methods. Empirical results show that the proposed algorithm is competitive with related first-order methods. \n", "questions": "", "limitations": "", "rating": 3, "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": "The paper proposes a new stochastic Newton algorithm by expressing the Newton update as the solution to a least-squares problem which one can optimize using stochastic gradients and stochastic Hessian-vector products for the objective. I'm listing all my concerns as below:\n\n1. The difference and connections between the three assumptions A1, A2 and A3 are not discussed sufficiently. It is unclear how the terms $\\rho$, $\\sigma$, $Q$ among others are related, which makes it hard to determine which algorithm has a better rate. \n\n2. From the rate given in the paper, I think the contribution is not significant enough compared to the previous literature. The rate for new algorithm has some counter-intuitive dependencies. For example, for all other first-order methods the algorithm will converge with all parameters fixed and the rounds of communication going to infinity. However, the upper bound in this paper suggests that the algorithm will not converge in this case. This is also inconsistent with the experiments in Figure 1 and 2, where we seem to have convergent result when the number of communication rounds gets larger. \n\n3. Since the algorithm uses an extra information of stochastic Hessian-vector products compared to other pure first-order methods, one shall expect that the performance of the algorithm strictly dominates that of other first-order methods, which is not the case in the proposed algorithm. I'm also interested in how this method can approach the rate for second-order methods. It would be great if the authors can include some comparison with second-order methods, along with some discussions on how the lower bound looks like with the extra information of stochastic Hessian-vector product, instead of comparing the algorithm directly with the lower bound for first-order methods.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "IDtxUHylE1a", "reviewer": "Reviewer_yNcz", "summary": "As far as the writing of the paper allows to summarize, this work considers parallel stochastic Newton's method for machines holding IID or shared data to train. The main idea is to replace costly computation of Newton's direction by more efficient stochastic estimates using stochastic gradient and stochastic Hessian-vector products. The paper designs a new method, called FedSN, which is claimed to outperform baseline first-order methods.", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "The quality and clarity of the writing is extremely low. In its current version, most part of the paper is not readable due to typos, grammar errors, odd word choices, sentence structure and lack of proper organization.\n\n(line 69) A basic driver of progress common among…\n(line 86) ..all the while dealing with technical challenges..\n(lines 104-105) Leveraging this structure, in combination with distributed second-order methods, has since been shown to lead to improved communication efficiency.\n(lines 159-164) ..a key difficulty comes from the fact that our Newton-type updates can only ensure small error in expectation. .. . It is details such as these in the subproblem solver ..\n(Line 175) though we allow for an additive error in the subproblem solves in addition to the multiplicative error\n\na.k.a. means also-known-as, which appears in the caption of Algorithm 1 (FedSN). Given that FedSN is the proposed method of this work, mentioning a.k.a. makes confusion. Is FedSN a new method or known ?\n\nIn the abstract “At the heart of our approach is the recent work showing that …\". That recent work should be cited there since it seems important to be mentioned in the second sentence of the abstract.\n\ncitep and citet macros are used randomly.\n\nThe steps of the Algorithms are not explained properly, notations are introduced randomly without descriptions. For example, what are $Q, C, \\bar{\\lambda}, r^*(\\lambda), \\epsilon(\\lambda)$ in Theorem 2, are they defined before or inside of Theorem 2 ? Where the steps (and also notations) of Algorithm 2 are explained ?\n\nWhere the limitations of your work are described ? It is mentioned “Yes” in the checklist. I failed to find it in the appendix too.\n\nLines 90-91: “we provide a more practical version of our method, FedSN-Lite”. Does it mean FedSN is less practical ? What are the practical limitations of it compared to FedSN-Lite ?\n\nThe title, abstract and the intro motivate the topic by discussing distributed optimization. By distributed optimization it is typically assumed that data distributed among several machines (this is also mentioned in lines 102-104). However, the main contribution of this work (line 52, 82), FedSN method, is not analyzed under distributed setup since the key component of it, One-Shot-SGD (Algorithm 3), assumes the whole data is available to all machines (see 2nd of Algorithm 3). This is homogeneous data setup or alternatively dataset is shared across machines.\n\nThe main result of FedSN seems to be that in *some* regime it hits the lower bound obtained for first-order methods. The regime where this happens is highly unrealistic and impractical: all constants $H, B, \\sigma, \\alpha$ should be $1$, the number of machines must be infinitely big, the number of local steps $K$ must be sufficiently large and noise rho must be sufficiently small (as $\\rho < 1/\\log K$ must hold).\n\nWhy in the plots methods have so different sub-optimality at 5th round ? Are they initialized at the same point ?\n\nWhy FedSN is not compared in the plots ?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I failed to find where the limitations of this work are described (main paper and the appendix) ? It is mentioned “Yes” in the checklist. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper analyzes a stochastic Newton's method for distributed convex optimization. I share many concerns mentioned by the reviewers, including but not limited to the unusual dependence on parameters in the rate, the poor performance of the algorithm compared to first-order methods with access to more information, and inconsistency between theory and experiments. I agree that the paper is not in publishable form and I regretfully cannot recommend acceptance. 
Decision: Accept (Poster)