FLeet: Online Federated Learning via Staleness Awareness and Performance Prediction

Federated Learning (FL) is very appealing for its privacy benefits: essentially, a global model is trained with updates computed on mobile devices while keeping the data of users local. Standard FL infrastructures are however designed to have no energy or performance impact on mobile devices, and are therefore not suitable for applications that require frequent (online) model updates, such as news recommenders. This paper presents FLeet, the first Online FL system, acting as a middleware between the Android OS and the machine learning application. FLeet combines the privacy of Standard FL with the precision of online learning thanks to two core components: (i) I-Prof, a new lightweight profiler that predicts and controls the impact of learning tasks on mobile devices, and (ii) AdaSGD, a new adaptive learning algorithm that is resilient to delayed updates. Our extensive evaluation shows that Online FL, as implemented by FLeet, can deliver a 2.3× quality boost compared to Standard FL, while only consuming 0.036% of the battery per day. I-Prof can accurately control the impact of learning tasks by improving the prediction accuracy up to 3.6× (computation time) and up to 19× (energy). AdaSGD outperforms alternative FL approaches by 18.4% in terms of convergence speed on heterogeneous data.

Population Sensing Using Mobile Devices

Farid Movahedi Naini

In our daily lives, our mobile phones sense our movements and interactions via a rich set of embedded sensors such as a GPS, Bluetooth, accelerometers, and microphones. This enables us to use mobile phones as agents for collecting spatio-temporal data. The idea of mining these spatio-temporal data is currently being explored for many applications, including environmental pollution monitoring, health care, and social networking. When used as sensing devices, a particular feature of mobile phones is their aspect of mobility, in contrast to static sensors. Furthermore, despite having useful applications, collecting data from mobile phones introduces privacy concerns, as the collected data might reveal sensitive information about the users, especially if the collector has access to auxiliary information. In the first part of this thesis, we use spatio-temporal data collected by mobile phones in order to evaluate different features of a population related to their mobility patterns. In particular, we consider the problems of population-size and population-density estimation that have applications, among others, in crowd monitoring, activity-hotspot detection, and urban analysis. We first conduct an experiment where ten attendees of an open-air music festival act as Bluetooth probes. Next, we construct parametric statistical models to estimate the total number of visible Bluetooth devices and their density in the festival area. We further test our proposed models against Wi-Fi traces obtained on the EPFL campus. We conclude that mobile phones can be effectively used as sensing devices to evaluate mobility-related parameters of a population. For the specific problem of population-density estimation, we investigate the mobility aspect of sensing: We quantitatively analyze the performance of mobile sensors compared to static sensors. Under an independent and identically distributed mobility model for the population, we derive the optimal random-movement strategy for mobile sensors in order to yield the best estimate of population density (in the mean-squared error sense). This enables us to plan an adaptive trajectory for the mobile sensors. In particular, we demonstrate that mobility brings an added value to the sensors; these sensors outperform static sensors for long observation intervals. In the second part of this thesis, we analyze the vulnerability of anonymized mobility statistics stored in the form of histograms. We consider an attacker who has access to an anonymized set of histograms of a set of users’ mobility traces and to an independent set of non-anonymized histograms of traces belonging to the same users. We study the hypothesis-testing problem of identifying the correct matching between the anonymized histograms and the non-anonymized histograms. We show that the solution can be obtained by using a minimum-weight matching algorithm on a complete weighted bipartite graph. By applying the algorithm to Wi-Fi traces obtained on the EPFL campus, we demonstrate that in fact anonymized histograms contain a significant amount of information that could be used to uniquely identify users by an attacker with access to auxiliary information about the users. Finally, we demonstrate how trust relationships between users can be exploited to enhance their privacy. We consider the specific problem of the privacy-preserving computation of functions of data that belong to users in a social network. An example of an application is a poll or a survey on a private issue. Most of the known non-cryptographic solutions to this problem can be viewed as belonging to one of the following two extreme regimes. The first regime is when every user trusts only herself and she is responsible for protecting her own privacy. In other words, the circle of trust of a user has a single member: herself. In the second regime, every user trusts herself and the server, but not any of the other users. In other words, the circle of trust of a user comprises herself and the server. We investigate this problem under the assumption that users are willing to share their private data with trusted friends in the network, hence we consider a regime in which the circle of trust of a user consists of herself and her friends. Thus, our approach falls in-between the two mentioned regimes. Our algorithm consists of first partitioning users into circles of trust and then computing the global function by using results of local computations within each circle. We demonstrate that such trust relationships can be exploited to significantly improve the tradeoff between the privacy of users' data and the accuracy of the computation.

EPFL2014

Applications of Approximate Learning and Inference for Probabilistic Models

Young Jun Ko

We develop approximate inference and learning methods for facilitating the use of probabilistic modeling techniques motivated by applications in two different areas. First, we consider the ill-posed inverse problem of recovering an image from an underdetermined system of linear measurements corrupted by noise. Second, we consider the problem of inferring user preferences for items from counts, pairwise comparisons and user activity logs, instances of implicit feedback. Plausible models for images and the noise, incurred when recording them, render posterior inference intractable, while the scale of the inference problem makes sampling based approximations ineffective. Therefore, we develop deterministic approximate inference algorithms for two different augmentations of a typical sparse linear model: first, for the rectified-linear Poisson likelihood, and second, for tree-structured super-Gaussian mixture models. The rectified-linear Poisson likelihood is an alternative noise model, applicable in astronomical and biomedical imaging applications, that operate in intensity regimes in which quantum effects lead to observations that are best described by counts of particles arriving at a sensor, as well as in general Poisson regression problems arising in various fields. In this context we show, that the model-specific computations for Expectation Propagation can be robustly solved by a simple dynamic program. Next, we develop a scalable approximate inference algorithm for structured mixture models, that uses a discrete graphical model to represent dependencies between the latent mixture components of a collection of mixture models. Specifically, we use tree-structured mixtures of super-Gaussians to model the persistence across scales of large coefficients of the Wavelet transform of an image for improved reconstruction. In the second part on models of user preference, we consider two settings: the global static and the contextual dynamic setting. In the global static setting, we represent user-item preferences by a latent low-rank matrix. Instead of using numeric ratings we develop methods to infer this latent representation for two types of implicit feedback: aggregate counts of users interacting with a service and the binary outcomes of pairwise comparisons. We model count data using a latent Gaussian bilinear model with Poisson likelihoods. For this model, we show that the Variational Gaussian approximation can be further relaxed to be available in closed-form by adding additional constraints, leading to an efficient inference algorithm. In the second implicit feedback scenario, we infer the latent preference matrix from pairwise preference statements. We combine a low-rank bilinear model with non-parameteric item- feature regression and develop a novel approximate variational Expectation Maximization algorithm that mitigates the computational challenges due to latent couplings induced by the pairwise comparisons. Finally, in the contextual dynamic setting, we model sequences of user activity at the granularity of single interaction events instead of aggregate counts. Routinely gathered in the background at a large scale in many applications, such sequences can reveal temporal and contextual aspects of user behavior through recurrent patterns. To describe such data, we propose a generic collaborative sequence model based on recurrent neural networks, that combines ideas from collaborative filtering and language modeling.

EPFL2017

Low Power Sensing and Processing in Wearable Biomedical Devices for Personalized Health Monitoring

Grégoire Casimir Joseph Surrel

Whether it is for personal use or for medical application, wearable sensors are becoming more and more widespread. This is the industry answer to two parallel trends. First, the public show a wish to collect data about their own lifestyle. This rather new effect appeared with the rise of smartphones, smartwatches and other heart-rate belts for athletes, with the promise of understanding and improving their health and performance. From a medical point-of-view, these commercial devices are not usable because their results come from an unproven algorithm, far from clinical trials. However, the health-care professionals see a strong benefit of having trustworthy wearable devices, which can be used by their patients for extended periods of time. Having in situ medical-grade data collection is able to give insights about the patient's health status and its development. There are however limitations to what can be performed. Ideally, such a device should record as many data as possible, without requiring any set-up nor maintenance. Because of technical limitations, there are choices to be made. For example, which signals are captured, or what should be the minimal battery life? Any additional burden put on the patient hinders using the device, especially in the case of a non immediate life-threatening situation such as a daily screening. State-of-the-art biomedical wearable devices deploy multiple strategies to match the specification's stringent requirements. First it is engetically expensive to sense signals. The more data is collected, the smaller the battery lifetime. Therefore, extensive research is pursued beforehand to minimize the number of signals required. If a pathology can be reliably identified with fewer data, it is a meaningful saving. Additional energy savings are possible by minimizing the amount of data to transmit. Pushing this idea to the extreme, if the diagnostics algorithm can be efficiently run on the device itself, sending only the results is an excellent approach adopted by a number of sensor nodes. In this thesis, I first propose event-driven approaches for sensing bio-signals, designed to take into account the signal's behavior. Changing the sampling strategy is based on the fact that oversampling is frequent, because this approach provides strong guarantees about the data quality. However, it is not taking into account the actual signal's temporal characteristics, where a constant value is digitized with the same rate as a high-frequency pattern. Taking into account the signal's evolution, several kinds of events are envisioned for triggering the measure, from a simple level-crossing strategy to a more refined knowledge-based one. This event-driven sampling paradigm minimizes the amount of data to process, leading to an increased battery lifetime. Secondly, I consider a widespread but under-diagnosed disease: obstructive sleep apnea. This disease is connected to increased risks of cardiovascular diseases, motivating the need for diagnostic and treatment. The target device I consider is an existing wearable biomedical node. Following the optimization process described previously, I rely on a single biological signal processed directly on the sensor. Using machine learning, a limited number of features are extracted and filtered before being used for the obstructive sleep apnea assessment. Afterwards, the device only requires to send the results to a base station, being a non-instrusive OSA screening system.

EPFL2019