# Questions tagged [machine-learning]

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

363 questions
Filter by
Sorted by
Tagged with
1 vote
38 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 ...
24 views

### Finding an algorithm EF[1,1] and PO division for more than two agents

From this research paper I want to write an algorithm for finding envy-freeness(EF) and Pareto optimality(PO) division for more than two agents. We consider the problem of fairly and efficiently ...
56 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}$ ...
78 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 ...
16 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 ...
1 vote
78 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 ...
38 views

### What are the prerequisites for reading the book "Understanding machine learning: from theory to algorithms"

The book mentions "the reader is assumed to be comfortable with basic notions of probability, linear algebra, analysis, and algorithms" I am a graduate in electronics engineering. I have ...
30 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 ...
1 vote
39 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 ...
61 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 ...
55 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: ...
30 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. ...
51 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 ...
16 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 ...
1 vote
44 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 ...
1 vote
90 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))$ ...
87 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 ...
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 ...
1 vote
58 views

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. ...
101 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 vote
28 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{ ...
1 vote
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 (...
153 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 ...
63 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 ...
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 ...
31 views

161 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 vote
205 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 ...
77 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 ...
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 ...