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

learn more… | top users | synonyms

3
votes
0answers
76 views

Are there any learning algorithms with any provable guarantees for manifold learning or manifold regularization?

First of all, I want to make clear that my question is about algorithms. I'd like to know if there are any algorithms with provable guarantees in the context of manifold learning (or manifold ...
-2
votes
0answers
27 views

Heuristics for streaming data matching

I have an index composed by thousands of documents. Slightly modified copies of those documents are sent to my application in small chunks, and I need to check, from those chunks, which document has ...
5
votes
3answers
131 views

Dimensionality reduction in machine learning

This is less of a question and more of a "here's my take let me know if you agree" (so I guess it might turn into a big-list?). Dimensionality reduction refers to a collection of techniques that ...
-2
votes
0answers
28 views

finite hypothesis classes which are not PAC learnable

Finite hypothesis class with bounded loss function are PAC learnable. Are there examples for finite hypothesis classes which aren't PAC learnable, if we omit the bounded loss assumption?
2
votes
0answers
53 views

Dynamical systems analysis of deep learning

I am interested in finding out references that apply dynamical systems analysis to develop the "theory" of deep learning, specifically (say) feedforward deep neural nets. The only paper I seem to have ...
2
votes
0answers
54 views

Johnson Lindenstrauss for Random variables?

Does the Johnson-Lindenstrauss Lemma apply to any finite-dimensional Hilbert Space? In particular, I am interested in the space of random variables $X = (X_1,...,X_N)$ over $N$ uncertain states. If ...
0
votes
1answer
49 views

Bounding Rademacher Averages, with and without chaining

One can bound the Rademacher average $R_n(A)$ of a finite set of vectors $A\subseteq\{0,1\}^n$ using Massart's Finite Lemma: $$ R_n(A)\le \max_{a\in A}\|a\|\frac{\sqrt{2\ln|A|}}{n} $$ where ...
4
votes
1answer
202 views

Sample complexity of distinguishing two Gaussian distributions?

Below is a description of the problem: Suppose I have two $p$-dimensional Gaussian distributions with the same covariance matrix $\Sigma$ and means $\mu_1$, $\mu_0$. And I can get $n$ samples ...
6
votes
0answers
59 views

Learning read-once branching programs with membership queries

Let $B=\{0,1\}$. A read-once branching program of width $n$ and size $w$ is given by a graph with layers $0,\ldots, n$, where the first layer has just the starting node, the last layer has nodes ...
2
votes
1answer
55 views

How to exploit knowledge of the sampling distribution for better generalization bounds?

In the PAC learning model, suppose the learner actually knows the sampling distribution $P$. Surely this knowledge can be exploited to yield better generalization bounds -- but how? One idea is using ...
-1
votes
1answer
97 views

VC-dimension of triangles in 2D space

I have been reading in multiple places (e.g. [1], section 4) that the VC-dimension of the class of triangles (in 2D space) is 7. The issue is that, for the case when 4 points lying on a straight line ...
0
votes
1answer
62 views

Are single hidden-layered neural networks at least as good as multi hidden-layered neural networks?

If I have a multi hidden-layered neural network that is getting a better approximation for a function than a single one, does that mean that there is something "fishy" about my multi layered one ...
2
votes
1answer
91 views

Characterizing the exponential savings in active learning

Let $H$ be a hypothesis class with VC dimension $d$. In supervised learning, we need almost $O(\frac{d}{\epsilon})$ random labelled examples to return a hypothesis within $\epsilon$ from the target ...
7
votes
1answer
235 views

Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning?

I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics). I am particularly ...
2
votes
0answers
72 views

What mathematical models can analyze and optimize such message passing system?

I look for a mathematical model that can accommodate, analyze and suggest optimizations for a system that can be humanly described as message passing black box programs to which where optimal message ...
2
votes
1answer
115 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}$. ...
1
vote
0answers
21 views

Identifying ambiguities in inductively learned concepts

I'm looking at ways in which "ambiguities" can be identified in labeled training data by a system undergoing some sort of inductive learning process. Do you know if there is any literature on this ...
2
votes
1answer
50 views

Are (empirical) Rademacher complexity always positive?

Rademacher complexity and empirical Rademacher complexity are used to provide upper bound on the loss of solving an learning problem. That seems to imply that Rademacher complexity and empirical ...
1
vote
0answers
64 views

Follow the Perturbed Leader for nonlinear cost functions

The famous FTPL algorithm [1] is analyzing linear cost function. Is there any generalized proof for nonlinear functions known? Note that in the last paragraph of [1] it says "It would be great to ...
1
vote
1answer
40 views

direct connection between gradient descent and follow the (perturbed) leader algorithm or weighted majority?

Is there a direct conversion between gradient descent ([1], Alg 1 ) and any of the following algorithms? 1) Weighted Majority: http://onlineprediction.net/?n=Main.WeightedMajorityAlgorithm 2) ...
2
votes
1answer
48 views

Are there closed-form expressions providing the VC-dimension for the multi-class case for different classifiers?

So far, I've only encountered the VC-dim for binary classifiers. I'm interested to learn how this notion can be extended to the multi-class case. Are there expressions that provide bounds on the ...
2
votes
0answers
43 views

Cellular neural networks

I'm a new at the cellular neural network, which is a special case of the recurrent neural network: my questions are: I understand the implementation of Chua circuit for the CNN, but I still need to ...
9
votes
2answers
226 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 ...
2
votes
0answers
74 views

Do Genetic Algorithms Expect a Independent Search Space

Genetic Algorithms seem like multiple simulated annealing instances, augmented with a crossover genetic operator. The crossover operator selects predefined genes from two different parent solutions to ...
0
votes
0answers
28 views

Are there other names for multilayer perceptrons or multidimensional interpolants based on Kolmogorov's approximation work?

Are there other names for multilayer perceptrons that are used outside of the neural net community? At its core, multilayer perceptrons form a multidimensional interpolant of the form $$ ...
1
vote
0answers
101 views

How to define deep learning? [closed]

Ive read some articles about deep learning but I found its hard to provide a clear definition of deep learning. For me its like an intelligent feature selection method. But it seems that its not ...
4
votes
0answers
91 views

extracting/ exploiting similarity of SAT instances by solver

suppose that two SAT formulas on different variables $F_1, F_2$ are given on the input that are known to be true and the problem is to build an algorithm that finds a solution to each. the formulas ...
2
votes
0answers
72 views

Fast rates — cleanest proof

Fast rates generally refers to generalization bounds interpolating between the $1/n$ consistent rate and the $1/\sqrt n$ agnostic rate. I am aware of two basic approaches for obtaining these: (1) ...
2
votes
1answer
112 views

Doubt in John Langford's “Tutorial on Practical Prediction Theory for Classification” paper

I am reading John Langford's paper on practical prediction theory (link), and I have the following doubt with definition of Binomial Tail inversion. The paper says that binomial tail inversion is the ...
0
votes
1answer
48 views

How to define the _regret_ in multiagent systems? Any good definition please?

I am reading this book. In chapter 7, section 7.5 page 240 (in the pdf), the authors defined (definition 7.5.1) the regret as being the difference between the average per-period reward the agent ...
0
votes
0answers
47 views

What's the meaning of the class indicator matrix when transforming the class label matrix into it in canonical correlation analysis?

When using canonical correlation analysis (CCA), we can integrate the dataset and label information via transforming the class label matrix Y into the class indicator matrix T. Such as: $T = ...
2
votes
0answers
133 views

How useful is program search in the field of programming-language theory?

I've been thinking: computing systems such as the Lambda Calculus and its variations are usually very simple and can be implemented in as few as ~80 lines of Haskell code. There is a self-interpreter ...
11
votes
1answer
193 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)$. ...
7
votes
1answer
395 views

Is testing easier/harder than learning?

How is the Property testing is related to PAC model of learning? More precisely, Let we have given a property tester, $\mathcal{A}$, for the (concept) class of function $\mathcal{F_n}$ which ...
5
votes
2answers
170 views

Learnability of constraint satisfaction problems CSPs?

This may sound more like a soft question but I am struggling to find an answer for it. While the learnability of Bayesian Networks and other graphical models are well detailed in the literature of ...
0
votes
1answer
166 views

Representation of procedural knowledge

I know that knowledge about relationships between things can be represented using ontologies and stored in some sort of file or database system. Can a network of procedural knowledge also be created ...
12
votes
3answers
1k views

When to use the Johnson-Lindenstrauss lemma over SVD?

The Johnson-Lindenstrauss lemma allows one to represent points in a high dimensional space into points in lower dimension. When finding lower dimensional spaces of best fit, a standard technique is to ...
2
votes
1answer
121 views

How to deal with concept classes with exponential value of VC dimension

Let $C$ be a concept class with VC dimension $d$ exponential to the input size (i.e number of variables represented in each concept $c\in C$). I am looking for papers/resources/suggestions of how ...
3
votes
1answer
123 views

Is this variant of PAC learning known?

Here is a problem I've never seen, in a model similar to the PAC model. It asks a similar question to PAC learning, but wishes to optimize, rather than learn. I wonder if this problem is known, has ...
3
votes
1answer
199 views

Objective function for stochastic optimization

Stochastic Optimization problems in general deals with random variables in the 'loss function'. Incase of a Deterministic optimization problem with basic objective $\parallel Ax-b \parallel_2^2$, we ...
5
votes
0answers
155 views

Complexity of the Transductive SVM training problem

The Transductive Support Vector Machine training problem is a non-convex mixed integer programming problem: Transductive Support Vector Machine training problem. $$ \begin{align} ...
1
vote
3answers
245 views

Which algorithms have been proposed to learn the architecture of a deep neural network?

Yoshua Benhgio's Learning Deep Architectures for AI book mentions that we should [...] strive to develop learning algorithms that use the data to determine the depth of the final architecture. ...
3
votes
1answer
177 views

Using Indicator Functions as Transfer Functions for Neural Networks

Does there exist any theory (other than Cybenko's proof of the Universal Approximation Theorem with sigmoids) advocating the use of indicator functions as transfer functions for machine learning with ...
3
votes
0answers
156 views

Practical Implications of Kolmogorov's Result on the Universal Approximation Theorem with Neural Networks

After having read matus's beautiful answer in this thread explaining (among other things) Kolmogorov's result regarding the Universal Approximation Theorem with Neural Networks, I wonder: if just ...
1
vote
0answers
79 views

Generalization Issues with Practical Suggestions from Universal Approximation Theorem with Neural Networks

After having read matus's beautiful answer in this thread explaining (among other things) Cybenko's proof of the Universal Approximation Theorem for Neural Networks, I wonder: if we use a piecewise ...
2
votes
0answers
152 views

Expected probability of error in Vapnik's book

In Vapnik's book "Statistical Learning Theory", Theorem 10.5 states that - for a Support Vector Machine - the expected probability of error (of the optimal hyperplane) is upper bounded by $1/(l+1)$ ...
6
votes
1answer
177 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 ...
1
vote
1answer
94 views

Reference for Dudley's chaining integral

Dudley's chaining integral is commonly used to bound Rademacher complexities. I recall seeing several papers give this as the reference ...
6
votes
0answers
107 views

Branching Boosting Algorithms

Long/Servedio showed AdaBoost/etc doesn't perform well under noisy environments, but that branching forms of boosting do. Can any point me to a list of branching boosting algorithms, or a reference ...
3
votes
0answers
49 views

Lower Bound on Zero-order Regret

Here is a brief summary of the experts framework: Given $n$ experts who either give correct or wrong advice for each round $t\in [T]$, an algorithm is required to give a best prediction for each round ...