# Questions tagged [machine-learning]

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

305 questions
Filter by
Sorted by
Tagged with
27 views

### What to choose Deep learning or Artificial Intelligence after learning basic Machine Learning?

I Learned basics from Machine Learning and its algorithm and I wanted to choose the on subject from deep learning and artificial neural network so I am confused which one to choose can any one guide ...
28 views

### Algorithm to decide percentage of data from previous node, current node and forward nodes

I have a graph-like structure, let's say there is one node $C$, who has 2 predecessors $A,B$ and 1 successor $D$. I have a value of $C$. Let's say value at $C=30$%. From this, I could infer that I ...
31 views

### Online to batch sample complexity. Conservative assumption on online algorithm needed?

To the best of my knowledge, typical approaches to convert an online algorithm with mistake bound into a batch algorithm with PAC bound make the following assumption. A1: The online algorithm is ...
36 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'...
93 views

521 views

### Results on universal approximation for learners other than ANNs

I have an applied machine-learning and statistics background, and when I read the Universal approximation theorem, which (in the context of the learning theory of ANNs - Artificial Neural Networks) ...
314 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$ ...
109 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 ...
279 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 ...
45 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 ...
441 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}$$ ...
72 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 ...
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 ...
13k views

### Why can machine learning not recognize prime numbers?

Say we have a vector representation of any integer of magnitude n, V_n This vector is the input to a machine learning algorithm. First question : For what type of representations is it possible to ...
197 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 ...
177 views

166 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 ...
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 ...
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 ...
156 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 ...
47 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 ...
166 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 ...
65 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 ...
567 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 ...
512 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 ...
53 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 ...
137 views

129 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 ...
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 ...
421 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 ...
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 ...
550 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 ...
78 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 ...
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 ...
5k 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 ...
108 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 ...
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 ...
257 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 ...