Machine learning pipelines often rely on optimization procedures to make discrete decisions (e.g. sorting, picking closest neighbors, finding shortest paths or optimal matchings). Although these discrete decisions are easily computed in a forward manner, they cannot be used to modify model parameters using first-order optimization techniques because they break the back-propagation of computational graphs. In order to expand the scope of learning problems that can be solved in an end-to-end fashion, we propose a systematic method to transform a block that outputs an optimal discrete decision into a differentiable operation. Our approach relies on stochastic perturbations of these parameters, and can be used readily within existing solvers without the need for ad hoc regularization or smoothing. These perturbed optimizers yield solutions that are differentiable and never locally constant. The amount of smoothness can be tuned via the chosen noise amplitude, whose impact we analyze. The derivatives of these perturbed solvers can be evaluated eciently. We also show how this framework can be connected to a family of losses developed in structured prediction, and describe how these can be used in unsupervised and supervised learning, with theoretical guarantees.
We demonstrate the performance of our approach on several machine learning tasks in experiments on synthetic and real data.[-]

La génération aléatoire est un outil de choix pour étudier les structures combinatoires et notamment leurs propriétés asymptotiques. Bien qu'il soit parfois possible de concevoir des générateurs ad hoc efficaces pour certaines classes d'objets combinatoires, nous nous intéresserons plutôt aux méthodes de générations dites 'automatiques' : la méthode récursive et la méthode de Boltzmann en particulier. Dans les deux cas, il est possible de traduire directement les spécifications combinatoires issues de la méthode symbolique de Flajolet et Sedgewick en algorithmes de génération aléatoire uniforme (tous les objets de même taille ont la même probabilité d'être tirés). Ces deux techniques s'appuient fortement sur l'utilisation des séries génératrices afin de garantir l'uniformité des tirages. Dans le cas de la méthode récursive, on exploitera les coefficients des séries formelles alors que la méthode de Boltzmann s'appuie sur l'évaluation numérique de ces mêmes séries. Durant la séance d'exercices vous pourrez programmer vos propres générateurs suivant l'une ou l'autre de ces méthodes.[-]

Approximation methods and probabilistic algorithms are two important ways to obtain efficient algorithms giving approximate solutions to hard problems. We give some examples from optimization, counting and verification problems. Property testing is also a very efficient method to approximate verification problems.
complexity - difficult problem - approximation - probabilistic approximation schemes - optimization - counting
verification - property testing[-]

Many of us use smartphones and rely on tools like auto-complete and spelling auto-correct to make using these devices more pleasant, but building these tools presents a challenge. On the one hand, the machine-learning algorithms used to provide these features require data to learn from, but on the other hand, who among us is willing to send a carbon copy of all our text messages to device manufacturers to provide that data? 'Local differential privacy' and related concepts have emerged as the gold standard model in which to analyze tradeoffs between losses in utility and privacy for solutions to such problems. In this talk, we give a new state-of-the-art algorithm for estimating histograms of user data, making use of projective geometry over finite fields coupled with a reconstruction algorithm based on dynamic programming.
This talk is based on joint work with Vitaly Feldman (Apple), Huy Le Nguyen (Northeastern), and Kunal Talwar (Apple).[-]

La génération aléatoire est un outil de choix pour étudier les structures combinatoires et notamment leurs propriétés asymptotiques. Bien qu'il soit parfois possible de concevoir des générateurs ad hoc efficaces pour certaines classes d'objets combinatoires, nous nous intéresserons plutôt aux méthodes de générations dites 'automatiques' : la méthode récursive et la méthode de Boltzmann en particulier. Dans les deux cas, il est possible de traduire directement les spécifications combinatoires issues de la méthode symbolique de Flajolet et Sedgewick en algorithmes de génération aléatoire uniforme (tous les objets de même taille ont la même probabilité d'être tirés). Ces deux techniques s'appuient fortement sur l'utilisation des séries génératrices afin de garantir l'uniformité des tirages. Dans le cas de la méthode récursive, on exploitera les coefficients des séries formelles alors que la méthode de Boltzmann s'appuie sur l'évaluation numérique de ces mêmes séries. Durant la séance d'exercices vous pourrez programmer vos propres générateurs suivant l'une ou l'autre de ces méthodes.[-]