More Like this

1. Ordered Gradient Approach for Communication-Efficient Distributed Learning

   https://doi.org/10.1109/SPAWC48557.2020.9153887  

   Chen, Yicheng ; Sadler, Brian M. ; Blum, Rick S. ( May 2020 , 2020 IEEE 21st International Workshop on Signal Processing Advances in Wireless Communications (SPAWC))

   null (Ed.)

   The topic of training machine learning models by employing multiple gradient-computing workers is attracting great interest recently. Communication efficiency in such distributed learning settings is an important consideration, especially for the case where the needed communications are expensive in terms of power usage. We develop a new approach which is efficient in terms of communication transmissions. In this scheme, only the most informative worker results are transmitted to reduce the total number of transmissions. Our ordered gradient approach provably achieves the same order of convergence rate as gradient descent for nonconvex smooth loss functions while gradient descent always requires more communications. Experiments show significant communication savings compared to the best existing approaches in some cases. 

   more » « less
2. Data Encoding Methods for Byzantine-Resilient Distributed Optimization

   https://doi.org/10.1109/ISIT.2019.8849857  

   Data, Deepesh ; Song, Linqi ; Diggavi, Suhas ( July 2019 , IEEE International Symposium on Information Theory (ISIT))

   We consider distributed gradient computation, where both data and computation are distributed among m worker machines, t of which can be Byzantine adversaries, and a designated (master) node computes the model/parameter vector for generalized linear models, iteratively, using proximal gradient descent (PGD), of which gradient descent (GD) is a special case. The Byzantine adversaries can (collaboratively) deviate arbitrarily from their gradient computation. To solve this, we propose a method based on data encoding and (real) error correction to combat the adversarial behavior. We can tolerate up to t <= (m−1)/2 corrupt worker nodes, which is 2 information-theoretically optimal. Our method does not assume any probability distribution on the data. We develop a sparse encoding scheme which enables computationally efficient data encoding. We demonstrate a trade-off between the number of adversaries tolerated and the resource requirement (storage and computational complexity). As an example, our scheme incurs a constant overhead (storage and computational complexity) over that required by the distributed PGD algorithm, without adversaries, for t <= m . Our encoding works as efficiently in the streaming data setting as it does in the offline setting, in which all the data is available beforehand. 

   more » « less
3. How Data Augmentation affects Optimization for Linear Regression

   Hanin, Boris ; Sun, Yi ( January 2021 , Advances in neural information processing systems)

   Though data augmentation has rapidly emerged as a key tool for optimization in modern machine learning, a clear picture of how augmentation schedules affect optimization and interact with optimization hyperparameters such as learning rate is nascent. In the spirit of classical convex optimization and recent work on implicit bias, the present work analyzes the effect of augmentation on optimization in the simple convex setting of linear regression with MSE loss.We find joint schedules for learning rate and data augmentation scheme under which augmented gradient descent provably converges and characterize the resulting minimum. Our results apply to arbitrary augmentation schemes, revealing complex interactions between learning rates and augmentations even in the convex setting. Our approach interprets augmented (S)GD as a stochastic optimization method for a time-varying sequence of proxy losses. This gives a unified way to analyze learning rate, batch size, and augmentations ranging from additive noise to random projections. From this perspective, our results, which also give rates of convergence, can be viewed as Monro-Robbins type conditions for augmented (S)GD. 

   more » « less
4. FL-NTK: A Neural Tangent Kernel-based Framework for Federated Learning Analysis

   Huang, Baihe ; Li, Xiaoxiao ; Song, Zhao ; Yang, Xin ( July 2021 , Proceedings of Machine Learning Research)

   Meila, Marina ; Zhang, Tong (Ed.)

   Federated Learning (FL) is an emerging learning scheme that allows different distributed clients to train deep neural networks together without data sharing. Neural networks have become popular due to their unprecedented success. To the best of our knowledge, the theoretical guarantees of FL concerning neural networks with explicit forms and multi-step updates are unexplored. Nevertheless, training analysis of neural networks in FL is non-trivial for two reasons: first, the objective loss function we are optimizing is non-smooth and non-convex, and second, we are even not updating in the gradient direction. Existing convergence results for gradient descent-based methods heavily rely on the fact that the gradient direction is used for updating. The current paper presents a new class of convergence analysis for FL, Federated Neural Tangent Kernel (FL-NTK), which corresponds to overparamterized ReLU neural networks trained by gradient descent in FL and is inspired by the analysis in Neural Tangent Kernel (NTK). Theoretically, FL-NTK converges to a global-optimal solution at a linear rate with properly tuned learning parameters. Furthermore, with proper distributional assumptions, FL-NTK can also achieve good generalization. The proposed theoretical analysis scheme can be generalized to more complex neural networks. 

   more » « less
5. Diving into the shallows: a computational perspective on large-scale shallow learning

   Ma, Siyuan ; Belkin, Mikhail ( October 2017 , Advances in neural information processing systems)

   Remarkable recent success of deep neural networks has not been easy to analyze theoretically. It has been particularly hard to disentangle relative significance of architecture and optimization in achieving accurate classification on large datasets. On the flip side, shallow methods (such as kernel methods) have encountered obstacles in scaling to large data, despite excellent performance on smaller datasets, and extensive theoretical analysis. Practical methods, such as variants of gradient descent used so successfully in deep learning, seem to perform below par when applied to kernel methods. This difficulty has sometimes been attributed to the limitations of shallow architecture. In this paper we identify a basic limitation in gradient descent-based optimization methods when used in conjunctions with smooth kernels. Our analysis demonstrates that only a vanishingly small fraction of the function space is reachable after a polynomial number of gradient descent iterations. That drastically limits the approximating power of gradient descent leading to over-regularization. The issue is purely algorithmic, persisting even in the limit of infinite data. To address this shortcoming in practice, we introduce EigenPro iteration, a simple and direct preconditioning scheme using a small number of approximately computed eigenvectors. It can also be viewed as learning a kernel optimized for gradient descent. Injecting this small, computationally inexpensive and SGD-compatible, amount of approximate second-order information leads to major improvements in convergence. For large data, this leads to a significant performance boost over the state-of-the-art kernel methods. In particular, we are able to match or improve the results reported in the literature at a small fraction of their computational budget. 

   more » « less