D-Cliques: Compensating for Data Heterogeneity with Topology in Decentralized Federated Learning

Related publications (22)

Stochastic distributed learning with gradient quantization and double-variance reduction

Konstantin Mishchenko, Sebastian Urban Stich

We consider distributed optimization over several devices, each sending incremental model updates to a central server. This setting is considered, for instance, in federated learning. Various schemes have been designed to compress the model updates in order to reduce the overall communication cost. However, existing methods suffer from a significant slowdown due to additional variance omega > 0 coming from the compression operator and as a result, only converge sublinearly. What is needed is a variance reduction technique for taming the variance introduced by compression. We propose the first methods that achieve linear convergence for arbitrary compression operators. For strongly convex functions with condition number kappa, distributed among n machines with a finite-sum structure, each worker having less than in components, we also (i) give analysis for the weakly convex and the non-convex cases and (ii) verify in experiments that our novel variance reduced schemes are more efficient than the baselines. Moreover, we show theoretically that as the number of devices increases, higher compression levels are possible without this affecting the overall number of communications in comparison with methods that do not perform any compression. This leads to a significant reduction in communication cost. Our general analysis allows to pick the most suitable compression for each problem, finding the rig ht balance between additional variance and communication savings. Finally, we also (iii) give analysis for arbitrary quantized updates.

TAYLOR & FRANCIS LTD2022

Learning Approach to Delineation of Curvilinear Structures in 2D and 3D Images

Agata Justyna Mosinska

Detection of curvilinear structures has long been of interest due to its wide range of applications. Large amounts of imaging data could be readily used in many fields, but it is practically not possible to analyze them manually. Hence, the need for automated delineation approaches. In the recent years Computer Vision witnessed a paradigm shift from mathematical modelling to data-driven methods based on Machine Learning. This led to improvements in performance and robustness of the detection algorithms. Nonetheless, most Machine Learning methods are general-purpose and they do not exploit the specificity of the delineation problem. In this thesis, we present learning methods suited for this task and we apply them to various kinds of microscopic and natural images, proving the general applicability of the presented solutions. First, we introduce a topology loss - a new training loss term, which captures higher-level features of curvilinear networks such as smoothness, connectivity and continuity. This is in contrast to most Deep Learning segmentation methods that do not take into account the geometry of the resulting prediction. In order to compute the new loss term, we extract topology features of prediction and ground-truth using a pre-trained network, whose filters are activated by structures at different scales and orientations. We show that this approach yields better results in terms of conventional segmentation metrics and overall topology of the resulting delineation. Although segmentation of curvilinear structures provides useful information, it is not always sufficient. In many cases, such as neuroscience and cartography, it is crucial to estimate the network connectivity. In order to find the graph representation of the structure depicted in the image, we propose an approach for joint segmentation and connection classification. Apart from pixel probabilities, this approach also returns the likelihood of a proposed path being a part of the reconstructed network. We show that segmentation and path classification are closely related tasks and can benefit from the synergy. The aforementioned methods rely on Machine Learning, which requires significant amounts of annotated ground-truth data to train models. The labelling process often requires expertise, it is costly and tiresome. To alleviate this problem, we introduce an Active Learning method that significantly decreases the time spent on annotating images. It queries the annotator only about the most informative examples, in this case the hypothetical paths belonging to the structure of interest. Contrary to conventional Active Learning methods, our approach exploits local consistency of linear paths to pick the ones that stand out from their neighborhood. Our final contribution is a method suited for both Active Learning and proofreading the result, which often requires more time than the automated delineation itself. It investigates edges of the delineation graph and determines the ones that are especially significant for the global reconstruction by perturbing their weights. Our Active Learning and proofreading strategies are combined with a new efficient formulation of an optimal subgraph computation and reduce the annotation effort by up to 80%.

EPFL2019

Designing Augmented Reality for the Classroom

Quentin Bonnard, Sébastien Cuendet, Pierre Dillenbourg

Augmented reality (AR) has recently received a lot of attention in education. Multiple AR systems for learning have been developed and tested through empirical studies often conducted in lab settings. While lab studies can be insightful, they leave out the complexity of a classroom environment. We developed three AR learning environments that have been used in genuine classroom contexts, some of them being now part of classroom regular practices. These systems and the learning activities they provide have been co-designed with teachers, for their own classrooms, through multiple cycles of prototyping and testing. We present here the features that emerged from these co-design cycles and abstract them into design principles. (C) 2013 Elsevier Ltd. All rights reserved.

Elsevier2013

Leveraging topology, geometry, and symmetries for efficient Machine Learning

Michaël Defferrard

When learning from data, leveraging the symmetries of the domain the data lies on is a principled way to combat the curse of dimensionality: it constrains the set of functions to learn from. It is more data efficient than augmentation and gives a generalization guarantee. Symmetries might however be unknown or expensive to find; domains might not be homogeneous.From the building blocks of space (vertices, edges, simplices), an incidence structure, and a metric---the domain's topology and geometry---a linear operator naturally emerges that commutes with any known and unknown symmetry action. We call that equivariant operator the generalized convolution operator. And we use it, designed or learned, to transform data and embed domains. In our generalized setting involving unknown and non-transitive symmetry groups, our convolution is an inner-product with a kernel that is localized instead of moved around by group actions like translations: a bias-variance tradeoff that paves the way to efficient learning on arbitrary discrete domains.We develop convolutional neural networks that operate on graphs, meshes, and simplicial complexes. Their implementation amounts to the multiplications of data tensors by sparse matrices and pointwise operations, with linear compute, memory, and communication requirements. We demonstrate our method's efficiency by reaching state-of-the-art performance for multiple tasks on large discretizations of the sphere. DeepSphere has been used for studies in cosmology and shall be used for operational weather forecasting---advancing our understanding of the world and impacting billions of individuals.

EPFL2022

Introducing Productive Engagement for Social Robots Supporting Learning

Jauwairia Nasir

We have all been one such student or seen such students who can maintain the 'good student' image while playing a video game under the table or those loyal backbenchers, seemingly always distracted, who then ace their exams. These intricacies of human behaviors are just a few examples of what makes it non-trivial and challenging even for expert teachers to know how students' visible behaviors relate with learning. As research investigates ways in which robots and AI can support teachers and students, it is faced with the same challenge of inferring students' engagement; thus, making the investigation of this topic increasingly popular in educational HRI. The state of the art usually explores the relationship between the robot behaviors and the engagement state of the learner while assuming a linear relationship between engagement and learning. However, is it correct to assume that to maximize learning, one needs to maximize engagement? Furthermore, conventional supervised engagement models require human annotators to get labels. This not only is laborious but can also introduce subjectivity. Can we have machine-learning engagement models where annotations do not rely on human annotators? Additionally, with the increase in open-ended learning activities which by design employ the 'learning by failing' paradigm, in-task performance can not be the best measure for learning. Can we instead rely on multi-modal behaviors? In an effort to cater for these challenges, this thesis dives deep to identify and quantify the relationship between learning and engagement, which we term as Productive Engagement (PE). In order to develop, design, and evaluate our PE framework, (1) we first designed and developed an open-ended collaborative learning activity that served as a platform for evaluating different robot variants over time. With 98 children interacting with the baseline version from 2 international Swiss schools, we showed that in-task performance and learning are indeed not correlated. Thus, this showed the importance of not being limited to robot interventions that affect only superficial measures of students' learning. (2) Then, with learner's multi-modal behaviors, we showed that indeed there is a hidden link between learner's behaviors and learning that can be quantified, i.e., validating the proposed concept of Productive Engagement. (3) This quantifiable link surfaced three collaborative multi-modal learner profiles, by using a forward and backward clustering and classification technique, two of which are linked to higher learning. This technique gave a possibility to surface data driven labels for engagement; thus, evading the process of human annotations. We then identified similarities and differences between these learner profiles both at an aggregate and at the temporal level. (4) Based on (3), we constructed a PE score that can either be directly used as an assessment metric by a social robot in real-time or as data driven labels for building more sophisticated regression models. (5) With the learner profiles and the PE score, we designed and evaluated more advanced robot variants for the final studies with ~160 students from 7 international Swiss schools. With the design of different robot variants that employ knowledge about the learner's skills conducive to learning, rather than domain knowledge, in order to provide interventions; we provided a complementary perspective on the role of social robots in educational settings.

EPFL2022

Learning continuous-time working memory tasks with on-policy neural reinforcement learning

Davide Zambrano

An animals' ability to learn how to make decisions based on sensory evidence is often well described by Reinforcement Learning (RL) frameworks. These frameworks, however, typically apply to event-based representations and lack the explicit and fine-grained notion of time needed to study psychophysically relevant measures like reaction times and psychometric curves. Here, we develop and use a biologically plausible continuous-time RL scheme of CT-AuGMEnT (Continuous-Time Attention-Gated MEmory Tagging) to study these behavioural quantities. We show how CT-AuGMEnT implements on-policy SARSA learning as a biologically plausible form of reinforcement learning with working memory units using 'attentional' feedback. We show that the CT-AuGMEnT model efficiently learns tasks in continuous time and can learn to accumulate relevant evidence through time. This allows the model to link task difficulty to psychophysical measurements such as accuracy and reaction-times. We further show how the implementation of a separate accessory network for feedback allows the model to learn continuously, also in case of significant transmission delays between the network's feedforward and feedback layers and even when the accessory network is randomly initialized. Our results demonstrate that CTAuGMEnT represents a fully time-continuous biologically plausible end-to-end RL model for learning to integrate evidence and make decisions. (c) 2021 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

2021

A Distributed Luenberger Observer for Linear State Feedback Systems With Quantized and Rate-Limited Communications

Andrea Alessandretti, Francisco Fernandes Castro Rego, Colin Neil Jones, Ye Pu

This article addresses the problem of simultaneous distributed state estimation, and control of linear systems with linear state feedback, subjected to process, and measurement noise, under the constraints of quantized, and rate-limited network data transmission. In the set-up adopted, sensors and actuators communicate through a network with a strongly connected topology. Unlike the case of centralized linear systems, for which the separation principle holds, the above practical assumption prevents the separate design of observers, and controller because each of the nodes does not necessarily have access to the control inputs generated at all the other nodes. We derive a linear distributed Luenberger observer, and a set of sufficient conditions that guarantee ultimate boundedness of the estimation error, and system state vectors, with bounds that depend on the L-infinity norm of the noise signals, and the number of bits used in the transmissions. A numerical example illustrates the performance and effectiveness of the proposed algorithm in controlling a network of open-loop unstable systems.

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021

Learning in Volatile Environments With the Bayes Factor Surprise

Johanni Michael Brea, Wulfram Gerstner, Vasiliki Liakoni, Alireza Modirshanechi

Surprise-based learning allows agents to rapidly adapt to nonstationary stochastic environments characterized by sudden changes. We show that exact Bayesian inference in a hierarchical model gives rise to a surprise-modulated trade-off between forgetting old observations and integrating them with the new ones. The modulation depends on a probability ratio, which we call the Bayes Factor Surprise, that tests the prior belief against the current belief. We demonstrate that in several existing approximate algorithms, the Bayes Factor Surprise modulates the rate of adaptation to new observations. We derive three novel surprise-based algorithms, one in the family of particle filters, one in the family of variational learning, and one in the family of message passing, that have constant scaling in observation sequence length and particularly simple update dynamics for any distribution in the exponential family. Empirical results show that these surprise-based algorithms estimate parameters better than alternative approximate approaches and reach levels of performance comparable to computationally more expensive algorithms. The Bayes Factor Surprise is related to but different from the Shannon Surprise. In two hypothetical experiments, we make testable predictions for physiological indicators that dissociate the Bayes Factor Surprise from the Shannon Surprise. The theoretical insight of casting various approaches as surprise-based learning, as well as the proposed online algorithms, may be applied to the analysis of animal and human behavior and to reinforcement learning in nonstationary environments.

MIT PRESS2021

Deep Generative Models and Applications

Tatjana Chavdarova

Over the past few years, there have been fundamental breakthroughs in core problems in machine learning, largely driven by advances in deep neural networks. The amount of annotated data drastically increased and supervised deep discriminative models exceeded human-level performances in certain object detection tasks. The increasing availability in quantity and complexity of unlabelled data also opens up exciting possibilities for the development of unsupervised learning methods. Among the family of unsupervised methods, deep generative models find numerous applications. Moreover, as real-world applications include high dimensional data, the ability of generative models to automatically learn semantically meaningful subspaces makes their advancement an essential step toward developing more efficient algorithms. Generative Adversarial Networks (GANs) are a family of unsupervised generative algorithms that have demonstrated impressive performance for data synthesis and are now used in a wide range of computer vision tasks. Despite this success, they gained a reputation for being difficult to train, which results in a time-consuming and human-involved development process to use them. In the first part of this thesis, we focus on improving the stability and the performances of GANs. Foremost, we consider an alternative training process to the standard one, named SGAN, in which several adversarial âlocalâ pairs of networks are trained independently so that a âglobalâ supervising pair of networks can be trained against them. Experimental results on both toy and real-world problems demonstrate that this approach outperforms standard training in terms of better mitigating mode collapse, stability while converging and that it surprisingly, increases the convergence speed as well. To further reduce the computational footprint while maintaining the stability and performance advantages of SGAN, we focus on training a single pair of adversarial networks using variance reduced gradient. More precisely, we study the effect of the stochastic gradient noise on the training of generative adversarial networks (GANs) and show that it can prevent the convergence of standard game optimization methods, while the batch version converges. We address this issue with two stochastic variance-reduced gradient and extragradient optimization algorithms for GANs, named SVRG-GAN and SVRE, respectively. We observe empirically that SVRE performs similarly to a batch method on the MNIST dataset, while being computationally cheaper, and that SVRE yields more stable GAN training on standard datasets. In the second part of the thesis we present our work on people detection. People detection methods are highly sensitive to occlusions between pedestrians, and using joint visual information from multiple synchronized cameras gives the opportunity to improve detection performance. We address the problem of multi-view people occupancy map estimation using an endâtoâend deep learning algorithm called DeepMCD that jointly utilizes the correlated streams of visual information. DeepMCD empirically outperformed the classical approaches by a large margin. Finally, we present a new large-scale and high-resolution dataset, named WILDTRACK. We provide an accurate joint calibration, as well as a series of benchmark results using baseline algorithms published over the recent months for multi-view detection with deep neural networks, and trajectory estimation using a non-Markovian model.

EPFL2020

OrthoNet: Multilayer Network Data Clustering

Giovanni Chierchia, Mireille El Gheche, Pascal Frossard

Network data appears in very diverse applications, like biological, social, or sensor networks. Clustering of network nodes into categories or communities has thus become a very common task in machine learning and data mining. Network data comes with some information about the network edges. In some cases, this network information can even be given with multiple views or layers, each one representing a different type of relationship between the network nodes. Increasingly often, network nodes also carry a feature vector. We propose in this paper to extend the node clustering problem, that commonly considers only the network information, to a problem where both the network information and the node features are considered together for learning a clustering-friendly representation of the feature space. Specifically, we design a generic two-step algorithm for multilayer network data clustering. The first step aggregates the different layers of network information into a graph representation given by the geometric mean of the network Laplacian matrices. The second step uses a neural net to learn a feature embedding that is consistent with the structure given by the network layers. We propose a novel algorithm for efficiently training the neural net via gradient descent, which encourages the neural net outputs to span the leading eigenvectors of the aggregated Laplacian matrix, in order to capture the pairwise interactions on the network, and provide a clustering-friendly representation of the feature space. We demonstrate with an extensive set of experiments on synthetic and real datasets that our method leads to a significant improvement w.r.t. state-of-the-art multilayer graph clustering algorithms, as it judiciously combines nodes features and network information in the node embedding algorithms.

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020