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": "hTdf7HA1qD_", "reviewer": "Reviewer_we6s", "summary": "This paper proposes a federated stochastic Newton algorithm for optimizing quasi-self-concordant objectives,\nwith concrete theoretical analysis showing this algorithm can outperform other existing first-order stocahstic optimization algorithms and numerical experiments to support the analysis.", "questions": "", "limitations": "", "rating": 6, "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": "* Originality\n\nThis work is novel because it approximates a Newton step by solving a local optimization problem using stochastic gradient descent and provides extensive theoretical analysis,\nwhich are not well-explored in prior literature.\n\n* Quality\n\nFED-SN reaches a convergence rate that dominates other algorithms in certain regimes.\nThe proof is detailed and well-written, lists most assumptions and important steps.\nHowever, the assumptions in this paper is too strong, but it is understandable since the analysis of FED-SN is challenging.\n\n* Clarity\n\nThis paper is clearly written, well-organized and reproducible.\n\n* Significance\n\nThe results obtained in this paper is novel, and improves upon current state-of-the art results in certain settings.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The biggest limitation of this paper is how to compute the hessian. This paper avoids computing the inverse of hessian, which is a great improvement over the original Newton algorithm. However, it is not fair to say it uses less communication because the hessian is communicated, when the dimension is moderately big, the communication overhead will be significant.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "b7OX4a5uquC", "reviewer": "Reviewer_Huyz", "summary": "In this paper, the authors introduced a stochastic Newton-type algorithm for distributed quasi-self-concordant convex optimization. The high level idea is to reduce the problem into approximately solving for a sequence of trust-region constrained quadratic subproblems. The subproblems are in turn solved by binary search on the optimal regularization parameter $\\lambda^*$, followed by calling for unconstrained stochastic local SGD solver with a single round of communication. The algorithm assumes access to stochastic hessian-vector product, in addition to stochastic gradient. Numerical experiments are conducted on a more practical variant of the algorithm for the logistic objective.", "questions": "", "limitations": "", "rating": 6, "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 relevant literature is adequately surveyed, although I'd add that the idea of solving the inner quadratic problem using stochastic gradient method has been considered before, see e.g., Corollary 18 in Carmon et al: https://proceedings.neurips.cc/paper/2020/file/dba4c1a117472f6aca95211285d0587e-Paper.pdf. The claims do look right and the writing is pretty clear. The analysis itself is a combination of somewhat standard techniques/building blocks from the optimization literature.\n\nThe improvement seems to be quite tied to the parameter regime however, and it's a bit elusive with the somewhat non-standard oracle/assumptions/missing evidence of lower bound how applicable/relevant the algorithm really is in practice. It would be good to know how the proposed algorithm work on common objectives on real data with (potentially unknown) quantities defined in the assumptions.\n\n====================== post author-response ========================\nThank you for the given example and I'd like to keep the positive score.", "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": "2.5"}, "extra_text": {}}, {"review_id": "Y5yqaUxMv2", "reviewer": "Reviewer_sbMG", "summary": "\nThis paper studies a distributed Stochastic Newton method in the intermittent communication model. At each step, the Newton direction is obtained by solving the associated minimization problem (instead of directly computing the Hessian) using One Shot Averaging (one round of communication only): nodes locally run a stochastic gradient algorithm and then average their solutions at the end. This is known to work well for quadratic objective, which is the case for computing the Newton direction. \n\nThen, under reasonable higher order smoothness assumptions (quasi self-concordance, third order smoothness and bounded fourth central moment), it is shown that obtaining approximate solutions to a constrained version of the Newton subproblem  leads to a globally convergent algorithm. Thus, the solution to the constrained Newton subproblem is replaced by the equivalent regularized subproblem, where the unknown regularization parameter is approximated by binary search. Thus, an approximate solution to the constrained subproblem is obtained by solving unconstrained subproblems only, which can be handled using one shot averaging.\n\nThen, an appropriate choice of parameters is given, which allows to prove convergence guarantees for the whole algorithm. These guarantees are compared to the lower bound, which can be beaten in some regimes thanks to the slightly different assumptions as well as the fact that stochastic Hessian-vector oracles are considered, which is reasonable for generalized linear models. \n\nFinally, simulations are given to show that FedSN outperforms reasonable baselines (Local and Minibatch SGD in particular) in terms of Suboptimality for a given number of communication rounds. \n", "questions": "", "limitations": "", "rating": 7, "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": "\nThe paper is globally clear and well-written. The relevant state of the art is adequately reviewed, and the series of (informal) theorems present a clear logical progression for the different steps needed to analyze the algorithm. \n\nAlthough the idea of approximating each Newton step using One Shot Averaging to reduce communications is quite natural, several tricks are required, such as approximating the constrained optimization problem. Besides, the analysis seems sound, and is based on strong but reasonable assumptions (local stability and quasi-self concordance in particular). \n\nIf I am not mistaken, all nodes need to draw stochastic gradients for the same function. Maybe this is worth mentioning (does not allow for data heterogeneity between nodes). \n\nIt seems that FedSN is globally convergent thanks to the constrained step, and then a complex scheme is developed to turn this into an unconstrained problem. In the end, the algorithm comes down to approximately solving a series of unconstrained Newton subproblems with varying regularization, similarly to, e.g., [A]. Is there a fundamental benefit of approximating constrained subproblems instead of a sequence of regularized Newton steps? If so, I believe it would be great to highlight it. Or is it the way [A] approximates the steps (directly via sketching) that makes the analysis viable without resorting to constrained subproblems? You don't assume strong convexity (but the experiments use regularized logistic regression), could that be an explanation?\n\nYou mention that the advantage of using Hessian-vector products is due to the distributed setting, and in particular the fact that the lower bound is not quadratic, so the Hessian-vector information is not equivalent to gradient information. Yet, if I understand correctly, this is also true for generalized linear models, which is the prime example for which stochastic Hessian vector products are easy to compute (and quasi-self concordance holds). From this perspective, it seems that using this kind of second-order information is mainly beneficial when it is not that easy to compute, or have I missed something? Is it possible that some slackness in the lower bound comes from different variance that is assumed for second order information (the \\rho parameter)? I believe that the \"comparison with the lower bound\" part is great, but could be improved even further. \n\n[A] Marteau-Ferey, Ulysse, Francis Bach, and Alessandro Rudi. \"Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses.\" Advances in Neural Information Processing Systems 32 (2019): 7636-7646.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No foreseeable societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "UgGQi0k9N7p", "reviewer": "Reviewer_4Wbd", "summary": "This work studies a distributed Newton-type algorithm for unconstrained convex optimization.\n", "questions": "", "limitations": "", "rating": 6, "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": "1. The least squares step in the Newton step can be solved using sketching based methods as well. There are published papers in the literature that focus on “distributed Newton sketch” type of algorithms where computing the exact Hessian is avoided and the Newton update is approximate. The algorithm presented in this paper seems to work very similarly to distributed Newton sketch and address the same problem. I think it would be great to compare the presented algorithm with the distributed Newton sketch approach so that the contributions of this paper can be better understood.\n\n2. Is “sub-optimality” (y-axis of figure 1) defined somewhere in the paper?\n\n3. I agree that comparing the performance with respect to the number of communication rounds is a good idea. But I think this, by itself, does not show the whole picture, since time complexity and required memory are important considerations as well. For instance, how does the performance look with respect to runtime?\n\n4. Also, related to my point in 1; it has been known for a while that least-squares objectives can be optimized to high accuracy with a single round of communication, i.e. averaging sketched solutions. Authors, in fact, cite the work by Wang et al., 2018, which is one of the papers that study the concept of averaging sketched solutions. It might justify/clarify the motivation of this work to further comment on how “local-SGD for least squares” and “averaging sketched solutions” compare.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a distributed Newton method that leverages a recently develop one-round communication methods for solving least-squares. The papers backs up all claims with clear theoretical arguments and numerical experiments. The reviewers have also reached a consensus that the paper should be accepted. 
Decision: Accept (Poster)