Questions tagged [lg.learning]

Machine learning and learning theory: PAC learning, algorithmic learning theory, and computational aspects of Bayesian inference and graphical models.

41
votes
4answers
8k views

Is finding the minimum regular expression an NP-complete problem?

I am thinking of the following problem: I want to find a regular expression that matches a particular set of strings (for ex. valid email addresses) and doesn't match others (invalid email addresses). ...
28
votes
1answer
1k views

Functions that are Not Efficiently Computable but Learnable

We know that (see, e.g., Theorems 1 and 3 of [1]), roughly speaking, under suitable conditions, functions that can be efficiently computed by Turing machine in polynomial time ("efficiently computable"...
26
votes
2answers
797 views

What is the complexity of distinguishing a true Fourier spectra from a fake one?

A $PH$ machine is given oracle access to a random Boolean function $f:\{0,1\}^n \to \{ -1,1 \}$ , and two Fourier spectra $g$ and $h$. The Fourier spectra of a function $f$ is defined as $F:\{0,1\}^...
25
votes
2answers
814 views

Approximating the sign rank of a matrix

The sign rank of a matrix A with +1,-1 entries is the least rank (over the reals) of a matrix B which has the same sign pattern as A (i.e., $A_{ij}B_{ij}>0$ for all $i,j$). This notion is important in ...
20
votes
3answers
388 views

Property testing in other metrics?

There is a large literature on "property testing" -- the problem of making a small number of black box queries to a function $f\colon\{0,1\}^n \to R$ to distinguish between two cases: $f$ is a ...
19
votes
1answer
800 views

The Warren Buffett Problem

Here is an abstraction of an online learning / bandit problem that I've been working on in the summer. I haven't seen a problem like this before, and it looks quite interesting. If you know of any ...
19
votes
2answers
527 views

Internal Regret in Online Convex Optimization

Zinkevich's "online convex optimization" ( http://www.cs.cmu.edu/~maz/publications/ICML03.pdf ) generalizes "regret minimization" learning algorithms from a linear settings to a convex setting and ...
15
votes
4answers
372 views

Worst number of questions needed to learn a monotonic predicate over a poset

Consider $(X, \leq)$ a finite poset over $n$ items, and $P$ an unknown monotonic predicate over $X$ (i.e., for any $x$, $y \in X$, if $P(x)$ and $x \leq y$ then $P(y)$). I can evaluate $P$ by ...
15
votes
2answers
590 views

Quantum PAC learning

Background Functions in $AC^0$ are PAC learnable in quasipolynomial time with a classical algorithm that requires $O(2^{log(n)^{O(d)}})$ randomly chosen queries to learn a circuit of depth d [1]. If ...
15
votes
2answers
268 views

On the status of learnability inside $\mathsf{TC}^0$

I'm trying to understand the complexity of functions expressible via threshold gates and this led me to $\mathsf{TC}^0$. In particular, I'm interested what's currently known about learning inside $\...
15
votes
3answers
335 views

Combinatorial characterization of exact learning with membership queries

Edit: Since I haven't received any responses/comments in a week, I'd like to add that I'm happy to hear anything about the problem. I don't work in the area, so even if it's a simple observation, I ...
14
votes
1answer
517 views

Best query complexity of Goldreich-Levin / Kushilevitz-Mansour learning algorithm

What is the best known query complexity of Goldreich-Levin learning algorithm? Lecture notes from Luca Trevisan's blog, Lemma 3, states it as $O(1/\epsilon^4 n \log n)$. Is this the best known in ...
14
votes
0answers
349 views

Applications of fat shattering dimension in computational geometry

The fat shattering dimension generalizes the notion of VC-dimension to handle function classes where the range is $(0,1)$, instead of $\{0,1\}$. Fat shattering dimension plays the same role as VC-...
13
votes
3answers
2k views

Statistical query model algorithms?

I asked this question in cross validated Q&A but seems that it is related to CS much more than Statistics. Can you give me examples of machine learning algorithms which learn from the statistical ...
13
votes
2answers
460 views

Learning triangles in the plane

I assigned my students the problem of finding a triangle consistent with a collection of $m$ points in $\mathbb{R}^2$, labeled with $\pm1$. (A triangle $T$ is consistent with the labeled sample if $T$ ...
13
votes
1answer
520 views

Reference Request: Submodular Minimization and Monotone Boolean Functions

Background: In machine learning, we often work with graphical models to represent high dimensional probability density functions. If we discard the constraint that a density integrates (sums) to 1, ...
12
votes
5answers
527 views

clustering algorithm for non-dimensional data

i have a dataset of thousands of points and a means of measuring the distance between any two points, but the data points have no dimensionality. i want an algorithm to find cluster centers in this ...
12
votes
1answer
706 views

The Cost of an Equivalence Query for DFA

Inspired by this question, I am curious about the following: What is the worst-case complexity of checking whether a given DFA accepts the same language as a given regular expression? Is this ...
12
votes
2answers
323 views

Computational query complexity of SQ-learning

It is known that for PAC learning, there are natural concept classes (e.g. subsets of decision lists) for which there are polynomial gaps between the sample complexity needed for information theoretic ...
12
votes
2answers
521 views

Estimating VC-Dimension

What is known about the following problem? Given a collection $C$ of functions $f:\{0,1\}^n\rightarrow\{0,1\}$, find a largest subcollection $S \subseteq C$ subject to the constraint that VC-...
12
votes
1answer
424 views

Minimizing residual finite state automata

Residual finite state automata (RFSAs, defined in [DLT02]) are NFAs that have some nice features in common with DFAs. In particular, there is always a canonical minimum sized RFSA for every regular ...
11
votes
2answers
324 views

Clustering formalizations other than K-means for separable data

Real world data sometimes has a natural number of clusters (trying to cluster it into a number of cluster lesser than some magic k will cause a dramatic increase the clustering cost). Today I attended ...
11
votes
2answers
253 views

Any Hypothesis Classes Other than Parity in Noisy PAC but not in SQ?

Angluin and Laird ('88) formalized learning with randomly corrupted data in the model "PAC with random classification noise" (or noisy PAC). This model is similar to PAC learning, except for the ...
11
votes
3answers
275 views

Learning with “taciturn” oracles

My question is a bit generic, so I'm making up a nice story to justify it. Bear with me if it's not realistic ;-) Story Mr. X, the head of the computer security department at a big company, is a bit ...
11
votes
1answer
493 views

Lower bounds for learning in the membership query and counterexample model

Dana Angluin (1987; pdf) defines a learning model with membership queries and theory queries (counterexamples to a proposed function). She shows that a regular language that is represented by a ...
11
votes
1answer
375 views

Agnostic learning over arbitrary distributions

Let $D$ be a distribution over bitstring/label pairs $\{0,1\}^d\times \{0,1\}$ and let $C$ be a collection of boolean valued functions $f:\{0,1\}^d\rightarrow\{0,1\}$. For each function $f \in C$, let:...
11
votes
1answer
232 views

Given $f:\{0,1\}^n \rightarrow \{-1,1\}$, find a subcube with large volume and large average value

Here is a problem with a similar flavor to learning juntas: Input: A function $f: \{0,1\}^n \rightarrow \{-1,1\}$, represented by a membership oracle, i.e. an oracle that given $x$, returns $f(x)$. ...
11
votes
1answer
518 views

Noisy Parity (LWE) lower bounds/hardness results

Some background: I'm interested in finding "lesser-known" lower bounds (or hardness results) for the Learning with Errors (LWE) problem, and generalizations thereof like Learning with Errors over ...
11
votes
0answers
346 views

Is Bayesian updating computationally unfeasible?

Bayesian theory is a very popular theory of probabilities based upon a subjective framework of beliefs. However, subjects and beliefs have to be embodied, meaning to be feasible, it ought to be ...
10
votes
5answers
3k views

What are good references on understanding online learning?

Specifically, I'm asking for resources to learn about machine learning systems that can update their respective belief networks (or equivalent) during operation. I've even run across a few, though I ...
10
votes
3answers
332 views

Keyword selection problem in search engine marketing auction

First of all, I am still not sure whether cstheory is well adapted for this question, so I won't be offended if the crowd thinks it is not the case... In search engine marketing, several problems are ...
10
votes
3answers
960 views

Resource / book for recent advances in statistical learning theory

I'm quite familiar with the theory behind VC-Dimension, but I'm now looking at the recent (last 10 years) advances in statistical learning theory: (local) Rademacher averages, Massart's Finite Class ...
10
votes
2answers
1k views

Introductory resources on Computational Learning Theory

Recently I've been reading a decent number of CoLT papers. Although I don't struggle with the individual papers (at least not more than I usually struggle with other theory papers), I don't feel I ...
10
votes
1answer
314 views

What machine learning classifiers are the most parallelizeable?

What machine learning classifiers are the most parallelizeable? If you had a difficult classification problem, limited time, but a decent LAN of computers to work with, what classifiers would you try? ...
10
votes
1answer
445 views

A parity learning question

Let us define a class of functions over a set of $n$ bits. Fix two distributions $p, q$ that are "reasonably" different from each other (if you like, their variational distance is at least $\epsilon$, ...
10
votes
1answer
377 views

Agnostic PAC sampling lower bound

It is well-known that for classical PAC learning, $\Omega(d/\varepsilon)$ examples are necessary in order to acheive an error bound of $\varepsilon$ w.h.p., where $d$ is the VC-dimension of the ...
9
votes
1answer
382 views

Proper PAC learning of 2-DNF under uniform distribution

What is the state of art result about query complexity of proper PAC learning 2-DNF formulas with sample queries and under uniform distribution? Or any non-trivial bound on it? Because I am not ...
9
votes
2answers
513 views

Theoretical results for random forests?

Random forests have a reputation among practitioners of being among the most effective classification techniques. Yet we don't encounter them much in the learning-theoretic literature, from which I ...
9
votes
2answers
375 views

Are there families of formal languages known to be truly PAC learnable?

I specifically mean language families that admit arbitrarily long strings -- not conjunctions over n bits or decision lists or any other "simple" language contained in {0,1}^n. I am asking about "...
9
votes
1answer
286 views

VC dimension of Voronoi cells in R^d?

Suppose I have $k$ points in $\mathbb{R}^d$. These induce a Voronoi diagram. If I assign to each of the $k$ points a $\pm$ label, these induce a binary function on $\mathbb{R}^d$. Question: what is ...
8
votes
2answers
3k views

Computational complexity of clustering algorithms

My wish is to describe the time complexity of several clustering approaches. For example, suppose we have $n$ data points in $m$ dimensional space. Suppose further that the pairwise dissimilarity ...
8
votes
1answer
482 views

Difficulty of “learning” rare instances

Is there any result showing that models (say SVM, Neural-Net, kNN, etc) will have difficulty in learning "rare" instances/tail phenomena?
8
votes
1answer
388 views

VC Dimension generalized to discrete, non-binary, unordered domains?

VC dimension is a measure of the complexity of classes of functions $f:X\rightarrow \{0,1\}$ that is closely tied to sample complexity. Fat shattering dimension is a generalization suited to richer ...
7
votes
1answer
158 views

Multi-armed bandit problems where more than one arm can be selected?

I want to know if there are any references in the literature on multi-armed bandit problem where in one round, you can select $k > 1$ arms.
7
votes
1answer
520 views

What does PAC-learnability say about the learner runtime?

I am new to PAC-learnability. Assume a class $\mathcal{H}$ of hypotheses is PAC-learnable. Then all we know that if we draw polynomial number of examples (in $\delta$ and $\epsilon$), we can return a ...
7
votes
2answers
149 views

Relating PAC learning results and abstaining classifiers

Quite a few results are available on learning miscellaneous concept classes in the PAC learning framework. I would like to know whether any of these results have been extended in the abstaining ...
7
votes
1answer
326 views

Statistical query model with Gaussian noise?

Kearns' statistical query model is a well-known learning model with noise tolerance. The statistical query oracle takes as input a statistical query of the form $\{\chi, \tau\}$. Here $\chi$ is any ...
7
votes
1answer
330 views

How hard is it to learn a linear modular function?

Let $k$ be a fixed number. Consider the following task $Q$: We are given a sequence of numbers $(x_0,x_1,\cdots,x_k)$. We know they satisfy $x_{k+1}=f(x_k)$, and $f(x)=(ax+b \mod p) \mod m$ where $...
7
votes
2answers
271 views

Learning Mixture of Univariate Gaussians

There are many papers on learning mixtures of multivariate Gaussians, which exploit various separation/projection techniques. What about one-dimensional (univariate) Gaussians -- any formal guarantees ...
7
votes
1answer
486 views

What is the VC Dimension of the $k-$Junta class

A boolean function $f(x_1,x_2,\dots,x_n)$ is $k$-Junta if it depends on at most $k$ variables. Consider the class $\mathcal{J}_{\leq k}$ of all $k$-Juntas over $n$ variables, what is the VC dimension ...