Questions tagged [machine-learning]
Theoretical questions about Machine learning, especially Computational Learning Theory, including Algorithmic Learning Theory, PAC learning, and Bayesian Inference
335
questions
0
votes
0
answers
39
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
29
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 ...
- 101
0
votes
0
answers
37
views
If two functions are close apart can I prove the difference of their empirical loss is also small?
I am trying to understand the proof of Theorem 3 in the paper "A Universal Law of Robustness via isoperimetry" by Bubeck and Sellke.
Basically there exist atleast one $w_{L,e}$ in $\...
- 113
0
votes
0
answers
24
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 ...
- 217
2
votes
1
answer
185
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 ...
- 217
2
votes
1
answer
110
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 ...
- 181
0
votes
1
answer
88
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
221
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 ...
0
votes
0
answers
37
views
Estimating mean of Gaussian vector with covariance as nuisance parameter
Suppose $X\in\mathbb{R}^d$ is a Gaussian random variable with mean $\mu\in\mathbb{R}^d$ and covariance $\Sigma\in\mathbb{R}^{d\times d}$. We are interested in estimating $\mu$, and for the purpose of ...
- 10k
0
votes
0
answers
17
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 ...
0
votes
0
answers
120
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
57
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
20
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 ...
0
votes
0
answers
39
views
Is it possible to count the total number of local minima for a scalar, multivariate function?
We can assume the function is differentiable, but it is also non-convex and setting the gradient equal to zero has no analytical solution.
We can also assume that the domain is bounded, namely the ...
- 1
2
votes
2
answers
345
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
130
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
151
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
0
votes
0
answers
34
views
Peer Based Machine Learning
Side Note: I originally asked this question on stack overflow but it was closed because apparently it wasn't the right place to ask the question. Please direct me to the right place if you don't think ...
- 11
1
vote
1
answer
123
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
69
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 ...
- 10k
-1
votes
1
answer
98
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
64
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
7
votes
0
answers
158
views
A variant of transfer learning
Suppose we want to train $K$ linear classifiers based on iid samples. Each classifier is of the form
$x\mapsto\mathrm{sign}(w\cdot x+\theta)$, with the constraint that the hyperplane $w$ is the same ...
- 10k
2
votes
1
answer
140
views
An invariance theorem for algorithmically random data in statistical learning
Motivation:
The following invariance theorem for statistical learning in the setting of algorithmically random data occurred to me yesterday. This theorem uses the fact that the property of ...
- 291
1
vote
2
answers
108
views
VC generalization bound extended to other types of target functions
In Y. S. Abu-Mostafa's book "Learning from Data", he mentions on page 55 after deriving the VC generalization bound for a binary target function that "it can be extended to other types ...
- 113
2
votes
0
answers
44
views
Energy-Based Modeling vs Deep Learning
I am doing some research on machine learning algorithms in the context of a seminar, which focuses on Energy-Based Modeling vs Deep Learning specifically in working with images Modeling. Now I know ...
- 21
12
votes
2
answers
316
views
Circuit and Formula Lower Bounds for Separating Sparse Sets of Strings
We say that a pair $(P,N)$ of subsets of strings from $\{0,1\}^n$ is an $n$-pair if $|P|=|N|=n$. Intuitively, sucha a pair consists of a set $P$ with $n$ positive $n$-bit strings, and a set $N$ with $...
- 1,052
0
votes
1
answer
131
views
Generalisations of the Fundamental Theorem of Statistical Learning to different tasks and losses
The fundamental theorem of statistical learning gives an equivalence between uniform convergence of the empirical risk to learning in the PAC framework.
I have only seen this stated in the case of ...
- 131
0
votes
1
answer
51
views
Machine Learning: Calibrating SubGroups of Probability Predictions inside a Dataset which should sum to 100%
I am working on an interesting type of problem where I want to make predicitons for individual elements within subgroups- with the knowledge that the sum of the probabilities within a subgroup should ...
1
vote
1
answer
216
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
1
vote
1
answer
817
views
What's the intuition behind Rademacher complexity?
As stated, what exactly is the intuition behind Rademacher Complexity which is defined:
Rademacher complexity captures the richness of a family of functions by measuring the degree to which a ...
- 121
-2
votes
1
answer
160
views
How to calculate complexity in a high dimensional space?
Edit: 'Fitness landscape analysis' was mentioned as a relevant measure. If you're going to downvote the post, at least leave a comment what is wrong.
For a specific f(), I'm defining a term '...
- 55
6
votes
1
answer
319
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
0
votes
1
answer
518
views
VC dimension for balanced binary decision trees
What is the VC dimension of all balanced binary decision tree of
depth $k$ in $\{0,1\}^d$? Does it depend on depth $k$ or dimension $d$?
1
vote
1
answer
129
views
Rademacher Complexity of the Composition with an Indicator
Consider the statistical learning setting where you have an arbitrary hypothesis space $\mathcal{H}$, a data space $\mathcal{Z}$, and a bounded loss function $\ell: \mathcal{H}\times \mathcal{Z} \...
- 113
7
votes
1
answer
279
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 ...
- 10k
3
votes
1
answer
141
views
Polynomial convergence to optimal move of the UCT algorithm. Missing proof?
This is a question regarding the theoretical convergence guarantees of the UCT algorithm, a popular variation of the Monte Carlo Tree Search algorithm (used in games, planning, reinforcement learning, ...
1
vote
0
answers
50
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
603
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
2
votes
1
answer
182
views
Why non-uniform learnability does not imply PAC learnability?
PAC guarantees provide us a a learning algorithm $A_n(\cdot)$ and sample complexity bound $n_{\mathcal{F}}(\epsilon,\sigma)$ that ensures
$
P\left[L_P(A(\mathcal{D}^n))-L_P(f^*)\leq \epsilon\right]\...
3
votes
0
answers
184
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
7
votes
1
answer
346
views
Complexity of constructing minimum depth decision trees
I am interested in the computational complexity of
Problem 1: Given a finite, non-empty set $J$, given $A, B \subseteq \{0,1\}^J$ such that $A \cap B = \emptyset$, and given $n \in \mathbb{N}$, does ...
- 183
0
votes
0
answers
83
views
Using martingale arguments to prove convergence of iterative algorithms
Can someone give me typical/educative examples of how martingales can be used to prove convergence of an iterative algorithmS?
The examples I know of can only go so far as to show that there exists ...
- 1,443
4
votes
0
answers
111
views
Status of the Junta Problem (soft question)
Does the learning theory community in general believe that juntas can be learned in polynomial time?
The naive algorithm works in quasi-polynomial time. MOS's paper shows how to solve the junta ...
- 187
5
votes
1
answer
208
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 ...
- 10k
4
votes
1
answer
280
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 $...
- 10k
0
votes
1
answer
127
views
Singular Value in Machine Learning
I'm reading the paper (http://proceedings.mlr.press/v9/glorot10a/glorot10a.pdf) from Glorot and Bengio. There is something that I don't understand at the abstract section on page 1.
"Training may be ...
- 11
1
vote
1
answer
81
views
Characterize a point cloud
Background: I have multiple point clouds (sets of objects) $\{S_i\}_{i\in\mathbb{N}}$ of variable size and "purity" (meaning that some sets contain very similar objects, some show a high diversity; ...
- 127
4
votes
2
answers
209
views
What are some good resources for strengthening my theoretical foundation for machine learning?
I'm a computer science major and I'm taking a lot of machine learning courses. I'm finding that my theoretical foundation on subjects like calculus and linear algebra are not as strong as I'd like ...
- 51
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 ...
- 10k