Questions tagged [machine-learning]
Theoretical questions about Machine learning, especially Computational Learning Theory, including Algorithmic Learning Theory, PAC learning, and Bayesian Inference
367
questions
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
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
0
answers
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
0
votes
0
answers
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 ...
- 1
2
votes
1
answer
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
0
answers
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
1
answer
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 ...
- 13
0
votes
1
answer
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
0
votes
0
answers
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 ...
- 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
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
0
votes
1
answer
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 ...
user70055
0
votes
0
answers
58
views
word2vec: vectors or projective vectors?
In "Efficient Estimation of Word Representations in
Vector Space" Mikolov et.al argue that any mapping of words into vectors should satisfy approximate constraints, such as
$vector(''Paris'')...
- 646
1
vote
0
answers
48
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
81
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
103
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
0
votes
0
answers
21
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
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
51
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
44
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
97
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
169
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
46
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
60
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
109
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
130
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
91
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
107
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
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 ...
0
votes
1
answer
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 ...
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
44
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
147
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
32
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
75
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
221
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
70
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
42
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
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
2
votes
1
answer
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 ...
- 201
0
votes
1
answer
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
1
answer
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 ...
- 13
1
vote
0
answers
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 ...
- 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
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 ...
- 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
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
4
votes
1
answer
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
0
votes
2
answers
168
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,453