# learning theory

Published articles for learning theory.

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

## Binary Search on Graphs

DevFeed: [Binary Search on Graphs](<https://devfeed.tech/articles/binary-search-on-graphs-40417.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2017/11/08/binary-search-on-graphs/>)

Published: 2017-11-08T08:59:38Z

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>), [Graphs](<https://devfeed.tech/topics/graphs.md>), [Algorithm](<https://devfeed.tech/topics/algorithm.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [binary-search](<https://devfeed.tech/tags/binary-search.md>), [depth-first-search](<https://devfeed.tech/tags/depth-first-search.md>), [dijkstra](<https://devfeed.tech/tags/dijkstra.md>), [equivalence-queries](<https://devfeed.tech/tags/equivalence-queries.md>), [graph](<https://devfeed.tech/tags/graph.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [learning-theory](<https://devfeed.tech/tags/learning-theory.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>), [search](<https://devfeed.tech/tags/search.md>), [vertex](<https://devfeed.tech/tags/vertex.md>)

### AI overview

The article examines whether binary search can be applied to graphs. It presents a graph-search model in which queries about vertices return either the target or an edge on a shortest path toward it, and notes that the line-graph case corresponds to ordinary binary search.

### Source excerpt

Binary search is one of the most basic algorithms I know. Given a sorted list of comparable items and a target item being sought, binary search looks at the middle of the list, and compares it to the target. If the target is larger, we repeat on the smaller half of the list, and vice versa. With each comparison the binary search algorithm cuts the search space in half. The result is a guarantee of no more than $ \log(n)$ comparisons, for a total runtime of $ O(\log n)$.

## Learning a single-variable polynomial, or the power of adaptive queries

DevFeed: [Learning a single-variable polynomial, or the power of adaptive queries](<https://devfeed.tech/articles/learning-a-single-variable-polynomial-or-the-power-of-adaptive-queries-40370.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/11/18/learning-a-single-variable-polynomial-or-the-power-of-adaptive-queries/>)

Published: 2014-11-18T09:00:18Z

Content type: tutorial

Language: en

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

Topics: [Computing](<https://devfeed.tech/topics/computing.md>), [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [Query (disambiguation)](<https://devfeed.tech/topics/query.md>)

Tags: [adaptive-queries](<https://devfeed.tech/tags/adaptive-queries.md>), [algorithm](<https://devfeed.tech/tags/algorithm.md>), [github](<https://devfeed.tech/tags/github.md>), [implementation](<https://devfeed.tech/tags/implementation.md>), [learning-theory](<https://devfeed.tech/tags/learning-theory.md>), [number-theory](<https://devfeed.tech/tags/number-theory.md>), [polynomial-identity-testing](<https://devfeed.tech/tags/polynomial-identity-testing.md>), [polynomial-interpolation](<https://devfeed.tech/tags/polynomial-interpolation.md>), [polynomials](<https://devfeed.tech/tags/polynomials.md>)

### AI overview

This tutorial shows how adaptive queries can recover a secret single-variable polynomial with nonnegative integer coefficients using only two queries: p(1) and p(p(1)+1). It explains how modular arithmetic extracts the coefficients and contrasts this with the larger number of non-adaptive queries required by polynomial interpolation.

### Source excerpt

Problem: Alice chooses a secret polynomial $ p(x)$ with nonnegative integer coefficients. Bob wants to discover this polynomial by querying Alice for the value of $ p(x)$ for some integer $ x$ of Bob's choice. What is the minimal number of queries Bob needs to determine $ p(x)$ exactly? Solution: Two queries. The first is $ p(1)$, and if we call $ N = p(1) + 1$, then the second query is $ p(N)$.

## 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.

## A problem that is not (properly) PAC-learnable

DevFeed: [A problem that is not (properly) PAC-learnable](<https://devfeed.tech/articles/a-problem-that-is-not-properly-pac-learnable-40356.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/04/21/an-un-pac-learnable-problem/>)

Published: 2014-04-21T10:00:16Z

Content type: tutorial

Language: en

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

Topics: [Learning](<https://devfeed.tech/topics/learning.md>), [math](<https://devfeed.tech/topics/math.md>), [Math and Logic](<https://devfeed.tech/topics/math-and-logic.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [boolean](<https://devfeed.tech/tags/boolean.md>), [boolean-satisfiability](<https://devfeed.tech/tags/boolean-satisfiability.md>), [classes](<https://devfeed.tech/tags/classes.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [computational-learning-theory](<https://devfeed.tech/tags/computational-learning-theory.md>), [learning-theory](<https://devfeed.tech/tags/learning-theory.md>), [logical](<https://devfeed.tech/tags/logical.md>), [math](<https://devfeed.tech/tags/math.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [misconceptions](<https://devfeed.tech/tags/misconceptions.md>), [np](<https://devfeed.tech/tags/np.md>), [np-completeness](<https://devfeed.tech/tags/np-completeness.md>), [pac-learning](<https://devfeed.tech/tags/pac-learning.md>), [reduction](<https://devfeed.tech/tags/reduction.md>), [rp](<https://devfeed.tech/tags/rp.md>)

### AI overview

This technical learning-theory article presents a standard example of a problem that is not learnable under the previously introduced PAC model, then explains how a more expressive hypothesis class changes that result. Its addendum clarifies that 3-term DNF formulas are not shown to be unlearnable under the standard PAC definition, only under the earlier restricted definition.

### Source excerpt

In a previous post we introduced a learning model called Probably Approximately Correct (PAC). We saw an example of a concept class that was easy to learn: intervals on the real line (and more generally, if you did the exercise, axis-aligned rectangles in a fixed dimension). One of the primary goals of studying models of learning is to figure out what is learnable and what is not learnable in the various models.

## Probably Approximately Correct -- a Formal Theory of Learning

DevFeed: [Probably Approximately Correct -- a Formal Theory of Learning](<https://devfeed.tech/articles/probably-approximately-correct-a-formal-theory-of-learning-40337.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/01/02/probably-approximately-correct-a-formal-theory-of-learning/>)

Published: 2014-01-02T18:45:51Z

Content type: tutorial

Language: en

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

Topics: [Learning](<https://devfeed.tech/topics/learning.md>), [Machine Learning & Artificial Intelligence](<https://devfeed.tech/topics/machine-learning-artificial-intelligence.md>), [Computer science](<https://devfeed.tech/topics/computer-science.md>), [Mathematics](<https://devfeed.tech/topics/mathematics.md>)

Tags: [learning](<https://devfeed.tech/tags/learning.md>), [learning-theory](<https://devfeed.tech/tags/learning-theory.md>), [machine-learning](<https://devfeed.tech/tags/machine-learning.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [occam-s-razor](<https://devfeed.tech/tags/occam-s-razor.md>), [pac-learning](<https://devfeed.tech/tags/pac-learning.md>), [theory](<https://devfeed.tech/tags/theory.md>)

### AI overview

A mathematical introduction to PAC learning, a foundational framework in computational learning theory. The article develops basic definitions, explains PAC-learnability through interval examples, and places the theory in its historical context.

### Source excerpt

In tackling machine learning (and computer science in general) we face some deep philosophical questions. Questions like, "What does it mean to learn?" and, "Can a computer learn?" and, "How do you define simplicity?" and, "Why does Occam's Razor work? (Why do simple hypotheses do well at modelling reality?)" In a very deep sense, learning theorists take these philosophical questions -- or at least aspects of them -- give them fleshy mathematical bodies, and then answer them with theorems and proofs.

## 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.