Skip to main content

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
6 votes
2 answers
663 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 ...
Aryeh's user avatar
  • 10.6k
4 votes
1 answer
280 views

Adversarial Machine Learning, Learning with (Malicious) noise

I am reading some old papers regarding Learning With Malicious Noise. In one of them, Learning in the presence of Malicious Errors, by Kearns and Li $[1]$ (https://www.cis.upenn.edu/~mkearns/papers/...
Cip Baetu's user avatar
6 votes
2 answers
782 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 ...
Clement C.'s user avatar
  • 4,471
6 votes
1 answer
543 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 ...
Jack's user avatar
  • 123
1 vote
0 answers
187 views

Boolean functions with high query complexity for PAC learning

The most general theorem for PAC learning of Boolean functions that I am aware of is the theorem in section 3.4 of Ryan O'Donnel's book where its basically shown that Boolean functions whose Fourier ...
gradstudent's user avatar
  • 1,453
4 votes
0 answers
1k views

Universal Approximation Theorem for non-sigmoidal activation functions

The most cited Universal Approximation Theories for multi-layer feedforward neural networks by Cybenko (1989) and Hornik (1991) assume the activation functions of the network to be sigmoidal. However, ...
Robo's user avatar
  • 41
1 vote
0 answers
202 views

Off-policy Monte Carlo Control

The off-policy Monte Carlo control algorithm to learn the optimal state-value function $V^*$ is given as follows, which is obtained from Sutton's book. I have three questions concerning this ...
Steve's user avatar
  • 451
24 votes
2 answers
792 views

If machine learning techniques keep improving, what's the role of algorithmics in the future?

Let's look at the future some 30 years from now. Let's be optimistic and assume that areas related to machine learning keep developing as quickly as what we have seen in the past 10 years. That would ...
Jukka Suomela's user avatar
-2 votes
1 answer
122 views

Supervised learning from "bad" examples - ANN [closed]

I want to recommend one of three possible treatments for a patient, based on his blood values A, B and C. To solve this task, I have constructed a supervised feed-forward NN with back-propagation (...
G. Werner's user avatar
  • 113
3 votes
1 answer
1k views

Examples of Fat-Shattering Dimension

What are some good examples for analysis of a class's Fat-Shattering dimension? By (Alon et al) I know that the Fat-Shattering Dimension characterizes the learnability of real-valued function classes ...
Meni's user avatar
  • 168
-1 votes
1 answer
325 views

What is the connection between adversarial learning in machine learning and program synthesis?

In particular, I'm considering the similarities in Generative Adversarial Networks and Combinatorial Sketching for Finite Programs. In the first paper, our concern is with learning generator ...
Samuel Schlesinger's user avatar
6 votes
0 answers
102 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 ...
gradstudent's user avatar
  • 1,453
1 vote
0 answers
17 views

Can the distribution over the squared moduli of the 'probabilities' defined by an RBM with complex weights be written as an RBM with real weights? [closed]

I posted this question originally on the math boards, but figured it would be better suited here. https://math.stackexchange.com/questions/2203967/can-the-distribution-over-the-squared-moduli-of-the-...
Geert's user avatar
  • 111
3 votes
1 answer
147 views

Minimax agnostic risk for Lipschitz functions

For $L>0$, let $F_L$ be the class of all $L$-Lipschitz functions on $[0,1]$. Let $D$ be a joint distribution on $[0,1]\times\mathbb{R}$, from which we sample $n$ iid copies $(X_i,Y_i)$. Given any $...
Aryeh's user avatar
  • 10.6k
4 votes
1 answer
194 views

Kleinberg-consistency of spectral clustering

Spectral clustering refers to a family of graph-based algorithms, which usually rely on a similarity function rather than a metric, though a metric $\rho(x,y)$ can always be converted to a similarity ...
Aryeh's user avatar
  • 10.6k
2 votes
1 answer
124 views

Upper bound on the size of a Concept Lattice (Galois Lattice)?

A context is a tuple $(O, A, R)$ where $O$ is the set of objects, $A$ the set of attributes and $R \subseteq O\times A$ is a relation. For $o \in O$ and $a \in A$ we read $oRa$ as the object $o$ ...
Luz's user avatar
  • 427
-2 votes
1 answer
136 views

Can Pattern Recognition algorithms be considered Oracle Machines (in the Turing sense)?

I was reading Paul Churchland's "Engine of Reason, Seat of the Soul", where argues that humans (and potentially artificial neural networks as well) are capable of non-Turing computation because they ...
Alexander S King's user avatar
-2 votes
2 answers
158 views

Machine Learning: How ML algorithms build classification rules [closed]

I am truly fascinated by algorithms learning on their own with a little help from humans and as a newbie in this field (with programming experience mainly in C/C++), seek your help to obtain the big ...
Raj's user avatar
  • 107
2 votes
0 answers
90 views

How does white noise on the output channels influence the training of a neural network?

Let $\rho(\sigma): \mathbb{R} \rightarrow \mathbb{R}$ be a probability density that is parametrized by a parameter vector $\sigma \in \mathbb{R}^s$ (for example the normal distribution where $s = 1$ ...
a_guest's user avatar
  • 121
2 votes
1 answer
165 views

Learning from derivative data

In many machine learning algorithm, it is often assumed that outputs of unknown function and their corresponding inputs are given to estimate the unknown function. However, I wonder whether there ...
Kyoungjae Lee's user avatar
55 votes
5 answers
6k views

What kind of answer does TCS want to the question "Why do neural networks work so well?"

My Ph.D. is in pure mathematics, and I admit I don't know much (i.e. anything) about theoretical CS. However, I have started exploring non-academic options for my career and in introducing myself to ...
Neuling's user avatar
  • 659
1 vote
0 answers
73 views

A well-known instance of overcomplete dictionaries

sparse representation is: A signal can be represented as a linear combination of basis functions where the set of basis functions is called dictionary and data samples are much more than their ...
B Faley's user avatar
  • 141
5 votes
0 answers
252 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'...
gradstudent's user avatar
  • 1,453
0 votes
1 answer
525 views

Serial and parallel neural network [closed]

The question is: can exist a parallel or serial neural network or someone talked about this? For explanation, in the network a single record in a data set enter in the input layer as a value between ...
Jump46's user avatar
  • 11
2 votes
2 answers
929 views

Convergence and representation theorems for machine learning

I come from a pure math background and am not very familiar with machine learning. So, I'll start with an example to compensate for my confused grasp of the terminology. Let's say we have a function $...
Jack M's user avatar
  • 247
2 votes
1 answer
370 views

Are biases necessary to make neural networks universal approximators when using sigmoid activations?

In a neural network, a bias is a constant term that is added to the weighted input in a neuron/unit: output = activation_function( input1*weight1 + ... + inputn*weightn + bias) I can see that the ...
mtanti's user avatar
  • 123
4 votes
0 answers
104 views

Adversarial distributions for PAC lower bounds

The various PAC lower bounds (realizable, agnostic, bounded noise) construct distributions supported on $d$ points, where $d$ is the VC-dimension of the hypothesis class in question. Does anyone ...
Aryeh's user avatar
  • 10.6k
-2 votes
1 answer
108 views

Can you use only the first summation term of cost function for typical logistic regression?

I have recently come across a Matlab implementation that appears to be using only the first term (i.e. in itself a product) of the typical logistic regression cost function. ...
valentin's user avatar
  • 105
2 votes
0 answers
170 views

About lower bounding the sample complexity of a distribution

Given a joint probability distribution over a finite number of random variables (each with a finite range space) of which only a certain subset is observable, is there a notion of "sample complexity" ...
Student's user avatar
  • 654
6 votes
0 answers
169 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 ...
Zur Luria's user avatar
  • 359
5 votes
1 answer
122 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 \}, \\ ...
Daniel's user avatar
  • 749
0 votes
1 answer
94 views

The dependence of learning generalization bounds on the dimension of the instance space

Here is a popular generalization bound: If $X$ is the input space and $Y=\{0, 1\}$ is the output/label space, and there is a joint distribution $D$ defined on this space. We sample $m$ ...
Daniel's user avatar
  • 749
2 votes
0 answers
71 views

Impossibility result on metric learning?

Are there any fundamental limitations (impossibility results) known for metric learning? Are there any direct connection reduction from/to that I can use results in clustering? (e.g. this: 2 ) 2 ...
Daniel's user avatar
  • 749
8 votes
1 answer
458 views

Competing against an optimal weighted majority in experts algorithm

In the experts problem, $n$ experts give you binary predictions on a daily basis, and you have to predict whether it's going to rain tomorrow. That is, at day $t$, you know the past predictions of ...
R B's user avatar
  • 9,458
2 votes
0 answers
54 views

Question about the definition of projecting concepts in learning

I am self-studying in the area of query learning and having a difficulty in understanding the definition of closed under projection for concept classes discussed in several papers (for example, here (...
seteropere's user avatar
2 votes
1 answer
158 views

Tolerance parameter of statistical query model and adaptivity

It seems that the reasonable assumption for the tolerance parameter of statistical query model is roughly $1/\sqrt{n}$, which is obtained from concentration inequalities (see, e.g., Definition 2.3 of ...
Minkov's user avatar
  • 862
1 vote
1 answer
183 views

Does MCMC belong to the statistical query model?

It is known that a wide range of algorithms fall into the statistical query (SQ) learning model by Michael Kearns. Examples include k-means, logistic regression, naive Bayes (NB), SVM, ICA, PCA, ...
Minkov's user avatar
  • 862
4 votes
1 answer
505 views

Does Approx Carathéodory's theorem implies dimensionality reduction

Carathéodory's theorem says that if a point $x$ of $R^d$ lies in the convex hull of a point set $P$, then there is a subset $P′ \subseteq P$ consisting of $d + 1$ or fewer points such that $x$ can be ...
Ram's user avatar
  • 639
7 votes
2 answers
918 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 ...
salmAn's user avatar
  • 93
7 votes
1 answer
326 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 ...
Gigili's user avatar
  • 133
2 votes
0 answers
206 views

Convergence of online convex optimization methods

I am new to this subject so this question might seem a bit trivial Assume that in each round $t\in{{1,...T}}$ we choose $x_t\in K $ where $K$ is a compact and convex set, The common methods for ...
rabe's user avatar
  • 21
2 votes
0 answers
1k views

Is there a closed form equation for the back-propagation equation update in Neural Networks?

I was trying to understand if there was a way to express the back-propagation equations from neural networks in a better way as to understand them better. I believe the equations can be written in a ...
Charlie Parker's user avatar
4 votes
1 answer
91 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 ...
picrin's user avatar
  • 185
1 vote
0 answers
42 views

How to find a proper probabilistic formulation given the objective function terms?

I want to pose a problem as maximisation of MAP probability $P(X,Y|Z)$ and I know which terms I want to have in the objective function. However, I am unable to combine these terms to form a joint ...
maksay's user avatar
  • 31
2 votes
0 answers
48 views

second order regularisation on a neurofuzzy network with Bernstein basis functions

We're trying to build a neural network that uses a neurofuzzy approach. Our reference is the book Adaptive Modelling, Estimation and Fusion from Data: A Neurofuzzy Approach by Chris Harris, Xia Hong, ...
cnrk's user avatar
  • 31
-2 votes
2 answers
253 views

Lemma needed for my machine learning research [closed]

Say $\sigma_1, \sigma_2, \dots, \sigma_m$ are i.i.d distributed $\pm1$ variables. How do I show that for any choice of $S_1, S_2, \dots, S_d$ subsets of $\{1, 2, \dots, m\}$, the expectation of the ...
user196651's user avatar
2 votes
1 answer
102 views

List of papers on Runtime and Statistical Tradeoffs on Machine Learning

I was interested in the connection between (statistical) learning guarantees (or any statistical properties) and their relation to run time. For example, I was wondering, in what cases does having ...
Charlie Parker's user avatar
4 votes
1 answer
277 views

Are there any learning algorithms with any provable guarantees for manifold learning or manifold regularization?

First of all, I want to make clear that my question is about algorithms. I'd like to know if there are any algorithms with provable guarantees in the context of manifold learning (or manifold ...
Charlie Parker's user avatar
5 votes
3 answers
423 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 ...
Aryeh's user avatar
  • 10.6k
2 votes
0 answers
243 views

Dynamical systems analysis of deep learning

I am interested in finding out references that apply dynamical systems analysis to develop the "theory" of deep learning, specifically (say) feedforward deep neural nets. The only paper I seem to have ...
ab12's user avatar
  • 21

1 2 3
4
5
8