Questions tagged [machine-learning]
Theoretical questions about Machine learning, especially Computational Learning Theory, including Algorithmic Learning Theory, PAC learning, and Bayesian Inference
310
questions
-1
votes
0answers
10 views
How to calculate complexity in a high dimensional space?
I'm defining a term 'complexity' relating to a specific f(), estimating 'how difficult is the given function to optimize'.
I attempted a solution in low dimension, but I might not be on the right ...
4
votes
1answer
116 views
Is there an equivalent to VC-dimension for density estimation as opposed to classification?
VC-dimension can be used to quantify the capacity for classifier models and compute generalization bounds, but is there an equivalent concept that can be applied to density estimation, e.g. to compute ...
0
votes
1answer
76 views
VC dimension for balanced binary decision trees
What is the VC dimension of all balanced binary decision tree of
depth $k$ in $\{0,1\}^d$? Does it depend on depth $k$ or dimension $d$?
1
vote
1answer
50 views
Rademacher Complexity of the Composition with an Indicator
Consider the statistical learning setting where you have an arbitrary hypothesis space $\mathcal{H}$, a data space $\mathcal{Z}$, and a bounded loss function $\ell: \mathcal{H}\times \mathcal{Z} \...
-1
votes
0answers
22 views
Feed-Forward artificial neural network memorization
In "Neural Networks Learning and Memorization with (almost) no Over-Parameterization" by Amit Daniely (2019), in the introduction it's written that
In order to memorize even just slightly ...
-4
votes
0answers
20 views
Can anyone recommend me a project idea for a ML project
I am a final year Computer Science student and I have to start working on my Final year project. I have chosen Machine learning as the field for my project but don't have any good ideas regarding the ...
7
votes
1answer
238 views
Testing for finite expectation
The mean of a positive random variable $X$ is either finite or infinite; define $J(X)$ to be $0$ in the former case and $1$ in the latter case. Claim: there does not exist a function $J_n$ from the ...
2
votes
0answers
65 views
Polynomial convergence to optimal move of the UCT algorithm. Missing proof?
This is a question regarding the theoretical convergence guarantees of the UCT algorithm, a popular variation of the Monte Carlo Tree Search algorithm (used in games, planning, reinforcement learning, ...
0
votes
0answers
39 views
Would a machine learning algorithm benefit from an “optimization oracle”?
I'm trying to understand the behavior of machine learning algorithms where the loss function is non-convex and the problem of training the ML on a specific data set is computationally hard.
Now let'...
1
vote
0answers
42 views
Is there a notion of Probably Approximately Correctness in Unsupervised Learning? [closed]
I've been learning a little bit about computational learning theory, but most of what I've seen so far is related to supervised learning. Perhaps dimensionality reduction will be touched on, but not ...
6
votes
3answers
445 views
Reference Request: Computational Learning Theory
Pretty soon I will be finishing up Understanding Machine Learning by Shai Ben-David and Shai Shalev-Shwartz. I absolutely love the subject and want to learn more, the only issue is I'm having trouble ...
0
votes
0answers
20 views
ML classification with missing inputs using joint probability distribution
I am self-studying the deep learning book by Goodfellow, Bengio and Courville(https://www.deeplearningbook.org/contents/ml.html). On page 100, it has a brief introduction to classification with ...
2
votes
1answer
101 views
Why non-uniform learnability does not imply PAC learnability?
PAC guarantees provide us a a learning algorithm $A_n(\cdot)$ and sample complexity bound $n_{\mathcal{F}}(\epsilon,\sigma)$ that ensures
$
P\left[L_P(A(\mathcal{D}^n))-L_P(f^*)\leq \epsilon\right]\...
0
votes
0answers
38 views
What is an example of a hard learning problem in the noisily realizable setting?
Suppose $f_{\vec{w}} : \mathbb{R}^n \rightarrow \mathbb{R}$ is a function parameterized by some parameter vector $\vec{w}$. Now for some true parameters $\vec{w}^*$, some noise function $\xi : \mathbb{...
3
votes
0answers
112 views
Understanding Dudley Chaining Argument for Rademacher Bound
I follow the proof of the Dudley chaining/metric entropy bound of the (empirical) Rademacher complexity, but I don't have any intuition for why this bound should be true. In particular, I don't know ...
7
votes
1answer
286 views
Complexity of constructing minimum depth decision trees
I am interested in the computational complexity of
Problem 1: Given a finite, non-empty set $J$, given $A, B \subseteq \{0,1\}^J$ such that $A \cap B = \emptyset$, and given $n \in \mathbb{N}$, does ...
0
votes
0answers
48 views
Using martingale arguments to prove convergence of iterative algorithms
Can someone give me typical/educative examples of how martingales can be used to prove convergence of an iterative algorithmS?
The examples I know of can only go so far as to show that there exists ...
4
votes
0answers
76 views
Status of the Junta Problem (soft question)
Does the learning theory community in general believe that juntas can be learned in polynomial time?
The naive algorithm works in quasi-polynomial time. MOS's paper shows how to solve the junta ...
0
votes
0answers
21 views
Showing SGLD has risk minimization ability vs showing that SGLD hits SOSP
I am comparing the following 2 results,
Theorem 2.1 here https://arxiv.org/abs/1702.03849
Theorem 4.3 here https://arxiv.org/abs/1904.13016
Given that the 2017 paper already shows that SGLD can ...
5
votes
1answer
198 views
Latest word on cross validation?
It's a standard result leave-one-out cross-validation is an unbiased estimator of the risk (see, e.g., Lemma 4.1 in Mohri, Rostamizadeh, Talwalkar). Are there any "better" results? Such as, say, with ...
4
votes
0answers
181 views
Is this a known learning problem?
Let $(\mathcal{X},\rho)$ be a metric space (say, $\mathcal{X}=[0,1]$ with the Euclidean metric). Let $\alpha:\mathcal{X}\to[0,1]$ be unknown. Suppose that $\mathcal{X}$ is endowed with a distribution $...
0
votes
1answer
117 views
Singular Value in Machine Learning
I'm reading the paper (http://proceedings.mlr.press/v9/glorot10a/glorot10a.pdf) from Glorot and Bengio. There is something that I don't understand at the abstract section on page 1.
"Training may be ...
1
vote
1answer
56 views
Characterize a point cloud
Background: I have multiple point clouds (sets of objects) $\{S_i\}_{i\in\mathbb{N}}$ of variable size and "purity" (meaning that some sets contain very similar objects, some show a high diversity; ...
4
votes
2answers
172 views
What are some good resources for strengthening my theoretical foundation for machine learning?
I'm a computer science major and I'm taking a lot of machine learning courses. I'm finding that my theoretical foundation on subjects like calculus and linear algebra are not as strong as I'd like ...
4
votes
1answer
79 views
Terminology and references for a learning model
Let's say we're doing regression over $[0,1]^d$ -- either in the PAC sense with bounded-range agnostic noise or in the more classical-statistics sense with additive Gaussian noise. Suppose further ...
1
vote
0answers
49 views
Average smoothness learning rates
This question is somewhat related to this one. There are many results in statistics where convergence rates (including minimax ones) are given in terms of the smoothness properties of the underlying ...
0
votes
0answers
67 views
representation of concept classes and pac learning
I was reading the book of Kearns and Vazirani and I didn't completely understand the following:
Let C be a concept class and suppose we want to PAC learn C, they say first consider a larger ...
1
vote
0answers
54 views
Which algorithms can be used to measure similarity for two very different languages?
recently I have read this paper, A Survey of text similarity approaches, and I discovered that there are a lot of algorithms that can be used to measure similarity.
At present I am applying the ...
1
vote
0answers
68 views
Sentences in what kinds of grammar in the Chomsky hierarchy can be parsed by an LSTM of a given size?
Given
an LSTM $N$ of a given size $A$,
a sentence $S$ with a given number of words $B$,
a Chomsky grammar hierarchy level $C$ in 0-3,
a Chomsky grammar $G$ of level $C$ of size $D$,
A given fixed, ...
1
vote
0answers
131 views
Minimum number of hours of speech needed to train a neural net to recognize speech [closed]
From a theoretical computer science point of view, is there a lower limit on the number of hours of speech needed to train a neural net to translate speech to text? An estimate from CMU is 3000-5000 ...
2
votes
0answers
84 views
Which computational framework lies behind the Chinese “Social Credit System”?
BACKGROUND
The Social Credit System is a data-driven reputation system which draws on several sources to label various entities, namely businesses and individual citizens, with a trustworthiness ...
1
vote
0answers
79 views
Agnostic query learning of decision trees
Gopalan, Kalai, Klivans gave an algorithm
https://dl.acm.org/citation.cfm?id=1374376.1374451
for agnostically learning decision trees $h:\{0,1\}^n\to\{0,1\}$ under the uniform distribution given ...
2
votes
1answer
168 views
How many samples are needed to reconstruct a path?
Consider an input set of vertices $V$ and vertices $s,t\in V$.
The goal is to learn some unknown shortest path from $s$ to $t$; the set of edges of the graph is hidden at first and there may be ...
3
votes
1answer
78 views
Agnostic query learning for DFAs
Angluin's membership+equivalence query algorithm allows to efficiently and exactly learn a target $n$-state DFA. But what if the target DFA is huge, or the target concept is not even a regular ...
0
votes
0answers
111 views
Lower bound to agnostic learning with membership queries
Setting:
Let $X$ be a finite set and $C = \{0, 1\}^X$ a finite family of classifiers on $X$. Fix an $f \in \{0, 1\}^X$ not in $C$, a (possibly randomized and adaptive) learner $A$ has access to a ...
4
votes
1answer
325 views
What was the significance of Leslie Valiant's, “A Theory of the Learnable?”
It seems like two of the main takeaways were that there is a natural limit to what computers can learn, and learning is bounded by polynomial algorithms. Why was his paper significant in the broader ...
-1
votes
2answers
83 views
Machine Learning Algorithm To Fill Data Holes
I'm having trouble finding a good place to begin with this. I'm just looking for a name or point to start researching a
Let's say I have 1000 records. 10 of these records are only 90% complete. The ...
2
votes
1answer
97 views
References on generalization bounds
I'm looking for references (books, papers, lecture notes etc) on generalization bounds and their proofs. Specifically, I'm looking to fully understand the technique of defining a hypothesis class (or ...
0
votes
1answer
30 views
Classic Neural Network Layout for regression: is the score function derivable?
I need to solve an optimization problem based on a function f(X). This function is not known, but it can be estimated from a training set. So first I train a model, then I get the score function f(X), ...
2
votes
0answers
80 views
how is time complexity defined in computational learning theory
In general, when we say an algorithm $A$ PAC learns $C$ in time $t$, we say $A$ takes time $t$ before outputting a hypothesis $h$, and the hypothesis can be evaluated (on every $x$) in time $t$.
Now ...
6
votes
1answer
278 views
How to generalize VC dimension?
Let's try to generalize the $VC$-dimension (of the class of hyperplanes) to include accuracy/error. Let $S$ be a set of points in $R^d$ and $t$ in $[0,1]$. We say that the class of hyperplanes $t$-...
0
votes
1answer
139 views
Confusion about covering number
Problem
I do not understand why larger $p$ will give a larger covering number.
Since when $p\geq q$, the corresponding hypercube is also larger (by $\| x \| _ { q } \leq n ^ { ( 1 / q - 1 / p ) } \|...
0
votes
1answer
40 views
Does fixed hyperparameters perform well regardless the number of training examples?
I'm new in this community and I don't know whether my question is proper for this community. I will delete this post if it is not proper.
I'm interested in deep learning network models and have a ...
2
votes
2answers
336 views
About learning a single Gaussian in total-variation distance
I am looking for the proof of this following result which I saw as being claimed as a "folklore" in a paper. It would be helpful if someone can share a reference where this has been shown!
Let $G$ ...
0
votes
1answer
87 views
Lower bound of real valued bounded function
Is well known that the lower bound on number of example necessary to reach a given error for concept classes $\Omega(d/\varepsilon)$ (cf. also
Agnostic PAC sampling lower bound )
I am looking for ...
2
votes
1answer
150 views
Oncina-Garcia RPNI algorithm for learning DFAs
The question refers to this paper:
ftp://altea.dlsi.ua.es/people/oncina/articulos/asspr1992.pdf
Given a sample of $p$ positive and $n$ negative strings, RPNI constructs a consistent DFA in time $O((p+...
1
vote
0answers
90 views
Complexity of low-rank matrix factorizations with rows in a simplex and outliers
Our goal is to obtain a matrix factorization in form of $M = U V'$, where $U\in\mathbb{R}^{d\times r}, V \in\mathbb{R}^{N\times r}$ and each row of $V$ satisfies
$$ \sum_{j}(V)_{ij}=1, (V)_{ij}\ge 0 $$...
1
vote
0answers
65 views
Back-propagation for computing derivative of certain line integral
Consider a function F (think of neural networks) with two sets of parameters: (1) model parameters $\mathbf{w}$, and (2) input data ${\bf x} \in {\mathbb R}^d$. Fix $i \in [d]$, consider the following ...
4
votes
2answers
158 views
Are there hypothesis classes that are hard to learn but easy to test?
Let $H$ be a binary hypothesis class, it is easy to see that if $H$ is (efficiently) properly PAC learnable then it is also (efficiently) testable (here we use the standard notion of within or $\...
3
votes
1answer
145 views
Is there a gap between weak learning and PAC-learning?
For concreteness lets use the definitions of PAC and weak-learning as in the notes of Avrim Blum (http://www.cs.cmu.edu/~avrim/ML12/lect0208.txt) and also his notes on SQ-Learning (http://www.cs.cmu....
