Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning
Kernel-based models such as kernel ridge regression and Gaussian processes are ubiquitous in machine learning applications for regression and optimization. It is well known that a major downside for kernel-based models is the high computational cost; given a dataset of $n$ samples, the cost grows as $\mathcal{O}(n^3)$. Existing sparse approximation methods can yield a significant reduction in the computational cost, effectively reducing the actual cost down to as low as $\mathcal{O}(n)$ in certain cases. Despite this remarkable empirical success, significant gaps remain in the existing results for the analytical bounds on the error due to approximation. In this work, we provide novel confidence intervals for the Nystr\"om method and the sparse variational Gaussian process approximation method, which we establish using novel interpretations of the approximate (surrogate) posterior variance of the models. Our confidence intervals lead to improved performance bounds in both regression and optimization problems.
Code (0)
등록된 구현이 없습니다.
Tasks
Gaussian ProcessesregressionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
First-Order Sparse Convex Optimization: Better Rates with Sparse Updates
In was recently established that for convex optimization problems with a sparse optimal solution (may it be entry-wise sparsity or matrix rank-wise sparsity) it is possible to have linear convergence rates which depend o…
Spike and slab variational Bayes for high dimensional logistic regression
Variational Bayes (VB) is a popular scalable alternative to Markov chain Monte Carlo for Bayesian inference. We study a mean-field spike and slab VB approximation of widely used Bayesian model selection priors in sparse …
Bayesian InferenceModel SelectionregressionVocal Bursts Intensity PredictionSparse Perturbations for Improved Convergence in Stochastic Zeroth-Order Optimization
Interest in stochastic zeroth-order (SZO) methods has recently been revived in black-box optimization scenarios such as adversarial black-box attacks to deep neural networks. SZO methods only require the ability to evalu…
Practical Inexact Proximal Quasi-Newton Method with Global Complexity Analysis
Recently several methods were proposed for sparse optimization which make careful use of second-order information [10, 28, 16, 3] to improve local convergence rates. These methods construct a composite quadratic approxim…
A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
Recent years have witnessed exciting progress in the study of stochastic variance reduced gradient methods (e.g., SVRG, SAGA), their accelerated variants (e.g, Katyusha) and their extensions in many different settings (e…