ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions

• URL: http://arxiv.org/abs/2106.12231v1
• Date: Wed, 23 Jun 2021 08:24:36 GMT
• Title: ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions
• Authors: Luigi Carratino, Stefano Vigogna, Daniele Calandriello, Lorenzo Rosasco
• Abstract summary: We introduce ParK, a new large-scale solver for kernel ridge regression. Our approach combines partitioning with random projections and iterative optimization to reduce space and time complexity.
• Score: 34.576469570537995
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce ParK, a new large-scale solver for kernel ridge regression. Our approach combines partitioning with random projections and iterative optimization to reduce space and time complexity while provably maintaining the same statistical accuracy. In particular, constructing suitable partitions directly in the feature space rather than in the input space, we promote orthogonality between the local estimators, thus ensuring that key quantities such as local effective dimension and bias remain under control. We characterize the statistical-computational tradeoff of our model, and demonstrate the effectiveness of our method by numerical experiments on large-scale datasets.

Related papers

• Advancing Bayesian Optimization via Learning Correlated Latent Space [15.783344085533187]
  We propose Correlated latent space Bayesian Optimization (CoBO), which focuses on learning correlated latent spaces. Specifically, our method introduces Lipschitz regularization, loss weighting, and trust region recoordination to minimize the inherent gap around the promising areas. We demonstrate the effectiveness of our approach on several optimization tasks in discrete data, such as molecule design and arithmetic expression fitting.
  arXiv  Detail & Related papers  (2023-10-31T08:24:41Z)
• Improved Distribution Matching for Dataset Condensation [91.55972945798531]
  We propose a novel dataset condensation method based on distribution matching. Our simple yet effective method outperforms most previous optimization-oriented methods with much fewer computational resources.
  arXiv  Detail & Related papers  (2023-07-19T04:07:33Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  Noise-contrastive estimation(NCE) has been proposed by formulating the objective as the logistic loss of the real data and the artificial noise. In this paper, we study it a direct approach for optimizing the negative log-likelihood of unnormalized models.
  arXiv  Detail & Related papers  (2023-06-13T01:18:16Z)
• Structured Optimal Variational Inference for Dynamic Latent Space Models [16.531262817315696]
  We consider a latent space model for dynamic networks, where our objective is to estimate the pairwise inner products plus the intercept of the latent positions. To balance posterior inference and computational scalability, we consider a structured mean-field variational inference framework.
  arXiv  Detail & Related papers  (2022-09-29T22:10:42Z)
• Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds [54.51566432934556]
  We consider distributed optimization methods for problems where forming the Hessian is computationally challenging. We leverage randomized sketches for reducing the problem dimensions as well as preserving privacy and improving straggler resilience in asynchronous distributed systems.
  arXiv  Detail & Related papers  (2022-03-18T05:49:13Z)
• Spatio-Temporal Variational Gaussian Processes [26.60276485130467]
  We introduce a scalable approach to Gaussian process inference that combinestemporal-temporal filtering with natural variational inference. We derive a sparse approximation that constructs a state-space model over a reduced set of inducing points. We show that for separable Markov kernels the full sparse cases recover exactly the standard variational GP.
  arXiv  Detail & Related papers  (2021-11-02T16:53:31Z)
• A local approach to parameter space reduction for regression and classification tasks [0.0]
  We propose a new method called local active subspaces (LAS), which explores the synergies of active subspaces with supervised clustering techniques. LAS is particularly useful for the community working on surrogate modelling.
  arXiv  Detail & Related papers  (2021-07-22T18:06:04Z)
• Featurized Density Ratio Estimation [82.40706152910292]
  In our work, we propose to leverage an invertible generative model to map the two distributions into a common feature space prior to estimation. This featurization brings the densities closer together in latent space, sidestepping pathological scenarios where the learned density ratios in input space can be arbitrarily inaccurate. At the same time, the invertibility of our feature map guarantees that the ratios computed in feature space are equivalent to those in input space.
  arXiv  Detail & Related papers  (2021-07-05T18:30:26Z)
• Real-Time Regression with Dividing Local Gaussian Processes [62.01822866877782]
  Local Gaussian processes are a novel, computationally efficient modeling approach based on Gaussian process regression. Due to an iterative, data-driven division of the input space, they achieve a sublinear computational complexity in the total number of training points in practice. A numerical evaluation on real-world data sets shows their advantages over other state-of-the-art methods in terms of accuracy as well as prediction and update speed.
  arXiv  Detail & Related papers  (2020-06-16T18:43:31Z)
• Spatially Adaptive Inference with Stochastic Feature Sampling and Interpolation [72.40827239394565]
  We propose to compute features only at sparsely sampled locations. We then densely reconstruct the feature map with an efficient procedure. The presented network is experimentally shown to save substantial computation while maintaining accuracy over a variety of computer vision tasks.
  arXiv  Detail & Related papers  (2020-03-19T15:36:31Z)
• Prediction with Spatio-temporal Point Processes with Self Organizing Decision Trees [0.0]
  We introduce a novel approach to this problem. Our approach is based on the Hawkes process, which is a non-stationary and self-exciting process. We provide experimental results on real-life data.
  arXiv  Detail & Related papers  (2020-03-07T20:39:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.