PEYRE Gabriel

Optimal Transport (OT) defines geometrically meaningful "Wasserstein" distances, used in machine learning applications to compare probability distributions. However, a key bottleneck is the design of a "ground" cost which should be adapted to the task under study. In most cases, supervised metric learning is not accessible, and one usually resorts to some ad-hoc approach. Unsupervised metric learning is thus a fundamental problem to enable data-driven applications of Optimal Transport. In this paper, we propose for the first time a canonical answer by computing the ground cost as a positive eigenvector of the function mapping a cost to the pairwise OT distances between the inputs. This map is homogeneous and monotone, thus framing unsupervised metric learning as a non-linear Perron-Frobenius problem. We provide criteria to ensure the existence and uniqueness of this eigenvector. In addition, we introduce a scalable computational method using entropic regularization, which-in the large regularization limit-operates a principal component analysis dimensionality reduction. We showcase this method on synthetic examples and datasets. Finally, we apply it in the context of biology to the analysis of a high-throughput single-cell RNA sequencing (scRNAseq) dataset, to improve cell clustering and infer the relationships between genes in an unsupervised way.

No summary available.

No summary available.

Optimization problems arise naturally during the training of supervised learning models. A typical example is the empirical risk minimization (ERM) problem, which aims at finding an estimator by minimizing the risk on a set of data. The main challenge is to design efficient optimization algorithms that can handle a large amount of data in high dimensional spaces. In this context, classical optimization methods, such as the gradient descent algorithm and its accelerated variant, are computationally expensive because they require going through all the data at each gradient evaluation. This shortcoming motivates the development of the class of incremental algorithms that perform updates with incremental gradients. These algorithms reduce the computational cost per iteration, resulting in a significant improvement in computational time compared to classical methods. A natural question arises: would it be possible to further accelerate these incremental methods? In Chapter 2, we develop a proximal variant of the Finito/MISO algorithm, which is an incremental method initially designed for smooth and strongly convex problems. We introduce a proximal step in the update of the algorithm to take into account the regularization penalty which is potentially non-smooth. In Chapter 3, we introduce a generic acceleration scheme, called Catalyst, which applies to a large class of optimization methods, in the context of convex optimizations. The generic feature of our scheme allows the user to select their preferred method best suited to the problems. We show that by applying Catalyst, we obtain an accelerated convergence rate. More importantly, this rate coincides with the optimal rate of incremental methods at a near logarithmic factor in worst-case analysis. Thus, our approach is not only generic but also nearly optimal from the theoretical point of view. We then show that the acceleration is well represented in practice, especially for ill-conditioned problems.In Chapter 4, we present a second generic approach that applies Quasi-Newton principles to accelerate first-order methods, calledQNing. The scheme applies to the same class of methods as Catalyst. Moreover, it admits a simple interpretation as a combination of the L-BFGS algorithm and the Moreau-Yosida regularization. To our knowledge, QNing is the first Quasi-Newton algorithm compatible with composite objectives and finite sum structure. We conclude this thesis by proposing an extension of the Catalyst algorithm to the non-convex case. This is a collaborative work with Dr. Courtney Paquette and Prof. Dmitriy Drusvyatskiy, from the University of Washington, and my thesis supervisors. The strength of this approach lies in its ability to automatically adapt to the convexity. Indeed, no information on the convexity of the function is necessary before launching the algorithm. When the objective is convex, the proposed approach presents the same convergence rates as the convex Catalyst algorithm, resulting in a speed-up. When the objective is non-convex, the algorithm converges to the stationary points with the best convergence rate for first order methods. Promising experimental results are observed by applying our method to recimonious matrix factorization problems and to the training of neural network models.

Mallat's book is the undisputed reference in this field - it is the only one that covers the essential material in such breadth and depth. - Laurent Demanet, Stanford UniversityThe new edition of this classic book gives all the major concepts, techniques and applications of sparse representation, reflecting the key role the subject plays in today's signal processing. The book clearly presents the standard representations with Fourier, wavelet and time-frequency transforms, and the construction of orthogonal bases with fast algorithms. The central concept of sparsity is explained and applied to signal compression, noise reduction, and inverse problems, while coverage is given to sparse representations in redundant dictionaries, super-resolution and compressive sensing applications.Features:• Balances presentation of the mathematics with applications to signal processing• Algorithms and numerical examples are implemented in WaveLab, a MATLAB toolboxNew in this edition• Sparse signal representations in dictionaries• Compressive sensing, super-resolution and source separation• Geometric image processing with curvelets and bandlets• Wavelets for computer graphics with lifting on surfaces• Time-frequency audio processing and denoising• Image compression with JPEG-2000• New and updated exercisesA Wavelet Tour of Signal Processing: The Sparse Way, Third Edition, is an invaluable resource for researchers and R&D engineers wishing to apply the theory in fields such as image processing, video processing and compression, bio-sensing, medical imaging, machine vision and communications engineering.Stephane Mallat is Professor in Applied Mathematics at École Polytechnique, Paris, France. From 1986 to 1996 he was a Professor at the Courant Institute of Mathematical Sciences at New York University, and between 2001 and 2007, he co-founded and became CEO of an image processing semiconductor company.Includes all the latest developments since the book was published in 1999, including itsapplication to JPEG 2000 and MPEG-4Algorithms and numerical examples are implemented in Wavelab, a MATLAB toolboxBalances presentation of the mathematics with applications to signal processing.

This paper studies least-square regression penalized with partly smooth convex regularizers. This class of penalty functions is very large and versatile, and allows to promote solutions conforming to some notion of low-complexity. Indeed, such penalties/regularizers force the corresponding solutions to belong to a low-dimensional manifold (the so-called model) which remains stable when the penalty function undergoes small perturbations. Such a good sensitivity property is crucial to make the underlying low-complexity (manifold) model robust to small noise. In a deterministic setting, we show that a generalized "irrepresentable condition" implies stable model selection under small noise perturbations in the observations and the design matrix, when the regularization parameter is tuned proportionally to the noise level. We also prove that this condition is almost necessary for stable model recovery.We then turn to the random setting where the design matrix and the noise are random, and the number of observations grows large. We show that under our generalized "irrepresentable condition", and a proper scaling of the regularization parameter, the regularized estimator is model consistent. In plain words, with a probability tending to one as the number of measurements tends to infinity, the regularized estimator belongs to the correct low-dimensional model manifold.This work unifies and generalizes a large body of literature, where model consistency was known to hold, for instance for the Lasso, group Lasso, total variation (fused Lasso) and nuclear/trace norm regularizers.We show that under the deterministic model selection conditions, the forward-backward proximal splitting algorithm used to solve the penalized least-square regression problem, is guaranteed to identifiy the model manifold after a finite number of iterations. Lastly, we detail how our results extend from the quadratic loss to an arbitrary smooth and strictly convex loss function. We illustrate the usefulness of our results on the problem of low-rank matrix recovery from random measurements using nuclear norm minimization.

We propose a sparse representation of 2D planar shape through the composi- tion of warping functions, termed formlets, localized in scale and space. Each formlet subjects the 2D space in which the shape is embedded to a localized isotropic radial deformation. By constraining these localized warping transfor- mations to be diffeomorphisms, the topology of shape is preserved, and the set of simple closed curves is closed under any sequence of these warpings. A gener- ative model based on a composition of formlets applied to an embryonic shape, e.g., an ellipse, has the advantage of synthesizing only those shapes that could correspond to the boundaries of physical objects. To compute the set of formlets that represent a given boundary, we demonstrate a greedy coarse-to-fine formlet pursuit algorithm that serves as a non-commutative generalization of matching pursuit for sparse approximations. We evaluate our method by pursuing par- tially occluded shapes, comparing performance against a contour-based sparse shape coding framework.