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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Machine learning and learning theory: PAC learning, algorithmic learning theory, and computational aspects of Bayesian inference and graphical models.

3
votes
1answer
91 views

Rademacher complexity for piecewise-linear convex function

Consider a function family $$\ell(x)=\max_{1\leq k\leq K} a_k^\top x + b_k,$$ where $a_k,b_k \in \mathbb{R}^d$ are bounded in the sense of some norm and $K\geq 2$. What is the best upper bound on the ...
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?
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) ...
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 ...
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 ...
4
votes
1answer
121 views

Tight VC bound for agnostic learning

The following result is supposedly known. However, the proofs I am able to find all prove a weaker result with an extra log factor. Where can I find the proof of the tight bound? Theorem. Let $\...
1
vote
0answers
75 views

Reference request for the relationship between approximating degree of Boolean functions and learning algorithms

This paper (http://www.cs.columbia.edu/~rocco/Public/stoc01.pdf) from STOC 2001 is possibly the first paper to show how to convert upperbounds on the $\frac{1}{3}-$approximation degree of a Boolean ...
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 $\...
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 $$ ...
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{...
2
votes
1answer
38 views

Nonsingular regret bound for UCB

Acer et al. "Finite-time Analysis of the Multiarmed Bandit Problem" show that the Upper Confidence Bound 1 (UCB1) algorithm has expected regret bounded by $$\left[ 8 \sum_{i: \mu_i < \mu^\ast} \...
1
vote
0answers
118 views

Cluster Assignment in the Stochastic Block Model

Recently, numerous papers have been published about the stochastic block model (SBM). In the literature about SBMs, a plethora of different settings are considered. I am interested in how vertices are ...
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"...
2
votes
0answers
106 views

Oracle for Hamming distance to a secret bitvector

Let $s \in \{0,1\}^n$ be a secret bitvector. Define $f(x)$ to be the Hamming distance between $x$ and $s$. Suppose I am given an oracle for $f$, and I want to find $x$. How many queries to the ...
0
votes
0answers
15 views

A synthetic dataset that scores good only on a given set of parameters

When designing a machine-learning system, there are various parameters that have to be determined. I am interested in the following general question: is it possible to construct a dataset on which the ...
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 ...
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 ...
3
votes
1answer
148 views

Rademacher complexity and lowerbounds in learning theory

Is there any function class known whose Rademacher complexity has a non-trivial lowerbound? Can the Rademacher complexity be used to lowerbound the generalization error in any learning situation?
5
votes
1answer
81 views

What is known about learning a maximal independent set in a (very) sparse graph?

Maximal independent set is known to be hard in many meanings (hard to approximate, $W[1]$-hard, etc.). But if the number of edges is very small, then the problem becomes simpler. Here, I'm interested ...
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, ...
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 ...
3
votes
1answer
94 views

Minimax agnostic risk for Lipschitz functions

For $L>0$, let $F_L$ be the class of all $L$-Lipschitz functions on $[0,1]$. Let $D$ be a joint distribution on $[0,1]\times\mathbb{R}$, from which we sample $n$ iid copies $(X_i,Y_i)$. Given any $...
5
votes
1answer
166 views

Kleinberg-consistency of spectral clustering

Spectral clustering refers to a family of graph-based algorithms, which usually rely on a similarity function rather than a metric, though a metric $\rho(x,y)$ can always be converted to a similarity ...
5
votes
0answers
95 views

Looking for an exposition of the proof of the LMN theorem

Is there any lecture note or review paper which gives a self-contained proof of the Linial-Mansour-Nisan theorem? The exposition of that in Ryan O'Donnel's book seems to use terminology and notation ...
8
votes
0answers
89 views

Learning function with a few low-order Fourier coefficients, from uniformly random samples

Let $f:\{-1,+1\}^n \to \{-1,+1\}$ be a boolean function where all of the energy of the Fourier transform of $f$ is concentrated in a small number of low-order coefficients, say $k$ coefficients each ...
1
vote
1answer
79 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 ...
7
votes
1answer
311 views

What is the VC Dimension of the $k-$Junta class

A boolean function $f(x_1,x_2,\dots,x_n)$ is $k$-Junta if it depends on at most $k$ variables. Consider the class $\mathcal{J}_{\leq k}$ of all $k$-Juntas over $n$ variables, what is the VC dimension ...
5
votes
0answers
245 views

What precisely is the extra power afforded by using deeper nets?

For any choice of activation function (fix the choice for all the hidden nodes for both the following DNNs) do we know of functions which some $k$ (hidden layer) DNN can compute but a $(k-1)-$DNN can'...
5
votes
0answers
90 views

Adversarial distributions for PAC lower bounds

The various PAC lower bounds (realizable, agnostic, bounded noise) construct distributions supported on $d$ points, where $d$ is the VC-dimension of the hypothesis class in question. Does anyone ...
3
votes
0answers
153 views

About lower bounding the sample complexity of a distribution

Given a joint probability distribution over a finite number of random variables (each with a finite range space) of which only a certain subset is observable, is there a notion of "sample complexity" ...
5
votes
0answers
151 views

Machine learning algorithms on hypergrap models

Graphical models are a very useful tool with many applications, whereby a joint distribution of a set of random variables is modeled using only pairwise dependencies between the variables, and two ...
0
votes
1answer
68 views

The dependence of learning generalization bounds on the dimension of the instance space

Here is a popular generalization bound: If $X$ is the input space and $Y=\{0, 1\}$ is the output/label space, and there is a joint distribution $D$ defined on this space. We sample $m$ ...
3
votes
0answers
61 views

Estimate smooth vector, from dot-product queries

I have a secret $n$-dimensional vector $\mathbb{s} \in \mathbb{Z}^n$. I don't know $\mathbb{s}$; my goal is to estimate $\mathbb{s}$. I do have an oracle for the function $f_\mathbb{s} : \mathbb{Z}^...
1
vote
1answer
97 views

Average Regret Bounds for Linear Stochastic Bandits

I am reading this paper on linear stochastic bandits : http://papers.nips.cc/paper/4417-improved-algorithms-for-linear-stochastic-bandits.pdf All the results are stated in a high-probability ...
2
votes
1answer
128 views

Tolerance parameter of statistical query model and adaptivity

It seems that the reasonable assumption for the tolerance parameter of statistical query model is roughly $1/\sqrt{n}$, which is obtained from concentration inequalities (see, e.g., Definition 2.3 of ...
5
votes
3answers
301 views

Dimensionality reduction in machine learning

This is less of a question and more of a "here's my take let me know if you agree" (so I guess it might turn into a big-list?). Dimensionality reduction refers to a collection of techniques that ...
4
votes
0answers
61 views

What is the largest noise rate $\eta(n)$ for which learning parities with noise is easy?

Learning Parity with Noise (LPN) is usually stated with constant noise rate $\eta < 1/2$ on the labels, and it is believed to be hard to learn because of the high statistical dimension of the ...
0
votes
1answer
290 views

Bounding Rademacher Averages, with and without chaining

One can bound the Rademacher average $R_n(A)$ of a finite set of vectors $A\subseteq\{0,1\}^n$ using Massart's Finite Lemma: $$ R_n(A)\le \max_{a\in A}\|a\|\frac{\sqrt{2\ln|A|}}{n} $$ where $\|\cdot\|$...
4
votes
1answer
448 views

Sample complexity of distinguishing two Gaussian distributions?

Below is a description of the problem: Suppose I have two $p$-dimensional Gaussian distributions with the same covariance matrix $\Sigma$ and means $\mu_1$, $\mu_0$. And I can get $n$ samples $X_1^{(...
2
votes
1answer
78 views

How to exploit knowledge of the sampling distribution for better generalization bounds?

In the PAC learning model, suppose the learner actually knows the sampling distribution $P$. Surely this knowledge can be exploited to yield better generalization bounds -- but how? One idea is using ...
6
votes
1answer
102 views

Does learning conjunctions with malicious noise reduce to learning conjunctions with random noise?

In Feldman-Gopalan-Khot-Ponnuswami 06 the authors show that agnostically learning parities reduces to learning parities with random classification noise. They also remark (among other things) that ...
0
votes
1answer
1k views

VC-dimension of triangles in 2D space [closed]

I have been reading in multiple places (e.g. [1], section 4) that the VC-dimension of the class of triangles (in 2D space) is 7. The issue is that, for the case when 4 points lying on a straight line ...
2
votes
1answer
112 views

Characterizing the exponential savings in active learning

Let $H$ be a hypothesis class with VC dimension $d$. In supervised learning, we need almost $O(\frac{d}{\epsilon})$ random labelled examples to return a hypothesis within $\epsilon$ from the target (...
3
votes
2answers
96 views

Learning k-parities with Membership Queries and Persistent Noise

Random independent misclassification error is an inappropriate noise model for a membership query (MQ) oracle because for any noise rate $\eta<1/2$ one can eliminate noise to an arbitrary extent by ...
1
vote
0answers
275 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 ...
6
votes
2answers
332 views

Which factors make the problem of inferring the grammar difficult?

Scott Aaronson said in the paper entitled "Why Philosophers Should Care About Computational Complexity" (Please see ECCC Report: TR11-108, section 7, pp 25-31): Following the work of Kearns and ...
9
votes
2answers
434 views

Theoretical results for random forests?

Random forests have a reputation among practitioners of being among the most effective classification techniques. Yet we don't encounter them much in the learning-theoretic literature, from which I ...