Douglas J. Leith

Julien Monteil, Melanie Bouroche, Douglas J. Leith

The presence of (partially) automated vehicles on the roads presents an opportunity to compensate the unstable behaviour of conventional vehicles. Vehicles subject to perturbations should (i) recover their equilibrium speed, (ii) react not to propagate but absorb perturbations. In this work, we start with considering vehicle systems consisting of heterogeneous vehicles updating their dynamics according to realistic behavioural car-following models. Definitions of all types of stability that are of interest in the vehicle system, namely input-output stability, scalability, weak and strict string stability, are introduced based on recent studies. Then, frequency domain linear stability analyses are conducted after linearisation of the modelled system of vehicles, leading to conditions for input-output stability, strict and weak string stability over the behavioural parameters of the system, for finite and infinite systems of homogeneous and heterogeneous vehicles. This provides a solid basis that was missing for car-following model-based control design in mixed traffic systems where only a proportion of vehicles can be controlled. After visualisation of the theoretical results in simulation, we formulate an optimisation strategy with LMI constraints to tune the behavioural parameters of the automated vehicles in order to maximise the L1 string stability of the mixed traffic flow while considering the comfort of automated driving. The optimisation strategy systematically leads to increased traffic flow stability. We show that very few automated vehicles are required to prevent the

Naram Mhaisen, George Iosifidis, Douglas Leith

The design of effective online caching policies is an increasingly important problem for content distribution networks, online social networks and edge computing services, among other areas. This paper proposes a new algorithmic toolbox for tackling this problem through the lens of \emph{optimistic} online learning. We build upon the Follow-the-Regularized-Leader (FTRL) framework, which is developed further here to include predictions for the file requests, and we design online caching algorithms for bipartite networks with pre-reserved or dynamic storage subject to time-average budget constraints. The predictions are provided by a content recommendation system that influences the users viewing activity and hence can naturally reduce the caching network's uncertainty about future requests. We also extend the framework to learn and utilize the best request predictor in cases where many are available. We prove that the proposed {optimistic} learning caching policies can achieve \emph{sub-zero} performance loss (regret) for perfect predictions, and maintain the sub-linear regret bound $O(\sqrt T)$, which is the best achievable bound for policies that do not use predictions, even for arbitrary-bad predictions. The performance of the proposed algorithms is evaluated with detailed trace-driven numerical tests.

Mohamed Suliman, Douglas Leith

In this paper we present new attacks against federated learning when used to train natural language text models. We illustrate the effectiveness of the attacks against the next word prediction model used in Google's GBoard app, a widely used mobile keyboard app that has been an early adopter of federated learning for production use. We demonstrate that the words a user types on their mobile handset, e.g. when sending text messages, can be recovered with high accuracy under a wide range of conditions and that counter-measures such a use of mini-batches and adding local noise are ineffective. We also show that the word order (and so the actual sentences typed) can be reconstructed with high fidelity. This raises obvious privacy concerns, particularly since GBoard is in production use.

Douglas J. Leith, George Iosifidis

In this paper we extend the classical Follow-The-Regularized-Leader (FTRL) algorithm to encompass time-varying constraints, through adaptive penalization. We establish sufficient conditions for the proposed Penalized FTRL algorithm to achieve $O(\sqrt{t})$ regret and violation with respect to strong benchmark $\hat{X}^{max}_t$. Lacking prior knowledge of the constraints, this is probably the largest benchmark set that we can reasonably hope for. Our sufficient conditions are necessary in the sense that when they are violated there exist examples where $O(\sqrt{t})$ regret and violation is not achieved. Compared to the best existing primal-dual algorithms, Penalized FTRL substantially extends the class of problems for which $O(\sqrt{t})$ regret and violation performance is achievable.

David Young, Douglas Leith, George Iosifidis

We show that a kernel estimator using multiple function evaluations can be easily converted into a sampling-based bandit estimator with expectation equal to the original kernel estimate. Plugging such a bandit estimator into the standard FTRL algorithm yields a bandit convex optimisation algorithm that achieves $\tilde{O}(t^{1/2})$ regret against adversarial time-varying convex loss functions.

George Iosifidis, Naram Mhaisen, Douglas J. Leith

AI/ML-based tools are at the forefront of resource management solutions for communication networks. Deep learning, in particular, is highly effective in facilitating fast and high-performing decision-making whenever representative training data is available to build offline accurate models. Conversely, online learning solutions do not require training and enable adaptive decisions based on runtime observations, alas are often overly conservative. This extensive tutorial proposes the use of optimistic learning (OpL) as a decision engine for resource management frameworks in modern communication systems. When properly designed, such solutions can achieve fast and high-performing decisions -- comparable to offline-trained models -- while preserving the robustness and performance guarantees of the respective online learning approaches. We introduce the fundamental concepts, algorithms and results of OpL, discuss the roots of this theory and present different approaches to defining and achieving optimism. We proceed to showcase how OpL can enhance resource management in communication networks for several key problems such as caching, edge computing, network slicing, and workload assignment in decentralized O-RAN platforms. Finally, we discuss the open challenges that must be addressed to unlock the full potential of this new resource management approach.

Vaibhav Gusain, Douglas Leith

We propose a novel redaction methodology that can be used to sanitize natural text data. Our new technique provides better privacy benefits than other state of the art techniques while maintaining lower redaction levels.

David Young, Douglas Leith

We develop a novel latent-bandit algorithm for tackling the cold-start problem for new users joining a recommender system. This new algorithm significantly outperforms the state of the art, simultaneously achieving both higher accuracy and lower regret.

Naram Mhaisen, George Iosifidis, Douglas Leith

The design of effective online caching policies is an increasingly important problem for content distribution networks, online social networks and edge computing services, among other areas. This paper proposes a new algorithmic toolbox for tackling this problem through the lens of optimistic online learning. We build upon the Follow-the-Regularized-Leader (FTRL) framework which is developed further here to include predictions for the file requests, and we design online caching algorithms for bipartite networks with fixed-size caches or elastic leased caches subject to time-average budget constraints. The predictions are provided by a content recommendation system that influences the users viewing activity, and hence can naturally reduce the caching network's uncertainty about future requests. We prove that the proposed optimistic learning caching policies can achieve sub-zero performance loss (regret) for perfect predictions, and maintain the best achievable regret bound $O(\sqrt T)$ even for arbitrary-bad predictions. The performance of the proposed algorithms is evaluated with detailed trace-driven numerical tests.

Daron Anderson, George Iosifidis, Douglas J. Leith

We consider the general problem of online convex optimization with time-varying additive constraints in the presence of predictions for the next cost and constraint functions. A novel primal-dual algorithm is designed by combining a Follow-The-Regularized-Leader iteration with prediction-adaptive dynamic steps. The algorithm achieves $\mathcal O(T^{\frac{3-β}{4}})$ regret and $\mathcal O(T^{\frac{1+β}{2}})$ constraint violation bounds that are tunable via parameter $β\!\in\![1/2,1)$ and have constant factors that shrink with the predictions quality, achieving eventually $\mathcal O(1)$ regret for perfect predictions. Our work extends the FTRL framework for this constrained OCO setting and outperforms the respective state-of-the-art greedy-based solutions, without imposing conditions on the quality of predictions, the cost functions or the geometry of constraints, beyond convexity.

Douglas J. Leith, Stephen Farrell

We report on the results of a measurement study carried out on a commuter bus in Dublin, Ireland using the Google/Apple Exposure Notification (GAEN) API. This API is likely to be widely used by Covid-19 contact tracing apps. Measurements were collected between 60 pairs of handset locations and are publicly available. We find that the attenuation level reported by the GAEN API need not increase with distance between handsets, consistent with there being a complex radio environment inside a bus caused by the metal-rich environment. Changing the people holding a pair of handsets, with the location of the handsets otherwise remaining unchanged, can cause variations of +/-10dB in the attenuation level reported by the GAEN API. Applying the rule used by the Swiss Covid-19 contact tracing app to trigger an exposure notification to our bus measurements we find that no exposure notifications would have been triggered despite the fact that all pairs of handsets were within 2m of one another for at least 15 mins. Applying an alternative threshold-based exposure notification rule can somewhat improve performance to a detection rate of 5% when an exposure duration threshold of 15 minutes is used, increasing to 8% when the exposure duration threshold is reduced to 10 mins. Stratifying the data by distance between pairs of handsets indicates that there is only a weak dependence of detection rate on distance.

Douglas J. Leith, Stephen Farrell

We report on measurements of Bluetooth Low Energy (LE) received signal strength taken on mobile handsets in a variety of common, real-world settings. We note that a key difficulty is obtaining the ground truth as to when people are in close proximity to one another. Knowledge of this ground truth is important for accurately evaluating the accuracy with which contact events are detected by Bluetooth LE. We approach this by adopting a scenario-based approach. In summary, we find that the Bluetooth LE received signal strength can vary substantially depending on the relative orientation of handsets, on absorption by the human body, reflection/absorption of radio signals in buildings and trains. Indeed we observe that the received signal strength need not decrease with increasing distance. This suggests that the development of accurate methods for proximity detection based on Bluetooth LE received signal strength is likely to be challenging. Our measurements also suggest that combining use of Bluetooth LE contact tracing apps with adoption of new social protocols may yield benefits but this requires further investigation. For example, placing phones on the table during meetings is likely to simplify proximity detection using received signal strength. Similarly, carrying handbags with phones placed close to the outside surface. In locations where the complexity of signal propagation makes proximity detection using received signal strength problematic entry/exit from the location might instead be logged in an app by e.g. scanning a time-varying QR code or the like.

Daron Anderson, Douglas Leith

We prove the familiar Lazy Online Gradient Descent algorithm is universal on polytope domains. That means it gets $O(1)$ pseudo-regret against i.i.d opponents, while simultaneously achieving the well-known $O(\sqrt N)$ worst-case regret bound. For comparison the bulk of the literature focuses on variants of the Hedge (exponential weights) algorithm on the simplex. These can in principle be lifted to general polytopes; however the process is computationally unfeasible for many important classes where the number of vertices grows quickly with the dimension. The lifting procedure also ignores any Euclidean bounds on the cost vectors, and can create extra factors of dimension in the pseudo-regret bound. Gradient Descent is simpler than the handful of purpose-built algorithms for polytopes in the literature, and works in a broader setting. In particular existing algorithms assume the optimiser is unique, while our bound allows for several optimal vertices.

A. Galanopoulos, A. G. Tasiopoulos, G. Iosifidis et al.

A large number of emerging IoT applications rely on machine learning routines for analyzing data. Executing such tasks at the user devices improves response time and economizes network resources. However, due to power and computing limitations, the devices often cannot support such resource-intensive routines and fail to accurately execute the analytics. In this work, we propose to improve the performance of analytics by leveraging edge infrastructure. We devise an algorithm that enables the IoT devices to execute their routines locally; and then outsource them to cloudlet servers, only if they predict they will gain a significant performance improvement. It uses an approximate dual subgradient method, making minimal assumptions about the statistical properties of the system's parameters. Our analysis demonstrates that our proposed algorithm can intelligently leverage the cloudlet, adapting to the service requirements.

A. Galanopoulos, V. Valls, G. Iosifidis et al.

We develop an edge-assisted object recognition system with the aim of studying the system-level trade-offs between end-to-end latency and object recognition accuracy. We focus on developing techniques that optimize the transmission delay of the system and demonstrate the effect of image encoding rate and neural network size on these two performance metrics. We explore optimal trade-offs between these metrics by measuring the performance of our real time object recognition application. Our measurements reveal hitherto unknown parameter effects and sharp trade-offs, hence paving the road for optimizing this key service. Finally, we formulate two optimization problems using our measurement-based models and following a Pareto analysis we find that careful tuning of the system operation yields at least 33% better performance for real time conditions, over the standard transmission method.

Daron Anderson, Douglas J. Leith

We consider online learning problems where the aim is to achieve regret which is efficient in the sense that it is the same order as the lowest regret amongst K experts. This is a substantially stronger requirement that achieving $O(\sqrt{n})$ or $O(\log n)$ regret with respect to the best expert and standard algorithms are insufficient, even in easy cases where the regrets of the available actions are very different from one another. We show that a particular lazy form of the online subgradient algorithm can be used to achieve minimal regret in a number of "easy" regimes while retaining an $O(\sqrt{n})$ worst-case regret guarantee. We also show that for certain classes of problem minimal regret strategies exist for some of the remaining "hard" regimes.

Daron Anderson, Douglas Leith

We show that the Subgradient algorithm is universal for online learning on the simplex in the sense that it simultaneously achieves $O(\sqrt N)$ regret for adversarial costs and $O(1)$ pseudo-regret for i.i.d costs. To the best of our knowledge this is the first demonstration of a universal algorithm on the simplex that is not a variant of Hedge. Since Subgradient is a popular and widely used algorithm our results have immediate broad application.

Pol Mac Aonghusa, Douglas Leith

Limiting online data collection to the minimum required for specific purposes is mandated by modern privacy legislation such as the General Data Protection Regulation (GDPR) and the California Consumer Protection Act. This is particularly true in online services where broad collection of personal information represents an obvious concern for privacy. We challenge the view that broad personal data collection is required to provide personalised services. By first developing formal models of privacy and utility, we show how users can obtain personalised content, while retaining an ability to plausibly deny their interests in topics they regard as sensitive using a system of proxy, group identities we call 3PS. Through extensive experiment on a prototype implementation, using openly accessible data sources, we show that 3PS provides personalised content to individual users over 98% of the time in our tests, while protecting plausible deniability effectively in the face of worst-case threats from a variety of attack types.

Pol Mac Aonghusa, Douglas J. Leith

We ask how to defend user ability to plausibly deny their interest in topics deemed sensitive in the face of search engine learning. We develop a practical and scalable tool called \PDE{} allowing a user to detect and assess threats to plausible deniability. We show that threats to plausible deniability of interest are readily detectable for all topics tested in an extensive testing program. Of particular concern is observation of threats to deniability of interest in topics related to health and sexual preferences. We show this remains the case when attempting to disrupt search engine learning through noise query injection and click obfuscation. We design a defence technique exploiting uninteresting, proxy topics and show that it provides a more effective defence of plausible deniability in our experiments.

Pól Mac Aonghusa, Douglas J. Leith

Our ability to control the flow of sensitive personal information to online systems is key to trust in personal privacy on the internet. We ask how to detect, assess and defend user privacy in the face of search engine personalisation? We develop practical and scalable tools allowing a user to detect, assess and defend against threats to plausible deniability. We show that threats to plausible deniability of interest are readily detectable for all topics tested in an extensive testing program. We show this remains the case when attempting to disrupt search engine learning through noise query injection and click obfuscation are used. We use our model we design a defence technique exploiting uninteresting, proxy topics and show that it provides amore effective defence of plausible deniability in our experiments.

Alessandro Checco, Giuseppe Bianchi, Doug Leith

We propose a privacy-enhanced matrix factorization recommender that exploits the fact that users can often be grouped together by interest. This allows a form of "hiding in the crowd" privacy. We introduce a novel matrix factorization approach suited to making recommendations in a shared group (or nym) setting and the BLC algorithm for carrying out this matrix factorization in a privacy-enhanced manner. We demonstrate that the increased privacy does not come at the cost of reduced recommendation accuracy.

Naoise Holohan, Doug Leith, Oliver Mason

We study mechanisms for differential privacy on finite datasets. By deriving \emph{sufficient sets} for differential privacy we obtain necessary and sufficient conditions for differential privacy, a tight lower bound on the maximal expected error of a discrete mechanism and a characterisation of the optimal mechanism which minimises the maximal expected error within the class of mechanisms considered.

Pól Mac Aonghusa, Douglas J. Leith

From buying books to finding the perfect partner, we share our most intimate wants and needs with our favourite online systems. But how far should we accept promises of privacy in the face of personal profiling? In particular we ask how can we improve detection of sensitive topic profiling by online systems? We propose a definition of privacy disclosure we call ε-indistinguishability from which we construct scalable, practical tools to assess an adversaries learning potential. We demonstrate our results using openly available resources, detecting a learning rate in excess of 98% for a range of sensitive topics during our experiments.