Theoretical questions about Machine learning, especially Computational Learning Theory, including Algorithmic Learning Theory, PAC learning, and Bayesian Inference
8
votes
1answer
460 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?
1
vote
0answers
23 views
Variability of gradient estimates and convergence rate in stochastic gradient descent/ascent
I am aware that convergence in stochastic gradient problems is very sensitive to the variance of your gradient estimator. One issue I'm running into is that the gradient is a random vector and so ...
1
vote
0answers
49 views
Ranking problem (single instance before others)
Suppose I am trying to learn function $f$ for a ranking-like objective:
The mapping: ranking one element at the top and the rest at the bottom.
More formally, suppose each input instance $I_i$ ...
-2
votes
0answers
20 views
What is a general equation for STDP learning in an SNN?
I have been reading many articles on SNNs, and I understand the different instances of STDP such as locality, boundedness etc. But what is the general equation for such a model? For example, ...
-4
votes
0answers
34 views
machine learning, linear regression, gradient descent [migrated]
I started learning ML and had stuck with the question "why do we need to iterate gradient descent algorithm, why we can't equate gradient to zero and find all local minimums?".
After that I figured ...
1
vote
1answer
131 views
What is the best place to get BibTeX entries for machine learning?
dblp seems the best i found so far (as also mentioned in the comments and in What is the best place to get BibTeX entries for computer science articles ?) but even there some papers from NIPS ...
-1
votes
0answers
11 views
How to use/modify Broad Learning System for image classification?
I have recently studied a paper about Broad Learning System (BLS) which is an efficient system of learning without deep architecture. It is fast as compared to Deep Learning Systems because it expands ...
4
votes
1answer
100 views
“Learning” when test and train distributions don't match
We know that the theory of PAC-learning is distribution-free, i.e. assuming that the test and train distributions are the same, we have guarantees on learning the hypothesis.
Question: what if the ...
1
vote
0answers
60 views
Learnability of under some characteristics of the distribution
TLDR; is there any results showing that more concentrated (or easier) distributions are easier to learn?
In PAC-learning, the guarantee is given for any underlying distributions. But in reality, we ...
1
vote
0answers
50 views
To what extent supervised learning ERM learn first-order knowledge
Suppose I have a collection of (hidden) first-order rules:
$$
\mathcal{R}: \{ Q_i(x) => P_i(x) \}_{i=1}^{k}
$$
all defined over $x \in \mathcal{X}$.
I can use these rules and (automatically) ...
3
votes
1answer
108 views
Tighter Probability Bounds
Let $\mathcal{F}$ be a class of binary functions on a probability space $\Omega$. For $f \in \mathcal{F}$, let $P(f) =\mathbb{E}(f(Z))$ and $P_n(f) = \frac{1}{n} \sum_{i=1}^n f(Z_i)$ where $Z_i$'s are ...
5
votes
1answer
123 views
Universal Approximation - Are ReLUs discriminatory?
In Cybenko's elegant proof of the Universal Approximation Theorem (UAT) he proves that single hidden layer neural networks (with linear output layer) are universal approximators whenever their ...
3
votes
1answer
115 views
PAC-learning bound with epsilon-cover of hypothesis class
In this video at 43:00, a version of the PAC bound for generalization error $\epsilon$, which I hadn't seen before, is quoted:
$$\epsilon^2 < \frac{\log{|H_\epsilon|} + \log{1/\delta}}{2m}$$
...
0
votes
1answer
40 views
About using smoothness of the Hessian for getting to approximate criticality of a non-convex objective
Is there any algorithm which shows that under the assumption of Lipschitz smoothness of the Hessian of a non-convex function one can get to its critical point faster?
4
votes
2answers
178 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 ...
0
votes
1answer
162 views
Why semi-gradient is used instead of the true gradient in Q-learning?
In reinforcement learning, with function approximation, a popular cost function is the Mean value error.
This involves a target value V_pi and a current value estimate V_hat.
When deriving the update ...
2
votes
1answer
76 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 ...
4
votes
1answer
139 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 ...
0
votes
0answers
40 views
How hard is nearly Bayes optimal reinforcement learning?
Consider a set of $n$ MDPs (Markov decision processes). An MDP $M$ is selected from this set according to some probability distribution $\xi$ and then interacts with a fixed policy $\pi$ for time $T$ ...
1
vote
1answer
137 views
What is the VC dimension of Turing machines with specified maximum size?
Note by "maximum size" in the question I'm referring to the size of the Turing machine's state machine.
I chose Turing machines in the question to make the question concrete, but I'm also more ...
6
votes
2answers
233 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 $\...
5
votes
0answers
101 views
Learning hidden variable distribution
Consider a set of $k$ continuous variables. Each variable $x_k$ is associated with a hidden distribution from which its value is sampled independently of other variables. I am given a set of ...
6
votes
0answers
102 views
Universal approximation theorem of second order
The universal approximation theorem (https://en.wikipedia.org/wiki/Universal_approximation_theorem)
informally states that up to several conditions, any function can be approximated by a shallow ...
-1
votes
1answer
93 views
What is the name of the category of problems that can only be solved with machine learning? [closed]
Wikipedia defines machine learning as the "field of computer science that gives computers the ability to learn without being explicitly programmed". A common example of a problem which machine ...
3
votes
0answers
61 views
Is there some research about infinitely many-armed bandit with non-stationary assumption?
Is there some research about infinitely many-armed bandit with non-stationary assumption? I have found the paper about infinitely many-armed bandit under stationary (or stochastic) assumption. And I ...
0
votes
0answers
55 views
Classification time complexity (NOT training time complexity) of different algorithms
I would like to know, what is the classification time complexity of these algorithms given the number of features d
logistic regression (I suspect O(d))
Support Vector Machines (Have no idea, read ...
2
votes
2answers
107 views
Can machine learning algorithms be trained to discard nonsense?
Afaik, the problem with many machine learning algorithms is that they will often label nonsense into some categories.
What measures can one take to discard nonsense results?
Eg. if you have a bot ...
1
vote
1answer
71 views
References for the computational complexity of training neural networks
I'm looking for a good review paper or book chapter that offers an accessible introduction to the computational complexity of training neural networks for classification problems.
In particular, I'm ...
9
votes
5answers
624 views
Can neural networks be used to devise algorithms?
After the newer and newer successes of neural networks in playing board games, one feels that the next goal we set could be something more useful than beating humans in Starcraft. More precisely, I ...
0
votes
1answer
56 views
Learning a discrete distribution in $\ell_r$ norm
Let $P=(p_1,\ldots,p_d)$ be a distribution on $[d]$. Given $n$ iid draws from $P$, we construct some empirical estimate
$\hat P_n=(\hat p_{n,1},\ldots,\hat p_{n,d})$. Let us define the $r$-risk
by
$$ ...
4
votes
1answer
408 views
Understanding the No Free Lunch Theorem
I came across the No Free Lunch Theorem via Jürgen Schmidhuber's paper on Universal Search and there were a couple remarks on NFL which stood out
to me. The first was that we can't define a uniform ...
0
votes
0answers
54 views
Approximation Capabilities of Partially Connected Neural Networks
A well known result (Cybenko 1989) holds that a single-layer feedforward "multilayer perceptron" style network:
$f(x) = \sum_{i=1}^{K}\alpha_{i}\sigma(w_{i}^{T}x + \theta_{i})$
Can approximate any ...
1
vote
1answer
77 views
$L_\mathcal{D}(A(S)) \le 0.1$ with prob at least $0.9$ implies PAC learnability
Suppose we have a hypothesis class $\mathcal{H}$ that is non-uniform learnable via sample compelxity function $m_{\text{NUL}}:[0,1]^2 \times \mathcal{H} \rightarrow \mathbb{N}$.
If we define $\mathcal{...
13
votes
0answers
186 views
Differential privacy and data poisoning
A differentially private algorithm takes datasets containing inputs and produces randomized outputs, such that no small change in the dataset can shift the distribution of outputs by too much. This ...
4
votes
1answer
321 views
Autoencoders and information compression
Disclaimer: I know very (very) little about deep nets, besides what an introductory course on machine learning would teach on neural networks, and skimming some paper abstracts and introductions.
If ...
0
votes
0answers
45 views
Wavelet based Non linear optimization technique
I am outlining a method for solving Non Linear optimization problems.
Consider the system of equations:--------------------------------- 1
f1(a0, a1, a2, a3 ......... an) = 0
f2(a0, a1, a2, a3 ........
12
votes
1answer
450 views
Is BPP vs. P a real problem after we know BPP lies in P/poly?
We know (for now about 40 years, thank Adleman, Bennet and Gill) that the inclusion BPP $\subseteq$ P/poly, and an even stronger BPP/poly $\subseteq$ P/poly hold.
The "/poly" means that we work non-...
1
vote
0answers
124 views
Convergence of Q-learning with non-linear function approximation
Q-learning is a well-known algorithm in Reinforcement learning which enjoys great empirical success but with insufficient theoretical understanding. In the tabular setting, it is known that if each ...
23
votes
1answer
937 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"...
3
votes
2answers
367 views
Learning a coin's bias (localized)
It's well known that the minimax sample complexity for estimating the bias $p$ of a coin to additive error $\epsilon$ with confidence $\delta$ is
$\Theta(\epsilon^{-2}\log(1/\delta))$. What if we ...
4
votes
1answer
184 views
Adversarial Machine Learning, Learning with (Malicious) noise
I am reading some old papers regarding Learning With Malicious Noise. In one of them, Learning in the presence of Malicious Errors, by Kearns and Li $[1]$ (https://www.cis.upenn.edu/~mkearns/papers/...
7
votes
1answer
286 views
Applications of Takens' theorem to TCS?
My apologies if the question is a tad vague—I did try to search the literature for more, but didn't find anything (the similarity between the keywords "Takens" and "taken" on Google may be partly to ...
4
votes
1answer
182 views
Textbook/resources for a beginning researcher in (Machine) Learning Theory
I'm looking to begin understanding basic concepts, notions, results and definitions in the area of Computational Learning Theory (or the theory of Machine Learning), as is done in the theoretical ...
1
vote
0answers
109 views
Boolean functions with high query complexity for PAC learning
The most general theorem for PAC learning of Boolean functions that I am aware of is the theorem in section 3.4 of Ryan O'Donnel's book where its basically shown that Boolean functions whose Fourier ...
3
votes
0answers
694 views
Universal Approximation Theorem for non-sigmoidal activation functions
The most cited Universal Approximation Theories for multi-layer feedforward neural networks by Cybenko (1989) and Hornik (1991) assume the activation functions of the network to be sigmoidal. However, ...
1
vote
0answers
65 views
Off-policy Monte Carlo Control
The off-policy Monte Carlo control algorithm to learn the optimal state-value function $V^*$ is given as follows, which is obtained from Sutton's book.
I have three questions concerning this ...
24
votes
2answers
620 views
If machine learning techniques keep improving, what's the role of algorithmics in the future?
Let's look at the future some 30 years from now. Let's be optimistic and assume that areas related to machine learning keep developing as quickly as what we have seen in the past 10 years. That would ...
-2
votes
1answer
96 views
Supervised learning from “bad” examples - ANN [closed]
I want to recommend one of three possible treatments for a patient, based on his blood values A, B and C.
To solve this task, I have constructed a supervised feed-forward NN with back-propagation (...
4
votes
1answer
273 views
Examples of Fat-Shattering Dimension
What are some good examples for analysis of a class's Fat-Shattering dimension?
By (Alon et al) I know that the Fat-Shattering Dimension characterizes the learnability of real-valued function classes ...
-1
votes
1answer
251 views
What is the connection between adversarial learning in machine learning and program synthesis?
In particular, I'm considering the similarities in Generative Adversarial Networks and Combinatorial Sketching for Finite Programs.
In the first paper, our concern is with learning generator ...
