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

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.

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.

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 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.

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.

Naoise Holohan, Douglas J. Leith, Oliver Mason

We examine a generalised Randomised Response (RR) technique in the context of differential privacy and examine the optimality of such mechanisms. Strict and relaxed differential privacy are considered for binary outputs. By examining the error of a statistical estimator, we present closed solutions for the optimal mechanism(s) in both cases. The optimal mechanism is also given for the specific case of the original RR technique as introduced by Warner in 1965.

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.

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.