Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [machine-learning]

Theoretical questions about Machine learning, especially Computational Learning Theory, including Algorithmic Learning Theory, PAC learning, and Bayesian Inference

Filter by
Sorted by
Tagged with
2 votes
1 answer
88 views

The true meaning of sampling from a distribution in the context of active learning

I would like to understand intuitively what it means to sample from a distribution $\mathcal{D}$. It may sound like a dumb question, but I can't find an answer anywhere, a colleague recommended ...
Guesttilunderstandingnature's user avatar
1 vote
0 answers
42 views

Constructing a DFA with $n$ states for which $L*$ needs $n$ equivalence queries

I'm working on constructing deterministic finite automata (DFAs) with a specific learning complexity when using the L* algorithm developed by Dana Angluin. My goal is to create a DFA of size ( n ) ...
Coping Forever's user avatar
1 vote
1 answer
63 views

Sequential Two-player Game related to "Bandit Detection"

Alice and Bob play a game over $n$ rounds. At each round, Alice picks a number $x_t \in [0,1]$ and Bob simultaneously chooses whether to "peek" at the number $x_t$ which is represented by a ...
Amaryllis 's user avatar
0 votes
1 answer
37 views

Feature selection problem under promise

Are there well used examples of feature selection problem where the problem is defined under certain promise? Let's say the task is to select the minimum number of features such that the mutual ...
Omar Shehab's user avatar
0 votes
0 answers
47 views

Computational complexity of LambdaMART

Could someone provide a general estimate of the average (time) complexity of the LambdaMART learning-to-rank algorithm? A particular implementation of LambdaMART is known as XGBRanker. It uses ...
Enk9456's user avatar
0 votes
0 answers
23 views

Is there a relation between packing number and disagreement coefficient in the active learning setting?

This is a question for active learning experts: Let $\mathcal{X}$ be the input space equipped with a distribution $\mathcal{D}$ and let $\mathcal{H}$ be a hypothesis class, $h \in \mathcal{H}$ our ...
rivana's user avatar
  • 65
3 votes
1 answer
87 views

Application of PCP and error correcting codes to LLMs?

Are there any interesting results in applying error correcting codes and ideas from PCP (Probabilistically Checkable Proofs) to improve the quality of large language models (LLM), or connecting them ...
Kaveh's user avatar
  • 21.7k
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
0 answers
56 views

word2vec: vectors or projective vectors?

In "Efficient Estimation of Word Representations in Vector Space" Mikolov et.al argue that any mapping of words into vectors should satisfy approximate constraints, such as $vector(''Paris'')...
Tegiri Nenashi's user avatar
1 vote
0 answers
45 views

Find the SVM kernel in detecting if a substring in a given string

Consider the task of learning to find a sequence of characters ("signature") in a file that indicates whether it contains a virus or not and let $\mathcal{X}$ be the set of all finite ...
Tran Khanh's 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
2 votes
2 answers
94 views

Learning with zero inductive bias

I want to understand the intuition behind the classic setting of learning theory, we always assume that the model belongs to some known class. Was there a formal proof that we can or can not learn a ...
rivana's user avatar
  • 65
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
1 vote
0 answers
41 views

Why the measure of information complexities for passive and active learning are increasing in research communities?

I am a PhD student working on the theory of active learning. Over the years, accepted papers in COLT and ALT for active learning are focused on approaches that almost all of them define new ...
Ayoubayjx's user avatar
  • 122
-1 votes
1 answer
74 views

Unable to understand the Sample complexity of PAC learning

I have been studying from the book "Understanding Machine Learning - From Theory to Algorithms" by Shai Shalev-Shwartz and Shai Ben-David I am struck at corollary 3.2 which states that Every ...
Sathishkumar Thirumalai's user avatar
2 votes
0 answers
128 views

Does PAC learnable imply agnostic PAC learnable for binary classification tasks?

The Fundamental Theorem of Statistical Learning from the book "Shai et al., Understanding Machine Learning: From Theory to Algorithms, Cambridge Press University", is written as follows: ...
Tran Khanh's user avatar
0 votes
0 answers
41 views

Derivation of influence function in Understanding Black-box Predictions via Influence Functions paper

In Understanding Black-box Predictions via Influence Functions paper Appendix A, the authors provide a standard derivation for influence functions, however, I could not understand one of the steps. ...
umityigitbsrn's user avatar
0 votes
0 answers
56 views

Learning a PAC-lernable using agnostic-PAC framework

given H a family of functions which is PAC lernable such that for $\epsilon$ error and $\delta $ confidence interval it required $m(\epsilon,\delta)$ samples. I understood that if we learn H under ...
Tomer Gigi's user avatar
0 votes
0 answers
17 views

Reference Request : For a paper on resolving conflicts in Interpretability methods

Well , this post is going to sound a bit similar to crush pages , where people post where and when they had seen someone and ask other people if they can help in identifying that person or this post ...
Amor Rei's user avatar
3 votes
1 answer
92 views

Is a Single Linear MLP Equivalent to a Random Projection

I am just hoping to confirm my hypothesis, that a single MLP (untrained and randomly initialized) can be used for random projection for dimensionality reduction. If a random MLP layer with no ...
Liam F-A's user avatar
1 vote
1 answer
122 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
2 votes
1 answer
88 views

Are there pseudorandom sequences which cannot be learned by any ML model but which still fail the Diehard tests?

This is likely a very silly question which has a simple answer. As I understand, ML models are able to detect patterns in sequences. Given a sequence which is not truly random but rather only ...
AaronYeloy's user avatar
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
0 answers
74 views

Learning Parities via Gradient Descent

[Disclaimer: Crossposted in cs --> link] In their recent work [DM20] Daniely and Malach prove that a two layer sufficiently wide NN can learn parities via gradient descent (GD). Since [Kearn94] it ...
uzer.name's user avatar
0 votes
1 answer
146 views

Boosting the probability of success(random projections, johnson lindenstrauss)

In the simple proof of the johnson lindenstrauss lemma written by Sanjoy Dasgupta, Anupam Gupta that can be found here they state the following (p.$62$): Repeating this projection $O(n)$ times can ...
randomizedalgo's user avatar
0 votes
1 answer
44 views

Differing definitions of a weak learner

I've been reading about boosting and have come across basically two definitions of a weak learner. Basically for hypothesis $h$ and target $c$, some definitions says that $h$ is a weak learner if $E[h(...
qc6518's user avatar
  • 1
0 votes
0 answers
40 views

Computational complexity of CVaR calculation

I am currently looking for literature discussing the computational complexity of CVaR calculation. At this point the only work I have found is the following. Mavronicolas, Marios, and Burkhard Monien. ...
Omar Shehab's user avatar
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
204 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
0 votes
0 answers
67 views

characterising the manifold representing images

Assuming that the Manifold Hypothesis is valid, or that real-world high-dimensional data lie on low-dimensional manifolds embedded within the high-dimensional space, How can one describe the ...
jeb2's user avatar
  • 101
0 votes
0 answers
41 views

PAC guarantees for linear prediction under the squared loss

I am looking for generalisation bounds under the squared loss, specifically for the class $\mathcal{F}_{\text{lin}} = \{f(x) = \langle w, x \rangle : \|w\| \leq C\}$ of bounded linear predictors. I am ...
Nick Bishop's user avatar
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
2 votes
1 answer
213 views

Upper bound for VCdim of $H$ in terms of subgraph$(F)$, where $H := \{S(f) | f \in F\}$, with $S(f) := \{(x,y) \in X \times \{\pm 1\} | yf(x) \le 1\}$

$\DeclareMathOperator\sg{sg}\DeclareMathOperator\VCdim{VCdim}$ Let $X$ be a measurable space and given a measurable function $f:X \to \mathbb R$, recall that the subgraph of $f$, denoted $\sg(f)$ is ...
dohmatob's user avatar
  • 291
2 votes
1 answer
348 views

VC dimension of the class of all polygons with k vertices

VC dimension of the class of convex polygons with $ k $ vertices is known to be $ 2k + 1$. For the general case I was able to derive a bound of the type $ O(k^2log(k)) $ (probably can be easily ...
Popescu Claudiu's user avatar
0 votes
1 answer
158 views

VC-dimension of the infinite intersection of two spheres

I'm searching for an upper-bound for the VC-dimension of the infinite intersection of two spheres. Thanks
shai's user avatar
  • 3
1 vote
1 answer
236 views

No free lunch theorem

Assume that learning algorithm $A$ is fixed. Let $D = \{ (x_1,y_1),\dots, (x_N,y_N) \}$, $F$ is set of a data-generating functions and $h : X \to Y$ is a classifier. $L(f(x),y) $ is $1$/$0$-loss ...
voroshilov's user avatar
1 vote
0 answers
536 views

Can I estimate the probability of a given output of the diffusion model?

I have a pretrained Grad-TTS (https://arxiv.org/abs/2105.06337) denoising diffusion model that predicts a spectrogram (an array of numerical values) $Y$ from input text $X$. If I have a text $X_0$ and ...
user65914's user avatar
0 votes
0 answers
123 views

Need advice about venue for publication

I have a new article where I propose a logical theory of machine learning (instead of statistical one). In particular, I propose a modal logic to express loss criteria, and show that large number of ...
Marina's user avatar
  • 123
-1 votes
1 answer
64 views

equivalence between Bayesian prior distribution and regularization metric?

Ridge and LASSO can be interpreted as OLS with priors over the coefficients (respectively, Gaussian and Laplacian). How much does this generalize? Given a prior, does it imply a regularization term ...
Colin Rowat's user avatar
0 votes
0 answers
27 views

Why can methods like ReSuMe, Chronotron and SPAN only train single-layer spiking neural networks?

ReSuMe, Chronotron and SPAN all use STDP-like local learning rules to implement their training algorithm (though they approach the training differently, e.g. SPAN uses gradient descent via spikes ...
WitCanStain's user avatar
2 votes
2 answers
458 views

Some issues with proof of Fundamental Theorem of Statistical learning

I am reading the book "Understanding Machine Learning" by Shai Shalev-Shwartz and Shai Ben-David. The theorem 6.7 has several equivalent statements for a class of functions $H$. The first ...
Marina's user avatar
  • 123
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
245 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
108 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
-1 votes
1 answer
164 views

No free lunch theorem and finite hypothesis classes

I have read the no free lunch theorem(NFLT) section 5.1 of Understanding machine learning by Shai Shalev-Shwartz. There is also this Corollary 4.6 which states any finite hypothesis class is PAC ...
KFkf's user avatar
  • 99

1
2 3 4 5
8