Abstract: Differentially private (DP) stochastic convex optimization (SCO) is a fundamental problem, where the goal is to approximately minimize the population risk with respect to a convex loss function, given a dataset of i.i.d. samples from a distribution, while satisfying differential privacy with respect to the dataset. Most of the existing works in the literature of private convex optimization focus on the Euclidean (i.e., $\ell_2$) setting, where the loss is assumed to be Lipschitz (and possibly smooth) w.r.t.~the $\ell_2$ norm over a constraint set with bounded $\ell_2$ diameter. Algorithms based on noisy stochastic gradient descent (SGD) are known to attain the optimal excess risk in this setting.
In this talk I will provide a brief overview of differential privacy and its applications in stochastic convex optimization, together with new upper and lower bounds on the population risk for DP-SCO in non-Euclidean setups, in particular where the reference norm is the $\ell_p$-norm, $1\leq p\leq \infty$. Our algorithms include DP versions of variance-reduced stochastic Frank-Wolfe and mirror-descent methods, together with a novel privacy mechanism, which generalizes the Gaussian mechanism. Our work draws upon concepts from the geometry of normed spaces, such as the notions of regularity, uniform convexity, and uniform smoothness.
Based on joint work with Raef Bassily and Anupama Nandi, and available at arXiv:2103.01278
Yohann de Castro
Abstract: Lifting problems in much bigger spaces may lead to a simplified and useful representation. This trick has been used, for instance, in Monge-Kantorovich formulation of Optimal Transport. We will use the same trick for sparse regularization of mixture models (MM). We will show that MM recovery can be lifted on the space of measures addressing two fundamental limits: the problem becomes convex and the knowledge of number of mixture components is not required.
Abstract:
Alexandre d’Aspremont
Michaël Fanuel
Christophe Biernacki
Wilfried Heyse
Florent Dewez
Abstract: Trajectory optimisation is a wide field of academic and industrial study with numerous applications in real-world problems. Optimal control methods are commonly used to compute the trajectory minimising the criterion while complying with certain constraints. This family of physical-based methods requires the knowledge of the underlying dynamics of the system to provide realistic solutions. Nevertheless the dynamics are often (partially) unknown in the applications, requiring estimation strategies which could be a challenging task. Further the solution may be affected by the statistical errors. In this talk, we will present a dynamics-free methodology for optimised and realistic trajectories. It leverages information in available trajectory data to derive constrained optimisation problems via a maximum a posteriori approach. These problems, which involve regularised objective functions, are constrained in a natural and simple way by the data: the search space is automatically restricted to a region centered on the data and contained in a metric space reflecting estimated features. The solutions inherit then realistic patterns from the observed trajectories. We will also present two applications, including an industrial problem from the aeronautics, whose results are actually very promising.This a joint work with Benjamin Guedj, Vincent Vandewalle and Arthur Talpaert.
Stephane Chretien
Ernesto Araya Valdivia
Abstract: In the model of Random Geometric Graphs (RGG), each vertex of a graph is associated to a latent point on a metric space and the probability of an edge between two vertices depends on the distance between the associated latent points. Placing ourselves in the context of dense graphs and taking the Euclidean unit sphere as the ambient (latent) space, we consider the following estimation problem: assume that a graph is generated by the RGG model, but we only have access to the adjacency matrix, our objective is to recover the distances between the latent points. We propose a spectral estimator for the matrix of latent distances, which is consistent provided that a spectral gap-type assumption holds. Moreover, we give its rate of convergence for the mean squared error and propose an efficient algorithm to compute it. We discuss extensions to the case when the sphere is replaced by the unit ball.
The talk is based on a joint work with Yohann de Castro.
Benjamin Guedj
Abstract: PAC-Bayes is a generic and flexible framework to address generalisation abilities of machine learning algorithms. It leverages the power of Bayesian inference and allows to derive new learning strategies. I will briefly present the key concepts of PAC-Bayes and illustrate a few of its recent successes for deep neural networks and for coherent risk measures.
- Letarte, Germain, Guedj and Laviolette, NeurIPS 2019 https://papers.nips.cc/paper/8911-dichotomize-and-generalize-pac-bayesian-binary-activated-deep-neural-networks.pdf
- Mhammedi, Guedj and Williamson, NeurIPS 2020 https://arxiv.org/abs/2006.14763
