Questions tagged [machine-learning]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
46 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 ...
Tomer Gigi's user avatar
0 votes
0 answers
15 views

Reference Request : For a paper on resolving conflicts in Interpretability methods

Well , this post is going to sound a bit similar to crush pages , where people post where and when they had seen someone and ask other people if they can help in identifying that person or this post ...
Amor Rei's user avatar
1 vote
1 answer
40 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 ...
Liam F-A's user avatar
1 vote
1 answer
78 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))$ ...
Liam F-A's user avatar
2 votes
1 answer
86 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 ...
AaronYeloy's user avatar
0 votes
0 answers
21 views

Can we ensemble multiple models using the same algorithm but with different features?

I am a beginner in machine learning and I wonder if I have any misinterpret or misunderstanding of the ensemble learning concept itself. As far as I know, the more diverse or unrelated the model, the ...
raven's user avatar
  • 1
1 vote
0 answers
40 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 \...
aome's user avatar
  • 111
0 votes
0 answers
63 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 ...
uzer.name's user avatar
0 votes
0 answers
77 views

Where does combinatorial optimization beat machine learning algorithms?

For some variant of the Vehicle Routing Problem my algorithm that is based on combinatorial optimization performs a lot better than the algorithms based on machine learning of my competitors. So I ask ...
Botanicus's user avatar
0 votes
0 answers
116 views

Open complexity theoretic questions for foundation models

What are the major current open complexity theoretic questions in foundation model? Any pointer would be appreciated.
Omar Shehab's user avatar
0 votes
0 answers
17 views

How to compute output function for an MLP that separates 3 regions in 2D plane?

I am trying to understand (mathematically) how to produce an output function that solves a problem as such : Let $A=\{(-2, 0), (2,0), (0, 2), (0,-2) \}$ be class 0 and $B=\{(0, 0\}$ be class one. I ...
tonythestark's user avatar
0 votes
0 answers
31 views

Proof that Sufficiency and Caliberation by group are equivalent notions

I am currently reading through the Fairness and Machine Learning book and I have a problem understanding the proof of Proposition 1 in Chapter 3 (titled Classification) (https://fairmlbook.org/...
Segun Ojo's user avatar
0 votes
1 answer
99 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 ...
randomizedalgo's user avatar
0 votes
0 answers
32 views

PAC learning in the convex case with bounded expected risk

In the context of computational learning theory: Let $f(w,z): \mathcal{W} \rightarrow \mathbb{R}$ be convex in $w \in \mathcal{W}$ where $\mathcal{W}$ bounded by R. Over $\mathcal{W}$, $|f| \leq C$. ...
Yakov Dan's user avatar
  • 101
0 votes
1 answer
43 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(...
qc6518's user avatar
  • 1
0 votes
0 answers
34 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. ...
Omar Shehab's user avatar
0 votes
0 answers
30 views

Distribution-free learning vs distribution-dependent learning

I asked this question on Mathoverflow and realized that it should have been better to ask here. My main confusion is, how to distinguish distribution-free learning and distribution-dependent learning ...
yinan's user avatar
  • 1
0 votes
1 answer
88 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 ...
qc6518's user avatar
  • 1
1 vote
0 answers
21 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{ ...
dohmatob's user avatar
  • 291
1 vote
0 answers
67 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 (...
student3365's user avatar
2 votes
1 answer
119 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 ...
Nick Bishop's user avatar
0 votes
0 answers
62 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 ...
jeb2's user avatar
  • 101
0 votes
0 answers
39 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 ...
Nick Bishop's user avatar
0 votes
0 answers
29 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 ...
dohmatob's user avatar
  • 291
2 votes
1 answer
203 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 ...
dohmatob's user avatar
  • 291
2 votes
1 answer
189 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 ...
Popescu Claudiu's user avatar
0 votes
1 answer
122 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
shai's user avatar
  • 3
1 vote
1 answer
226 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 ...
voroshilov's user avatar
1 vote
0 answers
231 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 ...
user65914's user avatar
0 votes
0 answers
123 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 ...
Marina's user avatar
  • 123
-1 votes
1 answer
59 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 ...
Colin Rowat's user avatar
0 votes
0 answers
22 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 ...
WitCanStain's user avatar
2 votes
2 answers
419 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 ...
Marina's user avatar
  • 123
4 votes
1 answer
154 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,\...
user332582's user avatar
0 votes
2 answers
160 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 ...
gradstudent's user avatar
  • 1,443
1 vote
1 answer
188 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 ...
kd212149's user avatar
2 votes
1 answer
75 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 ...
Aryeh's user avatar
  • 10.2k
-1 votes
1 answer
127 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 ...
KFkf's user avatar
  • 99
3 votes
1 answer
69 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 ...
gradstudent's user avatar
  • 1,443
7 votes
0 answers
161 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 ...
Aryeh's user avatar
  • 10.2k
3 votes
1 answer
147 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 ...
Aidan Rocke's user avatar
1 vote
2 answers
127 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 ...
ste's user avatar
  • 113
2 votes
0 answers
48 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 ...
dohm's user avatar
  • 21
12 votes
2 answers
326 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 $...
verifying's user avatar
  • 1,062
0 votes
1 answer
145 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 ...
user27182's user avatar
  • 131
0 votes
1 answer
53 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 ...
daffodil_flower_boy's user avatar
1 vote
1 answer
242 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⁡(...
amit's user avatar
  • 11
3 votes
1 answer
1k 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 ...
Abhishek Singh's user avatar
-2 votes
1 answer
181 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 '...
user2827214's user avatar
6 votes
1 answer
442 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 ...
Andy's user avatar
  • 105

1
2 3 4 5
8