Questions tagged [machine-learning]
Theoretical questions about Machine learning, especially Computational Learning Theory, including Algorithmic Learning Theory, PAC learning, and Bayesian Inference
363
questions
1
vote
0
answers
38
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 ...
- 131
-1
votes
0
answers
24
views
Finding an algorithm EF[1,1] and PO division for more than two agents
From this research paper I want to write an algorithm for finding envy-freeness(EF) and Pareto optimality(PO) division for more than two agents.
We consider the problem of fairly and efficiently ...
- 99
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
2
votes
2
answers
78
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 ...
- 53
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
1
vote
0
answers
39
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 ...
- 122
-1
votes
1
answer
61
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 ...
2
votes
0
answers
55
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:
...
- 131
0
votes
0
answers
30
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. ...
0
votes
0
answers
51
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 ...
0
votes
0
answers
16
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 ...
- 1
1
vote
1
answer
44
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 ...
- 21
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
2
votes
1
answer
87
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 ...
- 121
0
votes
0
answers
21
views
Can we ensemble multiple models using the same algorithm but with different features?
I am a beginner in machine learning and I wonder if I have any misinterpret or misunderstanding of the ensemble learning concept itself.
As far as I know, the more diverse or unrelated the model, the ...
- 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
63
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 ...
0
votes
0
answers
80
views
Where does combinatorial optimization beat machine learning algorithms?
For some variant of the Vehicle Routing Problem my algorithm that is based on combinatorial optimization performs a lot better than the algorithms based on machine learning of my competitors. So I ask ...
- 87
0
votes
0
answers
116
views
Open complexity theoretic questions for foundation models
What are the major current open complexity theoretic questions in foundation model? Any pointer would be appreciated.
- 653
0
votes
0
answers
18
views
How to compute output function for an MLP that separates 3 regions in 2D plane?
I am trying to understand (mathematically) how to produce an output function that solves a problem as such :
Let $A=\{(-2, 0), (2,0), (0, 2), (0,-2) \}$ be class 0 and $B=\{(0, 0\}$ be class one.
I ...
- 101
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
1
answer
101
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 ...
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
43
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(...
- 1
0
votes
0
answers
34
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. ...
- 653
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
153
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
0
votes
0
answers
63
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 ...
- 101
0
votes
0
answers
39
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 ...
- 123
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
2
votes
1
answer
206
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 ...
- 291
2
votes
1
answer
232
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 ...
- 201
0
votes
1
answer
134
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
- 3
1
vote
1
answer
229
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 ...
- 13
1
vote
0
answers
315
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 ...
- 11
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 ...
- 123
-1
votes
1
answer
60
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 ...
- 99
0
votes
0
answers
22
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 ...
2
votes
2
answers
438
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 ...
- 123
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
-1
votes
1
answer
145
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 ...
- 99
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