Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: 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. 

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:

1. 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. 

2. 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. 

3. 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.

limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.
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.

-------------------------------
I 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:
- 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).
- 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.
- 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.
- 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. 

Other 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.

Finally, 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?

Overall, I find the paper very confusing and  poorly written, thus it is difficult for me to even judge the merit of the contributions. 

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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: 

1. 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. 

2. 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.

3. 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.

References mentioned above:

1. 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.
limitations_and_societal_impact: None.
review_title: null

final_score: rating: 3: Clear rejection
review_content: 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.
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.

(line 69) A basic driver of progress common among…
(line 86) ..all the while dealing with technical challenges..
(lines 104-105) Leveraging this structure, in combination with distributed second-order methods, has since been shown to lead to improved communication efficiency.
(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 ..
(Line 175) though we allow for an additive error in the subproblem solves in addition to the multiplicative error

a.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 ?

In 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.

citep and citet macros are used randomly.

The 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 ?

Where the limitations of your work are described ? It is mentioned “Yes” in the checklist. I failed to find it in the appendix too.

Lines 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 ?

The 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.

The 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).

Why in the plots methods have so different sub-optimality at 5th round ? Are they initialized at the same point ?

Why FedSN is not compared in the plots ?
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_title: null

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)