# Questions tagged [machine-learning]

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

335 questions
Filter by
Sorted by
Tagged with
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
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
37 views

• 217
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
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 ...
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
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 ...
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
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 ...
120 views

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
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 ...
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 ...
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 ...
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
130 views

• 1,443
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
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
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
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
316 views

• 113
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
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
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
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
182 views

• 10k
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 ...
1 vote
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
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
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 ...