Questions tagged [lg.learning]
Machine learning and learning theory: PAC learning, algorithmic learning theory, and computational aspects of Bayesian inference and graphical models.
201
questions
0
votes
1
answer
56
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}$ ...
- 21
0
votes
0
answers
16
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
78
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 ...
- 21
-1
votes
0
answers
38
views
What are the prerequisites for reading the book "Understanding machine learning: from theory to algorithms"
The book mentions
"the reader is assumed to be comfortable with basic notions of probability, linear
algebra, analysis, and algorithms"
I am a graduate in electronics engineering. I have ...
0
votes
1
answer
30
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
62
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
90
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))$ ...
- 21
0
votes
0
answers
47
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
58
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
0
answers
57
views
How to find upper bound on regret of stochastic linear bandit not pseudo-regret
In stochastic linear bandit we assume that the reward at each period is generated from $r_t= x_t^\top \theta + \varepsilon_t$ where $\varepsilon_t$ is R-sub-Gaussian. Based on this definition, we ...
- 61
0
votes
0
answers
51
views
Is there any bound on the convergence rate of actions in bandit literature?
In classical bandit problems where there are $K$ arms and we should decide which arm to pull at each period, the main issue is to design an algorithm that minimizes the regret and we find a bound on ...
- 61
0
votes
0
answers
41
views
Proof that Sufficiency and Caliberation by group are equivalent notions
I am currently reading through the Fairness and Machine Learning book and I have a problem understanding the proof of Proposition 1 in Chapter 3 (titled Classification) (https://fairmlbook.org/...
0
votes
0
answers
32
views
PAC learning in the convex case with bounded expected risk
In the context of computational learning theory:
Let $f(w,z): \mathcal{W} \rightarrow \mathbb{R}$ be convex in $w \in \mathcal{W}$ where $\mathcal{W}$ bounded by R. Over $\mathcal{W}$, $|f| \leq C$.
...
- 101
0
votes
1
answer
101
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
28
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
67
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
152
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
115
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
166
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
160
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
161
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,443
1
vote
1
answer
205
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
77
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.3k
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,443
1
vote
1
answer
244
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
462
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
301
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.3k
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
105
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
53
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
6
votes
3
answers
684
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 ...
- 163
3
votes
0
answers
252
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
210
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.3k
4
votes
1
answer
283
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.3k
2
votes
1
answer
209
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,443
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.3k
5
votes
1
answer
147
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.3k
0
votes
0
answers
81
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
91
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.3k
3
votes
1
answer
105
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.3k
0
votes
0
answers
138
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 ...
- 199
2
votes
1
answer
112
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
104
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
166
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
567
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,443
0
votes
1
answer
156
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 ...
2
votes
1
answer
495
views
Oncina-Garcia RPNI algorithm for learning DFAs
The question refers to this paper:
ftp://altea.dlsi.ua.es/people/oncina/articulos/asspr1992.pdf
Given a sample of $p$ positive and $n$ negative strings, RPNI constructs a consistent DFA in time $O((p+...
- 10.3k
1
vote
0
answers
93
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 ...
- 161