Testing properties of distributions in the streaming model
- URL: http://arxiv.org/abs/2309.03245v1
- Date: Wed, 6 Sep 2023 10:53:29 GMT
- Title: Testing properties of distributions in the streaming model
- Authors: Sampriti Roy, Yadu Vasudev
- Abstract summary: We study distribution testing in the standard access model and the conditional access model.
The goal is to test the properties of distribution using an optimal number of samples subject to a memory constraint.
- Score: 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We study distribution testing in the standard access model and the
conditional access model when the memory available to the testing algorithm is
bounded. In both scenarios, the samples appear in an online fashion and the
goal is to test the properties of distribution using an optimal number of
samples subject to a memory constraint on how many samples can be stored at a
given time. First, we provide a trade-off between the sample complexity and the
space complexity for testing identity when the samples are drawn according to
the conditional access oracle. We then show that we can learn a succinct
representation of a monotone distribution efficiently with a memory constraint
on the number of samples that are stored that is almost optimal. We also show
that the algorithm for monotone distributions can be extended to a larger class
of decomposable distributions.
Related papers
- Controllable Generation via Locally Constrained Resampling [77.48624621592523]
We propose a tractable probabilistic approach that performs Bayesian conditioning to draw samples subject to a constraint.
Our approach considers the entire sequence, leading to a more globally optimal constrained generation than current greedy methods.
We show that our approach is able to steer the model's outputs away from toxic generations, outperforming similar approaches to detoxification.
arXiv Detail & Related papers (2024-10-17T00:49:53Z) - DOTA: Distributional Test-Time Adaptation of Vision-Language Models [52.98590762456236]
Training-free test-time dynamic adapter (TDA) is a promising approach to address this issue.
We propose a simple yet effective method for DistributiOnal Test-time Adaptation (Dota)
Dota continually estimates the distributions of test samples, allowing the model to continually adapt to the deployment environment.
arXiv Detail & Related papers (2024-09-28T15:03:28Z) - No free lunch theorems for quantum state measurements as resources in
classical sampling and generative modelling [0.29008108937701327]
We prove that $textitalmost all$ quantum states, when sampled according to the Haar measure over the unitary group, have the following property.
If copies of the state are measured to provide latent random variables, then any alternative state whose measurements can generate the same set of target distributions will do so with the same overall cost.
arXiv Detail & Related papers (2023-09-25T09:05:16Z) - StyleGenes: Discrete and Efficient Latent Distributions for GANs [149.0290830305808]
We propose a discrete latent distribution for Generative Adversarial Networks (GANs)
Instead of drawing latent vectors from a continuous prior, we sample from a finite set of learnable latents.
We take inspiration from the encoding of information in biological organisms.
arXiv Detail & Related papers (2023-04-30T23:28:46Z) - Arithmetic Sampling: Parallel Diverse Decoding for Large Language Models [65.52639709094963]
Methods such as beam search and Gumbel top-k sampling can guarantee a different output for each element of the beam, but are not easy to parallelize.
We present a framework for sampling according to an arithmetic code book implicitly defined by a large language model.
arXiv Detail & Related papers (2022-10-18T22:19:41Z) - Diverse Human Motion Prediction via Gumbel-Softmax Sampling from an
Auxiliary Space [34.83587750498361]
Diverse human motion prediction aims at predicting multiple possible future pose sequences from a sequence of observed poses.
Previous approaches usually employ deep generative networks to model the conditional distribution of data, and then randomly sample outcomes from the distribution.
We propose a novel sampling strategy for sampling very diverse results from an imbalanced multimodal distribution.
arXiv Detail & Related papers (2022-07-15T09:03:57Z) - Sampling from Arbitrary Functions via PSD Models [55.41644538483948]
We take a two-step approach by first modeling the probability distribution and then sampling from that model.
We show that these models can approximate a large class of densities concisely using few evaluations, and present a simple algorithm to effectively sample from these models.
arXiv Detail & Related papers (2021-10-20T12:25:22Z) - iNNformant: Boundary Samples as Telltale Watermarks [68.8204255655161]
We show that it is possible to generate sets of boundary samples which can identify any of four tested microarchitectures.
These sets can be built to not contain any sample with a worse peak signal-to-noise ratio than 70dB.
arXiv Detail & Related papers (2021-06-14T11:18:32Z) - IQDet: Instance-wise Quality Distribution Sampling for Object Detection [25.31113751275204]
We propose a dense object detector with an instance-wise sampling strategy, named IQDet.
Our best model achieves 51.6 AP, outperforming all existing state-of-the-art one-stage detectors and it is completely cost-free in inference time.
arXiv Detail & Related papers (2021-04-14T15:57:22Z) - VC Dimension and Distribution-Free Sample-Based Testing [0.8830479021890576]
We consider the problem of determining which classes of functions can be tested more efficiently than they can be learned.
We show that two natural classes of functions, juntas and monotone functions, can be tested with a number of samples that isly smaller than the number of samples required for PAC learning.
arXiv Detail & Related papers (2020-12-07T18:50:46Z) - Mask-guided sample selection for Semi-Supervised Instance Segmentation [13.091166009687058]
We propose a sample selection approach to decide which samples to annotate for semi-supervised instance segmentation.
Our method consists in first predicting pseudo-masks for the unlabeled pool of samples, together with a score predicting the quality of the mask.
We study which samples are better to annotate given the quality score, and show how our approach outperforms a random selection.
arXiv Detail & Related papers (2020-08-25T14:44:58Z)
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.