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
7
votes
1answer
443 views

Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning?

I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics). I am particularly ...
7
votes
1answer
631 views

What does PAC-learnability say about the learner runtime?

I am new to PAC-learnability. Assume a class $\mathcal{H}$ of hypotheses is PAC-learnable. Then all we know that if we draw polynomial number of examples (in $\delta$ and $\epsilon$), we can return a ...
7
votes
1answer
338 views

Statistical query model with Gaussian noise?

Kearns' statistical query model is a well-known learning model with noise tolerance. The statistical query oracle takes as input a statistical query of the form $\{\chi, \tau\}$. Here $\chi$ is any ...
7
votes
1answer
144 views

Optimal payoff from sampling from a collection of Bernoulli random variables?

Suppose I have several Bernoulli random variables, $\{X_1, \ldots, X_k\}$, each of which has a fixed probability $p_i$ of equaling 1 for each sample. Further suppose each $p_i$ is randomly distributed ...
7
votes
2answers
285 views

Learning Mixture of Univariate Gaussians

There are many papers on learning mixtures of multivariate Gaussians, which exploit various separation/projection techniques. What about one-dimensional (univariate) Gaussians -- any formal guarantees ...
7
votes
2answers
763 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 ...
7
votes
2answers
208 views

A PAC-like analogue for 1-class classification?

This is more of a philosophical question -- I am looking for a reasonable mathematical formulation of 1-class learning. In the PAC model, it's very natural to formulate our demand on the learner: ...
7
votes
2answers
522 views

Results on universal approximation for learners other than ANNs

I have an applied machine-learning and statistics background, and when I read the Universal approximation theorem, which (in the context of the learning theory of ANNs - Artificial Neural Networks) ...
7
votes
1answer
279 views

Complexity of constructing minimum depth decision trees

I am interested in the computational complexity of Problem 1: Given a finite, non-empty set $J$, given $A, B \subseteq \{0,1\}^J$ such that $A \cap B = \emptyset$, and given $n \in \mathbb{N}$, does ...
7
votes
1answer
148 views

Is it possible to create a machine learning classifier to generate Mock interfaces for systems testing?

I'm investigating whether it is feasible to be able to learn a system interface by watching network traffic (assuming the usual problems are solved e.g. encryption etc) I haven't been able to find ...
7
votes
2answers
267 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 ...
7
votes
1answer
311 views

Trying to understand a paper on ksvd algorithm (dictionary learning) by Elad, et al

Trying to understand a paper titled KSVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation by M.Elad, et al; my take of section IV.C. detailed description of KSVD, is ...
7
votes
0answers
168 views

Universal approximation theorem of second order

The universal approximation theorem (https://en.wikipedia.org/wiki/Universal_approximation_theorem) informally states that up to several conditions, any function can be approximated by a shallow ...
7
votes
0answers
183 views

Testing the degree of a vertex

Let's say we have a graph $G$ with $n$ vertices. Given $\epsilon>0$ and a specific vertex $v$, consider the problem of deciding whether $\mathrm{deg}(v) < \frac{\epsilon}{3}n$ or $\mathrm{deg}(v)...
7
votes
0answers
200 views

Sample complexity of PAC learning all k-DNFs over the uniform distribution

Is sample complexity of PAC learning all $k$-DNFs over the uniform distribution known (that is all DNFs with all terms of size at most $k$ and without restriction on the number of terms)? The only ...
6
votes
3answers
254 views

Asymmetry in Property Testing Definition

Property Testing refers to the problem of making a small number of queries to determine whether $x$ is in some language $L$ or whether it is far away from being in $L$. More precisely we want to ...
6
votes
3answers
423 views

Reference Request: Computational Learning Theory

Pretty soon I will be finishing up Understanding Machine Learning by Shai Ben-David and Shai Shalev-Shwartz. I absolutely love the subject and want to learn more, the only issue is I'm having trouble ...
6
votes
2answers
5k 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 ...
6
votes
2answers
568 views

Applications of Takens' theorem to TCS?

My apologies if the question is a tad vague—I did try to search the literature for more, but didn't find anything (the similarity between the keywords "Takens" and "taken" on Google may be partly to ...
6
votes
1answer
343 views

Textbook/resources for a beginning researcher in (Machine) Learning Theory

I'm looking to begin understanding basic concepts, notions, results and definitions in the area of Computational Learning Theory (or the theory of Machine Learning), as is done in the theoretical ...
6
votes
1answer
10k views

Computational complexity of learning (classification) algorithms - fitting the parameters

My wish is to describe the time complexity of several classification approaches. For example, suppose we have $n$ data points in $m$ dimensional space and a binary class variable. We do not assume ...
6
votes
1answer
266 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$-...
6
votes
1answer
227 views

Is there an accepted name for Ross Quinlan's adaptation of the ID3 decision algorithm to use a Pearson's chi-squared test for independence?

In Ross Quinlan's seminal paper Induction of Decision Trees, Quinlan summarizes the current state of machine learning in 1985 and loudly introduces the ID3 decision algorithm in the context of its ...
6
votes
0answers
92 views

Looking for an easy/pedantic exposition of Renegar's famous result on polynomial optimization

In September $1989$, Renegar had this famous sequence of 3 papers titled, "On the Computational Complexity and Geometry of the First-order Theory of the Reals, Part I/II/III". I was wondering if ...
6
votes
0answers
163 views

Machine learning algorithms on hypergrap models

Graphical models are a very useful tool with many applications, whereby a joint distribution of a set of random variables is modeled using only pairwise dependencies between the variables, and two ...
6
votes
0answers
139 views

Learning read-once branching programs with membership queries

Let $B=\{0,1\}$. A read-once branching program of width $n$ and size $w$ is given by a graph with layers $0,\ldots, n$, where the first layer has just the starting node, the last layer has nodes ...
6
votes
0answers
115 views

Branching Boosting Algorithms

Long/Servedio showed AdaBoost/etc doesn't perform well under noisy environments, but that branching forms of boosting do. Can any point me to a list of branching boosting algorithms, or a reference ...
6
votes
0answers
182 views

Occam razor for exact learning with membership/equivalence queries

In PAC learning, there is the "Occam razor" principle, which says that learning is qualitatively equivalent finding a succinct hypothesis that is consistent with the training samples. My question is ...
5
votes
1answer
197 views

Latest word on cross validation?

It's a standard result leave-one-out cross-validation is an unbiased estimator of the risk (see, e.g., Lemma 4.1 in Mohri, Rostamizadeh, Talwalkar). Are there any "better" results? Such as, say, with ...
5
votes
1answer
104 views

Generalization bounds for multiclass learning when the output is vector space?

There are plenty of results for muli-class learning with with fixed discrete labels: $$ \text{Standard multi-class classification:} \begin{cases} f: X \rightarrow Y_{index} = \{1, 2, 3, ..., k \}, \\ ...
5
votes
1answer
812 views

Computational Complexity of Computer Vision Problems

What is the computational complexity of computer vision problems (reconstruction, detection, etc.)? Are these problems NP-complete? Are they NP-hard? In most cases this will boil down to determining ...
5
votes
1answer
526 views

Understanding the No Free Lunch Theorem

I came across the No Free Lunch Theorem via Jürgen Schmidhuber's paper on Universal Search and there were a couple remarks on NFL which stood out to me. The first was that we can't define a uniform ...
5
votes
4answers
1k views

Genetic Algorithm to Draw a Graph? Position assignment problem

I have an assignment problem at hand and am wondering how suitable it would be to apply local search techniques to reach a desirable solution (the search space is quite large). I have a directed ...
5
votes
2answers
384 views

Learnability of constraint satisfaction problems CSPs?

This may sound more like a soft question but I am struggling to find an answer for it. While the learnability of Bayesian Networks and other graphical models are well detailed in the literature of ...
5
votes
2answers
2k views

Why is Bayesian filtering better than Neural Networks when classifying spam?

According to several people on StackOverflow Bayesian filtering is better than Neural Networks for detecting spam. According to the literature I've read that shouldn't be the case. Please explain!
5
votes
3answers
347 views

Dimensionality reduction in machine learning

This is less of a question and more of a "here's my take let me know if you agree" (so I guess it might turn into a big-list?). Dimensionality reduction refers to a collection of techniques that ...
5
votes
1answer
1k views

What happens if you minimize $D_{KL}(P_{parameters} || P_{data})$ under the Kullback-Leibler divergence?

If $D_{KL}$ is the Kullback-Leibler divergence, minimizing $D_{KL}(P_{data}||P_{parameters})$ performs maximum likelihood estimation of the parameters. What happens if you minimize $D_{KL}(P_{...
5
votes
1answer
352 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}\...
5
votes
0answers
250 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'...
5
votes
0answers
117 views

extracting/ exploiting similarity of SAT instances by solver

suppose that two SAT formulas on different variables $F_1, F_2$ are given on the input that are known to be true and the problem is to build an algorithm that finds a solution to each. the formulas ...
5
votes
0answers
183 views

Complexity of the Transductive SVM training problem

The Transductive Support Vector Machine training problem is a non-convex mixed integer programming problem: Transductive Support Vector Machine training problem. $$ \begin{align} \mathop{\text{...
4
votes
2answers
422 views

Support Vector Machines and privacy-preservation

suppose we have data matrix A m-by-n (m observations and n features) which I want to Apply SVM on it achieving privacy (Privacy-Preserving SVM) the questions are:- 1 - Is applying kernel trick ...
4
votes
2answers
437 views

Learning a coin's bias (localized)

It's well known that the minimax sample complexity for estimating the bias $p$ of a coin to additive error $\epsilon$ with confidence $\delta$ is $\Theta(\epsilon^{-2}\log(1/\delta))$. What if we ...
4
votes
1answer
589 views

Parameters of energy function for TSP

[This question was initially asked here. It went unanswered so I thought I should ask it in a different community.] I am reading this paper by Hopfield et al. On page six, the authors defined the ...
4
votes
2answers
388 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 ...
4
votes
2answers
195 views

How to compute the disagreement between hypotheses

Given a class of hypothesis $\mathcal{H}$ representing the set of all consistent hypotheses with the examples seen so far, how to compute the region of uncertainty? The region of uncertainty is ...
4
votes
1answer
257 views

What was the significance of Leslie Valiant's, “A Theory of the Learnable?”

It seems like two of the main takeaways were that there is a natural limit to what computers can learn, and learning is bounded by polynomial algorithms. Why was his paper significant in the broader ...
4
votes
1answer
238 views

minimal finite automata given in-words and out-words

this seems an interesting FSM optimization problem; have not seen it studied, wondering if it has been and/ or looking for other insight. given: two finite sets of words $S_{in}$ and $S_{out}$. ...
4
votes
1answer
86 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 ...
4
votes
2answers
166 views

What are some good resources for strengthening my theoretical foundation for machine learning?

I'm a computer science major and I'm taking a lot of machine learning courses. I'm finding that my theoretical foundation on subjects like calculus and linear algebra are not as strong as I'd like ...

1
2
3 4 5
7