Determinantal point processes based on orthogonal polynomials for sampling minibatches in SGD

• URL: http://arxiv.org/abs/2112.06007v1
• Date: Sat, 11 Dec 2021 15:09:19 GMT
• Title: Determinantal point processes based on orthogonal polynomials for sampling minibatches in SGD
• Authors: Remi Bardenet, Subhro Ghosh, Meixia Lin
• Abstract summary: gradient descent (SGD) is a cornerstone of machine learning. default minibatch construction involves uniformly sampling a subset of the desired size. We show how specific DPPs and a string of controlled approximations can lead to gradient estimators with a variance that decays faster with the batchsize than under uniform sampling.
• Score: 0.0
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Stochastic gradient descent (SGD) is a cornerstone of machine learning. When the number N of data items is large, SGD relies on constructing an unbiased estimator of the gradient of the empirical risk using a small subset of the original dataset, called a minibatch. Default minibatch construction involves uniformly sampling a subset of the desired size, but alternatives have been explored for variance reduction. In particular, experimental evidence suggests drawing minibatches from determinantal point processes (DPPs), distributions over minibatches that favour diversity among selected items. However, like in recent work on DPPs for coresets, providing a systematic and principled understanding of how and why DPPs help has been difficult. In this work, we contribute an orthogonal polynomial-based DPP paradigm for minibatch sampling in SGD. Our approach leverages the specific data distribution at hand, which endows it with greater sensitivity and power over existing data-agnostic methods. We substantiate our method via a detailed theoretical analysis of its convergence properties, interweaving between the discrete data set and the underlying continuous domain. In particular, we show how specific DPPs and a string of controlled approximations can lead to gradient estimators with a variance that decays faster with the batchsize than under uniform sampling. Coupled with existing finite-time guarantees for SGD on convex objectives, this entails that, DPP minibatches lead to a smaller bound on the mean square approximation error than uniform minibatches. Moreover, our estimators are amenable to a recent algorithm that directly samples linear statistics of DPPs (i.e., the gradient estimator) without sampling the underlying DPP (i.e., the minibatch), thereby reducing computational overhead. We provide detailed synthetic as well as real data experiments to substantiate our theoretical claims.

Related papers

• A Bayesian Approach to Data Point Selection [24.98069363998565]
  Data point selection (DPS) is becoming a critical topic in deep learning. Existing approaches to DPS are predominantly based on a bi-level optimisation (BLO) formulation. We propose a novel Bayesian approach to DPS.
  arXiv  Detail & Related papers  (2024-11-06T09:04:13Z)
• Not All Samples Should Be Utilized Equally: Towards Understanding and Improving Dataset Distillation [57.6797306341115]
  We take an initial step towards understanding various matching-based DD methods from the perspective of sample difficulty. We then extend the neural scaling laws of data pruning to DD to theoretically explain these matching-based methods. We introduce the Sample Difficulty Correction (SDC) approach, designed to predominantly generate easier samples to achieve higher dataset quality.
  arXiv  Detail & Related papers  (2024-08-22T15:20:32Z)
• On Calibrating Diffusion Probabilistic Models [78.75538484265292]
  diffusion probabilistic models (DPMs) have achieved promising results in diverse generative tasks. We propose a simple way for calibrating an arbitrary pretrained DPM, with which the score matching loss can be reduced and the lower bounds of model likelihood can be increased. Our calibration method is performed only once and the resulting models can be used repeatedly for sampling.
  arXiv  Detail & Related papers  (2023-02-21T14:14:40Z)
• Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
  We introduce data structures for solving robust regression through gradient descent (SGD) Our algorithm effectively runs $T$ steps of SGD with importance sampling while using sublinear space and just making a single pass over the data.
  arXiv  Detail & Related papers  (2022-07-16T03:09:30Z)
• A Langevin-like Sampler for Discrete Distributions [15.260564469562542]
  discrete Langevin proposal (DLP) is a simple and scalable gradient-based proposal for sampling complex high-dimensional discrete distributions. DLP is able to update all coordinates in parallel in a single step and the magnitude of changes is controlled by a stepsize. We develop several variants of sampling algorithms, including unadjusted, adjusted, and preconditioned versions.
  arXiv  Detail & Related papers  (2022-06-20T17:36:03Z)
• Gaussian Process Inference Using Mini-batch Stochastic Gradient Descent: Convergence Guarantees and Empirical Benefits [21.353189917487512]
  gradient descent (SGD) and its variants have established themselves as the go-to algorithms for machine learning problems. We take a step forward by proving minibatch SGD converges to a critical point of the full log-likelihood loss function. Our theoretical guarantees hold provided that the kernel functions exhibit exponential or eigendecay.
  arXiv  Detail & Related papers  (2021-11-19T22:28:47Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  We study shuffling-based variants: minibatch and local Random Reshuffling, which draw gradients without replacement. For smooth functions satisfying the Polyak-Lojasiewicz condition, we obtain convergence bounds which show that these shuffling-based variants converge faster than their with-replacement counterparts. We propose an algorithmic modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-homogeneous settings.
  arXiv  Detail & Related papers  (2021-10-20T02:25:25Z)
• Nonparametric estimation of continuous DPPs with kernel methods [0.0]
  Parametric and nonparametric inference methods have been proposed in the finite case, i.e. when the point patterns live in a finite ground set. We show that a restricted version of this maximum likelihood (MLE) problem falls within the scope of a recent representer theorem for nonnegative functions in an RKHS. We propose, analyze, and demonstrate a fixed point algorithm to solve this finite-dimensional problem.
  arXiv  Detail & Related papers  (2021-06-27T11:57:14Z)
• Attentional-Biased Stochastic Gradient Descent [74.49926199036481]
  We present a provable method (named ABSGD) for addressing the data imbalance or label noise problem in deep learning. Our method is a simple modification to momentum SGD where we assign an individual importance weight to each sample in the mini-batch. ABSGD is flexible enough to combine with other robust losses without any additional cost.
  arXiv  Detail & Related papers  (2020-12-13T03:41:52Z)
• Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient [62.24615324523435]
  This paper provides a statistical analysis of high-dimensional batch Reinforcement Learning (RL) using sparse linear function approximation. When there is a large number of candidate features, our result sheds light on the fact that sparsity-aware methods can make batch RL more sample efficient.
  arXiv  Detail & Related papers  (2020-11-08T16:48:02Z)
• Learning from DPPs via Sampling: Beyond HKPV and symmetry [2.0305676256390934]
  We show how to approximate the distribution function of a linear statistic of a Determinantal point processes (DPP) Our approach is scalable and applies to very general DPPs, beyond traditional symmetric kernels.
  arXiv  Detail & Related papers  (2020-07-08T17:33:45Z)

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.