Questions tagged [machine-learning]
Theoretical questions about Machine learning, especially Computational Learning Theory, including Algorithmic Learning Theory, PAC learning, and Bayesian Inference
369 questions
0
votes
0
answers
24
views
Agnostic PAC learning - equivalent definitions?
Learning model:
Domain set: $\mathcal{X}$,
Label set: $\{0,1\}$,
Hypothesis class: a set $\mathcal{H}$ of binary hypotheses $h:\mathcal{X}\to\{0,1\}$
Data-labels generating distribution: $\mathcal{D}$...
- 1
-4
votes
0
answers
73
views
It's possible to disable a pixel on a monitor [closed]
I know this may it's a little bit often question, but I was searching for disabling pixel at computer monitor if it's possible now days, I'm looking for disable a specific pixel on screen or Monitor ...
- 1
0
votes
0
answers
24
views
Sample complexity of covariance matrix estimation of a Gaussian random variable (with explicit constants)
I'm seeking an explicit bound for the number of samples required to estimate the covariance matrix of a Gaussian distribution. In https://arxiv.org/pdf/1011.3027v7 (end of page 31), the following ...
0
votes
0
answers
35
views
Universal approximation theorem for functions in the Sobolev space $H^1(\Omega)$
I have a function $f \in H^1(\Omega)$ on some bounded domain $\Omega \subset \mathbb{R}^n$ which I want to approximate by some class of neural networks in the $H^1(\Omega)$ norm. I'm looking for a ...
- 1
1
vote
0
answers
67
views
ML Gradient Descent Convergence Theorem
Does there exist a generalization of this theorem, by Yurii Nesterov in Introductory Lectures on Convex Optimization (2004) which relaxes the assumption that the loss function is convex and shows that ...
- 11
1
vote
0
answers
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 ...
- 11
2
votes
0
answers
75
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
0
answers
28
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
0
votes
0
answers
66
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 ...
- 1
2
votes
1
answer
106
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
0
answers
51
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
1
answer
78
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 ...
- 13
0
votes
1
answer
48
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
0
votes
0
answers
52
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 ...
- 1
0
votes
0
answers
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
3
votes
1
answer
123
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.8k
0
votes
1
answer
141
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 ...
user70055
1
vote
0
answers
49
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
0
votes
1
answer
83
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}$ ...
user70055
2
votes
2
answers
107
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 ...
- 65
1
vote
1
answer
89
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 ...
user70055
0
votes
1
answer
63
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
46
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
141
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
205
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
61
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 ...
3
votes
1
answer
118
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 ...
- 41
1
vote
1
answer
142
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))$ ...
- 41
2
votes
1
answer
93
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
1
vote
0
answers
128
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
84
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
1
answer
163
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
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(...
- 1
0
votes
0
answers
46
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. ...
- 661
0
votes
1
answer
159
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
37
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
80
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
272
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
75
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
43
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
33
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
239
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
453
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
183
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
247
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 ...
- 113
1
vote
0
answers
727
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
125
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
68
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
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 ...
2
votes
2
answers
515
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