# Questions tagged [lg.learning]

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

182 questions
Filter by
Sorted by
Tagged with
108 views

28 views

### How to apply Statistical Query Algorithm for class of decision list

There were some people discussing how to apply SQ algorithm on learning monotone conjunction, but I wonder if anyone knows how to apply SQ algorithm on decision list?
117 views

### VC-dimension of infinite set of triangle wave

I am searching for the VC-dimension of the following: What is the VC-dimension of the infinite set of triangle wave functions with amplitude 1 and period parameter p on points on the line? 2πarcsin⁡(...
277 views

### Is there an equivalent to VC-dimension for density estimation as opposed to classification?

VC-dimension can be used to quantify the capacity for classifier models and compute generalization bounds, but is there an equivalent concept that can be applied to density estimation, e.g. to compute ...
269 views

### Testing for finite expectation

The mean of a positive random variable $X$ is either finite or infinite; define $J(X)$ to be $0$ in the former case and $1$ in the latter case. Claim: there does not exist a function $J_n$ from the ...
43 views

### understanding generalized coupon collector for distributions or learning mixture of distribution

Lets suppose we have a set $S=\{1,\ldots,n\}$ and $P$ is the uniform distribution over two subsets $T_1,T_2\subseteq S$, each of size $m\leq n/100$. Now, suppose somehow is given uniform samples from ...
100 views

### Logic of learning

Does Robust logic (Leslie Valiant), Default logic (Raymond Reiter) and Circumscription logic (John McCarthy) have any relation? I was Mathematician and Computer Science (dual degree undergraduate) ...
47 views

### Is there a notion of Probably Approximately Correctness in Unsupervised Learning? [closed]

I've been learning a little bit about computational learning theory, but most of what I've seen so far is related to supervised learning. Perhaps dimensionality reduction will be touched on, but not ...
539 views

### Reference Request: Computational Learning Theory

Pretty soon I will be finishing up Understanding Machine Learning by Shai Ben-David and Shai Shalev-Shwartz. I absolutely love the subject and want to learn more, the only issue is I'm having trouble ...
153 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 ...
206 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 ...
271 views

443 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$ ...
129 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 the ...
261 views

251 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 . (Note that AIC refers to ...
212 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 ...
144 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 ...
227 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 ...
498 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?
118 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 ...
61 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 ...
66 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) ...
478 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 ...