summaries: The paper provides a theoretical analysis comparing the training dynamics and performance of a specific 1 hidden-layer convolutional neural network with those of its corresponding finite width CNTK on a simple data distribution. This analysis is used to support their claim that the gap between neural networks and kernel methods may lie in the ````''Local Signal Adaptivity'', in the sense that neural networks outperform kernel methods in distinguishing localized influential features from noisy background. Furthermore, they empirically identify a performance gap between the CNN and finite width CNTK on noise extended variants of the CIFAR-10 dataset, which emphasizes the influence of the ``''Local Signal Adaptivity''. The authors conclude that this setting degrades the performance of kernels in a more pronounced way than it affects neural networks.

summaries: This paper introduces the notion of local signal adaptivity (LSA), which the authors claim is a new perspective on the benefits of feature learning in NNs over kernel methods like the NTK. LSA denotes the ability of non-linear NNs to find a sparse signal in the presence of large noise, and the authors theoretically show that in a particular data distribution setting with a sparse signal, a single filter CNN is able to train with GD to learn the signal. On the other hand, they show that for an underparameterised linear NN (linearised at initialisation in parameter space) the model is unable to learn the signal. Experimental results are provided comparing the degradation of non-linear and linear NNs under increasing noise, demonstrating that non-linear NNs are indeed more robust to noise in line with the theory.  **update after rebuttal** raising my score to 7

summaries: The authors study a toy binary classification problem where a certain CNN architecture is trained to detect one of two templates embedded in gaussian noise. The motivation is twofold: the problem is argued to capture relevant structures present in natural image classification tasks where CNNs succeed in practice (i.e., the detection of an object/motif in the image in the presence of a nuisance background), and the theoretical analysis establishes an architectural separation via the rates one gets by analyzing the problem with the neural tangent kernel approach and via the authors' analysis. Concretely, the data model consists of a fixed unknown template embedded in one of $k+1$ consecutive disjoint length-$d$ blocks of a length $d(k+1)$ 1D signal, with the other $k$ blocks containing i.i.d. gaussian noise of a certain variance (the blocks are imagined to be disjoint "image patches", and the template a motif of interest) -- samples from this data model have the patch where the template is contained uniformly randomized and contain independent noise, and the template is given either the positive or negative sign (representing the two classes in the problem). The noise variance is set to be large enough that it is not possible to perform naive matched filtering to recover the template. Accordingly, the CNN that is trained to solve this task contains a custom denoising nonlinearity, the standard soft thresholding function -- this corresponds to a one-layer, two-neuron ReLU network that computes two $d$-strided convolutions with specific weight sharing and output averaging (the shared biases end up corresponding to the soft thresholding function's parameter) -- which is trained using finite samples from the data generating distribution by mini-batch SGD on the logistic loss with gaussian random initialization. The authors show that this procedure yields a classifier for the data whp given polynomial samples and suitable step sizes; in contrast, they show that the network's convolutional NTK is unable to solve the task whp as long as the number of filters satisfies $o(d)$ (the neural network studied corresponds to a two filter network). Experiments involving embedding CIFAR-10 images into random backgrounds (either from ImageNet or having gaussian noise) with varying intensities and comparing neural network performance to their NTK's performance computationally on the classification tasks thus generated verifies the predicted performance gap.

summaries: This paper tackles the question of whether neural networks can be provable better than their induce neural tangent kernel for some problem setting. This question is answered in the context of a binary classification problem, in which the signal is shift invariant and embedded in a background of noise. The authors show that for this problem, a two layer neural network with relu activations and logistic loss efficiently learns (in sample and time complexity) this problem class with constant number of neurons, whereas its neural tangent kernel counterpart requires at least order d - the dimension of the (local) inputs. The authors then illustrate this basic problem in image classification settings where the problem setting is conceptually present, with results that align with their results in the toy-like distribution.

abstractText: Neural networks have been shown to outperform kernel methods in practice (including neural tangent kernels). Most theoretical explanations of this performance gap focus on learning a complex hypothesis class; in some cases, it is unclear whether this hypothesis class captures realistic data. In this work, we propose a related, but alternative, explanation for this performance gap in the image classification setting, based on finding a sparse signal in the presence of noise. Specifically, we prove that, for a simple data distribution with sparse signal amidst high-variance noise, a simple convolutional neural network trained using stochastic gradient descent simultaneously learns to threshold out the noise and find the signal. On the other hand, the corresponding neural tangent kernel, with a fixed set of predetermined features, is unable to adapt to the signal in this manner. We supplement our theoretical results by demonstrating this phenomenon empirically: in CIFAR-10 and MNIST images with various backgrounds, as the background noise increases in intensity, a CNN’s performance stays relatively robust, whereas its corresponding neural tangent kernel sees a notable drop in performance. We therefore propose the local signal adaptivity (LSA) phenomenon as one explanation for the superiority of neural networks over kernel methods.

authors:
Zeyuan Allen-Zhu
Yuanzhi Li

title: What Can ResNet Learn Efficiently, Going Beyond Kernels

venue: In Advances in Neural Information Processing Systems,

title: Backward feature correction: How deep learning performs deep learning

venue: arXiv preprint arXiv:2001.04413,

title: Feature purification: How adversarial training performs robust deep learning

venue: arXiv preprint arXiv:2005.10190,

authors:
Zeyuan Allen-Zhu
Yuanzhi Li
Yingyu Liang

title: Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers

venue: NeurIPS,

authors:
Sanjeev Arora
Simon S. Du
Zhiyuan Li
Ruslan Salakhutdinov
Ruosong Wang
Dingli Yu

title: Harnessing the power of infinitely wide deep nets on small-data tasks

venue: In International Conference on Learning Representations,

authors:
Ainesh Bakshi
Rajesh Jayaram
David P Woodruff

title: Learning two layer rectified neural networks in polynomial time

venue: arXiv preprint arXiv:1811.01885,

authors:
Digvijay Boob
Guanghui Lan

title: Theoretical properties of the global optimizer of two layer neural network

venue: arXiv preprint arXiv:1710.11241,

authors:
James Bradbury
Roy Frostig
Peter Hawkins
Matthew James Johnson
Chris Leary
Dougal Maclaurin
George Necula
Adam Paszke
Jake VanderPlas
Skye Wanderman-Milne
Qiao Zhang

title: JAX: composable transformations of Python+NumPy programs, 2018

venue: URL http://github.com/google/jax

authors:
Alon Brutzkus
Amir Globerson

title: Globally optimal gradient descent for a convnet with gaussian inputs

venue: arXiv preprint arXiv:1702.07966,

authors:
Minshuo Chen
Yu Bai
Jason D Lee
Tuo Zhao
Huan Wang
Caiming Xiong
Richard Socher

title: Towards Understanding Hierarchical Learning: Benefits of Neural Representations

authors:
Lénaïc Chizat
Edouard Oyallon
Francis Bach

title: On Lazy Training in Differentiable Programming

authors:
Amit Daniely
Eran Malach

title: Learning Parities with Neural Networks

authors:
Jia Deng
Wei Dong
Richard Socher
Li-Jia Li
Kai Li
Li Fei-Fei

title: Imagenet: A large-scale hierarchical image database

venue: IEEE conference on computer vision and pattern recognition,

authors:
Carles Domingo-Enrich
Alberto Bietti
Eric Vanden-Eijnden
Joan Bruna

title: On Energy-Based Models with Overparametrized Shallow Neural Networks

venue: In Proceedings of ICML,

authors:
Simon S. Du
Xiyu Zhai
Barnabas Poczos
Aarti Singh

title: Gradient Descent Provably Optimizes Over-parameterized Neural Networks

authors:
Rong Ge
Jason D Lee
Tengyu Ma

title: Learning one-hidden-layer neural networks with landscape design

venue: arXiv preprint arXiv:1711.00501,

authors:
Rong Ge
Rohith Kuditipudi
Zhize Li
Xiang Wang

title: Learning two-layer neural networks with symmetric inputs

venue: arXiv preprint arXiv:1810.06793,

authors:
Mario Geiger
Stefano Spigler
Arthur Jacot
Matthieu Wyart

title: Disentangling feature and lazy training in deep neural networks

venue: Journal of Statistical Mechanics: Theory and Experiment,

authors:
Behrooz Ghorbani
Song Mei
Theodor Misiakiewicz
Andrea Montanari

title: Limitations of Lazy Training of Two-layers Neural Network

title: When Do Neural Networks Outperform Kernel Methods

authors:
Alexander N. Gorban
Ivan Yu. Tyukin

title: Blessing of dimensionality: mathematical foundations of the statistical physics of data

authors:
Rémi Gribonval
Gitta Kutyniok
Morten Nielsen
Felix Voigtlaender

title: Approximation spaces of deep neural networks. 2020

venue: URL https://arxiv.org/abs/1905.01208

authors:
Arthur Jacot
Franck Gabriel
Clement Hongler

title: Neural Tangent Kernel: Convergence and Generalization in Neural Networks

authors:
Pritish Kamath
Omar Montasser
Nathan Srebro

title: Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity

venue: In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research,

title: Deep learning without poor local minima

title: Learning multiple layers of features from tiny images

authors:
Han-Wen Kuo
Yenson Lau
Yuqian Zhang
John Wright

title: Geometry and symmetry in short-andsparse deconvolution

authors:
Yann LeCun
Corinna Cortes
CJ Burges

title: Mnist handwritten digit database

venue: ATT Labs [Online]. Available: http://yann.lecun.com/exdb/mnist,

authors:
Jaehoon Lee
Samuel Schoenholz
Jeffrey Pennington
Ben Adlam
Lechao Xiao
Roman Novak
Jascha Sohl-Dickstein

title: Finite Versus Infinite Neural Networks: an Empirical Study

authors:
Aitor Lewkowycz
Guy Gur-Ari

title: On the training dynamics of deep networks with l_2 regularization

venue: arXiv preprint arXiv:2006.08643,

authors:
Yuanzhi Li
Zehao Dou

title: When can wasserstein gans minimize wasserstein distance

venue: arXiv preprint arXiv:2003.04033,

authors:
Yuanzhi Li
Yingyu Liang

title: Provable alternating gradient descent for non-negative matrix factorization with strong correlations

venue: In Proceedings of the 34th International Conference on Machine Learning-Volume

authors:
Yuanzhi Li
Yang Yuan

title: Convergence analysis of two-layer neural networks with relu activation

venue: In Advances in Neural Information Processing Systems, pages 597–607

authors:
Yuanzhi Li
Yingyu Liang
Andrej Risteski

title: Recovery guarantee of non-negative matrix factorization via alternating updates

venue: In Advances in neural information processing systems,

authors:
Yuanzhi Li
Tengyu Ma
Hongyang Zhang

title: Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations

authors:
Yuanzhi Li
Tengyu Ma
Hongyang R Zhang

title: Learning over-parametrized two-layer relu neural networks beyond ntk

venue: arXiv preprint arXiv:2007.04596,

authors:
Yuanzhi Li
Tengyu Ma
Hongyang R. Zhang

title: Learning Over-Parametrized Two-Layer Neural Networks beyond NTK

venue: In Proceedings of Thirty Third Conference on Learning Theory,

authors:
Eran Malach
Pritish Kamath
Emmanuel Abbe
Nathan Srebro

title: Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels

authors:
Edward Moroshko
Blake E Woodworth
Suriya Gunasekar
Jason D Lee
Nati Srebro
Daniel Soudry

title: Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy

authors:
Roman Novak
Lechao Xiao
Jiri Hron
Jaehoon Lee
Alexander A. Alemi
Jascha Sohl-Dickstein
Samuel S. Schoenholz

title: Neural tangents: Fast and easy infinite neural networks in python

authors:
Ryan O’Donnell
Rocco A. Servedio

title: New degree bounds for polynomial threshold functions

venue: In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing,

authors:
Samet Oymak
Mahdi Soltanolkotabi

title: Towards moderate overparameterization: global convergence guarantees for training shallow neural networks

venue: arXiv preprint arXiv:1902.04674,

authors:
Qing Qu
Xiao Li
Zhihui Zhu

title: A nonconvex approach for exact and efficient multichannel sparse blind deconvolution

authors:
Maria Refinetti
Sebastian Goldt
Florent Krzakala
Lenka Zdeborová

title: Classifying highdimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed

authors:
Alexander A. Sherstov
Pei Wu

title: Near-optimal lower bounds on the threshold degree and sign-rank of ac0

venue: In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing,

authors:
Mahdi Soltanolkotabi
Adel Javanmard
Jason D Lee

title: Theoretical insights into the optimization landscape of over-parameterized shallow neural networks

venue: arXiv preprint arXiv:1707.04926,

authors:
Daniel Soudry
Yair Carmon

title: No bad local minima: Data independent training error guarantees for multilayer neural networks

venue: arXiv preprint arXiv:1605.08361,

authors:
Qingyun Sun
David Donoho

title: Convex sparse blind deconvolution

title: Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality

authors:
Taiji Suzuki
Shunta Akiyama

title: Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods, 2020

venue: URL https://arxiv.org/ abs/2012.03224

authors:
Taiji Suzuki
Atsushi Nitanda

title: Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space. 2019

venue: URL https://arxiv.org/abs/1910.12799

title: The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi

title: An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis

venue: arXiv preprint arXiv:1703.00560,

authors:
Santosh Vempala
John Wilmes

title: Polynomial convergence of gradient descent for training onehidden-layer neural networks

venue: arXiv preprint arXiv:1805.02677,

authors:
Xiang Wang
Chenwei Wu
Jason D Lee
Tengyu Ma
Rong Ge

title: Beyond Lazy Training for Over-parameterized Tensor Decomposition

venue: Advances in Neural Information Processing Systems,

authors:
Colin Wei
Jason D Lee
Qiang Liu
Tengyu Ma

title: On the margin theory of feedforward neural networks

venue: arXiv preprint arXiv:1810.05369,

authors:
Blake Woodworth
Suriya Gunasekar
Jason D. Lee
Edward Moroshko
Pedro Savarese
Itay Golan
Daniel Soudry
Nathan Srebro

title: Kernel and Rich Regimes in Overparametrized Models

authors:
Bo Xie
Yingyu Liang
Le Song

title: Diversity leads to generalization in neural networks

venue: arXiv preprint Arxiv:1611.03131,

authors:
Gilad Yehudai
Ohad Shamir

title: On the power and limitations of random features for understanding neural networks

venue: arXiv preprint arXiv:1904.00687,

authors:
Bing Yu
Junzhao Zhang
Zhanxing Zhu

title: On the Learning Dynamics of Two-layer Nonlinear Convolutional

venue: Neural Networks. CoRR,

authors:
Yuqian Zhang
Han-Wen Kuo
John Wright

title: Structured local optima in sparse blind deconvolution

authors:
Kai Zhong
Zhao Song
Prateek Jain
Peter L Bartlett
Inderjit S Dhillon

title: Recovery guarantees for one-hidden-layer neural networks

venue: arXiv preprint arXiv:1706.03175,

heading: 1 Introduction

text:
Recently, deep learning (using multi-layer, non-linear neural networks) has demonstrated superior performance over traditional linear learners in many machine learning tasks. These achievements have bred much theoretical investigation into whether neural networks are, in fact, superior - and why. On the one hand, the Neural Tangent Kernel (NTK) and derivative works show that, under certain (limiting) conditions, a gradient-descent-trained neural network reduces to a kernel method with a specific architecture- and initialization-determined kernel [Jacot et al., 2018, Du et al., 2019]. However, this does not seem to be the full story, as it fails to capture the feature learning aspect of neural network training. This distinction between a fixed feature representation and a data-adaptive feature representation has been studied from a variety of perspectives, including the lazy vs. active regime framework [Chizat et al., 2019, Woodworth et al., 2020, Moroshko et al., 2020, Geiger et al., 2020, Wang et al., 2020]. Building on these insights, there has been increasing interest in now showing a provable gap between the performance of neural networks and kernel methods in various settings [Ghorbani et al., 2019, 2020, Allen-Zhu and Li, 2019, 2020, Li et al., 2020b, Malach et al., 2021, Kamath et al., 2020, Refinetti et al., 2021, Daniely and Malach, 2020, Chen et al., 2020, Domingo-Enrich et al., 2021].
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
In this work, we extend this theoretical investigation into the superiority of neural networks over linear learners and, inspired by practical settings, propose a new line of reasoning that we refer to as “Local Signal Adaptivity”. In particular, we explore the power of convolutional neural networks (CNNs) in image classification, compared to linear functions over prescribed feature mappings.
Our setting: We study a simple data distribution that captures one key property of natural image classification tasks: a small set of localized “label-determining” features embedded within a “noisy” background. We formally prove that even when such background occupies a rather large fraction of an image, a CNN can be quite effective at locating the label-determining signal and thus ignoring background information that is mostly irrelevant to the true label, to achieve high accuracy.
Our result: In the formal setting of our simple data distribution (presented in Section 3), we ask whether a particular two-layer CNN trained via stochastic gradient descent can provably acquire this “signal-finding” ability and how this compares to its associated finite-width convolutional neural tangent kernel (CNTK). We answer with a separation result between our CNN and its CNTK: We formally prove that a small CNN, trained using standard SGD from random initialization, can efficiently learn to find the “signal” and threshold out the noise, whereas the corresponding CNTK requires a comparatively larger model (i.e., with more features) in order to accomplish this.
Empirical justification: While we pick a simple data distribution in our work to illustrate the main idea and obtain a formal proof, we point out that our setting is very natural in real images: in many image classification tasks, the label-determining feature only occupies a small fraction of the image, and most other parts are background noise (Figure 1). Furthermore, in neural networks trained on natural images, it is generally accepted that activation patterns become increasingly sparse throughout training, effectively zeroing out the activations of low-magnitude noise and locating the true signal (suggestive of the denoising/LSA phenomenon studied in this work). For completeness, we have included such an experiment in Figure 2 above, illustrating how the average percentage of active neurons per instance decreases throughout training (details are provided in Appendix C). Finally, to empirically study our theoretical results, we create new datasets by embedding CIFAR-10 and MNIST images within either random Gaussian or IMAGENET backgrounds. Our experiments show that, as the intensity of the background noise grows and thus the “denoising task” becomes harder, the performance of the neural network stays relatively stable, while the performance of the corresponding NTK does, in fact, degrade significantly (Section 6, Figure 4).
Based on our theorem and experiments, we therefore believe that this per-instance “signal finding within noisy backgrounds” ability of convolutional neural networks, which we dub “Local Signal Adaptivity” (LSA), is one key component of the superiority of SGD-trained convolutional neural networks over fixed feature mappings.

heading: 2 Related work

text:
There is a long line of work proving that various concept classes can be learned efficiently by SGDtrained neural networks. Many of the theoretical works taking a “beyond-NTK” perspective and emphasizing the non-linearity of neural networks are only proved under Gaussian inputs [Kawaguchi, 2016, Soudry and Carmon, 2016, Xie et al., 2016, Ge et al., 2017, Soltanolkotabi et al., 2017, Tian, 2017, Brutzkus and Globerson, 2017, Zhong et al., 2017, Li and Yuan, 2017, Boob and Lan, 2017, Li et al., 2018, Vempala and Wilmes, 2018, Ge et al., 2018, Bakshi et al., 2018, Oymak and Soltanolkotabi, 2019, Yehudai and Shamir, 2019, Li and Yuan, 2017, Li and Liang, 2017, Li et al., 2016, Li and Dou, 2020, Li et al., 2020a]. In our work, we consider a more realistic setting in which there is a highly-structured signal hidden within random background noise. Along these lines, we recognize various aesthetic similarities to sparse blind deconvolution and related areas of the signal processing literature [Zhang et al., 2019, Kuo et al., 2019, Sun and Donoho, 2021, Qu et al., 2020]. However, there are key structural differences as well - e.g., rather than recovering the unknown sparse signal, we simply wish to extract the information relevant to the classification task; thus, further exploring possible connections between LSA and the signal processing literature presents an interesting avenue for future work.
We now give a more detailed comparison of our work with prior theoretical results on the separation between neural networks and kernels.
Representation power of neural networks. Many existing works focus on separating the representation power of neural networks from that of other models [Ghorbani et al., 2020, Refinetti et al., 2021, Gribonval et al., 2020, Suzuki, 2019, Suzuki and Nitanda, 2019]. However, the fact that a function can be represented efficiently by a neural network does not mean that it can be efficiently learned. Only a subset of such works prove efficient learnability, including Suzuki and Akiyama [2020] and Daniely and Malach [2020]. In our work, we focus on the set of functions that can be efficiently learned by neural networks, in particular learned via stochastic gradient descent over the standard training objective starting from random initialization.
Classification vs. regression. Many existing works only focus on separating the power of neural networks from that of other learners in a regression setting [Ghorbani et al., 2020, Suzuki and Akiyama, 2020, Allen-Zhu and Li, 2020, 2019, Li et al., 2020a, Wei et al., 2018, Yehudai and Shamir, 2019]. In this case, both the neural network and the other learning methods are required to fit the exact label. Although Daniely and Malach [2020] presents one of the few results in a classification setting, their final separation result is still in terms of hinge loss instead of 0-1 loss. In our result, we focus on the binary classification setting, where the neural network and (significantly) the linear learner are only required to fit the sign of the label, instead of the exact labeling function. Our final result is therefore more natural in image classification settings than prior works.
Learning a hidden subspace. Many of the existing works showing how neural networks are better than other learners, in particular kernel methods, focus on the case where the concept class is of the form f(x) = φ(Wx), where W is a rank-deficient matrix [Ghorbani et al., 2020, Wei et al., 2018]. Thus, the learning process can be divided into two phases: (1) Identifying the hidden subspace of W ; (2) Learning the function φ over this hidden subspace. We point out that to the best of our knowledge, all the cited works only shows the superior power of neural networks in (1). This means that, if W were known, then a neural network would have the same sample/time complexity as kernels when performing (2). As we will show, in our work, the underlying concept class does not have a fixed subspace, rather the signal can drift between different patches, and the neural network needs to identify the signal patch while ignoring the noise patches. Our explanation of how neural networks outperform kernels is therefore fundamentally different from the cited works.
Kernel lower bounds. Most of the existing theoretical works demonstrating the power of neural networks focus on showing how neural networks are better than kernel methods or linear functions over prescribed feature mappings. There are two related lines of work: (1) Showing that neural networks are better than any kernel method or any linear learner [Allen-Zhu and Li, 2020, Daniely and Malach, 2020]; (2) Showing that neural networks are better than a particular set of linear learners, most notably, the NTKs or finite-width NTKs of the corresponding neural network [Yehudai and Shamir, 2019, Refinetti et al., 2021, Wei et al., 2018]. Our work belongs to the second line.
Although a result along the first line gives a much stronger separation, we point out that in the classification setting, such a separation is known to be extremely challenging in computational complexity theory [O’Donnell and Servedio, 2003, Sherstov and Wu, 2019].
Finite- vs. infinite-width NTK. Empirical results in the literature suggest that the infinite-width NTK generally reaches slightly higher final test accuracy than the finite-width NTK [Allen-Zhu and Li, 2020, Lee et al., 2020]. In fact, in certain limited settings, such as low-data regimes, the infinite-width NTK has actually demonstrated performance competitive with that of the original neural network [Arora et al., 2020]. However, under certain conditions, the computational cost of the infinite-width NTK can be significant compared to that of the original neural network and its corresponding finitewidth NTK [Allen-Zhu and Li, 2020, Lee et al., 2020]. Therefore, due to these computational and accuracy distinctions between the finite- and infinite-width NTKs, in our experiments we examine both types of NTK. Our theoretical lower bound, however, is a representational lower bound for the finite-width NTK. This is primarily due to theoretical challenges such as those discussed above. Theoretical results such as Allen-Zhu and Li [2020] suggest that it may be possible, in follow-up work, to convert our finite-width NTK representational lower bound into an infinite-width NTK sample complexity lower bound. However, proving a sample complexity gap would likely require tightening our sample complexity upper bound as well. We believe, conceptually (and supported by our experiments), that the LSA phenomenon is at play for infinite-width NTKs as well, and it would thus be interesting to extend our theoretical gap to the infinite-width NTK setting as well.

heading: 3 Problem setup

text:
We now formally state our data distribution and the learning problem in our paper.
Relevant problem parameters. We consider the input X = (X1, · · · , Xk+1) to have k + 1 patches; each patch is associated with a vector Xi ∈ Rd. We can think of X as either the input image or the output of some intermediate layer of the convolutional neural network. It is convenient to think of X as a matrix with k + 1 rows and d columns, i.e., X ∈ R(k+1)×d. We treat k as “large” and d as polynomial in k, enabling us to simplify certain results by expressing them entirely in terms of k. We consider an unknown signal vector w? ∈ Rd with `2-norm ‖w?‖2 = 1, which determines how each (image) X is generated (described below). We also set σ = log k/ √ k, where σ determines the intensity of the noise in our problem (described below). In Section 5, we will only prove the kernel lower bound in the case where σ2 = 1/d; extending the result to σ2 = ω(1/d) might require alternative proof techniques.
Data distribution. We sample each (image, label) pair (X, y) ∼ D. The marginal distribution Dy is a uniform distribution over {−1, 1}, i.e., both classes occur with equal probability. We first sample y fromDy and then sample X ∼ DX|y as follows: (a) draw i? from {1, . . . , k+ 1} arbitrarily and put yw? in row i? (we call this the “signal” row); (b) in each of the k remaining rows (we call these the “noise” rows), put an independently-drawn vector i ∼ N (0, σ2Id×d). We use Xi ∈ Rd to denote row i of X , for i ∈ {1, . . . , k + 1}. Formally, we therefore have:
Xi =
{ yw? if i = i?
i otherwise.
Our data distribution shares many similarities with the distribution studied in Yu et al. [2019]. However, perhaps most crucially among the differences, the noise magnitude in our setting is significantly higher; in Yu et al. [2019], the noise magnitude is low enough to maintain linear separability, which is insufficient to show any separation with linear learners.
Remark. We consider the simplest setting where there is only one feature w?, though our result trivially extends to the case when there are multiple orthogonal features (as many as d). For example, the signal patch can contain features of the form ∑ i αiw ? i , where the label is determined by ∑ i αi, as in Allen-Zhu and Li [2020].
How to learn this concept class. In our concept class, one of the rows Xi is associated with the true signal yw?, and all the others are random Gaussian noise. Since this row can appear arbitrarily
in one of the k + 1 rows, the most naive way to learn this function is to use a convolutional linear classifier: l(X) = ∑k+1 i=1 〈w?, Xi〉. However, we argue that this linear classifier is actually very bad and cannot be used to classify the labels correctly. Note that in our problem setup, the noise rows are sampled according to N (0, σ2Id×d), which means that for each noise row i, we have 〈w?, Xi〉 ∼ N (0, σ2). Hence, the total accumulated noise over k noise rows would be N (0, kσ2). By our choice of σ = log k/ √ k, this means that the total noise is much bigger than the signal |y| = 1. Hence, the linear classifier fails to classify the labels correctly with at least probability 0.49.
The above argument suggests that, to learn the concept class, the model cannot naively sum up 〈w?, Xi〉. Rather, the model has to identify the signal row and ignore the noise rows. In other words, the model needs to distinguish between the case when 〈w?, Xi〉 is large (y) or small (N (0, σ2)). As we will show, this can be efficiently learned by a neural network with ReLU activations, trained using standard stochastic gradient descent from random initialization.
Convolutional neural network (CNN) architecture. Our goal is to learn the optimal parameters w ∈ Rd, b ∈ R of the following simple CNN:
fw,b(x) = k+1∑ i=1 φb(〈w, Xi〉) = k+1∑ i=1 [ ReLU(〈w, Xi〉+ b)− ReLU(−〈w, Xi〉+ b) ] .
This CNN can be understood from either of two equivalent perspectives:
(1) A single convolutional filter w ∈ Rd with stride d is applied to the image. Then the softthresholding activation function φb(x) = ReLU(x+ b)− ReLU(−x+ b) is applied pointwise over the resulting (k+ 1)-dimensional vector. Finally, the second (non-trainable) layer of the CNN simply sums up the k + 1 entries (i.e., the second layer is a fully-connected layer mapping from Rk+1 to R, with non-trainable weights all equal to 1).
(2) Two convolutional filters, each with stride d, are applied to the image. One filter is w ∈ Rd and the other is −w ∈ Rd. After each filter is applied, the activation function ϕb(x) = ReLU(x + b) is applied pointwise to all 2k + 2 pre-activation values (i.e., a k + 1 “vector” with 2 channels). A non-trainable fully-connected layer is then applied, mapping R2k+2 to R; in this layer, each of the k + 1 weights applied to the the first channel (i.e., from filter w) are all 1, and each of the weights applied to the second channel (i.e., from filter −w) are all −1. The key in both perspectives is how the two ReLU activation functions work together to implement a soft-thresholding function, which enables denoising. Throughout, we refer to our CNN as having one filter, since it only has d+ 1 trainable parameters, regardless of which perspective is taken.
Training algorithm. We initialize b deterministically at 0. We initialize w randomly by drawing from N ( 0, σ20Id×d ) , where σ0 is 1/poly(k). We train the above CNN using mini-batch stochastic
gradient descent (SGD) with the logistic loss, where the logistic loss ` is defined as `(fw,b(X), y) := log ( 1 + e−yfw,b(X) ) .
Specifically, at each iteration of SGD, we use poly(k) fresh samples from D. This will allow us to argue that, at each iteration, the empirical gradient is very close to the true population loss gradient.
To simply the proof, we use a slightly smaller learning rate for b (denoted ηb) than for w (denoted ηw). Specifically, we adopt a 1/poly(k) learning rate for w, and we set ηb/ηw = 1/k. With a bit more technical care, our proofs can be extended to cover the setting where ηb = ηw but we use this simpler version to illustrate the main idea of the learning process, as we will state in the next section.
To avoid any ambiguity, we define this procedure explicitly as Algorithm 1.
Algorithm 1 Mini-batch SGD
Initialization and learning rate b(0) ← 0; w(0) ← N (0, σ20Id×d); ηb ← η/k; ηw ← η for t← 1 . . . T do
Sample a mini-batch of examples of size n = poly(k): Z ← Dn Compute the stochastic gradient: gb = 1n ∑ z∈Z ∇b`(z), gw = 1 n ∑ z∈Z ∇w`(z)
Update using stochastic gradient descent: b(t) ← b(t−1) − ηbgb, w(t) ← w(t−1) − ηwgw return b(T ),w(T )
Additional notation. We will occasionally use the shorthand ft(·) to denote fw(t),b(t)(·), the network at iteration t. We use the standard big-O notation and its variants: O(·), o(·),Θ(·),Ω(·), ω(·), where k is the problem parameter that becomes large. Occasionally, we use the symbol Õ(·) (and analogously with the other four variants) to hide log k factors.
Our results will hold with high probability over the random initialization of w and the randomness of the mini-batches, where “high probability” here means a failure probability super-polynomially small in k. Unless specified otherwise, w.h.p. can be taken to mean: with probability at least 1−e−Ω(log2 k).

heading: 4 Neural network results

text:
We now present and briefly describe our main result on the provably efficient learning of the CNN described in Section 3.
Theorem 1 (Main result). There exists an absolute constant k0 such that, for every k ≥ k0, using poly(k) samples from D, learning rate η = 1/poly(k), and T = poly(k) iterations, w.h.p. over the randomness of the initialization and the samples, we have Pr(X,y)∼D[sign(fT (X)) 6= y] ≤ 0.01, for the final network fT returned by Algorithm 1.
Therefore, in contrast to its corresponding Neural Tangent Kernel (Section 5), our CNN trained via SGD provably achieves high accuracy efficiently. This stands in contrast to some of the prior works discussed in Section 2, many of which do not prove efficient learnability.
We defer our detailed proofs to Appendix A and summarize the key ideas here.
Empirical vs. population gradients. Our general proof technique involves analyzing the gradient of the population loss at each iteration (we call this the true gradient): ∇wE(X,y)∼D[`(fw,b(X), y)] and ∇bE(X,y)∼D[`(fw,b(X), y)]. Then, with poly(k) samples per mini-batch, we argue that w.h.p. the empirical gradient concentrates around the true gradient, and over T = poly(k) steps, the accumulated error is fairly small. This argument is made rigorous in Appendix A. Therefore, in the remainder of this section, to illustrate the key idea of the proof, we limit our discussion to the true gradient as just defined (and use the term gradient or derivative without further qualification).
Learning the signal direction. As training progresses, w ·w? grows from its small-magnitude initialization to a relatively large, but still O(1), positive value. Specifically, at each iteration, the gradient with respect to w has a component parallel to w?, with two opposing forces determining the sign/magnitude of this component: in expectation over (X, y) ∼ D,
1. the k “noise” rows of X push w ·w? to shrink and 2. the “signal” row pushes w ·w? to grow.
The “signal” row’s contribution has a magnitude of Θ(1), and the k “noise” rows have a total contribution of magnitude at most O ( |w ·w?| · k log k · σ2 ) = O ( |w ·w?| · log3 k ) . Therefore, as long as |w · w?| = o(1/ log3 k), the “signal” row’s contribution overpowers the “noise” rows’ contribution, causing w ·w? to grow. This means that, within Θ((ηw log4 k)−1) = poly(k) iterations, w·w? rises from its small-magnitude initialization to Θ(1/ log4 k). After w·w? rises to Θ(1/ log4 k), we no longer track its dynamics explicitly, as it must stay somewhere between Ω(1/ log4 k) andO(1) throughout the rest of training, and this turns out to be sufficient for the remainder of the argument. The main lemma we prove in Appendix A regarding the growth of w ·w? is a slightly more formal version of the following:
Lemma 1 (Sketched). For any t ≤ T , if |w(t) ·w?| = o ( 1 log3 k ) , then ∇wE[`(ft(X), y)] ·w? = −Θ(1).
Bounded growth along non-signal directions. As training progresses, we also track ‖w − (w · w?)w?‖2, the magnitude of w’s projection onto the orthogonal complement of span{w?}. Although the projection’s direction can change, we show that its norm remains very small, allowing w ·w? to dominate.
Specifically, letting w⊥ denote w − (w · w?)w? at the start of iteration t, we show that ∇wE[`(ft(X), y)] ∈ span{w?,w⊥}. Further, ∇wE[`(ft(X), y)] ·w⊥/‖w⊥‖2 mirrors the “noise” contribution above: it has magnitude at most O ( ‖w⊥‖2 · k log k · σ2 ) = O ( ‖w⊥‖2 · log3 k ) and pushes ‖w⊥‖2 to shrink. Thus, if we were actually using the true gradient, w⊥ would maintain its direction, and its norm would shrink. The effect of the stochastic gradient is that w⊥ can change direction slightly, and its norm can grow a bounded amount per iteration; however, as long as the mini-batch size is large enough (poly(k) suffices), its norm stays small enough throughout training. The main lemma we prove in Appendix A regarding ‖w⊥‖2 is therefore a slightly more formal version of the following:
Lemma 2 (Sketched). For any t ≤ T , let g(t)⊥ denote ∇wE[`(ft(X), y)] · w (t) ⊥ /‖w (t) ⊥ ‖2. Then g (t) ⊥ ≥ 0 and g (t) ⊥ = O ( ‖w(t)⊥ ‖2 · log 3 k ) .
Learning to threshold out the noise. The derivative with respect to b similarly has two opposing forces determining its sign/magnitude: in expectation over (X, y) ∼ D,
1. the k “noise” rows of X push b to decrease and 2. the “signal” row pushes b to increase.
The “signal” row’s contribution has a magnitude of Θ(1). Thus, we can only guarantee that b is decreasing if the “noise” rows’ total contribution is ω(1). Roughly, the “noise” rows’ contribution is determined by (i) the scalar projection of each noise vector i onto w and (ii) (when b < 0) how much of these scalar projections survive “thresholding”. As ‖w‖2 grows throughout training (primarily due to the growth of w ·w?, discussed above), (i) becomes larger. However, as b decreases (i.e, |b| grows, for b < 0), (ii) becomes smaller (i.e., much of the noise does not survive “thresholding”). Therefore, the crux of the proof is to show that, as long as the probability of misclassification is still > 0.01, despite b already “thresholding out” a fair amount of the noise, the “noise” rows’ total contribution will remain ω(1) and thus cause b to further decrease. The main lemma we prove in Appendix A regarding b is therefore a slightly more formal version of the following: Lemma 3 (Sketched). For any t ≤ T , if w(t) ·w? = ω(1/k1/8), then∇bE[`(ft(X), y)] = Ω(1).
We note that the requirement w(t) ·w? = ω(1/k1/8) is satisfied by the Ω(1/ log4 k) lower bound presented above, thus connecting the two phases of training.
Comment on actual dynamics. The elegance of this approach is that it largely allows us to ignore b’s behavior prior to w ·w? reaching the Ω(1/ log4 k) regime. In reality, there is a short phase at the beginning of training during which b grows (i.e., becomes increasingly positive); this occurs because, even though none of the noise is being “thresholded out” at this point, ‖w‖2 is not yet large enough for the “noise” rows’ contribution to dominate the “signal” row’s Θ(1) contribution (which itself does not scale with ‖w‖2). Then, at some point prior to w ·w? reaching Ω(1/ log4 k), b begins to decrease rather than increase - and, as we prove, eventually continues to decrease throughout the rest of training. However, for our performance guarantee, it does not matter exactly when this transition from increasing to decreasing actually occurs. The ηb/ηw = 1/k ratio ensures that |b|/|w ·w?| never exceeds Θ(1/k) while b > 0, which means that b = O(1/k) throughout its positive phase.
Provable efficiency. We argue that if Pr(X,y)∼D[sign(fT (X)) 6= y] ≥ 0.01, then we must have |w ·w?| = O(1). This, along with the rest of the argument, is made fully rigorous in Appendix A. We sum up the total number of iterations as follows. First, there are O((ηw log4 k)−1) iterations before b begins to decrease. Then, because |w · w?| = O(1), ∇bE[`(ft(X), y)] = Ω(1), and the classification accuracy is controlled by the ratio |b|/|w · w?|, we conclude that there are poly(k) iterations before |b| becomes large enough to yield Pr(X,y)∼D[sign(fT (X)) 6= y] ≤ 0.01. Thus, T = poly(k), and with poly(k) samples per mini-batch, we have total sample complexity poly(k).
Illustration of training dynamics with synthetic data. Figure 3 illustrates these training dynamics on synthetic data (with k = 1000, d = 10, σ = 1, ηw = 0.1, ηb = 0.1/1000). As can be seen in the figure, as training progresses, w ·w? increases and b decreases (i.e., b < 0, with increasing magnitude). Furthermore, as the ratio |b|/|w ·w?| grows (and thus more and more noise is “thresholded out”), the test accuracy increases as well, tightly aligning with the theory.

heading: 5 Kernel results

text:
In this section, we compare the function learned by our simple convolution neural network to its corresponding finite-width CNTK [Allen-Zhu et al., 2019]. We define the finite-width CNTK as:
kw(X) = ∑ i∈[k] ∑ j∈[m] 〈wj , Xi〉1|〈w(0)j ,Xi〉|+bj≥0,
which is a linear function over the gradient of fw,b(X) at initialization. We show that this NTK is unable to classify the target function correctly, unless the total number of channels m is large.
We prove this for the case where σ2 = 1/d. Extending the result to σ2 = ω(1/d) might require alternative proof techniques.
Theorem 2. As long as m = O(1), w.p. at least 0.999 over the random initialization {w(0)j }j∈[m] where each w(0)j i.i.d. ∼ N (0, σ20I), we have that for every set of weights w and for every set of biases {bj}j∈[m],
Pr X,y∼D
[sign(kw(X)) 6= y] ≥ 0.1.
Compared to our convolutional neural network, which only requires m = 1 neurons and can learn the target function correctly, the corresponding finite-width CNTK needs ω(1) neurons in order to even represent the target function. This is due to the fact that the features w(0)j are prescribed at random initialization, instead of trained. Thus, even with arbitrary tuned bias bj , the neural tangent kernel still fails to adapt to the local signal and perform denoising.

heading: 6 Experiments

text:
We now provide concrete empirical evidence that the LSA phenomenon does explain the performance gap between CNNs and kernels in real-world datasets. We first construct several variants of CIFAR-10 [Krizhevsky, 2009] with various forms of structured noise and compare how the scale of the noise affects CNNs and their corresponding finite-width NTKs. Next, we perform similar experiments using a smaller CNN on MNIST [LeCun et al., 2010]; in this setting we can efficiently compute the infinite-width NTK, as well as vary the width of the finite-width NTK, and observe whether the performance gap persists. CNN architecture and training details are given in Appendix C.1
CIFAR with structured noise. We construct several CIFAR-10 variants with structured noise, which capture a key property of real-world image classification tasks, that the signal is localized to patch amidst a large amount of background noise. Although real-world images also exhibit this property (as in Figure 1), we wanted the ability to easily vary the intensity of the background noise, while leaving the signal intact. On each dataset, we compare the performance of a 10-layer WideResNet (with widening factor of 10) to that of its finite-width NTK [Zagoruyko and Komodakis,
1Code for experiments is available at https://github.com/skarp/local-signal-adaptivity.
2016]. We vary the intensity of the noise and observe the resulting degradation in WideResNet (WRN) and NTK performance.
Each dataset is constructed by scaling a CIFAR image to 16x16 pixels and placing it onto a 32x32 noise background. In some instances described below, we used IMAGENET backgrounds [Deng et al., 2009]. Here we highlight experiments on four such datasets:
• CIFAR-10, IMAGENET noise. CIFAR-10 images are placed at a random location onto random background image chosen from the IMAGENET Plants synset. The Plants synset was chosen for its visual similarity to backgrounds in real images. In our experiments, we scale the background pixel intensity in a range between zero (black background) and one (original IMAGENET background). An example is shown in Figure 5 (bottom).
• CIFAR-2, IMAGENET noise. Same as above, except the CIFAR-10 classes are grouped into animals and vehicles and the classification task is now binary. In contrast to CIFAR-10, on CIFAR-2 the NTK performs nearly as well as the CNN in the zero-noise setting.
• CIFAR-2, Gaussian noise. Also using the CIFAR-2 task, but with standard Gaussian noise in the background, for a range of standard deviations σ.
• CIFAR-VEHICLES. The task is to classify between the four vehicle classes from CIFAR10. The vehicle appears in a random corner of the image, and the other three corners are filled with random images from the four CIFAR-10 animal classes. See Figure 5 (top). Unlike the relatively uniform IMAGENET plants backgrounds, this dataset is designed to capture a common type of background noise which consists of “distractor" signals which are not predictive of the true image class. For example, irrelevant people, bicycles, and birds could all occur in the background of a real-world vehicle-classification task.
For a more natural setting, we conduct an additional experiment on CIFAR-2 with IMAGENET noise, but maintaining the full pixel intensity and varying the size of the background noise. This is detailed in Appendix D, along with additional experiment variants such as different image placements, all of which display similar behavior to the experiments described here. While these datasets capture key attributes of real images, their synthetic construction does limit how realistic the images can be. We construct the datasets in this way in order to allow tunable noise levels, thus providing the x-axis of the plots in Figure 4. One could imagine alternative, more realistic ways of creating tunable noise levels, such as increasing the diversity of distractor images; these are viable avenues for future experimentation.
Observations. As seen in Figure 4, as the scale of the noise increases, NTK performance decreases significantly while WRN performance is relatively unaffected. Table 1 gives the percent of test
accuracy retained by each model as noise intensity increases from 0 to 1 (or from σ = 0 to σ = 2 in the Gaussian-noise case); that is, the percentage 100 · test acc. at max noise leveltest acc. at zero noise . The WRN always retains over 96% of its zero-noise performance, while the NTK in one case degrades below 70%.
Effect of NTK width (MNIST). We place MNIST images of size 28x28 onto 42x42 Gaussiannoise backgrounds. We use a small CNN with two convolutions with 8 and 16 channels, and compare to finite-width NTKs where the width has been increased by a factor of between 50 and 100. On a subset of 20k MNIST images, we also compare the same CNN and finite-width NTK (width factor=1) to the infinite-width NTK.
The results (Figure 6) indicate that the degradation of NTK performance persists for both infiniteand finite-width NTKs (regardless of finite NTK width). Results for intermediate NTK widths are shown in Appendix D. Another desirable feature which we observe in the MNIST setting is that the NTK and CNN perform on-par in the presence of zero noise.

heading: 7 Conclusion

text:
We have considered a simple, noisy data distribution that captures some of the key structure seen in natural images. We have (1) provably shown that a particular two-layer CNN trained via SGD can efficiently (in time and sample complexity) achieve high accuracy and (2) that its corresponding linear model (the finite-width NTK) requires a larger network size (i.e., more features). Overall, our results shed light on a new mechanism through which neural networks are provably better than their corresponding kernels: in particular, when there is a signal hidden within background noise, a neural network is able to simultaneously adapt to the local signal and perform “denoising”. We provide empirical justification showing that our theoretical framework does coincide with the superior power of neural networks over linear learners in practice. One avenue for future work involves extending the noise distribution: increasing σ beyond log k/ √ k, which can provide an even stronger separation with linear learners, and extending to other noise models beyond Gaussian. Another possible extension is to drop the restriction that the same filter is used in both parts of the activation function and study whether this soft-thresholding behavior is recovered automatically upon training the final-layer weights. We could also consider more general models in which the signal “patch” and the CNN filter are not perfectly aligned. Another possibility is to develop a limitation result for all kernel methods instead of the CNTK corresponding to our CNN; however, as discussed in Section 2, this would likely be a regression result instead of a classification result, which is weaker in other ways. Finally, it would be interesting to extend this theoretical analysis to deeper networks and thus more practical CNNs (perhaps “hierarchical denoising”).
[Ethics statement] Our work is primarily theoretical in nature and analyzes existing methods; thus, to the best of our knowledge, it does not have any negative societal impact.
Acknowledgments & Funding Disclosure
The authors thank Zico Kolter for conversations about the experiments and Jaehoon Lee and Ben Adlam for their help in navigating the neural-tangents API. The authors also thank the anonymous NeurIPS reviewers for their thoughtful, helpful feedback. YL acknowledges support from NSF RI 2007517.

title: Local Signal Adaptivity: Provable Feature Learning in Neural Networks Beyond Kernels


summaries: This work studies the problem of decentralized nonconvex optimization problems and it is relevant to the conference. The paper provides convergence analysis for an existing and well-studied algorithm -- stochastic gradient tracking algorithms, without providing any improvements. The paper prove its algorithm the same convergence compared to existing works. There are some light and limited experiments associated with the paper, but only limited to quadratic case.

summaries: This paper studies the gradient tracking method for decentralized optimization. While it is widely used, its convergence rate is not optimal compared with some other methods. This paper provides a tighter analysis for nonstrongly convex problems, strongly convex problems, and nonconvex problems. Faster convergence rates are proved in this paper.

summaries: The paper studies  the gradient tracking (GT) algorithm for stochastic distributed optimization problems over undirected, static graphs; nonconvex, strongly convex and weakly convex local objective functions are considered. The claimed contribution is a new line of analysis unlocking tighter (asymptotic) convergence rates than those already developed in the literature. The impact of some network parameters on the convergence rate is also discussed, and validated via some (albeit limited)  numerical results.

summaries: This paper analyzes Gradient Tracking, a very common decentralized optimization algorithm, in the stochastic setting. The authors first introduce the standard gradient tracking algorithms, along with the assumptions they use to analyze it. Then, they provide convergence results in 3 main settings: non-convex, strongly-convex and weakly-convex. In each case, the leading order term matches the rates of centralized mini-batch SGD, meaning that the methods are fast (at least when this term dominates). It is argued that many interesting extensions naturally fit in this framework and could be adapted without too much efforts.  Then, a proof sketch is given, and highlights the importance of studying the consensus difference X_t - \bar{X_t}, where \bar{X_t} is the average over all nodes, instead of studying just X_t. The other key ingredient is that a simple recursion, can be written with the consensus difference on both GT variables. Although the operator J involved in this recursion is not contractive at each step (spectral radius greater than 1), J^i with i large enough is contractive (spectral radius smaller than 1/2), which allows to prove convergence of the recursion.  Then, the rates obtained for Gradient Tracking are compared with rates previously obtained in the literature, and they compare favorably overall. Finally, some toy experiments are given to analyze the impact of the graph-dependent constants c and p that were introduced and that appear in the higher order terms. These experiments seem to confirm the theoretical rates.

abstractText: We consider decentralized machine learning over a network where the training data is distributed across n agents, each of which can compute stochastic model updates on their local data. The agent’s common goal is to find a model that minimizes the average of all local loss functions. While gradient tracking (GT) algorithms can overcome a key challenge, namely accounting for differences between workers’ local data distributions, the known convergence rates for GT algorithms are not optimal with respect to their dependence on the mixing parameter p (related to the spectral gap of the connectivity matrix). We provide a tighter analysis of the GT method in the stochastic strongly convex, convex and non-convex settings. We improve the dependency on p from O(p−2) to O(p−1c−1) in the noiseless case and from O(p−3/2) to O(p−1/2c−1) in the general stochastic case, where c ≥ p is related to the negative eigenvalues of the connectivity matrix (and is a constant in most practical applications). This improvement was possible due to a new proof technique which could be of independent interest.

authors:
Sulaiman Alghunaim
Ernest Ryu
Kun Yuan
Ali Sayed

title: Decentralized proximal gradient algorithms with linear convergence rates

venue: IEEE Transactions on Automatic Control,

authors:
Sulaiman A. Alghunaim
Ali H. Sayed

title: Linear convergence of primal–dual gradient methods and their performance in distributed optimization

authors:
Mahmoud Assran
Nicolas Loizou
Nicolas Ballas
Michael Rabbat

title: Stochastic gradient push for distributed deep learning

venue: In Proceedings of the 36th International Conference on Machine Learning (ICML). PMLR,

authors:
Stephen Boyd
Arpita Ghosh
Balaji Prabhakar
Devavrat Shah

title: Randomized gossip algorithms

venue: IEEE/ACM Trans. Netw.,

authors:
Ofer Dekel
Ran Gilad-Bachrach
Ohad Shamir
Lin Xiao

title: Optimal distributed online prediction using mini-batches

venue: Journal of Machine Learning Resesearch (JMLR),

authors:
J.C. Duchi
A. Agarwal
M.J. Wainwright

title: Dual averaging for distributed optimization: Convergence analysis and network scaling

title: Uber die Abgrenzung der Eigenwerte einer Matrix

venue: Bulletin de l’Académie des Sciences de l’URSS. Classe des sciences mathématiques et na,

authors:
Lie He
An Bian
Martin Jaggi

title: COLA: Decentralized linear learning. In Advances in Neural Information Processing Systems 31 (NeurIPS), pages 4541–4551

authors:
Franck Iutzeler
Pascal Bianchi
Philippe Ciblat
Walid Hachem

title: Asynchronous distributed optimization using a randomized alternating direction method of multipliers

venue: In Proceedings of the 52nd IEEE Conference on Decision and Control,

authors:
B. Johansson
M. Rabi
M. Johansson

title: A randomized incremental subgradient method for distributed optimization in networked systems

venue: SIAM Journal on Optimization,

authors:
Peter Kairouz
H. Brendan McMahan
Brendan Avent
Aurélien Bellet
Mehdi Bennis
Arjun Nitin Bhagoji
Keith Bonawitz
Zachary Charles
Graham Cormode
Rachel Cummings
Rafael G.L. D’Oliveira
Hubert Eichner
Salim El Rouayheb
David Evans
Josh Gardner
Zachary Garrett
Adrià Gascón
Badih Ghazi
Phillip B. Gibbons
Marco Gruteser
Zaid Harchaoui
Chaoyang He
Lie He
Zhouyuan Huo
Ben Hutchinson
Justin Hsu
Martin Jaggi
Tara Javidi
Gauri Joshi
Mikhail Khodak
Jakub Konečný
Aleksandra Korolova
Farinaz Koushanfar
Sanmi Koyejo
Tancrède Lepoint
Yang Liu
Prateek Mittal
Mehryar Mohri
Richard Nock
Ayfer Özgür
Rasmus Pagh
Mariana Raykova
Hang Qi
Daniel Ramage
Ramesh Raskar
Dawn Song
Weikang Song
Sebastian U. Stich
Ziteng Sun
Ananda Theertha Suresh
Florian Tramèr
Praneeth Vepakomma
Jianyu Wang
Li Xiong
Zheng Xu
Qiang Yang
Felix X. Yu
Han Yu
Sen Zhao

title: Advances and open problems in federated learning

venue: Foundations and Trends R © in Machine Learning,

authors:
Sai P. Karimireddy
Satyen Kale
Mehryar Mohri
Sashank J. Reddi
Sebastian U. Stich
Ananda T. Suresh

title: SCAFFOLD: Stochastic controlled averaging for on-device federated learning

authors:
David Kempe
Alin Dobra
Johannes Gehrke

title: Gossip-based computation of aggregate information

venue: In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society,

authors:
Anastasia Koloskova
Sebastian Stich
Martin Jaggi

title: Decentralized stochastic optimization and gossip algorithms with compressed communication

venue: In Proceedings of the 36th International Conference on Machine Learning (ICML),

authors:
Anastasia Koloskova
Nicolas Loizou
Sadra Boreiri
Martin Jaggi
Sebastian U. Stich

title: A unified theory of decentralized sgd with changing topology and local updates

venue: In Proceedings of the 37th International Conference on Machine Learning (ICML). PMLR,

authors:
Jakub Konečnỳ
H. Brendan McMahan
Daniel Ramage
Peter Richtárik

title: Federated optimization: Distributed machine learning for on-device intelligence

venue: arXiv preprint arXiv:1610.02527,

authors:
Lingjing Kong
Tao Lin
Anastasia Koloskova
Martin Jaggi
Sebastian U. Stich

title: Consensus control for decentralized deep learning

venue: In Proceedings of the 38th International Conference on Machine Learning (ICML),

authors:
Dmitry Kovalev
Anastasia Koloskova
Martin Jaggi
Peter Richtarik
Sebastian U. Stich

title: A linearly convergent algorithm for decentralized optimization: Sending less bits for free

venue: In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (AISTATS),

authors:
Boyue Li
Shicong Cen
Yuxin Chen
Yuejie Chi

title: Communication-efficient distributed optimization in networks with gradient tracking and variance reduction

venue: In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (AISTATS),

authors:
Tian Li
Anit Kumar Sahu
Maziar Sanjabi
Manzil Zaheer
Ameet Talwalkar
Virginia Smith

title: On the convergence of federated optimization in heterogeneous networks

venue: arXiv preprint arXiv:1812.06127,

authors:
Tian Li
Anit Kumar Sahu
Manzil Zaheer
Maziar Sanjabi
Ameet Talwalkar
Virginia Smith

title: Fed- DANE: A federated Newton-type method

venue: arXiv preprint arXiv:2001.01920,

authors:
Xiang Li
Kaixuan Huang
Wenhao Yang
Shusen Wang
Zhihua Zhang

title: On the convergence of FedAvg on non-IID data

venue: International Conference on Learning Representations (ICLR),

authors:
Tao Lin
Sai Praneeth Karimireddy
Sebastian Stich
Martin Jaggi

title: Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data

authors:
Paolo Di Lorenzo
Gesualdo Scutari

title: NEXT: In-network nonconvex optimization

venue: IEEE Transactions on Signal and Information Processing over Networks,

authors:
Songtao Lu
Xinwei Zhang
Haoran Sun
Mingyi Hong

title: GNSD: a gradient-tracking based nonconvex stochastic algorithm for decentralized optimization

venue: In IEEE Data Science Workshop (DSW),

authors:
Brendan McMahan
Eider Moore
Daniel Ramage
Seth Hampson
Blaise Agüera y Arcas

title: Communication-efficient learning of deep networks from decentralized data

venue: In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS),

authors:
H. Brendan McMahan
Eider Moore
Daniel Ramage
Blaise Agüera y Arcas

title: Federated learning of deep networks using model averaging

venue: arXiv preprint arXiv:1602.05629,

authors:
A. Nedić
A. Ozdaglar

title: Distributed subgradient methods for multi-agent optimization

authors:
A. Nedić
S. Lee
M. Raginsky

title: Decentralized online optimization with global objectives and local communication

venue: In 2015 American Control Conference (ACC),

authors:
Angelia Nedić
Alex Olshevsky

title: Distributed optimization over time-varying directed graphs

title: Distributed gradient methods for convex machine learning problems in networks: Distributed optimization

venue: IEEE Signal Processing Magazine,

authors:
Angelia Nedić
Alex Olshevsky
Wei Shi

title: Achieving geometric convergence for distributed optimization over time-varying graphs

authors:
Angelia Nedić
Alex Olshevsky
Wei Shi
César A. Uribe

title: Geometrically convergent distributed optimization with uncoordinated step-sizes

venue: American Control Conference (ACC),

authors:
Angelia Nedić
Alex Olshevsky
Michael G. Rabbat

title: Network topology and communicationcomputation tradeoffs in decentralized optimization

venue: Proceedings of the IEEE,

authors:
Arkadii Semenovich Nemirovsky
David Borisovich Yudin

title: Problem complexity and method efficiency in optimization

authors:
Lam M. Nguyen
Phuong Ha Nguyen
Peter Richtárik
Katya Scheinberg
Martin Takáč
Marten van Dijk

title: New convergence aspects of stochastic gradient algorithms

venue: Journal of Machine Learning Research,

authors:
Shi Pu
Angelia Nedić

title: Distributed stochastic gradient tracking methods

venue: Math. Program.,

authors:
Guannan Qu
Na Li

title: Harnessing smoothness to accelerate distributed optimization

venue: IEEE Transactions on Control of Network Systems,

title: Multi-agent mirror descent for decentralized stochastic optimization

venue: In IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP),

authors:
Wei Shi
Qing Ling
Gang Wu
Wotao Yin

title: EXTRA: An exact first-order algorithm for decentralized consensus optimization

title: Unified optimal analysis of the (stochastic) gradient method

venue: arXiv preprint arXiv:1907.04232,

authors:
Sebastian U. Stich
Sai P. Karimireddy

title: The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication

authors:
Hanlin Tang
Xiangru Lian
Ming Yan
Ce Zhang
Ji Liu

title: D2: Decentralized training over decentralized data

venue: In Proceedings of the 35th International Conference on Machine Learning (ICML),

authors:
Hanlin Tang
Xiangru Lian
Shuang Qiu
Lei Yuan
Ce Zhang
Tong Zhang
Ji Liu

title: Deepsqueeze: Decentralization meets error-compensated compression

title: Problems in decentralized decision making and computation

venue: PhD thesis, Massachusetts Institute of Technology,

authors:
Isidoros Tziotis
Constantine Caramanis
Aryan Mokhtari

title: Second order optimality in decentralized non-convex optimization via perturbed gradient tracking

venue: In Advances in Neural Information Processing Systems (NeurIPS),

authors:
Thijs Vogels
Lie He
Anastasia Koloskova
Tao Lin
Sai Praneeth Karimireddy
Sebastian U. Stich
Martin Jaggi

title: Relaysum for decentralized deep learning on heterogeneous data. In Advances in Neural Information Processing Systems (NeurIPS)

authors:
Jianyu Wang
Anit Kumar Sahu
Zhouyi Yang
Gauri Joshi
Soummya Kar

title: MATCHA: Speeding up decentralized SGD via matching decomposition sampling

venue: Sixth Indian Control Conference (ICC),

authors:
E. Wei
A. Ozdaglar

title: Distributed alternating direction method of multipliers

venue: In IEEE 51st IEEE Conference on Decision and Control (CDC),

authors:
Lin Xiao
Stephen Boyd

title: Fast linear iterations for distributed averaging

venue: Systems & Control Letters,

authors:
Ran Xin
Anit Kumar Sahu
Usman A. Khan
Soummya Kar

title: Distributed stochastic optimization with gradient tracking over strongly-connected networks

venue: In IEEE 58th Conference on Decision and Control (CDC),

authors:
Kun Yuan
Sulaiman A. Alghunaim

title: Removing data heterogeneity influence enhances network topology dependence of decentralized SGD

venue: arXiv preprint arXiv:2105.08023,

authors:
Kun Yuan
Bicheng Ying
Xiaochuan Zhao
Ali H. Sayed

title: Exact diffusion for distributed optimization and learning - part I: algorithm development

venue: IEEE Trans. Signal Process.,

title: Exact diffusion for distributed optimization and learning - part II: convergence analysis

authors:
Kun Yuan
Wei Xu
Qing Ling

title: Can primal methods outperform primal-dual methods in decentralized dynamic optimization

venue: IEEE Transactions on Signal Processing,

authors:
Kun Yuan
Yiming Chen
Xinmeng Huang
Yingya Zhang
Pan Pan
Yinghui Xu
Wotao Yin

title: DecentLaM: Decentralized momentum SGD for large-batch deep training

venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV),

authors:
Jiaqi Zhang
Keyou You

title: Decentralized stochastic gradient tracking for non-convex empirical risk minimization

venue: arXiv preprint arXiv:1909.02712,

authors:
Minghui Zhu
Sonia Martínez

title: Discrete-time dynamic average

venue: consensus. Automatica,

heading: 1 Introduction

text:
Methods that train machine learning models on decentralized data offer many advantages over traditional centralized approaches in core aspects such as data ownership, privacy, fault tolerance and scalability [12, 33]. Many current efforts in this direction come under the banner of federated learning [17, 29, 28, 12], where a central entity orchestrates the training and collects aggregate updates from the participating devices. Fully decentralized methods, that do not rely on a central coordinator and that communicate only with neighbors in an arbitrary communication topology, are still in their infancy [24, 18].
The work of Lian et al. [24] on decentralized stochastic gradient descent (D-SGD) has spurred the research on decentralized training methods for machine learning models. This lead to improved theoretical analyses [16] and to improved practical schemes, such as support for time-varying topologies [32, 3, 16] and methods with communication compression [45, 51, 15, 47]. One of the most challenging aspect when training over decentralized data is data-heterogeneity, i.e. training data that is in a non-IID fashion distributed over the devices (for instance in data-center training) or generated in non-IID fashion on client devices [21, 13, 22, 23]. For example, the D-SGD method has been shown to be affected by the heterogenity [16].
In contrast, certain methods can mitigate the impact of heterogeneous data in decentralized optimization. For instance the gradient tracking (GT) methods developed by Lorenzo and Scutari [26] and Nedić et al. [34], or the later D2 method by Tang et al. [46] which is designed for communication typologies that remain fixed and do not change over time.
∗Current affiliation: CISPA Helmholtz Center for Information Security.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
It is well known that GT methods do not depend on the heterogeneity of the data and that they converge linearly on distributed strongly convex problem instances without stochastic noise [26, 34]. However, when we apply these methods in the context of machine learning, we need to understand how they are affected by stochastic noise and how they behave on non-convex tasks.
In this paper, we develop a new, and improved, analysis of the gradient tracking algorithm with a novel proof technique. Along with the parallel contribution [55] that developed a tighter analysis of the D2 algorithm, we now have a more accurate understanding of in which setting GT works well and in which ones it does not, and our results allow for a more detailed comparison between the D-SGD, GT and D2 methods (see Section 5 below).
Our analysis improves over all existing results that analyze the GT algorithm. Specifically, we prove a weaker dependence on the connectivity of the network (spectral gap) which is commonly incorporated into the convergence rates via the standard parameter p. For example, in the strongly convex setting with stochastic noise we prove that GT converges at the rate Õ ( σ2 nε + 1 c · ( σ√ pε + 1 p log 1 ε )) where σ2 is an upper bound on the variance of the stochastic noise, and c ≥ p a new parameter (often a constant). By comparing this result with the previously best known upper bound, Õ ( σ2 nε + 1 p · ( σ√ pε + 1 p log 1 ε )) , by Pu and Nedić [39], we see that our upper bound improves the last two terms by a factor of cp ≥ 1 and that the first term matches with known lower bounds [37]. The D2 algorithm [46] only converges under the assumption that c is a constant2 and the recent upper bound from [55] coincides with our worst case complexity for GT on all topologies where D2 can be applied. We provide additional comparison of GT convergence rates in the Tables 1 and 2.
Contributions. Our main contributions can be summarized as: • We prove better complexity estimates for the GT algorithm than known before with a new proof
technique (which might be of independent interest). • In the non-asymptotic regime (of importance in practice), the convergence rate depends on the
network topology. By defining new graph parameters, we can give a tighter description of this dependency, explaining why the worst case behavior is rarely observed in practice (see Section 5.1). We verify this dependence in numerical experiments. • We show that in the presence of stochastic noise, the leading term in the convergence rate of GT is
optimal—we are the first to derive this in the non-convex setting—and matching the unimprovable rate of all-reduce mini-batch SGD.

heading: 2 Related Work

text:
Decentralized Optimization. Decentralized optimization methods have been studied for decades in the optimization and control community [48, 30, 52, 6]. Many decentralized optimization methods
2In D2 the smallest eigenvalue of the mixing matrix W must bounded from below: mini λi(W ) ≥ − 13 .
[30, 11] are based on gossip averaging [14, 53, 4]. Such methods usually also work well on nonconvex problems and can be used used for training deep neural networks [3, 24, 46]. There exists other methods, such as based on alternating direction method of multipliers (ADMM) [52, 10], dual averaging [6, 31, 41], primal-dual methods [2, 19], block-coordinate methods for generalized linear models [8] or using new gradient propagation mechanisms [50].
Decentralized Optimization with Heterogeneous Objective Functions. There exists several algorithms that are agnostic to data-heterogeneity. Notably, EXTRA [42] and decentralized primal-dual gradient methods [2] do not depend on the data heterogeneity and achieve linear convergence in the strongly convex noiseless setting. However, these algorithms are not designed to be used for non-convex tasks.
D2 [46, 55] (also known as exact diffusion [56, 57]) and Gradient Tracking (GT) [26] (also known as NEXT [26] or DIGing [34]) are both algorithms that are agnostic to the data heterogeneity level, can tolerate the stochastic noise, and that can be applied to non-convex objectives such as the training of deep neural networks in machine learning. A limitation of the D2 algorithm is that it is not clear how it can be applied to time-varying topologies, and that it can only be used on constant mixing topologies with negative eigenvalue bounded from below by − 13 . Other authors proposed algorithms that perform well on heterogeneous DL tasks [25, 59], but theoretical proofs that these algorithms are independent of the degree of heterogeneity are still pending.
Gradient Tracking. There is a vast literature on the Gradient Tracking method itself. A tracking mechanism was used by Zhu and Martínez [61] as a way to track the average of a distributed continuous process. Lorenzo and Scutari [26] applied this technique to track the gradients, and analyzed its asymptotic behavior in the non-convex setting with a time-varying topologies. Nedić et al. [34] analyze GT (named as DIGing) in the strongly convex noiseless case with a time-varying network. Qu and Li [40] extend the GT analysis to the non-convex, weakly-convex and strongly convex case without stochastic noise. Nedić et al. [35] allow the different stepsizes on different workers. Yuan et al. [58] analyze asymptotic behavior of GT for dynamic optimization. Pu and Nedić [39] studied the GT method on stochastic problems and strongly convex objectives. Further, Xin et al. [54] analyze asymptotic behavior of GT with stochastic noise. For non-convex stochastic functions GT was analyzed by Zhang and You [60] and Lu et al. [27]. Li et al. [20] combine GT with variance reduction to achieve linear convergence in the stochastic case. Tziotis et al. [49] obtain second order guarantees for GT.

heading: 3 Setup

text:
We consider optimization problems where the objective function is distributed across n nodes,
min x∈Rd
[ f(x) := 1
n n∑ i=1 [ fi(x) = Eξ∼Di Fi(x, ξ)
]] , (1)
where fi : Rd → R denotes the local function available to the node i, i ∈ [n] := {1, . . . n}. Each fi is a stochastic function fi(x) = Eξ∼Di Fi(x, ξ) with access only to stochastic gradients∇Fi(x, ξ). This setting covers empirical risk minimization problems with Di being a uniform distribution over the local training dataset. It also covers deterministic optimization when Fi(x, ξ) = fi(x), ∀ξ.
We consider optimization over a decentralized network, i.e. when there is an underlying communication graph G = (V,E), |V | = n, each of the nodes (e.g. a connected device) can communicate only along the edges E. In decentralized optimization it is convenient to parameterize communication by a mixing matrix W ∈ Rn×n, where wij = 0 if and only if nodes i and j are not communicating, (i, j) /∈ E. Definition 1 (Mixing Matrix). A matrix with non-negative entries W ∈ [0, 1]n×n that is symmetric (W =W>) and doubly stochastic (W1=1, 1>W =1>), where 1 denotes the all-one vector in Rn.

heading: 3.1 Notation

text:
We use the notation x(t)i ∈ Rd, y (t) i ∈ Rd to denote the iterates and the tracking sequence, respectively, on node i at time step t. For vectors zi ∈ Rd (zi could for instance be x(t)i or y (t) i ) defined for i ∈ [n]
we denote by z̄ = 1n ∑n i=1 zi.
We use both vector and matrix notation whenever it is more convenient. For vectors zi ∈ Rd defined for i ∈ [n] we denote by a capital letter the matrix with columns zi, formally
Z := [z1, . . . , zn] ∈ Rd×n , Z̄ := [z̄, . . . , z̄] ≡ Z 1n11 > , ∆Z := Z − Z̄ . (2)
We extend this definition to gradients of (1), with∇F (X(t), ξ(t)),∇f(X(t)) ∈ Rd×n:
∇F (X(t), ξ(t)) := [ ∇F1(x(t)1 , ξ (t) 1 ), . . . ,∇Fn(x(t)n , ξ(t)n ) ] ,
∇f(X(t)) := [ ∇f(x(t)1 ), . . . ,∇f(x(t)n ) ] .

heading: 3.2 Algorithm

text:
The Gradient Tracking algorithm (or NEXT, DIGing) can be written as( X(t+1)
γY (t+1)
)> = ( X(t)
γY (t) )>( W 0 −W W ) + γ ( 0 ∇F (X(t+1), ξ(t+1))−∇F (X(t), ξ(t)) )> (GT)
in matrix notation. Here and X(t) ∈ Rd×n denotes the iterates, Y (t) ∈ Rd×n, with Y (0) = ∇F (X(t), ξ(t)) the sequence of tracking variables, and γ > 0 denotes the stepsize. This update is summarized in Algorithm 1.
Algorithm 1 GRADIENT TRACKING
input Initial values x(0)i ∈ Rd on each node i ∈ [n], communication graph G = ([n], E) and mixing matrix W , stepsize γ, initialize y(0)i = ∇Fi(x (0) i , ξ (0) i ), g (0) i = y (0) i in parallel for i ∈ [n].
1: in parallel on all workers i ∈ [n], for t = 0, . . . , T − 1 do 2: each node i sends ( x
(t) i ,y (t) i
) to is neighbors
3: x(t+1)i = ∑ j:{i,j}∈E wij ( x (t) j − γy (t) j ) . update model parameters
4: Sample ξ(t+1)i , compute gradient g (t+1) i = ∇Fi
( x
(t+1) i , ξ (t+1) i ) 5: y(t+1)i = ∑ j:{i,j}∈E wijy (t) j + ( g (t+1) i − g (t) i ) . update tracking variable 6: end parallel for
Each node i stores and updates two variables, the model parameter x(t)i and the tracking variable y (t) i . The model parameters are updated on line 3 with a decentralized SGD update but using y(t)i instead of a gradient. Variable y(t)i tracks the average of all local gradients on line 5. Intuitively, the algorithm is agnostic to the functions heterogeneity because y(t)i is ‘close’ to the full gradient of f(x) (suppose we would replace line 5 with exact averaging in every timestep, then y(t+1)i = 1 n ∑n i=1 g (t+1) i . For further discussion of the tracking mechanism refer to [26, 34, 39].
deg(j) for {i, j} ∈ E, see e.g. [36].

heading: 3.3 Assumptions

text:
We first state an assumption on the mixing matrix. Assumption 1 (Mixing Matrix). Let λi(W ), i ∈ [n], denote the eigenvalues of the mixing matrix W with 1 = λ1(W ) > λ2(W ) ≥ · · · ≥ λn(W ) > −1. With this, we can define the spectral gap δ = 1−max{|λ2(W )|, |λn(W )|}, and the mixing parameters
p = 1−max{|λ2(W )|, |λn(W )|}2 , c = 1−min{λn(W ), 0}2 . (3) We assume that p > 0 (and consequently c > 0).
The assumption p > 0 ensures that the network topology is connected, and that the consensus distance decreases linearly after each averaging step, i.e. ∥∥XW − X̄∥∥2 F ≤ (1−p) ∥∥X − X̄∥∥2 F ,∀X ∈ Rd×n. The parameter p is closely related to the spectral gap δ as it holds p = 2δ − δ2. From this we can conclude that δ ≤ p ≤ 2δ and, asymptotically for δ → 0, p→ 2δ. Assuming a lower bound on p (or equivalently δ) is a standard assumption in the literature.
The parameter c is related to the most negative eigenvalue. From the definition (3) it follows that the auxiliary mixing parameter c ≥ p for all mixing matrices W . The parameters p and c are only equal when |λn(W )| ≥ |λ2(W )| and λn(W ) ≤ 0. Moreover, if the diagonal entries wii (self-weights) of the mixing matrix are all strictly positive, then c has to be strictly positive. Remark 1 (Lower bound on c.). Let W be a mixing matrix with diagonal entries (self-weights) wii ≥ ρ > 0, for a parameter ρ. Then λn(W ) ≥ 2ρ− 1 and c ≥ min{2ρ, 1}.
This follows from Gershgorin’s circle theorem [7] that guarantees λn(W ) ≥ 2ρ − 1, and hence c ≥ 1−min{2ρ− 1, 0}2 ≥ min{2ρ, 1}. For many choices of W considered in practice, most notably when the graph G has constant nodedegree and the weights wij are chosen by the popular Metropolis-Hastings rule, i.e. wij = wji = min { 1
deg(i)+1 , 1 deg(j)+1 } for (i, j) ∈ E, wii = 1− ∑n j=1 wij ≥ 1 maxj∈[n] deg(j)
, see also [53, 4]. In this case, the parameter c can be bounded by a constant depending on the maximal degree. Moreover, for any given W , considering 12 (W + In) instead (i.e. increasing the self-weights), ensures that c = 1. However, in contrast to e.g. the analysis in [55] we do not need to pose an explicit bound on c as an assumption. In practice, for many graphs, the parameter c is bounded by a constant (see Table 3).
We further use the following standard assumptions: Assumption 2 (L-smoothness). Each function fi : Rd → R, i ∈ [n] is differentiable and there exists a constant L ≥ 0 such that for each x,y ∈ Rd:
‖∇fi(y)−∇fi(x)‖ ≤ L ‖x− y‖ . (4)
Sometimes we will in addition assume that the functions are (strongly) convex. Assumption 3 (µ-strong convexity). Each function fi : Rd → R, i ∈ [n] is µ-strongly convex for constant µ ≥ 0, i.e. for all x,y ∈ Rd:
fi(x)− fi(y) + µ2 ‖x− y‖ 2 2 ≤ 〈∇fi(x),x− y〉 . (5)
Assumption 4 (Bounded noise). We assume that there exists constant σ s.t. ∀x1, . . .xn ∈ Rd
1 n ∑n i=1 Eξi ‖∇Fi(xi, ξi)−∇fi(xi)‖ 2 2 ≤ σ2 . (6)
We discuss possible relaxations of these assumptions in Section 4.1 below.

heading: 4 Convergence results

text: We now present our novel convergence results for GT in Section 4.1 and Section 4.2 below. We provide a proof sketch to explain the key difficulties and technical novelty compared to prior results later in the next Section 6.

heading: 4.1 Main theorem—GT convergence in the general case

text:
Theorem 2. Let x(t)i , i ∈ [n], T > 2p log ( 50 p (1 + log 1 p ) )
denote the iterates of the GT Algorithm 1 with a mixing matrix as in Definition 1. If Assumptions 1, 2 and 4 hold, then there exists a stepsize γ such that the optimization error is bounded as follows: Non-convex: Let F0 = f(x̄(0))− f? for f? ≤ minx∈Rd f(x). Then it holds
1 T+1 ∑T t=0 ∥∥∇f(x̄(t))∥∥2 2 ≤ ε , after Õ
( σ2
nε +
σ
( √ pc+ p √ n)ε3/2
+ 1 + LR̃20F −1 0
pcε
) ·LF0 iterations.
Strongly-convex: Under the additional Assumption 3 with µ > 0 and weights wt ≥ 0, WT =∑T t=0 wt, specified in the proof, it holds for R 2 T+1 = ∥∥x̄(T+1) − x?∥∥2: ∑T t=0 wt WT [ E f(x̄(t))− f? ] + µ2RT+1 ≤ ε , after Õ ( σ2
µnε +
√ Lσ
µ √ pc √ ε
+ L
µpc log
1
ε
) iterations.
General convex: Under the additional Assumption 3 with µ ≥ 0, it holds for R20 = ∥∥x̄(0) − x?∥∥2:
1 T+1 ∑T t=0 [ E f(x̄(t))− f? ] ≤ ε , after Õ
( σ2
nε2 +
√ Lσ
√ pcε3/2
+ L(1 + R̃20R −2 0 )
pcε
) ·R20 iterations,
where R̃20 = 1 n ∑n i=1 ‖x (0) i − x̄(0)‖2 + 1nL2 ∑n i=1 ‖y (0) i − ȳ(0)‖2.
From these results we see that the leading term in the convergence rate (assuming σ > 0) is not affected by the graph parameters. Moreover, in this term we see a linear speedup in n, the number of workers. The leading terms of all three results match with the convergence estimates for all-reduce mini-batch SGD [5, 43] and is optimal [37]. This means, that after a sufficiently long transient time, GT achieves a linear speedup in n. This transient time depends on the graph parameters p and c, but not on the data-dissimilarity. We will discuss the dependency of the convergence rate on the graph parameters c, p more carefully below in Sections 5 and 7, and compare the convergence rate to the convergence rates of D-SGD and D2.
Possible Relaxations of the Assumptions. Before moving on to the proofs, we mention briefly a few possible relaxations of the assumptions that are possible with only slight adaptions of the proof framework. These extensions can be addressed with known techniques and are omitted for conciseness. We give here the necessary references for completeness.
• Bounded Gradient Assumption I. The uniform bound on the stochastic noise in Assumption 4 could be relaxed by allowing the noise to grow with the gradient norm [16, Assumption 3b]. • Bounded Gradient Assumption II. In the convex setting it has been observed that σ2 can be replaced with σ2? := 1 n ∑n i=1 Eξi ‖∇Fi(x?, ξi)−∇fi(x?)‖ 2 2, the noise at the optimum. However,
this requires smoothness of each Fi(x, ξ), ξ ∈ Di, which is stronger than our Assumption 2. For the technique see e.g. [38]. • Different mixing for X and Y . In Algorithm 1, both the x and y iterates are averaged on the same communication topology (the same mixing matrix). This can be relaxed by allowing for two separate matrices. This follows from inspecting our proof below. • Local Steps. It is possible to extend Algorithm 1 and our analysis in Theorem 2 to allow for local computation steps. Mixing matrix would alternate between identity matrix I (no communication, local steps) and W (communication steps). However, it is non trivial to extend our analysis to the general time-varying graphs, as the product of two arbitrary mixing matrices W1W2 might be non symmetric.

heading: 4.2 Faster convergence on consensus functions

text:
We now state an additional result, which improves Theorem 2 on the consensus problem, defined as
min [ f(x) = 1
n n∑ i=1 [ fi(x) := 1 2 ‖x− µi‖
2 ]] , (7)
for vectors µi ∈ Rd, i ∈ [n] and optimal solution x? = 1n ∑n i=1 µi. Note that this is a special case of the general problem (1) without stochastic noise (σ = 0). For this function, we can improve the complexity estimate that would follow from Theorem 2 by proving a convergence rate that does not depend on c. Theorem 3. Let f be as in (7) let Assumption 1 hold. Then there exists a stepsize γ ≤ p such that it holds 1n ∑n i=1 ∥∥x(T )i −x?∥∥2 ≤ , for the iterates GT 1 and any > 0, after at most T = Õ (p log 1 ) iterations.

heading: 5 Discussion

text: We now provide a discussion of these results.

heading: 5.1 Parameter c

text:
The convergence rate in Theorem 2 depends on the parameter c, that in the worst case could be as small as p. In this case our theoretical result does not improve over existing results for the strongly convex case. However, for many graphs in practice parameter c is bounded by a constant (see Table 3 and discussion below Assumption 1).
While we show in Theorem 3 that it is possible to remove the dependency on c entirely from the convergence rate in special cases, it is still an open question if the parameter c in Theorem 2 is tight in general.

heading: 5.2 Comparison to prior GT literature

text: Tables 1 and 2 compare our theoretical convergence rates in strongly convex and non convex settings. Our result tightens all existing prior work.

heading: 5.3 Comparison to other methods.

text:
We now compare our complexity estimate of GT to D-SGD and D2 in the strongly convex case. Analogous observations hold for the other cases too.
Comparison to D-SGD. A popular algorithm for decentralized optimization is D-SGD [24] that converges as [16]:
Õ
( σ2
µnε +
√ L ( ζ + √ pσ )
µp √ ε
+ L
µp log
1
ε
) . (D-SGD)
While GT is agnostic to data-heterogenity, here the convergence estimate depends on the dataheterogenity, measured by a constant ζ2 that satisfies:
1 n ∑n i=1 ‖∇fi(x?)−∇f(x?)‖ 2 2 ≤ ζ2 . (8)
Comparing with Theorem 2, GT completely removes dependence on data heterogeneity level ζ. Moreover, even in the homogeneous case when ζ = 0, GT enjoys the same rate as D-SGD for many practical graphs when c is bounded by a constant.
Comparison to D2. Similarly to GT, D2 also removes the dependence on functions heterogeneity. The convergence rate of D2 holds under assumption that λmin (W ) > − 13 and it is equal to [55]:
O
( σ2
µnε +
√ Lσ
µ √ p √ ε
+ L
µp log
1
ε
) . (D2)
Under the assumption λmin (W ) > − 13 the parameter c is a constant, and the GT rate estimated in Theorem 2 matches (D2).

heading: 6 Proof sketch of the main theorem

text:
Here we give a proof sketch for Theorem 2, for the special case of strongly convex objectives. We give all proof details in the appendix and highlight the main technical difficulties and novel techniques.
Key Lemma. It is very common—and useful—to write the iterates in the form X(t) = X̄(t) + (X(t)−X̄(t)), where X̄(t) denotes the matrix with the average over the nodes. We can then separately analyze X̄(t) and the consensus difference ∆X(t) := (X(t) − X̄(t)) (and ∆Y (t) := (Y (t) − Ȳ (t))). Define W̃ = W − 11 >
n . From the update equation (GT) we see that( ∆X(t+1)
γ∆Y (t+1)
)> = ( ∆X(t)
γ∆Y (t) )> ︸ ︷︷ ︸
=:Ψt
( W̃ 0 −W̃ W̃ ) ︸ ︷︷ ︸
=:J
+γ
( 0(
∇F (Xt+1, ξt+1)−∇F (Xt, ξt) ) (I − 11 >
n ) )> ︸ ︷︷ ︸
=:Et
,
in short, by using the notation Ψt, J , and Et as introduced above,
Ψt+1 = ΨtJ + γEt . (9)
We could immediately adapt the proof technique from [16] if it would hold that the spectral radius of J is smaller than one. However, this is not the case, and in general ‖J‖ > 1. Note that for any integer i ≥ 0:
J i = ( W̃ i 0 −iW̃ i W̃ i ) ‖J i‖2 = ‖W̃ i‖2 + i2‖W̃ i‖2 ≤ (1− p)i + i2(1− p)i , (10)
by Assumption 1. With this observation we can now formulate a key lemma: Lemma 4 (Contraction). For any integer τ ≥ 2p log ( 50 p (1 + log 1 p ) ) it holds that ‖Jτ‖2 ≤ 12 .
While the constants in this lemma are chosen to ease the presentation, most important for us is that after τ = Θ̃ ( 1 p ) communication rounds, old parameter values (from τ steps ago) get discounted and averaged by a constant factor. We can alternatively write the statement of Lemma 4 as∥∥ZJτ − Z̄∥∥2 F ≤ 12 ∥∥Z − Z̄∥∥2 F , ∀Z ∈ R2d×n .
This resembles [16, Assumption 4] and the proof now follows the same pattern. A few crucial differences remain, as the result in [16] depends on a data-dissimilarity parameter which we can avoid by carefully estimating the tracking errors. For completeness, we sketch the outline and give all details in the appendix.
Average Sequence. First, we consider the average sequences X̄(t) and Ȳ (t). As all columns of these matrices are equal, we can equivalently consider a single column only: x̄(t) and ȳ(t).
Lemma 5 (Average). It holds that
ȳ(t) = 1
n n∑ i=1 ∇Fi ( x (t) i , ξ (t) i ) , x̄(t+1) = x̄(t) − γ 1 n n∑ i=1 ∇Fi ( x (t) i , ξ (t) i ) . (11)
This follows directly from the update (GT) and the fact that X̄ = X̄W for doubly stochastic mixing matrices. The update of x̄(t) in (11) is almost identical to one step of mini-batch SGD (on a complete graph). The average sequence behaves almost as a SGD sequence:
Lemma 6 (Descent lemma, [16, Lemma 8]). Under the Assumptions of Theorem 2 for the convex functions, the averages x̄(t) := 1n ∑n i=1 x (t) i of the iterates of Algorithm 1 with the stepsize γ ≤ 112L satisfy
E ∥∥x̄(t+1) − x?∥∥2 ≤ (1− γµ
2
) E ∥∥x̄(t) − x?∥∥2 + γ2σ2
n − γet +
3γL
n n∑ i=1 E ∥∥x̄(t) − x(t)i ∥∥2, (12)
where et = E f(x̄(t))− f?, for f? = minx∈Rd f(x).
Consensus Distance. The main difficulty comes from estimating the consensus distance ‖Ψt‖2, in the notation introduced in (9). Note that
‖Ψt‖2 = 1
n n∑ i=1 ∥∥x(t)i − x̄(t)∥∥22 + γ2n n∑ i=1 ∥∥y(t)i − ȳ(t)∥∥22 . By unrolling (9) for τ ≤ k ≤ 2τ , τ = 2p log ( 50 p (1 + log 1 p ) ) + 1 steps,
Ψt+k = ΨtJ k + γ k−1∑ j=1 Et+j−1J k−j . (13)
By taking the Frobenius norm, and carefully estimating the norm of the error term∥∥∑τ−1 j=1 Et+j−1J τ−j ∥∥2 F , and using Lemma 4 we can derive a recursion for the consensus distance. Lemma 7 (Consensus distance recursion). There exists absolute constants B1, B2, B3 > 0 such that for a stepsize γ < cB3Lτ
E ‖Ψt+k‖2F ≤ 7
8 E ‖Ψt‖2F +
1
128τ k−1∑ j=0 ‖Ψt+j‖2F + B1τLγ 2 c2 k−1∑ j=0 net+j + B2τγ 2 c2 nσ2. (14)
This lemma allows to replace p with c in the final convergence rate. This is achieved by grouping same gradients in the sum ∥∥∑k−1 j=1 Et+j−1J k−j ∥∥2 F and estimating the norm with Lemma 13.
An additional technical difficulty comes when unrolling consensus recursion (14). As iteration matrix J is not contractive, i.e. ‖J‖ > 1, then ‖Ψt+j‖2F for j < τ can be larger than ‖Ψt‖2F (up to ≈ 1p2 times as ∥∥J i∥∥2 ≤ O ( 1p2) ∀i). We introduce an additional term in the recursion that is provably non-increasing
Φt+τ := 1
τ τ−1∑ j=0 ‖Ψt+j‖2F .
With this we unroll consensus recursion. Lemma 8 (Unrolling recursion). For γ < c√
7B1Lτ ≤ 12Lτ it holds,
E ‖Ψt‖2F ≤ (
1− 1 64τ
)t A0 + 22B1τLγ 2
c2
t−1∑ j=0 ( 1− 1 64τ )t−j nej + 20B2τγ 2 c2 nσ2 (15)
where ej = E[f(x̄(j))− f(x?)], A0 = 16‖∆X(0)‖2F + 24γ2 p2 ‖∆Y (0)‖2F .
It remains to combine (14) and (15) using technique from [16].
Proof sketch of Theorem 3. Using the matrix notation introduced above, the iterations of GT on problem (7) can be written in a simple form:(
∆X(t+1)
γ∆Y (t+1)
)> = ( ∆X(t)
γ∆Y (t) )>( W̃ γ (W − I) −W̃ (1− γ)W̃ ) ︸ ︷︷ ︸
J′
.
Similar as above, also the matrix J ′ is not a contraction operator, but in contrast to J it is diagonalizable: J ′ = QΛQ−1 for some Q and diagonal Λ. It follows that ‖(J ′)t‖2 = ∥∥QΛtQ−1∥∥2 is decreasing as (1− p)t ‖Q‖2
∥∥Q−1∥∥2. With this observation, the proof simplifies.

heading: 7 Experiments

text:
In this section we investigate the tightness of parameters c and p in our theoretical result.
Setup. We consider simple quadratic functions defined as fi(x) = ‖x‖2, and x(0) is randomly initialized from a normal distribution N (0, 1). We add artificially stochastic noise to gradients as
∇Fi(x, ξ) = ∇fi(x) + ξ, where ξ ∼ N (0, σ 2
d I) so that Assumption 4 is satisfied. We elaborate the details as well as results under other problem setups in Appendix C.
We verify the dependence on graph parameters p and c for the stochastic noise term. We fix the stepsize γ to be constant, vary p and c and measure the value of f(x̄(t))− f? that GT reaches after a large number of steps. According to the theory, GT converges to the level O ( γσ2
n + γ2σ2 pc2
) in a
linear number of steps (to reach higher accuracy, smaller stepsizes must be used). To decouple the second term we need to ensure that the first term is small enough. For that, we take the number of nodes n to be large. In all experiments we ensure that the first term is at least by order of magnitude smaller than the second by comparing the noise level with GT on a fully-connected topology.
The effect of p. First, in Figure 1 we verify the expected O (
1 p
) dependence when c is a constant. For
a fixed n = 300 number of nodes with d = 100 we vary the value of a parameter p by interpolating the ring topology (with uniform weights) with the fully-connected graph. The loss value f(x(∞)) scales linearly in 1p as can be observed in Figure 1 and the dependency on p can thus not further be improved.
The effect of c. In Figure 2 we aim to examine the dependence of the term O
(
1 pc2
)
on the parameter
c, in terms of 1/(pc2) and 1/(cp). We take the ring topology on a fixed number of n = 300 nodes and reduce the self-weights to achieve different values of c (see appendix for details). Otherwise the setup is as above. The current numerical results may suggest the existence of a potentially better theoretical dependence of the term c (as discussed in Section 4.2); we leave the study for future work.

heading: 8 Conclusion

text:
We have derived improved complexity bounds for the GT method, that improve over all previous results. We verify the tightness of the second term in the convergence rate in numerical experiments. Our analysis identifies that the smallest eigenvalue of the mixing matrix has a strong impact on the performance of GT, however the smallest eigenvalue can often be controlled in practice by choosing large enough self-weights (wii) on the nodes.
Our proof technique might be of independent interest in the community and might lead to improved analyses for other gossip based methods where the mixing matrix is not contracting (for e.g. in directed graphs, or using row- or column-stochastic matrices).
Acknowledgments and Disclosure of Funding
This project was supported by SNSF grant 200020_200342, EU project DIGIPREDICT, and a Google PhD Fellowship. The authors thank Martin Jaggi for his support.

title: An Improved Analysis of Gradient Tracking for Decentralized Machine Learning