Learning Entangled Single-Sample Distributions via Iterative Trimming

• URL: http://arxiv.org/abs/2004.09563v2
• Date: Tue, 7 Jul 2020 16:04:55 GMT
• Title: Learning Entangled Single-Sample Distributions via Iterative Trimming
• Authors: Hui Yuan, Yingyu Liang
• Abstract summary: We analyze a simple and computationally efficient method based on iteratively trimming samples and re-estimating the parameter on the trimmed sample set. We show that the method in logarithmic iterations outputs an estimation whose error only depends on the noise level of the $lceil alpha n rceil$-th noisiest data point.
• Score: 28.839136703139225
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the setting of entangled single-sample distributions, the goal is to estimate some common parameter shared by a family of distributions, given one \emph{single} sample from each distribution. We study mean estimation and linear regression under general conditions, and analyze a simple and computationally efficient method based on iteratively trimming samples and re-estimating the parameter on the trimmed sample set. We show that the method in logarithmic iterations outputs an estimation whose error only depends on the noise level of the $\lceil \alpha n \rceil$-th noisiest data point where $\alpha$ is a constant and $n$ is the sample size. This means it can tolerate a constant fraction of high-noise points. These are the first such results for the method under our general conditions. It also justifies the wide application and empirical success of iterative trimming in practice. Our theoretical results are complemented by experiments on synthetic data.

Related papers

• Efficiently learning and sampling multimodal distributions with data-based initialization [20.575122468674536]
  We consider the problem of sampling a multimodal distribution with a Markov chain given a small number of samples from the stationary measure. We show that if the Markov chain has a $k$th order spectral gap, samples from the stationary distribution will efficiently generate a sample whose conditional law is $varepsilon$-close in TV distance to the stationary measure.
  arXiv  Detail & Related papers  (2024-11-14T01:37:02Z)
• Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplers [49.97755400231656]
  We present the first performance guarantee with explicit dimensional general score-mismatched diffusion samplers. We show that score mismatches result in an distributional bias between the target and sampling distributions, proportional to the accumulated mismatch between the target and training distributions. This result can be directly applied to zero-shot conditional samplers for any conditional model, irrespective of measurement noise.
  arXiv  Detail & Related papers  (2024-10-17T16:42:12Z)
• Improved Active Learning via Dependent Leverage Score Sampling [8.400581768343804]
  We show how to obtain improved active learning methods in the agnostic (adversarial noise) setting. We propose an easily implemented method based on the emphpivotal sampling algorithm In comparison to independent sampling, our method reduces the number of samples needed to reach a given target accuracy by up to $50%$.
  arXiv  Detail & Related papers  (2023-10-08T01:51:30Z)
• On counterfactual inference with unobserved confounding [36.18241676876348]
  Given an observational study with $n$ independent but heterogeneous units, our goal is to learn the counterfactual distribution for each unit. We introduce a convex objective that pools all $n$ samples to jointly learn all $n$ parameter vectors. We derive sufficient conditions for compactly supported distributions to satisfy the logarithmic Sobolev inequality.
  arXiv  Detail & Related papers  (2022-11-14T04:14:37Z)
• SIMPLE: A Gradient Estimator for $k$-Subset Sampling [42.38652558807518]
  In this work, we fall back to discrete $k$-subset sampling on the forward pass. We show that our gradient estimator, SIMPLE, exhibits lower bias and variance compared to state-of-the-art estimators. Empirical results show improved performance on learning to explain and sparse linear regression.
  arXiv  Detail & Related papers  (2022-10-04T22:33:16Z)
• Bias Mimicking: A Simple Sampling Approach for Bias Mitigation [57.17709477668213]
  We introduce a new class-conditioned sampling method: Bias Mimicking. Bias Mimicking improves underrepresented groups' accuracy of sampling methods by 3% over four benchmarks.
  arXiv  Detail & Related papers  (2022-09-30T17:33:00Z)
• Convergence for score-based generative modeling with polynomial complexity [9.953088581242845]
  We prove the first convergence guarantees for the core mechanic behind Score-based generative modeling. Compared to previous works, we do not incur error that grows exponentially in time or that suffers from a curse of dimensionality. We show that a predictor-corrector gives better convergence than using either portion alone.
  arXiv  Detail & Related papers  (2022-06-13T14:57:35Z)
• Unrolling Particles: Unsupervised Learning of Sampling Distributions [102.72972137287728]
  Particle filtering is used to compute good nonlinear estimates of complex systems. We show in simulations that the resulting particle filter yields good estimates in a wide range of scenarios.
  arXiv  Detail & Related papers  (2021-10-06T16:58:34Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  We consider the task of heavy-tailed statistical estimation given streaming $p$ samples. We design a clipped gradient descent and provide an improved analysis under a more nuanced condition on the noise of gradients.
  arXiv  Detail & Related papers  (2021-08-25T21:30:27Z)
• Jo-SRC: A Contrastive Approach for Combating Noisy Labels [58.867237220886885]
  We propose a noise-robust approach named Jo-SRC (Joint Sample Selection and Model Regularization based on Consistency) Specifically, we train the network in a contrastive learning manner. Predictions from two different views of each sample are used to estimate its "likelihood" of being clean or out-of-distribution.
  arXiv  Detail & Related papers  (2021-03-24T07:26:07Z)
• Pathwise Conditioning of Gaussian Processes [72.61885354624604]
  Conventional approaches for simulating Gaussian process posteriors view samples as draws from marginal distributions of process values at finite sets of input locations. This distribution-centric characterization leads to generative strategies that scale cubically in the size of the desired random vector. We show how this pathwise interpretation of conditioning gives rise to a general family of approximations that lend themselves to efficiently sampling Gaussian process posteriors.
  arXiv  Detail & Related papers  (2020-11-08T17:09:37Z)

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.