Meeting 18/02/15

Date : 18/02/2015
Lieu : Orange Labs

Introduction : A. Ouorou, P. Bianchi

Marc Boullé (Orange Labs) Automatic Feature Construction for Supervised Classification
Abstract. We suggest an approach to automate variable construction for supervised learning, especially in the multi-relational setting. Domain knowledge is specified by describing the structure of data by the means of variables, tables and links across tables, and choosing construction rules. The space of variables that can be constructed is virtually infinite, which raises both combinatorial and over-fitting problems. We introduce a prior distribution over all the constructed variables, as well as an effective algorithm to draw samples of constructed variables from this distribution. Experiments show that the approach is robust and efficient.

Olivier Fercoq (Telecom ParisTech) Descente par coordonnée primale-duale
Abstract. Nous étudions la méthode de descente par coordonnée pour les problèmes de point selle du type max min f(x)+g(x)-h*(y)+ où f, g, h sont des fonctions convexes, f est différentiable, g et h ont des opérateurs proximaux simples et K est une matrice. Bianchi, Hachem et Iutzeler ont introduit un algorithme de descente par coordonnée pour ce problème et ont prouvé sa convergence. Néanmoins, ils n’ont pas donné
de vitesse de convergence. Nous proposons ici une variante de leur algorithme pour laquelle nous avons prouvé que le saut de dualité du Lagrangien décroît à une vitesse de l’ordre de 1/k.

Raphaël Féraud, Tanguy Urvoy (Orange Labs). Online optimization of decisions
Abstract. The online optimization of decisions is based on maximization of rewards. It is used by the major players of Internet (Google, Yahoo…) in various applications. This optimization technique explores various policies in order to maximize online observed rewards. This is a generalization of A/B testing techniques, which multiplies the number of tested policies, for instance marketing campaigns, messages, contact channels…

Joseph Salmon (Telecom ParisTech) Mind the (duality) gap: safer rules for the Lasso
Abstract. Recently, screening variables has been considered to speed up optimization algorithms solving a Lasso problem or its derivatives. We propose new versions of the so called safe rules for the Lasso. Based on duality gap considerations, our new rules create safe test regions whose diameters converge to zero for any solver outputting a converging sequence toward a Lasso solution. This helps screening out more variables for a wider range of tuning parameters. In addition to faster convergence to a solution, we prove that we correctly identify active sets (supports) in finite time. Though our framework can encompass any solver, we have implemented our strategies on a popular coordinate descent version. We achieved noticeable computing time reduction with respect to former safe rules. This is a joint work with O. Fercoq and A. Gramfort.