Publication

Computing Bounds for the Star Discrepancy

2000
Journal Articles

Abstract

We observe that the time required to compute the star discrepancy of a sequence of points in a multidimensional unit cube is prohibitive and that the best known upper bounds for the star discrepancy of (t,s)-sequences and (t,m,s)-nets are useful only for sample sizes that grow exponentially with the dimension s. Then, an algorithm to compute upper bounds for the star discrepancy of an arbitrary set of n points in the s-dimensional unit cube is proposed. For an integer k≥1, this algorithm computes in O(nslogk+2^s*k^s) time and O(k^s) space a bound that is no better than a function depending on s and k. As an application, we give improved upper bounds for the star discrepancy of some Faure (0,m,s)-nets for s∈{7,…,20}.

Official source

https://infoscience.epfl.ch/entities/publication/0e41f5b4-e5d0-4800-b26d-2cd57a7c7fda

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2000
Journal Articles

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/0e41f5b4-e5d0-4800-b26d-2cd57a7c7fda

About this result

Related concepts (32)

Computable function

Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines.

Chernoff bound

In probability theory, a Chernoff bound is an exponentially decreasing upper bound on the tail of a random variable based on its moment generating function. The minimum of all such exponential bounds forms the Chernoff or Chernoff-Cramér bound, which may decay faster than exponential (e.g. sub-Gaussian). It is especially useful for sums of independent random variables, such as sums of Bernoulli random variables. The bound is commonly named after Herman Chernoff who described the method in a 1952 paper, though Chernoff himself attributed it to Herman Rubin.

Sample size determination

Sample size determination is the act of choosing the number of observations or replicates to include in a statistical sample. The sample size is an important feature of any empirical study in which the goal is to make inferences about a population from a sample. In practice, the sample size used in a study is usually determined based on the cost, time, or convenience of collecting the data, and the need for it to offer sufficient statistical power.

Related publications (5)

Computing Bounds for the Star Discrepancy

Chat with Graph Search

Building Conformal Prediction Intervals with Approximate Message Passing

Optimal Best Arm Identification under Differential Privacy

New perspectives on the performance of machine learning classifiers for mode-choice prediction