The (h, k)-Server Problem on Bounded Depth Trees

We study the k-server problem in the resource augmentation setting, i.e., when the performance of the online algorithm with k servers is compared to the offline optimal solution with h 0. Surprisingly, however, no o(h)-competitive algorithm is known even for HSTs of depth 2 and even when k/h is arbitrarily large. We obtain several new results for the problem. First, we show that the known k-server algorithms do not work even on very simple metrics. In particular, the Double Coverage algorithm has competitive ratio Omega(h) irrespective of the value of k, even for depth-2 HSTs. Similarly, the Work Function Algorithm, which is believed to be optimal for all metric spaces when k = h, has competitive ratio Omega(h) on depth-3 HSTs even if k = 2h. Our main result is a new algorithm that is O(1)-competitive for constant depth trees, whenever k = (1 + epsilon)h for any epsilon > 0. Finally, we give a general lower bound that any deterministic online algorithm has competitive ratio at least 2.4 even for depth-2 HSTs and when k/h is arbitrarily large. This gives a surprising qualitative separation between uniform metrics and depth-2 HSTs for the (h, k)-server problem.

Viability evolutionary algorithms and applications to neuroscience and biology

Andrea Maesani

Evolutionary algorithms are heuristic methods that operate on a population of individuals, which represent candidate solutions to optimization problems. Individuals with better quality, or fitness, are reproduced at a higher rate than less fit individuals by recombination and mutation. This process of selection and reproduction, based on fitness, models competition between individuals and leads to survival-of-the-fittest. Although this process lays at the foundation of evolutionary algorithms, the simplistic assumption that a single criterion can describe the quality of individuals is often unmet in real world problems, where multiple objectives or constraints have to be combined in the same fitness function. Furthermore, in nature, survival-of-the-fittest does not derive uniquely from competition, but is better seen as the outcome of an ongoing process of competition in parallel to a process of elimination of non-fit individuals. To resolve this mismatch and model different criteria for individuals separately, the Viability Evolution paradigm has been proposed in the literature. While the idea was previously introduced at a conceptual level, it had not yet been put to the test and lacks experimental validation. Here, we bridged this gap and tested whether viability-inspired evolutionary algorithms could confer advantages over the traditional evolutionary computation paradigm based on fitness. We started by investigating the evolutionary dynamics of a simple viability evolutionary method, and we analyzed the diversity of evolving populations. We also showed that the additional information available to a viability-based algorithm, such as the number of non-viable individuals for each viability criteria, can be exploited during the search for achieving better performance on optimization problems. In particular, we devised viability algorithms for constrained optimization, which outperformed current state-of-the-art methods on a well-known set of constrained optimization benchmarks. Furthermore, we embedded one of our algorithms into a novel framework for predicting structures of protein assemblies at atomic resolution. Finally, we used evolutionary methods to optimize neural networks in the context of a neuroscience investigation on the role of noise in animal behaviors. Noise is a ubiquitous feature of neural systems, but how it affects behaviors is far from being fully understood. After collecting large-scale measurements of Drosophila walking, we used evolutionary algorithms to search for neural networks that could match observed patterns of Drosophila spontaneous and odor-induced walking. By combining dynamical systems analysis and simulations, we showed how a noise-mediated memory of odor exposure accounts for the observed responses. In conclusion, this thesis contributes to evolutionary computation by testing the Viability Evolution paradigm and by proposing efficient viability evolutionary algorithms for constrained optimization. Furthermore, this thesis contributes to biology, by providing a new viability-based framework for predicting protein assemblies and by elucidating a mechanism through which neural noise may shape animal behaviors.

EPFL2015

Coordination and Sampling in Distributed Constraint Optimization

Brammert Ottens

The Distributed Constraint Optimization (DCOP) framework can be used to model a wide range of optimization problems that are inherently distributed. A distributed optimization problem can be viewed as a problem distributed over a set of agents, where agents are responsible for finding a solution for their part of the problem. In the DCOP framework, the decisions the agents need to take are modeled using decision variables, and both the local problems and the inter-dependencies are modeled using constraints. In this thesis, we attack two problems related to the DCOP framework. In the first part of this thesis, we look at coordination problems with complex, non- trivial preferences. In the DCOP literature, the notion of complex is used for problems where agents need to take multiple-decisions and thus own multiple decision variables. To express the fact that agents preferences are hard to obtain, we introduce the notion of a non-trivial local problem. The present DCOP literature has largely ignored the origin of preferences, i.e. algorithms assume that the constraints are known a-priori. In coordination problems with complex, non-trivial preferences this assumption no longer holds. In order to investigate the behavior of existing DCOP algorithms on such coordination problems, we first introduce a new DCOP model for such coordination problems, where we make an explicit distinction between the coordination part of the problem, and the local preferences of the agents. We then introduce two new benchmarks with complex, non-trivial local subproblems, and perform an evaluation of several complete and non-complete DCOP algorithms. Our results show that the O-DPOP algorithm, which elicits preferences from agents in a best-first order, outper- forms both other complete approaches as also local search approaches. We show that, despite the fact that a best first order cannot always be guaranteed when dealing with non-trivial local problems, O-DPOP still finds solutions that are either better, or on par with, local search algorithms. In the second part of this thesis, we introduce a new sampling based approach to solving DCOPs. Existing DCOP algorithms are either complete, but do not scale well, or scale well but are not guaranteed to find a solution. Our approach, inspired by the application of the UCB algorithm for the multi-armed bandit problem on trees, aims to provide method that scales well. Furthermore, given certain assumptions on the problem structure, our method is guaranteed to find good solutions. We introduce the Distributed UCT (DUCT) algorithm, that uses bounds similar to those used in the UCT algorithm, which is an adaptation of the UCB approach on trees. We introduce and evaluate four different variations of the DUCT algorithm, DUCT-A, DUCT-B, DUCT-C and DUCT-D, that differ in the bounds that they use. To evaluate our algorithms, we compare them with existing DCOP approaches on three different types of problems, both with and without hard constraints. Our results show that, compared with other DCOP algorithms, the DUCT-D variant consistently performs well on the problems used, with respect to both solution quality and runtime. Furthermore, it consistently sends less information than the state-of-the-art DCOP algorithms, and is thus shown to be a suitable and practical algorithm for solving DCOPs.

EPFL2012

Fréchet means in Wasserstein space

Yoav Zemel

This work studies the problem of statistical inference for Fréchet means in the Wasserstein space of measures on Euclidean spaces,

\mathcal W_2 ( \mathbb R^d )

. This question arises naturally from the problem of separating amplitude and phase variation in point processes, analogous to a well-known problem in functional data analysis. We formulate the point process version of the problem, show that it is canonically equivalent to that of estimating Fréchet means in

\mathcal W_2 ( \mathbb R d )

, and carry out estimation by means of

M

-estimation. This approach allows to achieve consistency in a genuinely nonparametric framework, even in a sparse sampling regime. For Cox processes on the real line, consistency is supplemented by convergence rates and, in the dense sampling regime,

\sqrt n

-consistency and a central limit theorem. Computation of the Fréchet mean is challenging when the processes are multivariate, in which case our Fréchet mean estimator is only defined implicitly as the minimiser of an optimisation problem. To overcome this difficulty, we propose a steepest descent algorithm that approximates the minimiser, and show that it converges to a local minimum. Our techniques are specific to the Wasserstein space, because Hessian-type arguments that are commonly used for similar convergence proofs do not apply to that space. In addition, we discuss similarities with generalised Procrustes analysis. The key advantage of the algorithm is that it requires only the solution of pairwise transportation problems. The results in the preceding paragraphs require properties of Fréchet means in

\mathcal W_2 ( \mathbb R ^d )

whose theory is developed, supplemented by some new results. We present the tangent bundle and exploit its relation to optimal maps in order to derive differentiability properties of the associated Fréchet functional, obtaining a characterisation of Karcher means. Additionally, we establish a new optimality criterion for local minima and prove a new stability result for the optimal maps that, enhanced with the established consistency of the Fréchet mean estimator, yields consistency of the optimal transportation maps.

EPFL2017