Questions tagged [machine-learning]

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

Filter by
Sorted by
Tagged with
-4
votes
0answers
49 views

Can super computers solve Mega Chess Problems

mega chess problems: Dots represent number of pieces on a square. Think it as a kind of 3D chess. Think that pieces on a chess square can stay top of each other(only its own kind). You can move them ...
0
votes
1answer
67 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
55 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; ...
7
votes
1answer
168 views

About assumptions needed to get convergence of stochastic gradient methods on non-convex objectives

What are the minimal conditions we know of under which we can prove that a stochastic gradient based algorithm can convergence to criticality on a non-convex objective? Are there any necessary ...
-3
votes
0answers
39 views

Four way competition for Machine Learning PhD admission. Which background increases the odds of getting in? [migrated]

Let's say there are students from four backgrounds (Mathematics, Applied Mathematics, Computer Science and Statistics) all from top programs. They are applying to a machine learning PhD program at a ...
-4
votes
0answers
37 views
5
votes
1answer
347 views

Solving “all-marginals” problem for independent sets on grid

Suppose I have a distribution over independent sets on an $n\times n$ grid where the probability of independent set occupying nodes $(i_1,j_1),\ldots,(i_k,j_k)$ is proportional to $\lambda_{i_1,j_1}\...
2
votes
2answers
142 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
77 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 ...
52
votes
5answers
5k views

What kind of answer does TCS want to the question “Why do neural networks work so well?”

My Ph.D. is in pure mathematics, and I admit I don't know much (i.e. anything) about theoretical CS. However, I have started exploring non-academic options for my career and in introducing myself to ...
2
votes
1answer
153 views

Learning from derivative data

In many machine learning algorithm, it is often assumed that outputs of unknown function and their corresponding inputs are given to estimate the unknown function. However, I wonder whether there ...
1
vote
0answers
46 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 ...
2
votes
1answer
164 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 ...
0
votes
0answers
56 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 ...
6
votes
2answers
495 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 ...
0
votes
1answer
481 views

What kind of reinforcement learning is MENACE?

The famous MENACE matchbox computer for playing tic-tac-toe, invented by Donald Mitchie, is an early example of a reinforcement learning algorithm. Here is a description: ...an interesting machine ...
1
vote
0answers
52 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 ...
0
votes
1answer
131 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 ) } \|...
1
vote
0answers
64 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, ...
10
votes
3answers
503 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 $\...
1
vote
0answers
118 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
1answer
92 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 ...
2
votes
1answer
392 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 ...
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 ...
4
votes
2answers
385 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 ...
1
vote
0answers
77 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 ...
3
votes
1answer
73 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 ...
4
votes
2answers
3k views

What is the best place to get BibTeX entries for ICLR and other machine learning papers?

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 ...
0
votes
0answers
103 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 ...
30
votes
10answers
2k views

Great algorithms, machine learning and no linear algebra

I teach an advanced algorithms course and would like to include some topics related to machine learning which will be of interest to my students. As a result, I would like to hear people's opinions of ...
4
votes
1answer
180 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
74 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 ...
0
votes
1answer
27 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
70 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
225 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$-...
28
votes
1answer
1k 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"...
4
votes
1answer
863 views

VC dimension of intersection of half-spaces

Define $$l_i(x) := \text{sgn} \left( w_i^\top x - b_i \right)$$ for $i=1,...,n$, where $x \in \mathbb{R}^d$. Then define the classifier $$ g(x) := \max \{ l_1(x),..., l_n(x) \}$$ which represents ...
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 ...
0
votes
1answer
84 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 ...
1
vote
1answer
111 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$ ...
2
votes
1answer
107 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+...
0
votes
0answers
21 views

Is there a stochastic/online version of the GLM-Tron algorithm?

The GLM-Tron algorithm appeared in Theorem $1$ in this paper, https://arxiv.org/pdf/1104.2018.pdf Is there a stochastic version of this? (...essentially something that will randomly sample a few ...
1
vote
2answers
3k views

Derive logitboost using the logistic loss function

An additive model constructed using the exponential loss function $$L(y, f (x)) = \exp(−yf (x))$$ gives Adaboost. How can we derive the corresponding additive model (known as logitboost) using ...
1
vote
0answers
83 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
46 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
144 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 $\...
2
votes
1answer
125 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....
3
votes
0answers
99 views

Do features always induce a metric?

It is well-known in functional analysis that an inner product always induces a norm and a norm always induces a metric, and the reverse directions do not hold in general. I am wondering if a similar ...
2
votes
0answers
132 views

Crime prevention using graph theory and machine learning

I am looking for a way to the model the incidence of crime among a network of individuals. Part of it will use machine learning, and part of it will have to resort to some graph theoretic ...
2
votes
1answer
99 views

Stochastic gradient methods and risk of neural nets

Under many situations it is currently provable that we can minimize the risk of neural nets using stochastic gradient based algorithms. For example : https://arxiv.org/abs/1811.03804, https://arxiv....