Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [lg.learning]

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

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 ...
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 ...
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 ...
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 ...
0
votes
0answers
77 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 disjoint ...
1
vote
2answers
215 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 ...
7
votes
0answers
186 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 ...
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 ...
14
votes
1answer
516 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 ...
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$ ...
1
vote
0answers
184 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 ...
3
votes
1answer
208 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
2answers
655 views

Advantages of ANN classifiers over the AdaBoost

So what are the advantages of ANN classifiers over the AdaBoost or Boosting algorithm?
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 ...
7
votes
1answer
148 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 ...
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 ...
7
votes
0answers
331 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 ...
-1
votes
1answer
183 views

Invariance in Property Testing

A property is said to be invariant under a permutation $\pi$ if permuting the data points by this permutation leaves the property unchanged. Invariance under permutations seems to help with property ...
10
votes
3answers
958 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 ...
11
votes
0answers
344 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
193 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 ...
10
votes
1answer
376 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 ...
15
votes
2answers
589 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 ...
4
votes
0answers
250 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?
0
votes
1answer
259 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 ...
3
votes
2answers
328 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 ...
14
votes
0answers
348 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-...
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 ...
1
vote
1answer
186 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
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.
0
votes
2answers
314 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 ...
12
votes
2answers
520 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-...
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 ...
6
votes
1answer
405 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) ...
7
votes
2answers
207 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: ...
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? ...
6
votes
1answer
203 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 ...
6
votes
1answer
9k 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 ...
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 ...
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 ...
2
votes
1answer
353 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 ...
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\}^...
-1
votes
1answer
2k views

off-policy and offline policy reinforcement learning

What's the difference between off-policy reinforcement learning algorithms and offline policy reinforcement learning algorithms ? Or do they mean the same thing ? thanks
11
votes
2answers
323 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 ...
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 ...
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 ...
2
votes
1answer
3k views

How does one augment AdaBoost with cross-validation?

How does one augment AdaBoost with cross-validation?
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 ...
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 ...
12
votes
5answers
526 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 ...