Questions tagged [lg.learning]
Machine learning and learning theory: PAC learning, algorithmic learning theory, and computational aspects of Bayesian inference and graphical models.
203
questions
1
vote
0
answers
32
views
PAC-learning description of (quantum) hypothesis class containing randomness
I was wondering how to correctly describe the following hypothesis class mathematically correctly:
Say I have a quantum circuit which I postprocess by feeding its results into a neural network. How ...
- 11
1
vote
0
answers
27
views
Agnosting Learning Algorithm for Squared Loss Regression and Conditional Density Estimation
In the lecture notes titled "Foundations of Reinforcement Learning and Interactive Decision Making" by Foster and Rakhlin, it is mentioned in the Proposition 1 that there exists an algorithm ...
- 153
4
votes
0
answers
139
views
Learning a regular language with a specified closure property
Consider an alphabet $\Sigma$, and a partial transformation function $f:S\to\Sigma^\ast$ defined on some subset $S\subseteq\Sigma^\ast$. Let $S_f$ denote the set of strings $s\in S$ such that $f^n(s)\...
- 141
0
votes
1
answer
95
views
What is the intution on the TTT algorithm for regular grammar inference?
This question is about the TTT algorithm for blackbox automata inference as defined in [1] and [2]. I am finding it difficult to understand all the innovations made by the algorithm. I understand how
...
- 197
2
votes
1
answer
117
views
What is the current state of the art on exact identification of DFAs with a maximum N states
This is a question about the blackbox grammar inference of deterministic finite state automata (DFAs). In particular I want to ask about when one can exactly identify the target DFA using queries to ...
- 197
3
votes
2
answers
154
views
An upper bound of pseudo-/VC-dimension
Let $\mathcal{F}\subseteq \left\{f:\mathbb{R}^d\to\mathbb{R}\right\}$ be a family of functions with bounded pseudo-dimension $\text{Pdim}(\mathcal{F})\le N$, i.e., the VC-dimension $\text{VCdim}(\left\...
- 68
0
votes
1
answer
119
views
How to properly learn when there is random classification noise?
The following problem is motivated by the one here from more than half a decade ago:
Let $C$ be a concept class that is efficiently proper PAC-learnable, i.e. there exists a learning algorithm that ...
user70055
0
votes
1
answer
81
views
Learning positive half-lines (in $\mathbb{N}$)
The second section of these notes points explains how one might PAC learn the concept class of intervals of all positive half-lines in $\mathbb{R}$. If we restricted our attention to $\mathbb{N}$ ...
user70055
0
votes
0
answers
21
views
What is the condition under which the estimation error increases (logarithmically) with hypothesis class size for a finite hypothesis class
In section 5.2 error decomposition (p.404) from the online book "Shai et al., Understanding Machine Learning: From Theory to Applications", the authors wrote:
As we have shown, for a finite ...
- 131
1
vote
1
answer
89
views
Learning arithmetic series
Let us say that an arithmetic series is a series of the form $s_t = \{0, t, 2t, \ldots\}$. For example, $s_3 = \{0, 3, 6, \ldots\}$. Now consider the concept class composed of all arithmetic series of ...
user70055
0
votes
1
answer
51
views
Why is the estimation error smaller in Structural Risk Minimization
On p.87 in this online Understanding Machine Learning book, the authors wrote:
Unlike the ERM paradigm discussed in previous chapters, we no longer just care about the empirical risk, $L_S(h)$, but ...
- 131
0
votes
0
answers
72
views
Why do we use Hoeffding inequality in UCB approach to drive the confidence set in multi-armed bandit problem?
In UCB algorithm, to drive the confidence set for unknown parameters we use Hoeffding inequality. I am wondering why we don't use Normal distribution instead which is much simpler to work with. Based ...
1
vote
1
answer
130
views
Information Bottleneck - Calculating the Mutual information between the Labels and the Features [closed]
I am trying to understand the Nonlinear Information Bottlecneck paper along with their implementation, but I am confused as to what is actually being calculated in the Mutual information $(I(Y, M))$ ...
- 41
0
votes
0
answers
58
views
The complexity order of regret (especially in online reinforcement learning)?
In online reinforcement learning theory, how to judge the complexity order of regret, if there are two or more terms in there?
For example, the state space is $X$, the action space is $A$, the episode ...
- 1
1
vote
0
answers
107
views
Proving existence of efficient PAC learning algorithm without noise info given poly-time algorithm with noise upper bound
How would I prove that if there is an efficient algorithm for PAC learning in the presence of classification noise by an algorithm that is given a noise rate upper bound $\eta_0$ ($1/2 > \eta_0 \...
- 111
0
votes
1
answer
146
views
PAC learning over continuous functions
I'm wondering if it's possible to use PAC learning to learn a continuous function. For example, if we wanted to learn a probability distribution or a CDF, is it valid to train on some set of m ...
- 1
1
vote
0
answers
32
views
Generalization bound for margin / ramp loss which is not vacuous when margin tends to zero, but recovers usual generalization bound for 0-1 loss
For any $t \ge 0$, consider the ramp loss function $\phi_t:\mathbb R \to [0,1]$ defined by
$$
\phi_t(z) = \begin{cases}0,&\mbox{ if }z \ge t,\\
1-z/t,&\mbox{ if }z \in (0,t),\\
1,&\mbox{ ...
- 291
1
vote
0
answers
75
views
Relationship between statistical query lower bounds and "traditional" iid sampling lower bounds
Coming from a more statistical background, it is not clear to me if or how lower bounds in the statistical query (SQ) model imply anything useful about traditional learning problems with iid samples (...
- 19
2
votes
1
answer
221
views
Fat Shattering / VC dimension / Statistical Complexity of piecewise linear functions
I am trying to establish a bound on the VC dimension of piecewise linear continuous functions with $k$ pieces. I am aware of an earlier question which tackles this problem in the case of convex ...
- 123
2
votes
0
answers
121
views
Are there more learnable but undecidable cases except the halting problem
Per request, I cross post the question here which is original from math.stackexchange
In the ICML 1996 paper, On the Learnability of the Uncomputables, by Richard Lathrop, he proved that halting ...
- 121
0
votes
0
answers
31
views
Minimax computation for classification problems with smooth densities functions
Fix $d=1$, $r \in (0,\infty)$ and a neigborhood $\Omega$ of $0$ in $\mathbb R^d$ and let and let $W^{1,\infty}(r)$ be the Sobolev ball continuously differentiable functions $f:\mathbb R^d \to \mathbb ...
- 291
0
votes
0
answers
188
views
How to read a COLT or other paper related learning theory?
I am a master student right now. And first time met the theoretical computer science, I am really interested in it, and especially the learning theory part. Wish to do research about this part in the ...
- 11
4
votes
1
answer
171
views
What is tightest known (VC-style) sample complexity bound for uniform convergence of empirical means?
The following result is adapted from Anthony and Bartlett, 1999 (Theorem 4.9).
Theorem There exist positive constants $m_0 \le 400$, $c_1 \le 8$, $c_2 \le 41$, $c_3 \ge 1/576$ such that, if $(\Omega,\...
- 143
0
votes
2
answers
168
views
An (unusual?) risk bound
I am told that that a bound on the generalization error of the following form exists in terms of something called the ``shattering coefficient" - but I am not able to reference this quantity in ...
- 1,453
1
vote
1
answer
258
views
Generalization bound for parameters rather than loss functions
I was wondering if it is possible to obtain high probability bounds (provided finite sample size of the training data) for the distance (say in the l-1 or l-2 norm) between the best parameter set and ...
- 11
2
votes
1
answer
120
views
Bayes-consistent cost-sensitive classification
In cost-sensitive classification,
we have a confusion (or cost) matrix
$C$, where $C(i,j)$ is the cost incurred
for predicting label $i$ when nature
specifies $j$. The costs are non-negative,
but no ...
- 10.6k
3
votes
1
answer
69
views
Examples of learning via exactly integrable gradient flows
If $\ell (\vec{w}, \vec{z})$ is the loss function at weights $\vec{w}$ and for data $\vec{z}$ then corresponding to a distribution ${\cal D}$ we can consider doing gradient flow with step-length $\eta ...
- 1,453
1
vote
1
answer
245
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(...
- 11
6
votes
1
answer
505
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 ...
- 105
7
votes
1
answer
319
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 ...
- 10.6k
0
votes
0
answers
47
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 ...
- 251
4
votes
0
answers
106
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) ...
1
vote
0
answers
56
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 ...
- 111
7
votes
3
answers
757
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 ...
- 173
3
votes
0
answers
279
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 ...
- 131
5
votes
1
answer
212
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 ...
- 10.6k
4
votes
1
answer
284
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 $...
- 10.6k
3
votes
1
answer
224
views
About estimating escape time of gradient Langevin dynamics
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 ...
- 1,453
4
votes
1
answer
80
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 ...
- 10.6k
5
votes
1
answer
151
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 ...
- 201
1
vote
0
answers
57
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 ...
- 10.6k
0
votes
0
answers
83
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 ...
- 251
1
vote
0
answers
92
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 ...
- 10.6k
3
votes
1
answer
118
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 ...
- 10.6k
0
votes
0
answers
148
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 ...
- 319
2
votes
1
answer
125
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 ...
- 63
2
votes
0
answers
106
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 ...
- 21
0
votes
1
answer
178
views
Confusion about covering number
Problem
I do not understand why larger $p$ will give a larger covering number.
Since when $p\geq q$, the corresponding hypercube is also larger (by $\| x \| _ { q } \leq n ^ { ( 1 / q - 1 / p ) } \|...
- 109
2
votes
2
answers
580
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$ ...
- 1,453
0
votes
1
answer
158
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 ...
