# chernoff

Published articles for chernoff.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## Occam's Razor and PAC-learning

DevFeed: [Occam's Razor and PAC-learning](<https://devfeed.tech/articles/occam-s-razor-and-pac-learning-40366.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/09/19/occams-razor-and-pac-learning/>)

Published: 2014-09-19T10:00:47Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Occam's razor machine learning](<https://devfeed.tech/topics/occam-s-razor-machine-learning.md>), [Learning](<https://devfeed.tech/topics/learning.md>), [data](<https://devfeed.tech/topics/data.md>)

Tags: [chernoff](<https://devfeed.tech/tags/chernoff.md>), [chernoff-bound](<https://devfeed.tech/tags/chernoff-bound.md>), [computational-learning-theory](<https://devfeed.tech/tags/computational-learning-theory.md>), [learning-theory](<https://devfeed.tech/tags/learning-theory.md>), [occam-s-razor](<https://devfeed.tech/tags/occam-s-razor.md>), [pac-learning](<https://devfeed.tech/tags/pac-learning.md>), [vc-dimension](<https://devfeed.tech/tags/vc-dimension.md>)

### AI overview

This tutorial develops a simple PAC-learning theorem for a finite hypothesis class. It explains that if a hypothesis consistent with observed data can always be found, the class can be learned efficiently, and it uses the Chernoff-Hoeffding bound to quantify the sample requirement for achieving low error.

### Source excerpt

So far our discussion of learning theory has been seeing the definition of PAC-learning, tinkering with it, and seeing simple examples of learnable concept classes. We've said that our real interest is in proving big theorems about what big classes of problems can and can't be learned. One major tool for doing this with PAC is the concept of VC-dimension, but to set the stage we're going to prove a simpler theorem that gives a nice picture of PAC-learning when your hypothesis class is small.

## Probabilistic Bounds -- A Primer

DevFeed: [Probabilistic Bounds -- A Primer](<https://devfeed.tech/articles/probabilistic-bounds-a-primer-40312.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2013/04/15/probabilistic-bounds-a-primer/>)

Published: 2013-04-15T11:14:32Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [math](<https://devfeed.tech/topics/math.md>), [Learning](<https://devfeed.tech/topics/learning.md>), [Streaming](<https://devfeed.tech/topics/streaming.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [chebyshev](<https://devfeed.tech/tags/chebyshev.md>), [chernoff](<https://devfeed.tech/tags/chernoff.md>), [chernoff-bound](<https://devfeed.tech/tags/chernoff-bound.md>), [inequality](<https://devfeed.tech/tags/inequality.md>), [learning-theory](<https://devfeed.tech/tags/learning-theory.md>), [machine-learning](<https://devfeed.tech/tags/machine-learning.md>), [markov](<https://devfeed.tech/tags/markov.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [probabilistic](<https://devfeed.tech/tags/probabilistic.md>), [probabilistic-method](<https://devfeed.tech/tags/probabilistic-method.md>), [probability-theory](<https://devfeed.tech/tags/probability-theory.md>), [random-variables](<https://devfeed.tech/tags/random-variables.md>), [streaming](<https://devfeed.tech/tags/streaming.md>), [streaming-algorithms](<https://devfeed.tech/tags/streaming-algorithms.md>), [variance](<https://devfeed.tech/tags/variance.md>)

### AI overview

This tutorial introduces probabilistic bounds used in algorithm analysis, machine learning theory, randomized algorithms, and streaming algorithms. It focuses on the Chernoff bound and presents simpler bounds from Markov's and Chebyshev's inequalities, including short proofs.

### Source excerpt

Probabilistic arguments are a key tool for the analysis of algorithms in machine learning theory and probability theory. They also assume a prominent role in the analysis of randomized and streaming algorithms, where one imposes a restriction on the amount of storage space an algorithm is allowed to use for its computations (usually sublinear in the size of the input). While a whole host of probabilistic arguments are used, one theorem in particular (or family of theorems) is ubiquitous: the Chernoff bound.