Optimal transport in high dimension : obtaining regularity and robustness using convexity and projections.
Francois pierre PATY, Marco CUTURI, Guillaume LECUE, Marco CUTURI, Guillaume LECUE, Jerome MALICK, Francois xavier VIALARD, Giovanni CONFORTI, Laetitia CHAPEL, Umut SIMSEKLI, Jerome MALICK, Francois xavier VIALARD
2021
In recent years, optimal transport has gained popularity in machine learning as a way to compare probability measures. Unlike more traditional dissimilarities for probability distributions, such as Kullback-Leibler divergence, optimal transport distances (or Wasserstein distances) allow for the comparison of distributions with disjoint supports by taking into account the geometry of the underlying space. This advantage is however hampered by the fact that these distances are usually computed by solving a linear program, which poses, when the underlying space is high dimensional, well documented statistical challenges commonly referred to as the ``dimensional curse''. Beyond this purely metric aspect, another interest of optimal transport theory is that it provides mathematical tools to study maps that can transform, or transport, one measure into another. Such maps play an increasingly important role in various fields of science (biology, brain imaging) or subfields of machine learning (generative models, domain adaptation), among others. In this thesis, we propose a new estimation framework for computing variants of Wasserstein distances. The goal is to reduce the effects of high dimensionality by taking advantage of the low dimensional structures hidden in the distributions. This can be done by projecting the measures onto a subspace chosen to maximize the Wasserstein distance between their projections. In addition to this new methodology, we show that this framework is more broadly consistent with a link between regularization of Wasserstein distances and robustness.In the following contribution, we start from the same problem of estimating the optimal transport in high dimension, but adopt a different perspective: rather than modifying the cost function, we return to the more fundamental view of Monge and propose to use Brenier's theorem and Caffarelli's regularity theory to define a new procedure for estimating lipschitzian transport maps which are the gradient of a strongly convex function.
A MOM-based ensemble method for robustness, subsampling and hyperparameter tuning.
Joon KWON, Guillaume LECUE, Matthieu LERASLE
Electronic Journal of Statistics | 2021
No summary available.
M-estimation and Median of Means applied to statistical learning.
Timothee MATHIEU, Matthieu LERASLE, Guillaume LECUE, David DONOHO, Christophe BIERNACKI, Gilles BLANCHARD, Olivier CATONI, Elvezio m. RONCHETTI, Po ling LOH, David DONOHO, Christophe BIERNACKI
2021
The main objective of this thesis is to study robust statistical learning methods. Traditionally, in statistics we use models or simplifying assumptions that allow us to represent the real world and to analyze it properly. However, some deviations from the assumptions can strongly disturb the statistical analysis of a database. By robust statistics, we mean here methods that can handle both so-called abnormal data (sensor error, human error) and data of a highly variable nature. We apply this kind of technique to statistical learning, thus giving theoretical assurances of efficiency of the proposed methods as well as illustrations on simulated and real data.
Robust high dimensional learning for Lipschitz and convex losses.
Geoffrey CHINOT, Guillaume LECUE, Matthieu LERASLE
Journal of Machine Learning Research | 2021
We establish risk bounds for Regularized Empirical Risk Minimizers (RERM) when the loss is Lipschitz and convex and the regularization function is a norm. In a first part, we obtain these results in the i.i.d. setup under subgaussian assumptions on the design. In a second part, a more general framework where the design might have heavier tails and data may be corrupted by outliers both in the design and the response variables is considered. In this situation, RERM performs poorly in general. We analyse an alternative procedure based on median-of-means principles and called "minmax MOM". We show optimal subgaussian deviation rates for these estimators in the relaxed setting. The main results are meta-theorems allowing a wide-range of applications to various problems in learning theory. To show a non-exhaustive sample of these potential applications, it is applied to classification problems with logistic loss functions regularized by LASSO and SLOPE, to regression problems with Huber loss regularized by Group LASSO, Total Variation and Fused LASSO. Another advantage of the minmax MOM formulation is that it suggests a systematic way to slightly modify descent based algorithms used in high-dimensional statistics to make them robust to outliers. We illustrate this principle in a Simulations section where a "minmax MOM" version of classical proximal descent algorithms are turned into robust to outliers algorithms.
Correction to: Robust classification via MOM minimization.
Guillaume LECUE, Matthieu LERASLE, Timothee MATHIEU
Machine Learning | 2020
No summary available.
Localization methods with applications to robust learning and interpolation.
Geoffrey CHINOT, Guillaume LECUE, Matthieu LERASLE, Alexandre b. TSYBAKOV, Guillaume LECUE, Matthieu LERASLE, Alexandre b. TSYBAKOV, Gabor LUGOSI, Sara a. van de GEER, Yannick BARAUD, Alexandra CARPENTIER, Gabor LUGOSI, Sara a. van de GEER
2020
This PhD thesis is focused on supervised learning. The main objective is the use of localization methods to obtain fast convergence speeds, i.e., speeds of the order O(1/n), where n is the number of observations. These speeds are not always achievable. It is necessary to impose constraints on the variance of the problem such as a Bernstein or margin condition. In particular, in this thesis we try to establish fast convergence speeds for robustness and interpolation problems. An estimator is said to be robust if it presents certain theoretical guarantees, under the least possible assumptions. This robustness problem is becoming more and more popular. The main reason is that in the current era of "big data", data are very often corrupted. Thus, building reliable estimators in this situation is essential. In this thesis we show that the famous (regularized) empirical risk minimizer associated with a Lipschitz loss function is robust to heavy-tailed noise and outliers in the labels. However, if the class of predictors is heavy-tailed, this estimator is not reliable. In this case, we build estimators called minmax-MOM estimator, optimal when the data are heavy-tailed and possibly corrupted.In statistical learning, we say that an estimator interpolates, when it predicts perfectly on a training set. In high dimension, some estimators interpolating the data can be good. In particular, in this thesis we study the linear Gaussian model in high dimension and show that the estimator interpolating the smallest norm data is consistent and even reaches fast speeds.
A MOM-based ensemble method for robustness, subsampling and hyperparameter tuning.
Joon KWON, Matthieu LERASLE, Guillaume LECUE
2020
Hyperparameters tuning and model selection are important steps in machine learning. Unfortunately, classical hyperparameter calibration and model selection procedures are sensitive to outliers and heavy-tailed data. In this work, we construct a selection procedure which can be seen as a robust alternative to cross-validation and is based on a median-of-means principle. Using this procedure, we also build an ensemble method which, trained with algorithms and corrupted heavy-tailed data, selects an algorithm, trains it with a large uncorrupted subsample and automatically tune its hyperparameters. The construction relies on a divide-and-conquer methodology, making this method easily scalable for autoML given a corrupted database. This method is tested with the LASSO which is known to be highly sensitive to outliers.
Learning from MOM’s principles: Le Cam’s approach.
Guillaume LECUE, Matthieu LERASLE
Stochastic Processes and their Applications | 2019
We obtain estimation error rates for estimators obtained by aggregation of reg-ularized median-of-means tests, following a construction of Le Cam. The results hold with exponentially large probability, under only weak moments assumptions on data. Any norm may be used for regularization. When it has some sparsity inducing power we recover sparse rates of convergence. The procedure is robust since a large part of data may be corrupted, these outliers have nothing to do with the oracle we want to reconstruct. Our general risk bound is of order max minimax rate in the i.i.d. setup, number of outliers number of observations. In particular, the number of outliers may be as large as (number of data) ×(minimax rate) without affecting this rate. The other data do not have to be identically distributed but should only have equivalent L 1 and L 2 moments. For example, the minimax rate s log(ed/s)/N of recovery of a s-sparse vector in R d is achieved with exponentially large probability by a median-of-means version of the LASSO when the noise has q 0 moments for some q 0 > 2, the entries of the design matrix should have C 0 log(ed) moments and the dataset can be corrupted up to C 1 s log(ed/s) outliers.
MONK -- Outlier-Robust Mean Embedding Estimation by Median-of-Means.
Matthieu LERASLE, Zoltan SZABO, Timothee MATHIEU, Guillaume LECUE
International Conference on Machine Learning (ICML) | 2019
Mean embeddings provide an extremely flexible and powerful tool in machine learning and statistics to represent probability distributions and define a semi-metric (MMD, maximum mean discrepancy. also called N-distance or energy distance), with numerous successful applications. The representation is constructed as the expectation of the feature map defined by a kernel. As a mean, its classical empirical estimator, however, can be arbitrary severely affected even by a single outlier in case of unbounded features. To the best of our knowledge, unfortunately even the consistency of the existing few techniques trying to alleviate this serious sensitivity bottleneck is unknown. In this paper, we show how the recently emerged principle of median-of-means can be used to design estimators for kernel mean embedding and MMD with excessive resistance properties to outliers, and optimal sub-Gaussian deviation bounds under mild assumptions.
Contributions to high dimensional statistics.
Olga KLOPP, Patrice BERTAIL, Gerard BIAU, Stephane BOUCHERON, Marc HOFFMANN, Olivier GUEDON, Guillaume LECUE, Alexandre b. TSYBAKOV
2019
The purpose of this thesis is to give an account of my contributions to high dimensional statistics. The first part is devoted to the problem of matrix completion. After presenting the problem, I describe the main results obtained in the papers [Klo11, GK17, KLMS15, Klo15, KLT16, KT15, LKMS14]. The second part is devoted to the variable coefficients model . I present the main results of the non-asymptotic studies [KP13, KP15]. Finally, the third part presents the results of [KTV16] concerning the parsimonious network model and the graphon model.
Frequency hopping waveforms and Compressed Sensing: Application to airborne detection and reconnaissance.
Philippe MESNARD, Guillaume LECUE, Cyrille ENDERLI, Erwan LE PENNEC, Guillaume LECUE, Cyrille ENDERLI, Erwan LE PENNEC, Yohann de CASTRO, Jalal FADILI, Olga KLOPP, Yohann de CASTRO, Jalal FADILI
2019
Changes in the context of airborne radar processing imply more and more improvements that justify the search for an alternative to adaptive filtering, which is the process classically used to estimate the parameters of detected targets. Compressed Sensing opens the prospect of a new treatment, equally effective in multiple target configurations, with better tracking and recognition performance than the classical approach. We aim to apply this processing to so-called frequency hopping waveforms. The integral choice of the definition parameters of the transmitted signal completely determines the measurement matrix of the Compressed Sensing procedure, which solution provides all the desired information on the observed scene. For each frequency hopping signal, and of constant amplitude, the corresponding measurement matrix is obtained by extracting some rows from a particular extended Fourier matrix, the 2D Fourier matrix. The construction of the generation of the measurement matrix is important because the success of the reconstruction depends on the algebraic properties of this matrix.
Robust high dimensional learning for Lipschitz and convex losses.
Geoffrey CHINOT, Guillaume LECUE, Matthieu LERASLE
2019
We establish risk bounds for Regularized Empirical Risk Minimizers (RERM) when the loss is Lipschitz and convex and the regularization function is a norm. We obtain these results in the i.i.d. setup under subgaussian assumptions on the design. In a second part, a more general framework where the design might have heavier tails and data may be corrupted by outliers both in the design and the response variables is considered. In this situation, RERM performs poorly in general. We analyse an alternative procedure based on median-of-means principles and called "minmax MOM". We show optimal subgaussian deviation rates for these estimators in the relaxed setting. The main results are meta-theorems allowing a wide-range of applications to various problems in learning theory. To show a non-exhaustive sample of these potential applications, it is applied to classification problems with logistic loss functions regularized by LASSO and SLOPE, to regression problems with Huber loss regularized by Group LASSO, Total Variation and Fused LASSO and to matrix completion problems with quantile loss regularized by the nuclear norm. A short simulation study concludes the paper, illustrating in particular robustness properties of regularized minmax MOM procedures.
Robust statistical learning with Lipschitz and convex loss functions.
Geoffrey CHINOT, Guillaume LECUE, Matthieu LERASLE
Probability Theory and Related Fields | 2019
No summary available.
Robust machine learning by median-of-means : theory and practice.
Guillaume LECUE, Matthieu LERASLE
Annals of Statistics | 2019
We introduce new estimators for robust machine learning based on median-of-means (MOM) estimators of the mean of real valued random variables. These estimators achieve optimal rates of convergence under minimal assumptions on the dataset. The dataset may also have been corrupted by outliers on which no assumption is granted. We also analyze these new estimators with standard tools from robust statistics. In particular, we revisit the concept of breakdown point. We modify the original definition by studying the number of outliers that a dataset can contain without deteriorating the estimation properties of a given estimator. This new notion of breakdown number, that takes into account the statistical performances of the estimators, is non-asymptotic in nature and adapted for machine learning purposes. We proved that the breakdown number of our estimator is of the order of (number of observations)*(rate of convergence). For instance, the breakdown number of our estimators for the problem of estimation of a d-dimensional vector with a noise variance sigma^2 is sigma^2d and it becomes sigma^2 s log(d/s) when this vector has only s non-zero component. Beyond this breakdown point, we proved that the rate of convergence achieved by our estimator is (number of outliers) divided by (number of observation). Besides these theoretical guarantees, the major improvement brought by these new estimators is that they are easily computable in practice. In fact, basically any algorithm used to approximate the standard Empirical Risk Minimizer (or its regularized versions) has a robust version approximating our estimators. As a proof of concept, we study many algorithms for the classical LASSO estimator. A byproduct of the MOM algorithms is a measure of depth of data that can be used to detect outliers.
Robust Statistical learning with Lipschitz and convex loss functions.
Geoffrey CHINOT, Guillaume LECUE, Matthieu LERASLE
Probability Theory and Related Fields | 2019
We obtain risk bounds for Empirical Risk Minimizers (ERM) and minmax Median-Of-Means (MOM) estimators based on loss functions that are both Lipschitz and convex. Results for the ERM are derived without assumptions on the outputs and under subgaussian assumptions on the design and a new "local Bernstein assumption" on the class of predictors. Similar results are shown for minmax MOM estimators in a close setting where the design is only supposed to satisfy moment assumptions, relaxing the Subgaussian hypothesis necessary for ERM. The analysis of minmax MOM estimators is not based on the small ball assumption (SBA) as it was the case in the first analysis of minmax MOM estimators. In particular, the basic example of non parametric statistics where the learning class is the linear span of localized bases, that does not satisfy SBA can now be handled. Finally, minmax MOM estimators are analysed in a setting where the local Bernstein condition is also dropped out. It is shown to achieve an oracle inequality with exponentially large probability under minimal assumptions insuring the existence of all objects.
Linear regression and learning: contributions to regularization and aggregation methods.
Raphael DESWARTE, Guillaume LECUE, Gilles STOLTZ, Pierre ALQUIER, Guillaume LECUE, Gilles STOLTZ, Karim LOUNICI, Veronique GERVAIS, Tim VAN ERVEN, Olivier WINTENBERGER, Vincent RIVOIRARD
2018
This thesis deals with the subject of linear regression in different frameworks, notably related to learning. The first two chapters present the context of the work, its contributions and the mathematical tools used. The third chapter is devoted to the construction of an optimal regularization function, allowing for example to improve on the theoretical level the regularization of the LASSO estimator. The fourth chapter presents, in the field of convex sequential optimization, accelerations of a recent and promising algorithm, MetaGrad, and a conversion from a so-called "deterministic sequential" framework to a so-called "stochastic batch" framework for this algorithm. The fifth chapter focuses on successive interval forecasts, based on the aggregation of predictors, without intermediate feedback or stochastic modeling. Finally, the sixth chapter applies several aggregation methods to a petroleum dataset, resulting in short-term point forecasts and long-term forecast intervals.
On the Gap Between Restricted Isometry Properties and Sparse Recovery Conditions.
Sjoerd DIRKSEN, Guillaume LECUE, Holger RAUHUT
IEEE Transactions on Information Theory | 2018
No summary available.
Robust classification via MOM minimization.
Guillaume LECUE, Matthieu LERASLE, Timothee MATHIEU
2018
We present an extension of Vapnik's classical empirical risk minimizer (ERM) where the empirical risk is replaced by a median-of-means (MOM) estimator, the new estimators are called MOM minimizers. While ERM is sensitive to corruption of the dataset for many classical loss functions used in classification, we show that MOM minimizers behave well in theory, in the sense that it achieves Vapnik's (slow) rates of convergence under weak assumptions: data are only required to have a finite second moment and some outliers may also have corrupted the dataset. We propose an algorithm inspired by MOM minimizers. These algorithms can be analyzed using arguments quite similar to those used for Stochastic Block Gradient descent. As a proof of concept, we show how to modify a proof of consistency for a descent algorithm to prove consistency of its MOM version. As MOM algorithms perform a smart subsampling, our procedure can also help to reduce substantially time computations and memory ressources when applied to non linear algorithms. These empirical performances are illustrated on both simulated and real datasets.
Learning from MOM's principles : Le Cam's approach.
Guillaume LECUE, Matthieu LERASLE
2017
We obtain estimation error rates for estimators obtained by aggregation of reg-ularized median-of-means tests, following a construction of Le Cam. The results hold with exponentially large probability, under only weak moments assumptions on data. Any norm may be used for regularization. When it has some sparsity inducing power we recover sparse rates of convergence. The procedure is robust since a large part of data may be corrupted, these outliers have nothing to do with the oracle we want to reconstruct. Our general risk bound is of order max minimax rate in the i.i.d. setup, number of outliers number of observations. In particular, the number of outliers may be as large as (number of data) ×(minimax rate) without affecting this rate. The other data do not have to be identically distributed but should only have equivalent L 1 and L 2 moments. For example, the minimax rate s log(ed/s)/N of recovery of a s-sparse vector in R d is achieved with exponentially large probability by a median-of-means version of the LASSO when the noise has q 0 moments for some q 0 > 2, the entries of the design matrix should have C 0 log(ed) moments and the dataset can be corrupted up to C 1 s log(ed/s) outliers.
An IHT Algorithm for Sparse Recovery From Subexponential Measurements.
Simon FOUCART, Guillaume LECUE
IEEE Signal Processing Letters | 2017
No summary available.
Cross-validation and penalization for density estimation.
Nelo MAGALHAES, Lucien BIRGE, Pascal MASSART, Yannick BARAUD, Lucien BIRGE, Pascal MASSART, Yannick BARAUD, Vincent RIVOIRARD, Nicolas VAYATIS, Guillaume LECUE, Vincent RIVOIRARD, Nicolas VAYATIS
2015
This thesis is based on the estimation of a density, considered from a non-parametric and non-asymptotic point of view. It deals with the problem of the selection of a kernel estimation method. The latter is a generalization of, among others, the problem of model selection and window selection. We study classical procedures, by penalization and resampling (in particular V-fold cross-validation), which evaluate the quality of a method by estimating its risk. We propose, thanks to concentration inequalities, a method to optimally calibrate the penalty to select a linear estimator and prove oracle inequalities and adaptation properties for these procedures. Moreover, a new resampled procedure, based on the comparison between estimators by robust tests, is proposed as an alternative to procedures based on the principle of unbiased risk estimation. A second objective is the comparison of all these procedures from a theoretical point of view and the analysis of the role of the V-parameter for the V-fold penalties. We validate the theoretical results by simulation studies.
Minimax rate of convergence and the performance of empirical risk minimization in phase recovery.
Guillaume LECUE, Shahar MENDELSON
Electronic Journal of Probability | 2015
No summary available.
Interactions between compressed sensing random matrices and high dimensional geometry.
Djalil CHAFAI, Olivier GUEDON, Guillaume LECUE, Alain PAJOR
2013
No summary available.
Comment to “Generic chaining and the ℓ1-penalty” by Sara van de Geer.
Guillaume LECUE
Journal of Statistical Planning and Inference | 2013
No summary available.
The logarithmic Sobolev constant of the lamplighter.
Evgeny ABAKUMOV, Anne BEAULIEU, Francois BLANCHARD, Matthieu FRADELIZI, Nathael GOZLAN, Bernard HOST, Thiery JEANTHEAU, Magdalena KOBYLANSKI, Guillaume LECUE, Miguel MARTINEZ, Mathieu MEYER, Marie helene MOURGUES, Frederic PORTAL, Francis RIBAUD, Cyril ROBERTO, Pascal ROMON, Julien ROTH, Paul marie SAMSON, Pierre VANDEKERKHOVE, Abdellah YOUSSFI
Journal of Mathematical Analysis and Applications | 2013
We give estimates on the logarithmic Sobolev constant of some finite lamplighter graphs in terms of the spectral gap of the underlying base. Also, we give examples of application.
Interplay between concentration, complexity and geometry in learning theory with applications to high dimensional data analysis.
Guillaume LECUE
2011
In this document I present the works I undertook since the end of my Ph.D. I started my Ph.
Aggregation methods: optimality and fast speeds.
Guillaume LECUE, Alexandre b. TSYBAKOV
2007
No summary available.
Aggregation procedures: optimality and fast rates.
Guillaume LECUE
2007
In this thesis we deal with aggregation procedures under the margin assumption. We prove that the margin assumption improves the rate of aggregation. Another contribution of this thesis is to show that some empirical risk minimization procedures are suboptimal when the loss function is convex, even under the margin assumption. Contrarily to some aggregation procedures with exponential weights, these model selection methods cannot benefit from the large margin. Then, we apply aggregation methods to construct adaptive estimators in several different problems. The final contribution of this thesis is to purpose a new approach to the control of the bias term in classification by introducing some spaces of sparse prediction rules. Minimax rates of convergence have been obtained for these classes of functions and, by using an aggregation method, we provide an adaptive version of these estimators.
