Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [machine-learning]

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

0
votes
0answers
16 views

how is time complexity defined in computational learning theory

In general, when we say an algorithm $A$ PAC learns $C$ in time $t$, we say $A$ takes time $t$ before outputting a hypothesis $h$, and the hypothesis can be evaluated (on every $x$) in time $t$. Now ...
6
votes
1answer
184 views

How to generalize VC dimension?

Let's try to generalize the $VC$-dimension (of the class of hyperplanes) to include accuracy/error. Let $S$ be a set of points in $R^d$ and $t$ in $[0,1]$. We say that the class of hyperplanes $t$-...
1
vote
1answer
355 views

What kind of reinforcement learning is MENACE?

The famous MENACE matchbox computer for playing tic-tac-toe, invented by Donald Mitchie, is an early example of a reinforcement learning algorithm. Here is a description: ...an interesting machine ...
28
votes
1answer
1k views

Functions that are Not Efficiently Computable but Learnable

We know that (see, e.g., Theorems 1 and 3 of [1]), roughly speaking, under suitable conditions, functions that can be efficiently computed by Turing machine in polynomial time ("efficiently computable"...
4
votes
1answer
771 views

VC dimension of intersection of half-spaces

Define $$l_i(x) := \text{sgn} \left( w_i^\top x - b_i \right)$$ for $i=1,...,n$, where $x \in \mathbb{R}^d$. Then define the classifier $$ g(x) := \max \{ l_1(x),..., l_n(x) \}$$ which represents ...
-1
votes
0answers
20 views

Approximate a Decision Function Using a Neural Network

I have 10 variables $Y_i$, $i=1,\dots,10$ for a data record and I want to classify that record into one of three groups. A suggested decision function is the following: Group 1 if: $Y_i=0$ for $i=1,\...
2
votes
1answer
351 views

Follow the Perturbed Leader for nonlinear cost functions

The famous FTPL algorithm [1] is analyzing linear cost function. Is there any generalized proof for nonlinear functions known? Note that in the last paragraph of [1] it says "It would be great to ...
1
vote
1answer
63 views

Confusion about covering number

Problem I do not understand why larger $p$ will give a larger covering number. Since when $p\geq q$, the corresponding hypercube is also larger (by $\| x \| _ { q } \leq n ^ { ( 1 / q - 1 / p ) } \|...
0
votes
1answer
36 views

Does fixed hyperparameters perform well regardless the number of training examples?

I'm new in this community and I don't know whether my question is proper for this community. I will delete this post if it is not proper. I'm interested in deep learning network models and have a ...
6
votes
1answer
108 views

About assumptions needed to get convergence of stochastic gradient methods on non-convex objectives

What are the minimal conditions we know of under which we can prove that a stochastic gradient based algorithm can convergence to criticality on a non-convex objective? Are there any necessary ...
0
votes
1answer
81 views

Lower bound of real valued bounded function

Is well known that the lower bound on number of example necessary to reach a given error for concept classes $\Omega(d/\varepsilon)$ (cf. also Agnostic PAC sampling lower bound ) I am looking for ...
1
vote
1answer
75 views

About learning a single Gaussian in total-variation distance

I am looking for the proof of this following result which I saw as being claimed as a "folklore" in a paper. It would be helpful if someone can share a reference where this has been shown! Let $G$ ...
2
votes
1answer
77 views

Oncina-Garcia RPNI algorithm for learning DFAs

The question refers to this paper: ftp://altea.dlsi.ua.es/people/oncina/articulos/asspr1992.pdf Given a sample of $p$ positive and $n$ negative strings, RPNI constructs a consistent DFA in time $O((p+...
5
votes
1answer
311 views

Solving “all-marginals” problem for independent sets on grid

Suppose I have a distribution over independent sets on an $n\times n$ grid where the probability of independent set occupying nodes $(i_1,j_1),\ldots,(i_k,j_k)$ is proportional to $\lambda_{i_1,j_1}\...
0
votes
0answers
11 views

Is there a stochastic/online version of the GLM-Tron algorithm?

The GLM-Tron algorithm appeared in Theorem $1$ in this paper, https://arxiv.org/pdf/1104.2018.pdf Is there a stochastic version of this? (...essentially something that will randomly sample a few ...
1
vote
2answers
3k views

Derive logitboost using the logistic loss function

An additive model constructed using the exponential loss function $$L(y, f (x)) = \exp(−yf (x))$$ gives Adaboost. How can we derive the corresponding additive model (known as logitboost) using ...
1
vote
0answers
71 views

Complexity of low-rank matrix factorizations with rows in a simplex and outliers

Our goal is to obtain a matrix factorization in form of $M = U V'$, where $U\in\mathbb{R}^{d\times r}, V \in\mathbb{R}^{N\times r}$ and each row of $V$ satisfies $$ \sum_{j}(V)_{ij}=1, (V)_{ij}\ge 0 $$...
1
vote
0answers
36 views

Back-propagation for computing derivative of certain line integral

Consider a function F (think of neural networks) with two sets of parameters: (1) model parameters $\mathbf{w}$, and (2) input data ${\bf x} \in {\mathbb R}^d$. Fix $i \in [d]$, consider the following ...
4
votes
2answers
134 views

Are there hypothesis classes that are hard to learn but easy to test?

Let $H$ be a binary hypothesis class, it is easy to see that if $H$ is (efficiently) properly PAC learnable then it is also (efficiently) testable (here we use the standard notion of within or $\...
2
votes
1answer
111 views

Is there a gap between weak learning and PAC-learning?

For concreteness lets use the definitions of PAC and weak-learning as in the notes of Avrim Blum (http://www.cs.cmu.edu/~avrim/ML12/lect0208.txt) and also his notes on SQ-Learning (http://www.cs.cmu....
3
votes
0answers
87 views

Do features always induce a metric?

It is well-known in functional analysis that an inner product always induces a norm and a norm always induces a metric, and the reverse directions do not hold in general. I am wondering if a similar ...
2
votes
0answers
119 views

Crime prevention using graph theory and machine learning

I am looking for a way to the model the incidence of crime among a network of individuals. Part of it will use machine learning, and part of it will have to resort to some graph theoretic ...
2
votes
1answer
95 views

Stochastic gradient methods and risk of neural nets

Under many situations it is currently provable that we can minimize the risk of neural nets using stochastic gradient based algorithms. For example : https://arxiv.org/abs/1811.03804, https://arxiv....
2
votes
1answer
70 views

Empirical Rademacher averages versus Hoeffdings bound

Let $M$ be finite set with $n$ distinct elements. I want to probalistically approximate the relative counts $\frac{|P(Q)|}{|M|}$ of $Q \subseteq M$, where $P(Q) = |P \cap M|$. An upper-bound for ...
2
votes
0answers
46 views

Lower bounds for SRM?

This question is about structural risk minimization and model selection. Let $H_n$ be the collection of all binary classifiers on some fixed set with an $n$-bit description length in some fixed ...
2
votes
1answer
99 views

Minimization version of matrix p-norms?

I considered a minimization version of matrix p-norms, defined for a matrix $A$ by $$ f_p(A)= \min_{x\neq 0} \frac{||Ax||_p}{||x||_p}. $$ Notice that $f_p(A) = 0$ if and only if $A$'s columns are ...
4
votes
1answer
83 views

Data Mining of self-replicators

My current (very limited) understanding of the creative process that leads to the design of self-replicators is that any particular self-replicator, like Universal Constructor, Langton's loop or ...
10
votes
1answer
366 views

Agnostic PAC sampling lower bound

It is well-known that for classical PAC learning, $\Omega(d/\varepsilon)$ examples are necessary in order to acheive an error bound of $\varepsilon$ w.h.p., where $d$ is the VC-dimension of the ...
1
vote
0answers
51 views

Average margin bounds for separable SVM

Suppose we're training a linear separator in the realizable PAC setting. Given $m$ labeled examples $(x_i,y_i)$ in $\mathbb R^d\times\{-1,1\}$, a (consistent) linear separator is a vector $w\in\mathbb ...
1
vote
1answer
543 views

Why semi-gradient is used instead of the true gradient in Q-learning?

In reinforcement learning, with function approximation, a popular cost function is the Mean value error. This involves a target value V_pi and a current value estimate V_hat. When deriving the update ...
1
vote
1answer
57 views

Sample complexity for learning Boltzmann Distribution parameters

I am trying to think through the number of samples that I would need to estimate the parameters of a Boltzmann partition function to a desirable precision. Suppose that there are N possible states ...
11
votes
1answer
592 views

How do database aggregations form a monoid?

On cs.stackexchange I asked about the algebird scala library on github, speculating on why they might need an abstract algebra package. The github page has some clues: Implementations of Monoids ...
5
votes
2answers
338 views

Complexity of finding a consistent hyperplane

Given $m$ binary labeled points in $\mathbb{R}^d$, it is well-known that in general it's NP-hard to find a hyperplane that minimizes sample error. A brute-force search considers all $O(m^d)$ sample ...
0
votes
0answers
42 views

Function that maps non-linear distribution to normal distribution while maintaining distance

I have a collection $X$ of 10 million $(x,y,z)$ 3-tuples, where $x$, $y$, and $z$ are all numbers between 0 and 1. The distribution of $x$, $y$, and $z$ values are complex, and the distributions of $...
3
votes
2answers
175 views

How can AIC converge in the limit when even 2 parameter models can have infinite VC dimension?

AIC-based model-selection converges to zero error in the limit, and also has finite-sample convergence that is rate-optimal with respect to worst case minimax error [1]. (Note that AIC refers to ...
1
vote
0answers
48 views

Is there a theoretical guarantee that an autoencoder $g$ has $I(x;g(x)) \approx H(x)$?

I know that in general, a function $g$ can be a good auto-encoder (i.e., $g(x) \approx x$ for $x \sim D$) and on the same time $I(g(x);x)$ is small. This is the case when $g$ forms a good correlation ...
2
votes
1answer
766 views

What is the best place to get BibTeX entries for ICLR and other machine learning papers?

dblp seems the best i found so far (as also mentioned in the comments and in What is the best place to get BibTeX entries for computer science articles ?) but even there some papers from NIPS ...
3
votes
1answer
67 views

Examples of nontrivial non-discriminatory functions

I am reading Cybenko's "Approximation by Superpositions of a Sigmoidal Function". The paper defines a discriminatory function as: $\sigma$ is discriminatory if for a measure $\mu$, \begin{align} \int ...
8
votes
1answer
481 views

Difficulty of “learning” rare instances

Is there any result showing that models (say SVM, Neural-Net, kNN, etc) will have difficulty in learning "rare" instances/tail phenomena?
1
vote
0answers
28 views

Variability of gradient estimates and convergence rate in stochastic gradient descent/ascent

I am aware that convergence in stochastic gradient problems is very sensitive to the variance of your gradient estimator. One issue I'm running into is that the gradient is a random vector and so ...
1
vote
0answers
50 views

Ranking problem (single instance before others)

Suppose I am trying to learn function $f$ for a ranking-like objective: The mapping: ranking one element at the top and the rest at the bottom. More formally, suppose each input instance $I_i$ ...
3
votes
2answers
236 views

Discerning the best model for a problem

This is a vague question. I will do my best, I think it has definite answers. I am hoping for answers of the form "Read book x, learn this specific topic, read this paper/s". What is bothering me is ...
4
votes
1answer
108 views

“Learning” when test and train distributions don't match

We know that the theory of PAC-learning is distribution-free, i.e. assuming that the test and train distributions are the same, we have guarantees on learning the hypothesis. Question: what if the ...
1
vote
0answers
60 views

Learnability of under some characteristics of the distribution

TLDR; is there any results showing that more concentrated (or easier) distributions are easier to learn? In PAC-learning, the guarantee is given for any underlying distributions. But in reality, we ...
11
votes
4answers
12k views

Why can machine learning not recognize prime numbers?

Say we have a vector representation of any integer of magnitude n, V_n This vector is the input to a machine learning algorithm. First question : For what type of representations is it possible to ...
4
votes
1answer
522 views

Autoencoders and information compression

Disclaimer: I know very (very) little about deep nets, besides what an introductory course on machine learning would teach on neural networks, and skimming some paper abstracts and introductions. If ...
5
votes
0answers
246 views

What precisely is the extra power afforded by using deeper nets?

For any choice of activation function (fix the choice for all the hidden nodes for both the following DNNs) do we know of functions which some $k$ (hidden layer) DNN can compute but a $(k-1)-$DNN can'...
1
vote
0answers
54 views

To what extent supervised learning ERM learn first-order knowledge

Suppose I have a collection of (hidden) first-order rules: $$ \mathcal{R}: \{ Q_i(x) => P_i(x) \}_{i=1}^{k} $$ all defined over $x \in \mathcal{X}$. I can use these rules and (automatically) ...
7
votes
2answers
632 views

How does the Multiplicative Weights Update method maximize entropy?

"The Multiplicative Weights Update (MWU) method is known to maximize both utility and entropy". This is a comment by C. Papadimitriou on MWU. I understand that MWU maximizes utility as it solves ...
11
votes
1answer
479 views

Lower bounds for learning in the membership query and counterexample model

Dana Angluin (1987; pdf) defines a learning model with membership queries and theory queries (counterexamples to a proposed function). She shows that a regular language that is represented by a ...