Kernel Methods
Jun 11, 2019
Speakers
Alberto Bietti
Speaker · 0 followers
Alexander Ratner
Speaker · 1 follower
Arthur Gretton
Speaker · 8 followers
Bastian Rieck
Speaker · 4 followers
Chloe-Agathe Azencott
Speaker · 0 followers
Christopher De Sa
Speaker · 0 followers
Christian Bock
Speaker · 0 followers
Christopher Ré
Speaker · 5 followers
Clément Chatelain
Speaker · 0 followers
Dexiong Chen
Speaker · 1 follower
Dino Oglic
Speaker · 0 followers
Dino Sejdinovic
Speaker · 0 followers
Dougal Sutherland
Speaker · 2 followers
Fabio Ramos
Speaker · 0 followers
Grégoire Mialon
Speaker · 0 followers
Heiko Strathmann
Speaker · 0 followers
Jean-Francois Ton
Speaker · 0 followers
Jean-Philippe Vert
Speaker · 0 followers
Juho Rousu
Speaker · 0 followers
Julien Mairal
Speaker · 0 followers
Karsten Borgwardt
Speaker · 1 follower
Kelvin Hsu
Speaker · 0 followers
Kexin Rong
Speaker · 0 followers
Li Kevin Wenliang
Speaker · 0 followers
Lotfi Slim
Speaker · 0 followers
Moses Charikar
Speaker · 0 followers
Paris Siminelakis
Speaker · 0 followers
Peter Bailis
Speaker · 0 followers
Philip Levis
Speaker · 0 followers
Sahely Bhadra
Speaker · 0 followers
Thomas Gaertner
Speaker · 0 followers
Viivi Uurtio
Speaker · 0 followers
Virginia Smith
Speaker · 16 followers
About
Towards a Unified Analysis of Random Fourier Features Random Fourier features is a widely used, simple, and effective technique for scaling up kernel methods. The existing theoretical analysis of the approach, however, remains focused on specific learning tasks and typically gives pessimistic bounds which are at odds with the empirical results. We tackle these problems and provide the first unified risk analysis of learning with random Fourier features using the squared error and Lipschitz continuous loss functions. In our bounds, the trade-off between the computational cost and the expected risk convergence rate is problem specific and expressed in terms of the regularization parameter and the number of effective degrees of freedom. We study both the standard random Fourier features method for which we improve the existing bounds on the number of features required to guarantee the corresponding minimax risk convergence rate of kernel ridge regression, as well as a data-dependent modification which samples features proportional to ridge leverage scores and further reduces the required number of features. As ridge leverage scores are expensive to compute, we devise a simple approximation scheme which provably reduces the computational cost without loss of statistical efficiency. Learning deep kernels for exponential family densities The kernel exponential family is a rich class of distributions, which can be fit efficiently and with statistical guarantees by score matching. Being required to choose a priori a simple kernel such as the Gaussian, however, limits its practical applicability. We provide a scheme for learning a kernel parameterized by a deep network, which can find complex location-dependent local features of the data geometry. This gives a very rich class of density models, capable of fitting complex structures on moderate-dimensional problems. Compared to deep density models fit via maximum likelihood, our approach provides a complementary set of strengths and tradeoffs: in empirical studies, the former can yield higher likelihoods, whereas the latter gives better estimates of the gradient of the log density, the score, which describes the distribution's shape. Bayesian Deconditional Kernel Mean Embeddings Conditional kernel mean embeddings form an attractive nonparametric framework for representing conditional means of functions, describing the observation processes for many complex models. However, the recovery of the original underlying function of interest whose conditional mean was observed is a challenging inference task. We formalize deconditional kernel mean embeddings as a solution to this inverse problem, and show that it can be naturally viewed and used as a nonparametric Bayes' rule. Critically, we introduce the notion of task transformed Gaussian processes and establish deconditional kernel means embeddings as their posterior predictive mean. This connection provides Bayesian interpretations and uncertainty estimates for deconditional kernel means, explains its regularization hyperparameters, and provides a marginal likelihood for kernel hyperparameter learning. They further enable practical applications such as learning sparse representations for big data and likelihood-free inference. A Kernel Perspective for Regularizing Deep Neural Networks We propose a new point of view for regularizing deep neural networks by using the norm of a reproducing kernel Hilbert space (RKHS). Even though this norm cannot be computed, it admits upper and lower approximations leading to various practical strategies. Specifically, this perspective (i) provides a common umbrella for many existing regularization principles, including spectral norm and gradient penalties, or adversarial training, (ii) leads to new effective regularization penalties, and (iii) suggests hybrid strategies combining lower and upper bounds to get better approximations of the RKHS norm. We experimentally show this approach to be effective when learning on small datasets, or to obtain adversarially robust models. A Persistent Weisfeiler--Lehman Procedure for Graph Classification Inspired by the Weisfeiler--Lehman graph kernel, we augment its iterative feature map construction approach by a set of multi-scale topological features. More precisely, we leverage propagated node label information to transform an unweighted graph into a metric one. We then use persistent homology, a technique from topological data analysis, to assess the topological properties, i.e. connected components and cycles, of the metric graph. Through this process, each graph can be represented similarly to the original Weisfeiler--Lehman sub-tree feature map. We demonstrate the utility and improved accuracy of our method on numerous graph data sets while also discussing theoretical aspects of our approach. Rehashing Kernel Evaluation in High Dimensions Kernel methods are effective but do not scale well to large scale data: a larger training set improves accuracy but incurs a quadratic increase in overall evaluation time. This is especially true in high dimensions where the geometric data structures used to accelerate kernel evaluation suffer from the curse of dimensionality. Recent theoretical advances have proposed fast kernel evaluation algorithms leveraging hashing techniques with worst-case asymptotic improvements. However, these advances are largely confined to the theoretical realm due to concerns such as super-linear preprocessing time and diminishing gains in non-worst case datasets. In this paper, we close the gap between theory and practice by addressing these challenges via provable and practical procedures for adaptive sample size selection, preprocessing time reduction, and new refined data-dependent variance bounds that quantify the performance of random sampling and hashing-based kernel evaluation methods on a given dataset. Our experiments show that these new tools offer up to 10x improvement in evaluation time on a range of synthetic and real world datasets. Large-Scale Sparse Kernel Canonical Correlation Analysis This paper presents gradKCCA, a large-scale sparse non-linear canonical correlation method. Like Kernel Canonical Correlation Analysis (KCCA), our method finds non-linear correlations through kernel functions, but unlike KCCA, our method does not incorporate a kernel matrix, a known bottleneck for scaling up kernel methods. gradKCCA corresponds to solving KCCA with the additional constraint that the canonical projection directions in the kernel-induced feature space have pre-images in the original data space. Firstly, this modification allows us to very efficiently maximize kernel canonical correlation through an alternating projected gradient algorithm working in the original data space. Secondly, we can control the sparsity of the projection directions by constraining the ℓ1 norm of the pre-images of the projection directions, facilitating the interpretation of the discovered patterns, which is not available through KCCA. Our empirical experiments demonstrate that gradKCCA outperforms state-of-the-art CCA methods in terms of speed and robustness to noise both in simulated and real-world datasets. A Kernel Theory of Modern Data Augmentation Data augmentation, a technique in which a training set is expanded with class-preserving transformations, is ubiquitous in modern machine learning pipelines. In this paper, we seek to establish a theoretical framework for understanding data augmentation. We approach this from two directions: First, we provide a general model of augmentation as a Markov process, and show that kernels appear naturally with respect to this model, even when we do not employ kernel classification. Next, we analyze more directly the effect of augmentation on kernel classifiers, showing that data augmentation can be approximated by first-order feature averaging and second-order variance regularization components. These frameworks both serve to illustrate the ways in which data augmentation affects the downstream learning model, and the resulting analyses provide novel connections between prior work in invariant kernels, tangent propagation, and robust optimization. Finally, we provide several proof-of-concept applications showing that our theory can be useful for accelerating machine learning workflows, such as reducing the amount of computation needed to train using augmented data, and predicting the utility of a transformation prior to training. kernelPSI: a Post-Selection Inference Framework for Nonlinear Variable Selection Model selection is an essential task for many applications in scientific discovery. The most common approaches rely on univariate linear measures of association between each feature and the outcome. Such classical selection procedures fail to take into account nonlinear effects and interactions between features. Kernel-based selection procedures have been proposed as a solution. However, current strategies for kernel selection fail to measure the significance of a joint model constructed through the combination of the basis kernels. In the present work, we exploit recent advances in post-selection inference to propose a valid statistical test for the association of a joint model of the selected kernels with the outcome. The kernels are selected via a step-wise procedure which we model as a succession of quadratic constraints in the outcome variable. Scalable Learning in Reproducing Kernel Krein Spaces We provide the first mathematically complete derivation of the Nyström method for low-rank approximation of indefinite kernels and propose an efficient method for finding an approximate eigendecomposition of such kernel matrices. Building on this result, we devise highly scalable methods for learning in reproducing kernel Krein spaces. The devised approaches provide a principled and theoretically well-founded means to tackle large scale learning problems with indefinite kernels. The main motivation for our work comes from problems with structured representations (e.g., graphs, strings, time-series), where it is relatively easy to devise a pairwise (dis)similarity function based on intuition and/or knowledge of domain experts. Such functions are typically not positive definite and it is often well beyond the expertise of practitioners to verify this condition. The effectiveness of the devised approaches is evaluated empirically using indefinite kernels defined on structured and vectorial data representations.Towards a Unified Analysis of Random Fourier Features Random Fourier features is a widely used, simple, and effective technique for scaling up kernel methods. The existing theoretical analysis of the approach, however, remains focused on specific learning tasks and typically gives pessimistic bounds which are at odds with the empirical results. We tackle these problems and provide the first unified risk analysis of learning with random Fourier features using the squared error and Lipschitz cont…
Categories
AI & Data Science
Category · 10.8k presentations
About ICML 2019
The International Conference on Machine Learning (ICML) is the premier gathering of professionals dedicated to the advancement of the branch of artificial intelligence known as machine learning. ICML is globally renowned for presenting and publishing cutting-edge research on all aspects of machine learning used in closely related areas like artificial intelligence, statistics and data science, as well as important application areas such as machine vision, computational biology, speech recognition, and robotics. ICML is one of the fastest growing artificial intelligence conferences in the world. Participants at ICML span a wide range of backgrounds, from academic and industrial researchers, to entrepreneurs and engineers, to graduate students and postdocs.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
DNN Training and Inference with Hyper-Scaled Precision
Watch later
We Need No Pixels: Video Manipulation Detection Using Stream Descriptors
Watch later
Interpretability Contributed Talks
Watch later
Ali Pinar, …
Spotlights
Watch later
Imitation, Prediction, and Model-Based Reinforcement Learning for Autonomous Driving
Watch later
