# Questions tagged [lg.learning]

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

175 questions
Filter by
Sorted by
Tagged with
40 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 ...
70 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) ...
41 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 ...
401 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 ...
35 views

Suppose $f_{\vec{w}} : \mathbb{R}^n \rightarrow \mathbb{R}$ is a function parameterized by some parameter vector $\vec{w}$. Now for some true parameters $\vec{w}^*$, some noise function $\xi : \mathbb{... 0answers 104 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 ... 0answers 20 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 ... 1answer 190 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 ... 0answers 166 views ### Is this a known learning problem? Let$(\mathcal{X},\rho)$be a metric space (say,$\mathcal{X}=[0,1]$with the Euclidean metric). Let$\alpha:\mathcal{X}\to[0,1]$be unknown. Suppose that$\mathcal{X}$is endowed with a distribution$...
83 views

I am trying to understand the argument in the proof of Lemmma 6.3 (page 18) of this paper https://arxiv.org/abs/1902.08179. Let me summarize the conceptual crux of the argument here using a slightly ...
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 ...
74 views

### Reconstruction of a sequence generated by a Markov chain - reference request

Let S be a finite sequence of symbols from a finite alphabet, with gaps - that is on some known locations an unknown number of symbols are missing. Assuming that the sequence , including the symbols ...
46 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 ...
61 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 ...
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 ...
106 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 ...
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 ...
78 views

### how is time complexity defined in computational learning theory

In general, when we say an algorithm $A$ PAC learns $C$ in time $t$, we say $A$ takes time $t$ before outputting a hypothesis $h$, and the hypothesis can be evaluated (on every $x$) in time $t$. Now ...
137 views

58 views

### Back-propagation for computing derivative of certain line integral

Consider a function F (think of neural networks) with two sets of parameters: (1) model parameters $\mathbf{w}$, and (2) input data ${\bf x} \in {\mathbb R}^d$. Fix $i \in [d]$, consider the following ...
142 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....
106 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 ...
263 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 ...
89 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 ...
103 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 ...
82 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 ...
77 views

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 ... 2answers 205 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 ... 1answer 108 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 ... 1answer 125 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 ... 1answer 174 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 ... 1answer 493 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? 1answer 112 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 ... 0answers 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 ... 0answers 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) ... 2answers 381 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 ... 1answer 271 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 ... 1answer 208 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$\...
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 ...