INDIVIDUAL COMMENTS / QUESTIONS 1) I really appreciate how the paper ties up loose ends by unifying the analysis of several momentum-based methods in the stochastic setting. I am not very closely familiar with the literature analyzing momentum methods, but there's a lot of work out there (e.g., the line of research studying momentum methods in the continuous time limit). A brief review would be very helpful to position the paper within the existing work. To me this implies that the analysis would go through for more general functions. I don't find it obvious that it would.

The reviewers agree that the topic tackled in the paper is interesting and the mathematical results are promising. Overall, this submission is a good attempt in deriving a mathematical understanding of QHM, but the results are often only partially investigated and commented. For instance, in section 3 the main result (i.e. the convergence rate for quadratics) is really hard to parse and is poorly commented in the sense that its practical value is unclear. The paper also makes a number of conjectures that are not backed up and the authors are therefore advised to tone down their claims. This includes "we conjecture that the optimal convergence rate is a monotonically decreasing function of nu" as well as the quality of the approximation in Section 4. In conclusion, all three reviewers liked the paper but also highlighted some shortcomings, therefore justifying acceptance as a poster but not an oral.

Additional Feedback: The authors propose the SDA approach, which has the potential to be an alternative to UCB and Thompson sampling for bandit learning. The main advantage of the proposed approach is that it is non-parametric, and for exponential families of distritions, it could achieve the optimal regret bound matching the lower bound, without knowing which distribution family the unknown distribution belongs to. However, I feel that achieve optimal regret guarantee is mostly theoretical interest. UCB may not be optimal in this sense but it could achieve consistent regret gurantee for all distributions. RB-SDA algorithm, it is unclear to me if its theoretical guarantee of O(log T) regret bound could be achieved for any distribution.

The panel of knowledgeable reviewers is clearly in favor of this paper and its results. The author response also helped significantly to address most concerns raised by the initial reviews. Hence, I am glad to recommend acceptance.

Summary and Contributions: The paper considers the problem of agnostically learning a single neuron with respect to the squared loss via gradient descent (GD). The focus of the paper is on specifically understanding the guarantees GD obtains. Under only boundedness of the input distribution, the authors show that for strictly increasing (gradient bounded below by a constant) activation functions, GD finds a point that achieves error O(\sqrt{opt}) \eps where opt is the loss of the best fitting neuron. They extend the result to ReLU under standard anti-concentration assumptions (similar to [1,2]). For ReLU, it is known that you in fact get O(opt) \eps under essentially the same assumptions (see [1]) using an alternate algorithm.

The reviewers agree that the techniques in this paper are interesting and novel, and that the paper is well-written. For the camera ready version, the authors should include discussion for the additional references pointed out by Reviewer #2. In particular, it would be good to point out that one of the main strengths of this work is the fact that it handles arbitrary distributions over x. Per the comments of Reviewers 3 and 4, it would also be nice to include some additional discussion of the challenges of extending these techniques to multiple neurons.

I'll keep my mark and vote for accepting this paper. Yet, the techniques for bounding each term seem borrowed and adapted from previous papers analyzing SGD for least-squares problems -related papers are adequately cited. Quality and clarity: Theoretically speaking, the paper is self-contained and provides proofs of all theorems and a clear discussion on all the assumptions made in the paper. Furthermore, despite the number of parameters concerned with the analysis, the main results (Theorem 1 and Corollary 1) are very clear and clearly compared with the relative work. However, the experimental section may lack of a real dataset where r can be computed and where we could see the difference between tail and uniform averaging.

In this work, we consider the optimization formulation for symmetric tensor decomposition recently introduced in the Subspace Power Method (SPM) of Kileel and Pereira. Unlike popular alternative functionals for tensor decomposition, the SPM objective function has the desirable properties that its maximal value is known in advance, and its global optima are exactly the rank-1 components of the tensor when the input is sufficiently low-rank. We analyze the non-convex optimization landscape associated with the SPM objective. We derive quantitative bounds such that any second-order critical point with SPM objective value exceeding the bound must equal a tensor component in the noiseless case, and must approximate a tensor component in the noisy case. For decomposing tensors of size D {\times m}, we obtain a near-global guarantee up to rank \widetilde{o}(D {\lfloor m/2 \rfloor}) under a random tensor model, and a global guarantee up to rank \mathcal{O}(D) assuming deterministic frame conditions.

Summary and Contributions: The paper proposes a new version of Local-SGD/Federated Averaging algorithm -- Federated Accelerated SGD (FedAc). In particular, the algorithm solves a smooth convex expectation minimization problem in a distributed/federated fashion: M workers in parallel can access the stochastic gradients of the objective function and periodically communicate with a parameter-server. FedAc is a combination of AC-SA method from (Ghadimi and Lan, 2012) and Federated Averaging. Authors propose a first analysis of this method for generally strongly convex functions (in the convex case this method was analyzed in (Woodworth et al., 2020), but only for quadratic objectives) under the assumption that the variance of the stochastic gradients is uniformly bounded. The derived bounds outperform the state-of-the-art result for federated methods in this setting, and these rates are close to the accelerated ones. Moreover, authors show how their bounds improve under the additional assumption that the Hessian is Lipschitz continuous, and the 4-th central moment of the stochastic gradient is bounded and also extended known results for Local-SGD (FedAvg) to this case.

This paper has been well-received by the reviewers and the author response addressed the reviewers' concerns adequately. Thus, the paper is suitable for acceptance at NeurIPS without significant changes.