Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 10,000 papers for “Sample complexity”

Sample Complexity

Claude Sammut, Geoffrey I. Webb · Encyclopedia of Machine Learning · 2010

Cited by 0

Computational Sample Complexity

Scott E. Decatur, Oded Goldreich, Dana Ron · SIAM Journal on Computing · 2000

In a variety of PAC learning models, a trade-off between time and information seems to exist: with unlimited time, a small amount of information suffices, but with time restrictions, more information sometimes seems to be required. In addition, it has long been known that there are concept classes that can be learned in the absence of computational restrictions, but (under standard cryptographic assumptions) cannot be learned in polynomial time (regardless of sample size). Yet, these results do not answer the question of whether there are classes for which learning from a small set of examples is computationally infeasible, but becomes feasible when the learner has access to (polynomially) more examples. To address this question, we introduce a new measure of learning complexity called computational sample complexity that represents the number of examples sufficient for polynomial time learning with respect to a fixed distribution. We then show concept classes that (under similar cryptographic assumptions) possess arbitrarily sized gaps between their standard (information-theoretic) sample complexity and their computational sample complexity. We also demonstrate such gaps for learning from membership queries and learning from noisy examples.

Cited by 30

Sample Complexity of Classification

John Langford, Ibm Research · 2008

We discuss basic sample complexity theory and it's impact on classification success evaluation, implications for learning algorithm design, and uses in learning algorithm execution. There are a two important implications of the results presented here: (1) Common practices for reporting results in classification should change to us the test set bound. (2) Train set bounds can sometimes be used to directly motivate learning algorithms.

Cited by 0

Sample Complexity versus Approximation Error

Peter L. Bartlett, Robert C. Williamson · 2007

We consider the problem of learning an unknown real-valued function from a sequence of values of the function at randomly chosen points when the estimates are constrained to some class of functions called the hypothesis class. Ideally, thehypothesis class should be able to approximate a wide variety of target functions, yet not need an excessive number of examples to ensure that a learning algorithm can choose a near-optimal approximation to the target function. We show that these two objectives are incompatible, in the sense that as the approximation error of the hypothesis class decreases, a lower bound on the sample complexity must increase. The approximation error is the largest distance between an element of the class of candidate target functions and its best approximation in the hypothesis class. The sample complexity isthenumber of examples necessary for a nearoptimal estimate of any target function. The relationship between approximation error and sample complexity depends on a combinatorial dimension of the class of candidate target functions which are to be approximated. We give an example of this relationship for the

Cited by 0

Sample Complexity of Forecast Aggregation

Tao Lin, Yi‐Ling Chen · arXiv (Cornell University) · 2022

We consider a Bayesian forecast aggregation model where $n$ experts, after observing private signals about an unknown binary event, report their posterior beliefs about the event to a principal, who then aggregates the reports into a single prediction for the event. The signals of the experts and the outcome of the event follow a joint distribution that is unknown to the principal, but the principal has access to i.i.d. "samples" from the distribution, where each sample is a tuple of the experts' reports (not signals) and the realization of the event. Using these samples, the principal aims to find an $\varepsilon$-approximately optimal aggregator, where optimality is measured in terms of the expected squared distance between the aggregated prediction and the realization of the event. We show that the sample complexity of this problem is at least $\tilde Ω(m^{n-2} / \varepsilon)$ for arbitrary discrete distributions, where $m$ is the size of each expert's signal space. This sample complexity grows exponentially in the number of experts $n$. But, if the experts' signals are independent conditioned on the realization of the event, then the sample complexity is significantly reduced, to $\tilde O(1 / \varepsilon^2)$, which does not depend on $n$. Our results can be generalized to non-binary events. The proof of our results uses a reduction from the distribution learning problem and reveals the fact that forecast aggregation is almost as difficult as distribution learning.

Cited by 1Open access

Token Sample Complexity of Attention

Léa Bohbot, Cyril Letrouit, Gabriel Peyré et al. · ArXiv.org · 2025

As context windows in large language models continue to expand, it is essential to characterize how attention behaves at extreme sequence lengths. We introduce token-sample complexity: the rate at which attention computed on $n$ tokens converges to its infinite-token limit. We estimate finite-$n$ convergence bounds at two levels: pointwise uniform convergence of the attention map, and convergence of moments for the transformed token distribution. For compactly supported (and more generally sub-Gaussian) distributions, our first result shows that the attention map converges uniformly on a ball of radius $R$ at rate $C(R)/\sqrt{n}$, where $C(R)$ grows exponentially with $R$. For large $R$, this estimate loses practical value, and our second result addresses this issue by establishing convergence rates for the moments of the transformed distribution (the token output of the attention layer). In this case, the rate is $C'(R)/n^β$ with $β<\tfrac{1}{2}$, and $C'(R)$ depends polynomially on the size of the support of the distribution. The exponent $β$ depends on the attention geometry and the spectral properties of the tokens distribution. We also examine the regime in which the attention parameter tends to infinity and the softmax approaches a hardmax, and in this setting, we establish a logarithmic rate of convergence. Experiments on synthetic Gaussian data and real BERT models on Wikipedia text confirm our predictions.

Cited by 0Open access

Low Sample Complexity Participatory Budgeting

Mohak Goyal, Sukolsak Sakshuwong, Sahasrajit Sarmasarkar et al. · arXiv (Cornell University) · 2023

We study low sample complexity mechanisms in participatory budgeting (PB), where each voter votes for a preferred allocation of funds to various projects, subject to project costs and total spending constraints. We analyse the distortion that PB mechanisms introduce relative to the minimum-social-cost outcome in expectation. The Random Dictator mechanism for this problem obtains a distortion of 2. In a special case where every voter votes for exactly one project, [Fain et al., 2017] obtain a distortion of 4/3. We show that when PB outcomes are determined as any convex combination of the votes of two voters, the distortion is 2. When three uniformly randomly sampled votes are used, we give a PB mechanism that obtains a distortion of at most 1.66, thus breaking the barrier of 2 with the smallest possible sample complexity. We give a randomized Nash bargaining scheme where two uniformly randomly chosen voters bargain with the disagreement point as the vote of a voter chosen uniformly at random. This mechanism has a distortion of at most 1.66. We provide a lower bound of 1.38 for the distortion of this scheme. Further, we show that PB mechanisms that output a median of the votes of three voters chosen uniformly at random, have a distortion of at most 1.80.

Cited by 4Open access

Sample Complexity for Nonlinear Dynamics

Yongxin Chen, Umesh Vaidya · arXiv (Cornell University) · 2018

We consider the identification problems for nonlinear dynamical systems. An explicit sample complexity bound in terms of the number of data points required to recover the models accurately is derived. Our results extend recent sample complexity results for linear dynamics. Our approach for obtaining sample complexity bounds for nonlinear dynamics relies on a linear, albeit infinite dimensional, representation of nonlinear dynamics provided by Koopman and Perron-Frobenius operator. We exploit the linear property of these operators to derive the sample complexity bounds. Such complexity bounds will play a significant role in data-driven learning and control of nonlinear dynamics. Several numerical examples are provided to highlight our theory.

Cited by 2Open access

Sample Complexity of Forecast Aggregation

Tao Lin, Yiling Chen · RePEc: Research Papers in Economics

We consider a Bayesian forecast aggregation model where $n$ experts, after observing private signals about an unknown binary event, report their posterior beliefs about the event to a principal, who then aggregates the reports into a single prediction for the event. The signals of the experts and the outcome of the event follow a joint distribution that is unknown to the principal, but the principal has access to i.i.d. "samples" from the distribution, where each sample is a tuple of the experts' reports (not signals) and the realization of the event. Using these samples, the principal aims to find an $\varepsilon$-approximately optimal aggregator, where optimality is measured in terms of the expected squared distance between the aggregated prediction and the realization of the event. We show that the sample complexity of this problem is at least $\tilde \Omega(m^{n-2} / \varepsilon)$ for arbitrary discrete distributions, where $m$ is the size of each expert's signal space. This sample complexity grows exponentially in the number of experts $n$. But, if the experts' signals are independent conditioned on the realization of the event, then the sample complexity is significantly reduced, to $\tilde O(1 / \varepsilon^2)$, which does not depend on $n$. Our results can be generalized to non-binary events. The proof of our results uses a reduction from the distribution learning problem and reveals the fact that forecast aggregation is almost as difficult as distribution learning.

Cited by 0

Sample Complexity Bounds on Differentially Private Learning via\n Communication Complexity

Vitaly Feldman, David Xiao · arXiv (Cornell University) · 2014

In this work we analyze the sample complexity of classification by\ndifferentially private algorithms. Differential privacy is a strong and\nwell-studied notion of privacy introduced by Dwork et al. (2006) that ensures\nthat the output of an algorithm leaks little information about the data point\nprovided by any of the participating individuals. Sample complexity of private\nPAC and agnostic learning was studied in a number of prior works starting with\n(Kasiviswanathan et al., 2008) but a number of basic questions still remain\nopen, most notably whether learning with privacy requires more samples than\nlearning without privacy.\n We show that the sample complexity of learning with (pure) differential\nprivacy can be arbitrarily higher than the sample complexity of learning\nwithout the privacy constraint or the sample complexity of learning with\napproximate differential privacy. Our second contribution and the main tool is\nan equivalence between the sample complexity of (pure) differentially private\nlearning of a concept class $C$ (or $SCDP(C)$) and the randomized one-way\ncommunication complexity of the evaluation problem for concepts from $C$. Using\nthis equivalence we prove the following bounds:\n 1. $SCDP(C) = \\Omega(LDim(C))$, where $LDim(C)$ is the Littlestone's (1987)\ndimension characterizing the number of mistakes in the online-mistake-bound\nlearning model. Known bounds on $LDim(C)$ then imply that $SCDP(C)$ can be much\nhigher than the VC-dimension of $C$.\n 2. For any $t$, there exists a class $C$ such that $LDim(C)=2$ but $SCDP(C)\n\\geq t$.\n 3. For any $t$, there exists a class $C$ such that the sample complexity of\n(pure) $\\alpha$-differentially private PAC learning is $\\Omega(t/\\alpha)$ but\nthe sample complexity of the relaxed $(\\alpha,\\beta)$-differentially private\nPAC learning is $O(\\log(1/\\beta)/\\alpha)$. This resolves an open problem of\nBeimel et al. (2013b).\n

Cited by 12Open access

Optimal Sample Complexity of Contrastive Learning

Noga Alon, Dmitrii Avdiukhin, Dor Elboim et al. · arXiv (Cornell University) · 2023

Contrastive learning is a highly successful technique for learning representations of data from labeled tuples, specifying the distance relations within the tuple. We study the sample complexity of contrastive learning, i.e. the minimum number of labeled tuples sufficient for getting high generalization accuracy. We give tight bounds on the sample complexity in a variety of settings, focusing on arbitrary distance functions, both general $\ell_p$-distances, and tree metrics. Our main result is an (almost) optimal bound on the sample complexity of learning $\ell_p$-distances for integer $p$. For any $p \ge 1$ we show that $\tilde Θ(\min(nd,n^2))$ labeled tuples are necessary and sufficient for learning $d$-dimensional representations of $n$-point datasets. Our results hold for an arbitrary distribution of the input samples and are based on giving the corresponding bounds on the Vapnik-Chervonenkis/Natarajan dimension of the associated problems. We further show that the theoretical bounds on sample complexity obtained via VC/Natarajan dimension can have strong predictive power for experimental results, in contrast with the folklore belief about a substantial gap between the statistical learning theory and the practice of deep learning.

Cited by 0Open access

The Sample Complexity of Revenue Maximization

Richard Cole, Tim Roughgarden · arXiv (Cornell University) · 2015

In the design and analysis of revenue-maximizing auctions, auction performance is typically measured with respect to a prior distribution over inputs. The most obvious source for such a distribution is past data. The goal is to understand how much data is necessary and sufficient to guarantee near-optimal expected revenue. Our basic model is a single-item auction in which bidders' valuations are drawn independently from unknown and non-identical distributions. The seller is given $m$ samples from each of these distributions "for free" and chooses an auction to run on a fresh sample. How large does m need to be, as a function of the number k of bidders and eps > 0, so that a (1 - eps)-approximation of the optimal revenue is achievable? We prove that, under standard tail conditions on the underlying distributions, m = poly(k, 1/eps) samples are necessary and sufficient. Our lower bound stands in contrast to many recent results on simple and prior-independent auctions and fundamentally involves the interplay between bidder competition, non-identical distributions, and a very close (but still constant) approximation of the optimal revenue. It effectively shows that the only way to achieve a sufficiently good constant approximation of the optimal revenue is through a detailed understanding of bidders' valuation distributions. Our upper bound is constructive and applies in particular to a variant of the empirical Myerson auction, the natural auction that runs the revenue-maximizing auction with respect to the empirical distributions of the samples. Our sample complexity lower bound depends on the set of allowable distributions, and to capture this we introduce alpha-strongly regular distributions, which interpolate between the well-studied classes of regular (alpha = 0) and MHR (alpha = 1) distributions. We give evidence that this definition is of independent interest.

Cited by 6Open access

Sample complexity of model-based search

Christopher D. Rosin · 1998

Article Sample complexity of model-based search Share on Author: Christopher D. Rosin The Scripps Research Institute and University of California, San Diego, CSE Dept., and The Scripps Research Institute, Mail Drop MB5, 10550 North Torrey Pines Road, La Jolla, CA The Scripps Research Institute and University of California, San Diego, CSE Dept., and The Scripps Research Institute, Mail Drop MB5, 10550 North Torrey Pines Road, La Jolla, CAView Profile Authors Info & Claims COLT' 98: Proceedings of the eleventh annual conference on Computational learning theoryJuly 1998 Pages 259–267https://doi.org/10.1145/279943.279994Online:24 July 1998Publication History 0citation220DownloadsMetricsTotal Citations0Total Downloads220Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Cited by 1

Sample A—Minimal complexity graphical search.

João António (6496931), Jorge Valente (18946157), Carlos Mora (3315090) et al. · Figshare · 2024

<p>Reproduced under a CC BY license, with permission from Techframe—Sistemas de Informação, SA, original copyright 2023.</p>

Cited by 0Open access

Coarse Sample Complexity Bounds for Active

Learning Sanjoy Dasgupta, Sanjoy Dasgupta · 2008

We characterize the sample complexity of active learning problems in terms of a parameter which takes into account the distribution over the input space, the specific target hypothesis, and the desired accuracy.

Cited by 0

Automata Cascades: Expressivity and Sample Complexity

Alessandro Ronca, Nadezda Alexandrovna Knorozova, Giuseppe De Giacomo · Proceedings of the AAAI Conference on Artificial Intelligence · 2023

Every automaton can be decomposed into a cascade of basic prime automata. This is the Prime Decomposition Theorem by Krohn and Rhodes. Guided by this theory, we propose automata cascades as a structured, modular, way to describe automata as complex systems made of many components, each implementing a specific functionality. Any automaton can serve as a component; using specific components allows for a fine-grained control of the expressivity of the resulting class of automata; using prime automata as components implies specific expressivity guarantees. Moreover, specifying automata as cascades allows for describing the sample complexity of automata in terms of their components. We show that the sample complexity is linear in the number of components and the maximum complexity of a single component, modulo logarithmic factors. This opens to the possibility of learning automata representing large dynamical systems consisting of many parts interacting with each other. It is in sharp contrast with the established understanding of the sample complexity of automata, described in terms of the overall number of states and input letters, which implies that it is only possible to learn automata where the number of states is linear in the amount of data available. Instead our results show that one can learn automata with a number of states that is exponential in the amount of data available.

Cited by 1Open access