- Scalable stochastic variance reduced gradient methods (SCAVARG)
PGMO Call 2018.
Budget: 8 kE
Coordinator: Robert M. Gower (Associate Professor, Telecom-Paristech)
Participants: Dr. Robert M. Gower (Maître de conférence/ Project leader), Télécom ParisTech, Nidham Gazagnadou (PhD student), Télécom ParisTech Martin Jaggi (Tenure-track assistant professor at EPFL)
Abstract: Large scale optimization problems in Machine Learning, most notably the empirical risk minimization problem, has put pressure on the optimization community to design new highly scalable and incremental methods. This pressure has led to the revival of a rather old method from the 1950's, the stochastic gradient descent (SGD) method. SGD and its variants are now widely used in training deep neural, support vector machines and more. Though highly scalable, for SGD to work well the user needs to determine a sequence of decreasing stepsizes for the method to converge. This project proposes the development of new stochastic variance reduced methods that can be applied to huge scale problems, such as deep nets, but are also grounded theoretically, thus give a solid foundation on which to advance the field.
- Generating Specialized Biased Experts for Electricity and Pollution Forecasting using Online Mixture
PGMO Call 2018.
Budget: 9 kE
Coordinator : Jairo Cugliari (Maître de Conférences, Université Lumière Lyon 2
Participants: Mathias Bourel (Profesor Adjunto), LPE, IESTA, Universidad de la Republica, Uruguay ; Jairo Cugliari (Assistant Professor), ERIC EA 3083, Université de Lyon, Lumière 2, Lyon ; Jean-Michel Poggi (Professor), LMO, Univ Paris Saclay, Univ Paris Descartes ; Yannig Goude, EDF R&D.
Abstract: Ensemble methods is a popular strategy for prediction task by letting the practitioner combine individual predictions of different experts. In time series where the combination has to be done in an online setting, aggregation of experts (base learners that are combined) has been shown to produce good forecasting performance and a lot of algorithms have been proposed. However, the literature on designing the experts is surprisingly small as one of the keys of this approach is to reduce the bias of the mixture forecast. Our propose in this project is to shed light on online mixture techniques by producing specialized biased experts. The project is focused on two practical applications : electricity load and air pollution forecast. A one day workshop will be organized around the topic of Online Forecasting.
- Spectral bounds for graph partitioning
PGMO Call 2018.
Budget : 4 kE
Coordinator : José Neto (Asssitant Professor, Samovar, Télécom SudParis
Participants : Miguel F. Anjos (Professor, NSERC-Hydro-Québec-Schneider Electric Industrial Research Chair), GERAD & Ecole Polytechnique de Montréal
Abstract: Let G = (V;E) be an undirected simple graph having node set V = {1, 2,… n}, edge set E, and let w denote a weight function on the edges. Let k denote a positive integer and m = (m1, m2, …, mk) denote a vector of k positive integers summing up to n. We consider the problem denoted by P_{k,m} which consists in determining a partition of V into k subsets S1, S2,…, Sk of sizes m1, m2,…, mk, respectively, so as to maximize the sum of the weights of the edges having both endpoints in the same subset of the partition. This is a well-known NP-hard problem with many applications. This project aims at developing new eigenvalue-based methods for computing bounds on the optimum of P_{k,m}. We shall investigate new formulas involving the spectrum of the weight matrix (given by the function w). They involve parameters that are difficult to compute. Semidefinite programming based approaches will be developed to evaluate the new bounds for large instances and compare them with other works from the literature.
- Extraction de descripteurs génériques synthétisant les informations contenues dans les courbes de consommation électrique d'un parc de bâtiments comparables à partir d'une analyse en composantes principales fonctionnelle
PGMO Call 2018.
Budget: 5 kE
Coordinator: François ROUEFF (Professor, Telecom ParisTech)
Participants: Alexandre GIRARD, Ingénieur-chercheur en Traitement du Signal et des Images, EDF R&D, Chatou ; Jean-Marc JICQUEL, Ingénieur-chercheur en Thermique du Bâtiment, EDF R&D, Les Renardières.
Abstract: One important goal for an electricity provider is to be able to give pertinent advises about the electric consumption management by the customer. The available data for this purpose are the electric load curves which have to be processed to extract the pertinent information. A lot of descriptors in the past have already been developed based on one given load curve. In the case of a set of comparable buildings, supplementary information can be extracted by using recent theoretical advances in sources unmixing for functional data to decline them to load curves. The objective precisely here is to extract parsimonious descriptors allowing for example to compare the thermal performances of the buildings in order to give indications to the customer on the priority renovations.
- Analysis of Evolutionary Algorithms : Beyond Expected Optimization Times
Appel PGMO 2018.
Budget : 7 kE
Coordinateur : Carola DOERR (chargée de recherché CNRS, Sorbonne Université)
Participant : Denis Antipov, PhD student, ITMO University, St. Petersburg, Russia and LIX, Ecole Polytechnique, France ; Thomas Back, Professor, Leiden University, The Netherlands ; Benjamin Doerr, Professor, LIX, Ecole Polytechnique, France ; Carola Doerr, CNRS researcher, LIP6, Sorbonne Université, France ; Timo Kotzing, Senior researcher, HPI Potsdam, Germany ; Johannes Lengler, Researcher, ETH Zurich, Switzerland; Pietro S. Oliveto, Senior Lecturer, University of She_eld, UK; Markus Wagner, Senior Lecturer, The University of Adelaide, Australia ; Carsten Witt, associate professor, Technical University of Denmark; Jing Yang, PhD student, LIX, Ecole Polytechnique, France ;
Abstract: Theory of evolutionary algorithms aims at contributing to a more efficient use of these general purpose optimization techniques through a better mathematical understanding of their underlying working principles. The predominant performance measure in this research area is the expected optimization time, which counts the average number of function evaluations that an evolutionary algorithm performs until it evaluates for the first time an optimal solution candidate. Expected optimization time is a very coarse measure, which reduces the whole optimization process to a single number, thus losing a lot of information that can be useful for the design of efficient problem solvers. We therefore suggest to establish more fine-grained performance indicators. More specifically, our project aims at a systematic analysis of fixed-target runtimes and distributional guarantees.
- Cloud dataset augmentation through texture synthesis
Funded through PGMO Call 2017.
Budget: 6 kE
Coordinator : Erwan Le Pennec (CMAP)
Participant : Michel Prenat (Thalès Optronique)
- Anomaly Detection based on Functional Physical Data for Predictive Maintenance of Aircraft Fleet
PGMO Call 2017.
Budget : 7 kE
Coordinator : Stephan Clémençon (LTCI)
Participants : Anne Sabourin (Telecom ParisTech), Florence D'Alché-Buc (Telecom ParisTech), Vincent Feuillard (Airbus)
Abstract: The research activity prolongates the baseline developed in [1], where a statistical method for identifying groups of components of a heavy-tailed multivariate r.v., which may take simultaneously very large values (assimilated as a certain type of anomaly). The latter relies on the concept of angular measure in multivariate extreme value theory, which characterizes the dependence structure of the components in the extremes. More precisely, we have exploit this approach further, by means of a mixture model that permits to describe the distribution of extremal observations and where the anomaly type is viewed as a latent variable. In particular, the model enables to assign to any such point X a posterior probability for each anomaly type, defining implicitly a similarity measure between anomalies. A procedure based on the EM algorithm has also been proposed here to infer the parameters of the mixture model from a (truncated) training dataset and the corresponding posterior similarity measure estimates permit to obtain an informative planar representation of anomalies using standard graph-mining tools. The relevance and usefulness of the 2-d visual display thus designed has been shown on real datasets, in the aeronautics application domain, provided by Airbus. The source code is open source, available on a Git repository. The first results obtained are presented by Chiapino, Clémençon, Sabourin & Feuillard (2018).
- Self-Adjusting Parameter Choices in Heuristic Optimization
PGMO Call 2017.
Budget: 7 kE
Coordinator: Carola Doerr (LIP6)
Coordinator for Paris-Saclay: Benjamin Doerr (LIX)
Participants: Timo Kötzing (HPI Potsdam), Johannes Lengler (ETH Zurich), Régis Makhmara (PhD student, LIX), Pietro S. Oliveto (University of She_eld), Carsten Witt (Technical University of Denmark), Jing Yang (PhD student, LIX)
Abstract: Heuristic Search is the predominant technique to solve large-scale optimization problems as well as problems that do not allow direct access to the underlying target function (e.g., due to privacy concerns). Many optimization heuristics are parametrized. Their performance often crucially depends on the quality of the specified parameter values. It is thus one of the key challenges in optimization research to identify parameter values that are particularly suitable for a given class of problems. It is today widely acknowledged that optimal parameter values change quite drastically during the optimization process; e.g., to allow for more exploration in the beginning, and a more focused search later on. The goal of our project is to use recent advances in the analysis of heuristic search to rigorously analyze and to design parameter update rules that are able to identify and to track best-possible parameter choices “on the go”.
- Le e-bison futé du véhicule électrique
PGMO Call 2017.
Budget : 7 kE
Coordinator : Dominique Quadri (LRI)
Participants : MARTIN Steven (LRI), HAYEL Yezekael et JIMENEZ Tania (LIA), BEAUDE Olivier et JEANDIN A. (EDF R&D)
- Efficacité énergétique en Planification de production : modèles algorithmiques et optimisation combinatoire
PGMO Call 2017.
Budget : 6 kE
Coordinator : Bernard Penz (Institut Polytechnique de Grenoble)
Coordinator pour Paris-Saclay : Céline Gicquel (LRI)
Participants : Ayse Akbalik (LGIPM, Université de Lorraine), Christophe Rapine (LGIPM, Université de Lorraine)
- Algorithms for Expensive Simulation-Based Optimization Problems
PGMO Call 2017.
Budget: 7 kE
Coordinator: Dimo Brocko_ (INRIA Saclay, CMAP)
Participants: Anne Auger (INRIA Saclay, CMAP), Nikolhaus Hansen (INRIA Saclay), David Gaudrie (doctorant, EMSE), Rodolphe Le Riche (EMSE), Victor Picheny (INRA Toulouse), Sébastien Da Veiga (Safran Tech), Tea Tusar (postdoc, Josef Stefan Institute, SL), Tobias Glasmachers (RU Bochum), Günter Rudolph (TU Dortmund)
Abstract: Numerical optimization problems occur frequently in all areas of a modern society. Solving them, often requires computationally expensive numerical simulations, e.g. when a simulation model has to be calibrated with real-world data. A fundamental difficulty when approaching (such expensive) problems is the choice of the appropriate optimization algorithm. To recommend the best and filter out the worst algorithms, one typically relies on numerical benchmarking. Tedious and time-consuming, numerical benchmarking is best done automatically with software frameworks such as the Comparing Continuous Optimizers platform (COCO, github.com/numbbo/coco/). The goal of the AESOP project is to bring together researchers with backgrounds in expensive optimization and benchmarking in order to benchmark existing and design new optimization algorithms for expensive simulation-based optimization with the help of the COCO platform.
- Optimisation et Comparaison Stochastique
PGMO Call 2017.
Budget: 6 kE
Coordinator: Jean-Michel Fourneau (lab. DAVID, UVSQ)
Participants: Nihal Pekergin (LACL, UPEC), Yann Strozecki (lab. DAVID, UVSQ), David Auger (lab. DAVID, UVSQ), Thierry Mautor (lab. DAVID, Univ. Cergy), Pierre Coucheney (lab. DAVID, UVSQ), Farah Ait Salaht (ENSAI & LIP6)
- On-line algorithms with random order
PGMO Call 2017.
Budget: 8 kE
Coordinator: Claire Mathieu (CNRS)
Coordinator for Paris-Saclay : Thang Nguyen (Université d'Évry, detached at CNRS)
Participants: Christoph Dürr (CNRS, UPMC), Chien-Chung Huang (CNRS, ENS), Abhinav Srivastav (postdoc, ENS and Paris-Dauphine).
Abstract: In the online model of computation, the input is not given all at once but is revealed gradually over time, in a sequential manner. The algorithm must maintain at all times a solution for the input seen so far, and its decisions are usually irrevocable. This setting can be interpreted as a game played between an on-line algorithm and an adversary generating the input sequence. Motivated by the observation that the input items often come from diverse uncoordinated and unsynchronized sources, the random order model assumes that the adversary chooses an arbitrary instance, but its elements are presented to the algorithm in uniform random order. Under this paradigm, we will study three categories of online problems that have recently been de_ned or have seen recent major progress : Bigtable compaction policies, truthful mechanisms for combinatorial auctions, and scheduling problems.
- BAndits with Structure and Sparsity
PGMO Call 2016.
Budget: 10 kE
Coordinator: Vianney Perchet (ENSAE)
Participants: Vianney Perchet (ENSAE), A. Bismuth (PhD student, ENSAE), R. Degenne (PhD student, ENSAE), Joon Kwon (Post-doc, CMAP, Polytechnique)
Abstract: The project "BAndits with Structure and Sparsity - BASS" has started in 2016 and focuses on studying online learning problem where some inherent structure on the rewards, feedbacks or actions set are considered to model more precisely real life problems. The first principal objective of that project is the theoretical study of these models, and the construction & analysis of algorithms.
- Parameter Optimization via Drift Analysis
PGMO Call 2016.
Budget : 10 kE
Coordinator : Carola Doerr (LIP6, Univ. Pierre et Marie Curie)
Participants : Benjamin Doerr, (Professor, LIX, Ecole Polytechnique), Carola Doerr (CNRS CR2 researcher, CNRS and LIP6, UPMC), Timo Kötzing (Senior researcher, HPI Potsdam, Germany), Johannes Lengler (Researcher, ETH Zurich, Switzerland), Jing Yang (PhD student, LIX, Ecole Polytechnique).
Abstract: One driving question in the study of randomized search heuristics (RSH, an important class of black-box optimization algorithms) is the investigation of optimal parameter settings such as the size of the memory, the right trade-off between exploration and exploitation, etc. Mathematical investigations shed light on which parameter settings are most suitable in di_erent optimization contexts and have inspired the design of new algorithms. Such analyses benefit from very precise estimates for the behavior of typical RSH. Due to the randomized nature of RSH such estimates are hard to obtain by classical methods. Recently developed drift theorems form the most important technique in today's theory of RSH. The goal of our project is to develop drift methods that are particularly suitable for the analysis of very precise estimates of the optimization times of RSH and for the analysis of RSH with dynamic parameters that change during the optimization process.
- From monotone operators to smoothed duality gap
PGMO Call 2016.
Budget: 10 kE
Coordinator : Olivier Fercoq (Assistant Professor, LTCI, Telecom ParisTech)
Participants: Pascal Bianchi (Professor, Télécom ParisTech), Volkan Cevher (Professor, EPFL, Switzerland), Quoc Tran-Dinh (Assistant professor, University of North Carolina).
Abstract: The monotone operators theory has been very successful in the design of optimization algorithms. However, this theory does not give a simple answer to the question of convergence speed and also, some very famous methods do not rely on monotone operators. The smoothed duality gap technique has been recently introduced in order to tackle these issues and has led to the development of a new primal-dual algorithm with a guaranteed convergence speed. Basing on this concept, we are going to give an alternative analysis of existing primal-dual methods in order to treat better the convergence speed, even in the case of functions with unbounded domains. This is important in order to give guarantees for problems with constraints that are split by Lagrangian duality. Then, we will introduce new methods, with a special focus on stochastic algorithms with constraint splitting.
- Stochastic Optimization for Planning Remanufacturing Activities in Reverse Supply Chains
PGMO Call 2016.
Budget: 7 kE
Coordinator: Céline Gicquel (LRI, Univ. Paris-Sud)
Participants: Céline Gicquel (LRI - UPSUD), Sa_a Kedad Sidhoum (LIP6 - UPMC), Dominique Quadri (LRI - UPSUD), Quan Dong Vu (stagiaire, 6 mois en 2016, LRI - UPSUD), Franco Quezada (intern, 5 months in 2017, LRI - UPSUD)
Abstract: One possible way of mitigating the environmental impact of industrial products in terms of waste generation and natural resource consumption is by remanufacturing them once they have reached their end of life. Remanufacturing consists in replacing components or reprocessing damaged parts from used products in order to bring them to a like-new condition. The present project deals with mathematical optimization problems linked with the mid-term and short term planning of remanufacturing activities in reverse supply chains. One of the main related challenges is the high level of uncertainty in the input data needed to make these planning decisions. This is mainly due to a lack of control by the company on the flows of used products brought back by customers at collection points. The main novelty of our proposal lies in the fact that we will seek to explicitly take into account in our models the uncertainties in the problem input data. We intend to achieve this by developing new stochastic programming based approaches. This should enable us to provide practitioners with the prototype of an efficient decision-aid tool to manage their remanufacturing activities as well as with some general useful insights on the uncertainty management in remanufacturing planning. One possible way of mitigating the environmental impact of industrial products in terms of waste generation and natural resource consumption is by remanufacturing them once they have reached their end of life. Remanufacturing consists in replacing components or reprocessing damaged parts from used products in order to bring them to a like-new condition. The present project deals with mathematical optimization problems linked with the mid-term and short term planning of remanufacturing activities. One of the main related challenges is the high level of uncertainty in the input data needed to make these planning decisions. Our main objective is to develop models and solution algorithms for planning remanufacturing activities under uncertainty.
- Méthodes tropicales pour l'analyse de performance de systèmes temporisés, application au dimensionnement d'un centre d'appel EDF
PGMO Call 2016.
Budget: 15 kE
Coordinator : Xavier Allamigeon (INRIA Saclay)
Participants: Xavier Allamigeon (Chargé de recherche, Ecole Polytechnique), Marianne Akian (Directrice de recherche, Ecole Polytechnique), Pascale Bendotti (Chercheuse, EDF R& D), Agnès Bialecki (Chercheuse, EDF R&D), Stéphane Gaubert (Directeur de recherche, Ecole Polytechnique), Ricardo D. Katz (Chercheur, CONICET, CIFASIS, Argentine), Vianney Boeuf (PhD student, Ecole Polytechnique), Mateusz Skomra (PhD student, Ecole Polytechnique), Master student intern, to be recruited.
Abstract: This project aims at analyzing and optimizing the performance of a commercial call center of EDF, by using and developing techniques coming from tropical geometry. The project consists of a part focused on the application to EDF call center, and a more theoretical part on the mathematical and algorithmic issues raised by this application in tropical real algebraic geometry.