Time-Varying Gaussian Process Bandit Optimization

We consider the sequential Bayesian optimization problem with bandit feedback, adopting a formulation that allows for the reward function to vary with time. We model the reward function using a Gaussian process whose evolution obeys a simple Markov model. We introduce two natural extensions of the classical Gaussian process upper confidence bound (GP-UCB) algorithm. The first, R-GP-UCB, resets GP-UCB at regular intervals. The second, TV-GP-UCB, instead forgets about old data in a smooth fashion. Our main contribution comprises of novel regret bounds for these algorithms, providing an explicit characterization of the trade-off between the time horizon and the rate at which the function varies. We illustrate the performance of the algorithms on both synthetic and real data, and we find the gradual forgetting of TV-GP-UCB to perform favorably compared to the sharp resetting of R-GP-UCB. Moreover, both algorithms significantly outperform classical GP-UCB, since it treats stale and fresh data equally.

Robust Adaptive Decision Making: Bayesian Optimization and Beyond

Ilija Bogunovic

The central task in many interactive machine learning systems can be formalized as the sequential optimization of a black-box function. Bayesian optimization (BO) is a powerful model-based framework for \emph{adaptive} experimentation, where the primary goal is the optimization of the black-box function via sequentially chosen decisions. In many real-world tasks, it is essential for the decisions to be \emph{robust} against, e.g., adversarial failures and perturbations, dynamic and time-varying phenomena, a mismatch between simulations and reality, etc. Under such requirements, the standard methods and BO algorithms become inadequate. In this dissertation, we consider four research directions with the goal of enhancing robust and adaptive decision making in BO and associated problems. First, we study the related problem of level-set estimation (LSE) with Gaussian Processes (GPs). While in BO the goal is to find a maximizer of the unknown function, in LSE one seeks to find all "sufficiently good" solutions. We propose an efficient confidence-bound based algorithm that treats BO and LSE in a unified fashion. It is effective in settings that are non-trivial to incorporate into existing algorithms, including cases with pointwise costs, heteroscedastic noise, and multi-fidelity setting. Our main result is a general regret guarantee that covers these aspects. Next, we consider GP optimization with robustness requirement: An adversary may perturb the returned design, and so we seek to find a robust maximizer in the case this occurs. This requirement is motivated by, e.g., settings where the functions during optimization and implementation stages are different. We propose a novel robust confidence-bound based algorithm. The rigorous regret guarantees for this algorithm are established and complemented with an algorithm-independent lower bound. We experimentally demonstrate that our robust approach consistently succeeds in finding a robust maximizer while standard BO methods fail. We then investigate the problem of GP optimization in which the reward function varies with time. The setting is motivated by many practical applications in which the function to be optimized is not static. We model the unknown reward function via a GP whose evolution obeys a simple Markov model. Two confidence-bound based algorithms with the ability to "forget" about old data are proposed. We obtain regret bounds for these algorithms that jointly depend on the time horizon and the rate at which the function varies. Finally, we consider the maximization of a set function subject to a cardinality constraint

k

in the case a number of items

\tau

from the returned set may be removed. One notable application is in batch BO where we need to select experiments to run, but some of them can fail. Our focus is on the worst-case adversarial setting, and we consider both \emph{submodular} (i.e., satisfies a natural notion of diminishing returns) and \emph{non-submodular} objectives. We propose robust algorithms that achieve constant-factor approximation guarantees. In the submodular case, the result on the maximum number of allowed removals is improved to

\tau = o(k)

in comparison to the previously known

\tau=o(\sqrt{k})

. In the non-submodular case, we obtain new guarantees in the support selection and batch BO tasks. We empirically demonstrate the robust performance of our algorithms in these, as well as, in data summarization and influence maximization tasks.

EPFL2019

Evaluating Latency of Distributed Algorithms Using Petri Nets

Nicoleta Sergent

Evaluating Latency of Distributed Algorithms Using Petri Nets N. Sergent The time it takes to a distributed algorithm to finish (the distributed algorithm latency) cannot be directly measured in asynchronous systems if the algorithm starts and ends on different processors, since the system has no global time. A simple method to evaluate this latency is to build and simulate a unified model which includes the network and the distributed algorithm sub-models. In this paper we introduce a network model for UDP (User Datagram Protocol) which allows to establish a relationship between the number of messages exchanged in a distributed algorithm and the communication delays. As an application, we consider the two-phase commitment algorithm. Numerical results derived from simulating the model are compared with data obtained from performance measures.

1997

Analysis and numerical simulation of viscoelastic flows

Andrea Bonito

Mathematical and numerical aspects of viscoelastic flows are investigated here. Two simplified mathematical models are considered. They are motivated by a splitting algorithm for solving viscoelastic flows with free surfaces. The first model is a simplified Oldroyd-B model. Existence on a fixed time interval is proved in several Banach spaces provided the data are small enough. Short time existence is also proved for arbitrarily large data in Hölder spaces for the time variable. These results are based on the maximal regularity property of the Stokes operator and on the analycity behavior of the corresponding semi-group. A finite element discretization in space is then proposed. Existence of the numerical solution is proved for small data, as well as a priori error estimates, using an implicit function theorem framework. Then, the extension of these results to a stochastic simplified Hookean dumbbells model is discussed. Because of the presence of the Brownian motion, existence in a fixed time interval, provided the data are small enough, is proved only in some of the Banach spaces considered previously. The dumbbells' elongation is split in two parts, one satisfying a standart stochastic differential equation, the other satisfying a partial differential equation with a stochastic source term. A finite element discretization in space is also proposed. Existence of the numerical solution is proved for small data, as well as a priori error estimates. A numerical algorithm for solving viscoelastic flows with free surfaces is also described. This algorithm is based on a splitting method in time and two different meshes are used for the space discretization. Convergence of the numerical model is checked for the pure extensional flow and the filling of a pipe. Then, numerical results are reported for the stretching of a filament and for jet buckling.

EPFL2006

Robust Adaptive Decision Making: Bayesian Optimization and Beyond

Ilija Bogunovic

k

in the case a number of items

\tau

\tau = o(k)

in comparison to the previously known

\tau=o(\sqrt{k})

EPFL2019