78 research outputs found
FedNL: Making Newton-Type Methods Applicable to Federated Learning
No full textInspired by recent work of Islamov et al (2021), we propose a family of
Federated Newton Learn (FedNL) methods, which we believe is a marked step in
the direction of making second-order methods applicable to FL. In contrast to
the aforementioned work, FedNL employs a different Hessian learning technique
which i) enhances privacy as it does not rely on the training data to be
revealed to the coordinating server, ii) makes it applicable beyond generalized
linear models, and iii) provably works with general contractive compression
operators for compressing the local Hessians, such as Top- or Rank-,
which are vastly superior in practice. Notably, we do not need to rely on error
feedback for our methods to work with contractive compressors. Moreover, we
develop FedNL-PP, FedNL-CR and FedNL-LS, which are variants of FedNL that
support partial participation, and globalization via cubic regularization and
line search, respectively, and FedNL-BC, which is a variant that can further
benefit from bidirectional compression of gradients and models, i.e., smart
uplink gradient and smart downlink model compression. We prove local
convergence rates that are independent of the condition number, the number of
training data points, and compression variance. Our communication efficient
Hessian learning technique provably learns the Hessian at the optimum. Finally,
we perform a variety of numerical experiments that show that our FedNL methods
have state-of-the-art communication complexity when compared to key baselines.Comment: 65 pages, 7 algorithms, 14 figures --- Accepted to ICML 202
Double Momentum and Error Feedback for Clipping with Fast Rates and Differential Privacy
No full textStrong Differential Privacy (DP) and Optimization guarantees are two desirable properties for a method in Federated Learning (FL). However, existing algorithms do not achieve both properties at once: they either have optimal DP guarantees but rely on restrictive assumptions such as bounded gradients/bounded data heterogeneity, or they ensure strong optimization performance but lack DP guarantees. To address this gap in the literature, we propose and analyze a new method called Clip21-SGD2M based on a novel combination of clipping, heavy-ball momentum, and Error Feedback. In particular, for non-convex smooth distributed problems with clients having arbitrarily heterogeneous data, we prove that Clip21-SGD2M has optimal convergence rate and also near optimal (local-)DP neighborhood. Our numerical experiments on non-convex logistic regression and training of neural networks highlight the superiority of Clip21-SGD2M over baselines in terms of the optimization performance for a given DP-budget.Rustem Islamov and Aurelien Lucchi acknowledge the financial support of the Swiss National
Foundation, SNF grant No 207392. Peter Richtárik acknowledges the financial support of King
Abdullah University of Science and Technology (KAUST): i) KAUST Baseline Research Scheme,
ii) Center of Excellence for Generative AI, under award number 5940, iii) SDAIA-KAUST Center of Excellence in Artificial Intelligence and Data Science
FedNL: Making Newton-Type Methods Applicable to Federated Learning
No full textInspired by recent work of Islamov et al (2021), we propose a family of Federated Newton Learn (\algname{FedNL}) methods, which we believe is a marked step in the direction of making second-order methods applicable to FL. In contrast to the aforementioned work, \algname{FedNL} employs a different Hessian learning technique which i) enhances privacy as it does not rely on the training data to be revealed to the coordinating server, ii) makes it applicable beyond generalized linear models, and iii) provably works with general contractive compression operators for compressing the local Hessians, such as Top-K or Rank-R, which are vastly superior in practice. Notably, we do not need to rely on error feedback for our methods to work with contractive compressors. Moreover, we develop \algname{FedNL-PP}, \algname{FedNL-CR} and \algname{FedNL-LS}, which are variants of \algname{FedNL} that support partial participation, and globalization via cubic regularization and line search, respectively, and \algname{FedNL-BC}, which is a variant that can further benefit from bidirectional compression of gradients and models, i.e., smart uplink gradient and smart downlink model compression. We prove local convergence rates that are independent of the condition number, the number of training data points, and compression variance. Our communication efficient Hessian learning technique provably learns the Hessian at the optimum. Finally, we perform a variety of numerical experiments that show that our \algname{FedNL} methods have state-of-the-art communication complexity when compared to key baselines
AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms
No full textWe analyze asynchronous-type algorithms for distributed SGD in the
heterogeneous setting, where each worker has its own computation and
communication speeds, as well as data distribution. In these algorithms,
workers compute possibly stale and stochastic gradients associated with their
local data at some iteration back in history and then return those gradients to
the server without synchronizing with other workers. We present a unified
convergence theory for non-convex smooth functions in the heterogeneous regime.
The proposed analysis provides convergence for pure asynchronous SGD and its
various modifications. Moreover, our theory explains what affects the
convergence rate and what can be done to improve the performance of
asynchronous algorithms. In particular, we introduce a novel asynchronous
method based on worker shuffling. As a by-product of our analysis, we also
demonstrate convergence guarantees for gradient-type algorithms such as SGD
with random reshuffling and shuffle-once mini-batch SGD. The derived rates
match the best-known results for those algorithms, highlighting the tightness
of our approach. Finally, our numerical evaluations support theoretical
findings and show the good practical performance of our method
EControl: Fast Distributed Optimization with Compression and Error Control
No full textModern distributed training relies heavily on communication compression to
reduce the communication overhead. In this work, we study algorithms employing
a popular class of contractive compressors in order to reduce communication
overhead. However, the naive implementation often leads to unstable convergence
or even exponential divergence due to the compression bias. Error Compensation
(EC) is an extremely popular mechanism to mitigate the aforementioned issues
during the training of models enhanced by contractive compression operators.
Compared to the effectiveness of EC in the data homogeneous regime, the
understanding of the practicality and theoretical foundations of EC in the data
heterogeneous regime is limited. Existing convergence analyses typically rely
on strong assumptions such as bounded gradients, bounded data heterogeneity, or
large batch accesses, which are often infeasible in modern machine learning
applications. We resolve the majority of current issues by proposing EControl,
a novel mechanism that can regulate error compensation by controlling the
strength of the feedback signal. We prove fast convergence for EControl in
standard strongly convex, general convex, and nonconvex settings without any
additional assumptions on the problem or data heterogeneity. We conduct
extensive numerical evaluations to illustrate the efficacy of our method and
support our theoretical findings
Distributed Second Order Methods with Fast Rates and Compressed Communication
No full textWe develop several new communication-efficient second-order methods for distributed optimization. Our first method, NEWTON-STAR, is a variant of Newton's method from which it inherits its fast local quadratic rate. However, unlike Newton's method, NEWTON-STAR enjoys the same per iteration communication cost as gradient descent. While this method is impractical as it relies on the use of certain unknown parameters characterizing the Hessian of the objective function at the optimum, it serves as the starting point which enables us to design practical variants thereof with strong theoretical guarantees. In particular, we design a stochastic sparsification strategy for learning the unknown parameters in an iterative fashion in a communication efficient manner. Applying this strategy to NEWTON-STAR leads to our next method, NEWTON-LEARN, for which we prove local linear and superlinear rates independent of the condition number. When applicable, this method can have dramatically superior convergence behavior when compared to state-of-the-art methods. Finally, we develop a globalization strategy using cubic regularization which leads to our next method, CUBIC-NEWTON-LEARN, for which we prove global sublinear and linear convergence rates, and a fast superlinear rate. Our results are supported with experimental results on real datasets, and show several orders of magnitude improvement on baseline and state-of-the-art methods in terms of communication complexity
In Memory of a Friend
No full textThe article is dedicated to the memory of Rustem Sultanovich Gabyashev (1941-2010), an outstanding Kazan archeologist. He was one of the renowned experts in the Mesolithic and the Neolithic of the Volga-Kama region. The author, the researcher’s colleague and friend, narrates about his scientific and, first of all, expedition activities, offers some biographical data and characterizes his personal qualitie
Smoothed Normalization for Efficient Distributed Private Optimization
No full textFederated learning enables training machine learning models while preserving the privacy of participants. Surprisingly, there is no differentially private distributed method for smooth, non-convex optimization problems. The reason is that standard privacy techniques require bounding the participants’ contributions, usually enforced via clipping of the updates. Existing literature typically ignores the effect of clipping by assuming the boundedness of gradient norms or analyzes distributed algorithms with clipping but ignores DP constraints. In this work, we study an alternative approach via smoothed normalization of the updates motivated by its favorable performance in the single-node setting. By integrating smoothed normalization with an error-feedback mechanism, we design a new distributed algorithm α-NormEC. We prove that our method achieves a superior convergence rate over prior works. By extending α-NormEC to the DP setting,
we obtain the first differentially private distributed optimization algorithm with provable convergence guarantees. Finally, our empirical results from neural network training indicate robust convergence of α-NormEC across different parameter settingsWe would like to thank Rustem Islamov for sharing his code. The research reported in this publication was supported by funding from King Abdullah University of Science and Technology (KAUST): i) KAUST Baseline Research Scheme, ii) Center of Excellence for Generative AI, under award number 5940, iii) SDAIA-KAUST Center of Excellence in Artificial Intelligence and Data Science
Co-aligning user-centered design and software engineering courses: A case study
No full textIntroducing students to different perspectives and roles in the development process allows them to engage in the work of cross-disciplinary diverse teams and even can enable them to change roles in designer-developer interactions. Industry work often places recent graduates in preexisting polarized relationship dynamics between different participants in the design and development process. This paper describes a two-stage attempt at co-alignment of software engineering and user-centered design courses: from full alignment with topic intersections and joint project to partial alignment through separate activities. We discuss challenges of both ways including time or technical constraints, increased effort from the program developers and instructors, students' and instructors' frustrations. We finalize by describing benefits of providing students with early experience identifying trade-offs between design requirements and architecture and opportunities for diverse group with different background in computer science.Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.Internet of Thing
Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregation
No full textDespite their high computation and communication costs, Newton-type methods remain an appealing option for distributed training due to their robustness against ill-conditioned convex problems. In this work, we study ommunication compression and aggregation mechanisms for curvature information in order to reduce these costs while preserving theoretically superior local convergence guarantees. We prove that the recently developed class of three point compressors (3PC) of Richtarik et al. [2022] for gradient communication can be generalized to Hessian communication as well. This result opens up a wide variety of communication strategies, such as contractive compression} and lazy aggregation, available to our disposal to compress prohibitively costly curvature information. Moreover, we discovered several new 3PC mechanisms, such as adaptive thresholding and Bernoulli aggregation, which require reduced communication and occasional Hessian computations. Furthermore, we extend and analyze our approach to bidirectional communication compression and partial device participation setups to cater to the practical considerations of applications in federated learning. For all our methods, we derive fast condition-number-independent local linear and/or superlinear convergence rates. Finally, with extensive numerical evaluations on convex optimization problems, we illustrate that our designed schemes achieve state-of-the-art communication complexity compared to several key baselines using second-order information
- …
