@article{MueckeBlanchard2018, author = {M{\"u}cke, Nicole and Blanchard, Gilles}, title = {Parallelizing spectrally regularized kernel algorithms}, series = {Journal of machine learning research}, volume = {19}, journal = {Journal of machine learning research}, publisher = {Microtome Publishing}, address = {Cambridge, Mass.}, issn = {1532-4435}, pages = {29}, year = {2018}, abstract = {We consider a distributed learning approach in supervised learning for a large class of spectral regularization methods in an reproducing kernel Hilbert space (RKHS) framework. The data set of size n is partitioned into m = O (n(alpha)), alpha < 1/2, disjoint subsamples. On each subsample, some spectral regularization method (belonging to a large class, including in particular Kernel Ridge Regression, L-2-boosting and spectral cut-off) is applied. The regression function f is then estimated via simple averaging, leading to a substantial reduction in computation time. We show that minimax optimal rates of convergence are preserved if m grows sufficiently slowly (corresponding to an upper bound for alpha) as n -> infinity, depending on the smoothness assumptions on f and the intrinsic dimensionality. In spirit, the analysis relies on a classical bias/stochastic error analysis.}, language = {en} } @article{MiethKloftRodriguezetal.2016, author = {Mieth, Bettina and Kloft, Marius and Rodriguez, Juan Antonio and Sonnenburg, Soren and Vobruba, Robin and Morcillo-Suarez, Carlos and Farre, Xavier and Marigorta, Urko M. and Fehr, Ernst and Dickhaus, Thorsten and Blanchard, Gilles and Schunk, Daniel and Navarro, Arcadi and M{\"u}ller, Klaus-Robert}, title = {Combining Multiple Hypothesis Testing with Machine Learning Increases the Statistical Power of Genome-wide Association Studies}, series = {Scientific reports}, volume = {6}, journal = {Scientific reports}, publisher = {Nature Publ. Group}, address = {London}, issn = {2045-2322}, doi = {10.1038/srep36671}, pages = {14}, year = {2016}, abstract = {The standard approach to the analysis of genome-wide association studies (GWAS) is based on testing each position in the genome individually for statistical significance of its association with the phenotype under investigation. To improve the analysis of GWAS, we propose a combination of machine learning and statistical testing that takes correlation structures within the set of SNPs under investigation in a mathematically well-controlled manner into account. The novel two-step algorithm, COMBI, first trains a support vector machine to determine a subset of candidate SNPs and then performs hypothesis tests for these SNPs together with an adequate threshold correction. Applying COMBI to data from a WTCCC study (2007) and measuring performance as replication by independent GWAS published within the 2008-2015 period, we show that our method outperforms ordinary raw p-value thresholding as well as other state-of-the-art methods. COMBI presents higher power and precision than the examined alternatives while yielding fewer false (i.e. non-replicated) and more true (i.e. replicated) discoveries when its results are validated on later GWAS studies. More than 80\% of the discoveries made by COMBI upon WTCCC data have been validated by independent studies. Implementations of the COMBI method are available as a part of the GWASpi toolbox 2.0.}, language = {en} } @article{KloftBlanchard2012, author = {Kloft, Marius and Blanchard, Gilles}, title = {On the Convergence Rate of l(p)-Norm Multiple Kernel Learning}, series = {JOURNAL OF MACHINE LEARNING RESEARCH}, volume = {13}, journal = {JOURNAL OF MACHINE LEARNING RESEARCH}, publisher = {MICROTOME PUBL}, address = {BROOKLINE}, issn = {1532-4435}, pages = {2465 -- 2502}, year = {2012}, abstract = {We derive an upper bound on the local Rademacher complexity of l(p)-norm multiple kernel learning, which yields a tighter excess risk bound than global approaches. Previous local approaches analyzed the case p - 1 only while our analysis covers all cases 1 <= p <= infinity, assuming the different feature mappings corresponding to the different kernels to be uncorrelated. We also show a lower bound that shows that the bound is tight, and derive consequences regarding excess loss, namely fast convergence rates of the order O( n(-)1+alpha/alpha where alpha is the minimum eigenvalue decay rate of the individual kernels.}, language = {en} } @article{KawanabeBlanchardSugiyamaetal.2006, author = {Kawanabe, Motoaki and Blanchard, Gilles and Sugiyama, Masashi and Spokoiny, Vladimir G. and M{\"u}ller, Klaus-Robert}, title = {A novel dimension reduction procedure for searching non-Gaussian subspaces}, issn = {0302-9743}, doi = {10.1007/11679363_19}, year = {2006}, abstract = {In this article, we consider high-dimensional data which contains a low-dimensional non-Gaussian structure contaminated with Gaussian noise and propose a new linear method to identify the non-Gaussian subspace. Our method NGCA (Non-Gaussian Component Analysis) is based on a very general semi-parametric framework and has a theoretical guarantee that the estimation error of finding the non-Gaussian components tends to zero at a parametric rate. NGCA can be used not only as preprocessing for ICA, but also for extracting and visualizing more general structures like clusters. A numerical study demonstrates the usefulness of our method}, language = {en} } @article{KatzSamuelsBlanchardScott2019, author = {Katz-Samuels, Julian and Blanchard, Gilles and Scott, Clayton}, title = {Decontamination of Mutual Contamination Models}, series = {Journal of machine learning research}, volume = {20}, journal = {Journal of machine learning research}, publisher = {Microtome Publishing}, address = {Cambridge, Mass.}, issn = {1532-4435}, pages = {57}, year = {2019}, abstract = {Many machine learning problems can be characterized by mutual contamination models. In these problems, one observes several random samples from different convex combinations of a set of unknown base distributions and the goal is to infer these base distributions. This paper considers the general setting where the base distributions are defined on arbitrary probability spaces. We examine three popular machine learning problems that arise in this general setting: multiclass classification with label noise, demixing of mixed membership models, and classification with partial labels. In each case, we give sufficient conditions for identifiability and present algorithms for the infinite and finite sample settings, with associated performance guarantees.}, language = {en} } @article{BlanchardZadorozhnyi2019, author = {Blanchard, Gilles and Zadorozhnyi, Oleksandr}, title = {Concentration of weakly dependent Banach-valued sums and applications to statistical learning methods}, series = {Bernoulli : official journal of the Bernoulli Society for Mathematical Statistics and Probability}, volume = {25}, journal = {Bernoulli : official journal of the Bernoulli Society for Mathematical Statistics and Probability}, number = {4B}, publisher = {International Statistical Institute}, address = {Voorburg}, issn = {1350-7265}, doi = {10.3150/18-BEJ1095}, pages = {3421 -- 3458}, year = {2019}, abstract = {We obtain a Bernstein-type inequality for sums of Banach-valued random variables satisfying a weak dependence assumption of general type and under certain smoothness assumptions of the underlying Banach norm. We use this inequality in order to investigate in the asymptotical regime the error upper bounds for the broad family of spectral regularization methods for reproducing kernel decision rules, when trained on a sample coming from a tau-mixing process.}, language = {en} } @article{BlanchardMuecke2018, author = {Blanchard, Gilles and M{\"u}cke, Nicole}, title = {Optimal rates for regularization of statistical inverse learning problems}, series = {Foundations of Computational Mathematics}, volume = {18}, journal = {Foundations of Computational Mathematics}, number = {4}, publisher = {Springer}, address = {New York}, issn = {1615-3375}, doi = {10.1007/s10208-017-9359-7}, pages = {971 -- 1013}, year = {2018}, abstract = {We consider a statistical inverse learning (also called inverse regression) problem, where we observe the image of a function f through a linear operator A at i.i.d. random design points X-i , superposed with an additive noise. The distribution of the design points is unknown and can be very general. We analyze simultaneously the direct (estimation of Af) and the inverse (estimation of f) learning problems. In this general framework, we obtain strong and weak minimax optimal rates of convergence (as the number of observations n grows large) for a large class of spectral regularization methods over regularity classes defined through appropriate source conditions. This improves on or completes previous results obtained in related settings. The optimality of the obtained rates is shown not only in the exponent in n but also in the explicit dependency of the constant factor in the variance of the noise and the radius of the source condition set.}, language = {en} } @article{BlanchardMuecke2020, author = {Blanchard, Gilles and M{\"u}cke, Nicole}, title = {Kernel regression, minimax rates and effective dimensionality}, series = {Analysis and applications}, volume = {18}, journal = {Analysis and applications}, number = {4}, publisher = {World Scientific}, address = {New Jersey}, issn = {0219-5305}, doi = {10.1142/S0219530519500258}, pages = {683 -- 696}, year = {2020}, abstract = {We investigate if kernel regularization methods can achieve minimax convergence rates over a source condition regularity assumption for the target function. These questions have been considered in past literature, but only under specific assumptions about the decay, typically polynomial, of the spectrum of the the kernel mapping covariance operator. In the perspective of distribution-free results, we investigate this issue under much weaker assumption on the eigenvalue decay, allowing for more complex behavior that can reflect different structure of the data at different scales.}, language = {en} } @article{BlanchardMathe2012, author = {Blanchard, Gilles and Mathe, Peter}, title = {Discrepancy principle for statistical inverse problems with application to conjugate gradient iteration}, series = {Inverse problems : an international journal of inverse problems, inverse methods and computerised inversion of data}, volume = {28}, journal = {Inverse problems : an international journal of inverse problems, inverse methods and computerised inversion of data}, number = {11}, publisher = {IOP Publ. Ltd.}, address = {Bristol}, issn = {0266-5611}, doi = {10.1088/0266-5611/28/11/115011}, pages = {23}, year = {2012}, abstract = {The authors discuss the use of the discrepancy principle for statistical inverse problems, when the underlying operator is of trace class. Under this assumption the discrepancy principle is well defined, however a plain use of it may occasionally fail and it will yield sub-optimal rates. Therefore, a modification of the discrepancy is introduced, which corrects both of the above deficiencies. For a variety of linear regularization schemes as well as for conjugate gradient iteration it is shown to yield order optimal a priori error bounds under general smoothness assumptions. A posteriori error control is also possible, however at a sub-optimal rate, in general. This study uses and complements previous results for bounded deterministic noise.}, language = {en} } @article{BlanchardKraemer2016, author = {Blanchard, Gilles and Kraemer, Nicole}, title = {Convergence rates of Kernel Conjugate Gradient for random design regression}, series = {Analysis and applications}, volume = {14}, journal = {Analysis and applications}, publisher = {World Scientific}, address = {Singapore}, issn = {0219-5305}, doi = {10.1142/S0219530516400017}, pages = {763 -- 794}, year = {2016}, abstract = {We prove statistical rates of convergence for kernel-based least squares regression from i.i.d. data using a conjugate gradient (CG) algorithm, where regularization against over-fitting is obtained by early stopping. This method is related to Kernel Partial Least Squares, a regression method that combines supervised dimensionality reduction with least squares projection. Following the setting introduced in earlier related literature, we study so-called "fast convergence rates" depending on the regularity of the target regression function (measured by a source condition in terms of the kernel integral operator) and on the effective dimensionality of the data mapped into the kernel space. We obtain upper bounds, essentially matching known minimax lower bounds, for the L-2 (prediction) norm as well as for the stronger Hilbert norm, if the true regression function belongs to the reproducing kernel Hilbert space. If the latter assumption is not fulfilled, we obtain similar convergence rates for appropriate norms, provided additional unlabeled data are available.}, language = {en} }