Questions tagged [lg.learning]

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

Filter by
Sorted by
Tagged with
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}$ ...
meeeeee's user avatar
  • 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 ...
Tran Khanh's user avatar
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 ...
meeeeee's user avatar
  • 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 ...
Sathishkumar Thirumalai's user avatar
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 ...
Tran Khanh's user avatar
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 ...
Katan katalan's user avatar
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))$ ...
Liam F-A's user avatar
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 ...
white's user avatar
  • 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 \...
aome's user avatar
  • 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 ...
Amin's user avatar
  • 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 ...
Amin's user avatar
  • 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/...
Segun Ojo's user avatar
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$. ...
Yakov Dan's user avatar
  • 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 ...
qc6518's user avatar
  • 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{ ...
dohmatob's user avatar
  • 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 (...
student3365's user avatar
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 ...
Nick Bishop's user avatar
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 ...
Mountain's user avatar
  • 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 ...
dohmatob's user avatar
  • 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 ...
Ariel's user avatar
  • 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,\...
user332582's user avatar
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 ...
gradstudent's user avatar
  • 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 ...
kd212149's user avatar
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 ...
Aryeh's user avatar
  • 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 ...
gradstudent's user avatar
  • 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⁡(...
amit's user avatar
  • 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 ...
Andy's user avatar
  • 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 ...
Aryeh's user avatar
  • 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 ...
Annonymous's user avatar
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) ...
Mahdi Heidarpoor's user avatar
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 ...
Marcel's user avatar
  • 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 ...
PMaynard's user avatar
  • 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 ...
user27182's user avatar
  • 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 ...
Aryeh's user avatar
  • 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 $...
Aryeh's user avatar
  • 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 ...
gradstudent's user avatar
  • 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 ...
Aryeh's user avatar
  • 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 ...
Popescu Claudiu's user avatar
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 ...
Aryeh's user avatar
  • 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 ...
Annonymous's user avatar
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 ...
Aryeh's user avatar
  • 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 ...
Aryeh's user avatar
  • 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 ...
Andrea's user avatar
  • 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 ...
LYH's user avatar
  • 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 ...
wwjohnsmith's user avatar
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 ) } \|...
Mr.Robot's user avatar
  • 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$ ...
gradstudent's user avatar
  • 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 ...
Dr.Raghnar's user avatar
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+...
Aryeh's user avatar
  • 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 ...
Xi Wu's user avatar
  • 161

1
2 3 4 5