Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [machine-learning]

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

2
votes
1answer
82 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
70 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
104 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 ...
6
votes
0answers
76 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 ...
2
votes
1answer
92 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....
2
votes
1answer
57 views

Empirical Rademacher averages versus Hoeffdings bound

Let $M$ be finite set with $n$ distinct elements. I want to probalistically approximate the relative counts $\frac{|P(Q)|}{|M|}$ of $Q \subseteq M$, where $P(Q) = |P \cap M|$. An upper-bound for ...
2
votes
0answers
33 views

Lower bounds for SRM?

This question is about structural risk minimization and model selection. Let $H_n$ be the collection of all binary classifiers on some fixed set with an $n$-bit description length in some fixed ...
2
votes
1answer
95 views

Minimization version of matrix p-norms?

I considered a minimization version of matrix p-norms, defined for a matrix $A$ by $$ f_p(A)= \min_{x\neq 0} \frac{||Ax||_p}{||x||_p}. $$ Notice that $f_p(A) = 0$ if and only if $A$'s columns are ...
1
vote
0answers
47 views

Average margin bounds for separable SVM

Suppose we're training a linear separator in the realizable PAC setting. Given $m$ labeled examples $(x_i,y_i)$ in $\mathbb R^d\times\{-1,1\}$, a (consistent) linear separator is a vector $w\in\mathbb ...
1
vote
1answer
53 views

Sample complexity for learning Boltzmann Distribution parameters

I am trying to think through the number of samples that I would need to estimate the parameters of a Boltzmann partition function to a desirable precision. Suppose that there are N possible states ...
0
votes
0answers
40 views

Function that maps non-linear distribution to normal distribution while maintaining distance

I have a collection $X$ of 10 million $(x,y,z)$ 3-tuples, where $x$, $y$, and $z$ are all numbers between 0 and 1. The distribution of $x$, $y$, and $z$ values are complex, and the distributions of $...
3
votes
2answers
163 views

How can AIC converge in the limit when even 2 parameter models can have infinite VC dimension?

AIC-based model-selection converges to zero error in the limit, and also has finite-sample convergence that is rate-optimal with respect to worst case minimax error [1]. (Note that AIC refers to ...
1
vote
0answers
43 views

Is there a theoretical guarantee that an autoencoder $g$ has $I(x;g(x)) \approx H(x)$?

I know that in general, a function $g$ can be a good auto-encoder (i.e., $g(x) \approx x$ for $x \sim D$) and on the same time $I(g(x);x)$ is small. This is the case when $g$ forms a good correlation ...
3
votes
1answer
56 views

Examples of nontrivial non-discriminatory functions

I am reading Cybenko's "Approximation by Superpositions of a Sigmoidal Function". The paper defines a discriminatory function as: $\sigma$ is discriminatory if for a measure $\mu$, \begin{align} \int ...
8
votes
1answer
476 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
26 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
50 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$ ...
1
vote
1answer
277 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 ...
4
votes
1answer
104 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
51 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
120 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
183 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
184 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
42 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?
5
votes
2answers
309 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 ...
1
vote
1answer
381 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
81 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
167 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
59 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
148 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
272 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
104 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
132 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
61 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
114 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
73 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
633 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
447 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
102 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
197 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
451 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
46 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 ........
13
votes
1answer
518 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
149 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 ...
26
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"...