Questions tagged [machine-learning]

Theoretical questions about Machine learning, especially Computational Learning Theory, including Algorithmic Learning Theory, PAC learning, and Bayesian Inference

20 questions
5k views

What are some real world applications for genetic algorithms?

What are some real world problems that have been solved using a genetic algorithm? What is the problem? What is the fitness test used to solve this problem?
1k views

Computational Power of Neural Networks?

Let's say we have a single-layer feed forward neural network with k inputs and one output. It calculates a function from $\lbrace 0,1\rbrace ^{n}\rightarrow\lbrace 0,1\rbrace$, it's fairly easy to ...
216 views

Rademacher complexity beyond the agnostic setting

The way I know of to bound generalization error by Rademacher complexity is Theorem 2.4 in this lecture notes, http://ttic.uchicago.edu/~tewari/lectures/lecture9.pdf. Here the quantity on the LHS that ...
196 views

minimal finite automata given in-words and out-words

this seems an interesting FSM optimization problem; have not seen it studied, wondering if it has been and/ or looking for other insight. given: two finite sets of words $S_{in}$ and $S_{out}$. ...
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 ...
6k views

Is there any gradient descent based technique for searching absolute minimum (maximum) of a function in multidimensional space?

I'm familiar with gradient descent algorithm which can find local minimum (maximum) of a given function. Is there any modification of gradient descent which allows to find absolute minimum (maximum),...
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 ...
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 ...
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 ...
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 ...
349 views

Complexity of finding a consistent hyperplane

Given $m$ binary labeled points in $\mathbb{R}^d$, it is well-known that in general it's NP-hard to find a hyperplane that minimizes sample error. A brute-force search considers all $O(m^d)$ sample ...
528 views

I come from a pure math background and am not very familiar with machine learning. So, I'll start with an example to compensate for my confused grasp of the terminology. Let's say we have a function $... 1answer 93 views Other Uniform Bound In theoretical machine learning, VC-dimension (VCD) and Rademacher average (RA) are two frequently used uniform bounds, providing better sample complexity than bounds such as Chernoff bound and ... 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 1answer 243 views Are there distribution properties which are “maximally” hard to test? A distribution testing algorithm for a distribution property P (which is just some subset of all distributions over [n]) is allowed access to samples according to some distribution D, and is required ... 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 ... 2answers 371 views Proper PAC learning VC dimension bounds It is well known that for a concept class$\mathcal{C}$with VC dimension$d$, it suffices to obtain$O\left(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}\right)$labelled examples to PAC learn$\...
367 views

The famous FTPL algorithm  is analyzing linear cost function. Is there any generalized proof for nonlinear functions known? Note that in the last paragraph of  it says "It would be great to ...
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 ...