# Questions tagged [machine-learning]

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

367 questions
Filter by
Sorted by
Tagged with
1 vote
32 views

### PAC-learning description of (quantum) hypothesis class containing randomness

I was wondering how to correctly describe the following hypothesis class mathematically correctly: Say I have a quantum circuit which I postprocess by feeding its results into a neural network. How ...
73 views

### Learning a boolean function using decision tree with small number of queries

I am working on a problem and I am looking to solve the following subproblem : Given a "restrictive" blackbox access to boolean function $\phi$, output a "small-sized" CNF that ...
1 vote
27 views

### Agnosting Learning Algorithm for Squared Loss Regression and Conditional Density Estimation

In the lecture notes titled "Foundations of Reinforcement Learning and Interactive Decision Making" by Foster and Rakhlin, it is mentioned in the Proposition 1 that there exists an algorithm ...
• 153
59 views

### Is there optimal or approximate solution to Single-machine scheduling problem with constraints?

I'm interested in particular setup of Single-machine scheduling. I'll use the Optimal job scheduling notation to specify the situation. I'm also aware of Interval scheduling. What I want to achieve is ...
104 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 ...
1 vote
48 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 ) ...
1 vote
70 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 ...
44 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 ...
• 661
51 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 ...
25 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 ...
• 65
97 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 ...
• 21.7k
120 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 ...
58 views

• 111
75 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 ...
155 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 ...
44 views

• 291
235 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
376 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 ...
171 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
242 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 ...
1 vote
649 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 ...
125 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
65 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 ...
29 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 ...
480 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
171 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
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 ...