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 [lg.learning]

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

2
votes
1answer
87 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 ...
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 ...
4
votes
1answer
71 views

What is the current state of the art in black-box grammar induction?

Grammar induction of Context Free Languages seems to be a very well researched field. I would like to know the current state of the art in inducing a Context Free Grammar (I am reading up Higuera's ...
2
votes
1answer
58 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 ...
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 ...
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
14 views

On-policy/Off-policy Offline/Online Evaluation: Which would be an example of Online Off-Policy Evaluation?

In the context of the following question: off-policy and offline policy reinforcement learning , it can be concluded that off-policy/on-policy learning can be orthogonal to an online/offline sampling ...
5
votes
1answer
93 views

Is Bayes optimal RL of a finite set of DFAs feasible?

Let $Q$ be a finite set of states, $\Sigma$ a finite alphabet, $q_0\in Q$ the start state and $F\subseteq Q$ the set of accepting sets. Let $\{\delta_k:Q\times\Sigma\rightarrow Q\}_{k=1}^n$ be a set ...
3
votes
1answer
108 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
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?
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
52 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) ...
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 ...
4
votes
1answer
168 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
133 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
273 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
103 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
42 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
122 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 ...
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"...
2
votes
0answers
121 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 ...
3
votes
2answers
375 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
317 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
177 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
82 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
117 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 ...
4
votes
0answers
925 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
315 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
100 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
169 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
96 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
94 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
81 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
368 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
95 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
155 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" ...
6
votes
0answers
155 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
62 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
103 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
132 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
310 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
63 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
306 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\|$...