Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

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
4 votes
0 answers
133 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)\...
LegionMammal978's user avatar
0 votes
1 answer
81 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 ...
Rahul Gopinath's user avatar
2 votes
1 answer
112 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 ...
Rahul Gopinath's user avatar
3 votes
2 answers
148 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\...
Recursion's user avatar
0 votes
1 answer
105 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 ...
user avatar
0 votes
1 answer
72 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}$ ...
user avatar
0 votes
0 answers
19 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
86 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 ...
user avatar
0 votes
1 answer
39 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
64 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
121 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
51 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
95 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
1 answer
137 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
29 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
71 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
203 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
118 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
182 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
170 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
167 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,453
1 vote
1 answer
242 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
106 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.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 ...
gradstudent's user avatar
  • 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⁡(...
amit's user avatar
  • 11
6 votes
1 answer
489 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
308 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.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 ...
Annonymous's user avatar
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) ...
Mahdi Heidarpoor's user avatar
1 vote
0 answers
55 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
728 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
270 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
211 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.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 $...
Aryeh's user avatar
  • 10.6k
3 votes
1 answer
223 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,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 ...
Aryeh's user avatar
  • 10.6k
5 votes
1 answer
149 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.6k
0 votes
0 answers
82 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.6k
3 votes
1 answer
111 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.6k
0 votes
0 answers
144 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
  • 319
2 votes
1 answer
120 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
105 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
171 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
577 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,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 ...
Dr.Raghnar's user avatar
2 votes
1 answer
578 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.6k
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