Machine learning and learning theory: PAC learning, algorithmic learning theory, and computational aspects of Bayesian inference and graphical models.
2
votes
1answer
80 views
Lower Bound for the Parity Learning Problem
What are known lower bounds for the time and query complexity of the problem of learning parities with an adaptive membership query oracle? To be clear the concept space $C$ is $\{x\in \{0,1\}^n \, \, ...
1
vote
0answers
67 views
VC dimension of intersection of half-spaces
Define $$l_i(x) := \text{sgn} \left( w_i^\top x - b_i \right)$$
for $i=1,...,n$, where $x \in \mathbb{R}^d$.
Then define the classifier
$$ g(x) := \max \{ l_1(x),..., l_n(x) \}$$
which represents ...
1
vote
0answers
129 views
VC dimension for ellipsoidal classifiers
What is the VC dimension of $g: \mathbb{R}^n \times (\mathbb{R}^{n \times n} \times \mathbb{R}^n \times \mathbb{R}) \rightarrow \{-1,1\}$ defined as
$$ g( x, (P_1,p_2,p_3), ) := \text{sgn} \left( ...
3
votes
0answers
60 views
A sampling and learning question
Suppose there is an oracle that returns a number $b \in \mathbb{Z}_{n}$ whenever I press the button.
We have $b = a + e$, where $a \in \mathbb{Z}_n$ is a fixed number and $e$ is sampled according to ...
4
votes
1answer
64 views
VC-Dimension and sample complexity dependent on size of subsets
I have a range space $(X,R)$, were $R$ is a collection of subsets of $R$ and I have an upper bound $d$ to the VC-dimension of $(X,R)$. Suppose for simplicity that $X$ is finite. Given $\delta\in(0,1)$ ...
9
votes
1answer
305 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$, ...
2
votes
0answers
201 views
PAC learning and computation over real numbers
I became familiar with the BSS model of computation recently.
I find it to be a better model of computation to study complexity of numerical analysis methods (cf. Complexity and Real Computation; ...
8
votes
1answer
265 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 ...
13
votes
4answers
287 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 ...
3
votes
1answer
113 views
Online to batch sample complexity
It is well known that a mistake bound can be converted to a PAC bound. I know how to prove a sample complexity of
$$ O( (1/\epsilon)[M + \log(M/\delta)] ), $$
where $M$ is an upper bound on the number ...
5
votes
2answers
160 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 ...
11
votes
1answer
208 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 ...
9
votes
1answer
152 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 ...
13
votes
2answers
161 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 ...
0
votes
0answers
68 views
Generalizing a set of positive and negative examples through DFAs [duplicate]
Possible Duplicate:
Is finding the minimum regular expression an NP-complete problem?
Let $\Sigma$ be an alphabet. Let $P$ and $N$ (the set of positive and negative examples) be two ...
0
votes
1answer
122 views
What are some theory problems in Information Retrieval and Search Engines which are not yet solved or can be bettered?
I'm interested in IR and Search Engines and want to work on a theory problem in this space. Most thoughts that I get are focused towards implementation and would like to explore something not solved ...
6
votes
0answers
79 views
Sample complexity of PAC learning all k-DNFs over the uniform distribution
Is sample complexity of PAC learning all $k$-DNFs over the uniform distribution known (that is all DNFs with all terms of size at most $k$ and without restriction on the number of terms)?
The only ...
5
votes
2answers
266 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
0answers
169 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 ...
11
votes
2answers
341 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$ ...
0
votes
0answers
100 views
Rademacher Averages, VC shatter coefficient, and eps-approximations
I am learning about Rademacher averages and their relation to VC-dimension for a project I am working on, but I am not sure I got everything right, so I will recap what I understood below and I would ...
2
votes
1answer
120 views
Agnostic Learning of K-Juntas over “small” distribution
I have two questions related to agnostic learning, one specific and one more general, specifically when the distribution relative to which the learner must operate is given explicitly as part of the ...
0
votes
1answer
215 views
Advantages of ANN classifiers over the AdaBoost
So what are the advantages of ANN classifiers over the AdaBoost or Boosting algorithm?
8
votes
1answer
192 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 ...
6
votes
1answer
95 views
Separation result for proper learning under the uniform vs. adversarial distributions?
Does anyone know of a concept class known to be (1) efficiently learnable under the uniform distribution but (1) NP-hard to learn under arbitrary [adversarial] distributions? I mean "learning" in the ...
7
votes
1answer
227 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 ...
6
votes
0answers
191 views
View of Multiplicative Weights in contexts of combinatorial optimization, low-regret/online optimization, and entropy-regularized gradient descent?
Also called exponentiated gradient.
I understand these are three places where multiplicative weights shows up (i.e. $w_{t+1} = w_{t}e^{- \text{loss}(w_{t})}$ or variations. And I understand a bit ...
5
votes
3answers
252 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
0answers
307 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 ...
4
votes
1answer
149 views
Active learning for inferring a convex optimization formulation
I was wondering if anybody knows of any relevant references on the general topic of active learning for gradually inferring/updating a convex opt. formulation.
As a specific example, I am thinking ...
8
votes
1answer
188 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 ...
13
votes
2answers
341 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 ...
3
votes
0answers
197 views
Open problems on epsilon nets
What would be a good source for open problems for (weak) epsilon nets? Is there a good survey/article that summarizes the recent advancements on the topic?
1
vote
1answer
205 views
Correspondence between Computability & Learnability Theory
Could someone give a brief explanation of the computability & learnability theory & the correspondence betwwen them if any? (pointers to good sources of info. on this other than wikipedia are ...
0
votes
2answers
264 views
Support Vector Machines
What is it the relationship between the number of support vectors in an SVM and its generalization ability? When lots of support vectors are used to classify, is the error rate minimized, but only to ...
12
votes
0answers
245 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 ...
7
votes
1answer
147 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 ...
1
vote
1answer
164 views
Has this online problem been studied before ?
Consider the following online problem:
For $\sigma$ and $k$ fixed, given a string of symbols from alphabet
$[1..\sigma]$, given one by one, guess a set $S$ of $k$ symbols such that the
next ...
7
votes
1answer
126 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.
0
votes
2answers
226 views
Learning using decision trees
I have a quick question that I'm stumped on. This is about constructing a decision tree using information gain (entropy). Let's say we have a dataset with two input attributes such that the ...
11
votes
2answers
319 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 ...
9
votes
2answers
178 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 ...
4
votes
1answer
134 views
Results on universal approximation for learners other than ANNs
I have an applied machine-learning and statistics background, and when I read the Universal approximation theorem, which (in the context of the learning theory of ANNs - Artificial Neural Networks) ...
5
votes
2answers
180 views
A PAC-like analogue for 1-class classification?
This is more of a philosophical question -- I am looking for a reasonable mathematical formulation of 1-class learning.
In the PAC model, it's very natural to formulate our demand on the learner: ...
7
votes
1answer
238 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?
...
6
votes
1answer
169 views
Stochastic multi-armed bandit problem with transition costs
The stochastic multi-armed bandit problem ($k$ arms, the $i$'th of which gives you a reward of $1$ with unknown probability $p_i$, and $0$ with probability $1-p_i$, and you must decide at each stage ...
2
votes
1answer
1k views
Computational complexity of learning (classification) algorithms - fitting the parameters
My wish is to describe the time complexity of several classification approaches. For example, suppose we have $n$ data points in $m$ dimensional space and a binary class variable. We do not assume ...
6
votes
2answers
646 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 ...
5
votes
2answers
128 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 ...
2
votes
1answer
181 views
K-NN or matrix factorization for discovering correlated features?
I am looking to cluster users together in a database, with each user represented by a number of features that are both discrete and continuous in nature. "Similar" users should be clustered together ...
