14

I haven't seen an answer from a trusted source, but I'll try to answer this myself, with a simple example (with my current knowledge). In general, note that training a MLP using back-propagation is usually implemented with matrices. Time complexity of matrix multiplication The time complexity of matrix multiplication for $M_{ij} * M_{jk}$ is simply $\...


7

Let's suppose that we have an MLP with $15$ inputs, $20$ hidden neurons and $2$ output neurons. The operations performed are only in the hidden and output neurons, given that the input neurons only represent the inputs (so they do not perform any operation). Each hidden neuron performs a linear combination of its inputs followed by the application of a non-...


5

For the evaluation of a single pattern, you need to process all weights and all neurons. Given that every neuron has at least one weight, we can ignore them, and have $\mathcal{O}(w)$ where $w$ is the number of weights, i.e., $n * n_i$, assuming full connectivity between your layers. The back-propagation has the same complexity as the forward evaluation (...


3

To the best of my knowledge, there haven't yet been many academic publications in this area, which could be broadly said to fall within Search-Based Software Engineering. Here are the ones I know of. Jerry Swan and Nathan Burles. Templar - A Framework for Template-Method Hyper-Heuristics. In: Genetic Programming - 18th European Conference, EuroGP 2015, ...


2

There is some recent work addressing this issue, to learn the conditional probability of an output sequence with elements that are discrete tokens corresponding to positions in an input sequence. see Pointer Networks


2

To the best of my knowledge there isn't any difference between the algorithmic methods and the NN methods. Those that can solve in polynomial time do not give a precise solution. Those that do give a precise solution do not solve in polynomial time. Of those that give a precise solution the fastest takes 2^Nth, but it blows up in terms of memory. The fastest ...


1

No. In general, you can't find a tight bound for evolutionary algorithms, and it is one of the main difference of these algorithms with the classical algorithms. You should notice that it does not mean you can't find when the evolutionary algorithms are finished! But, you can't find a tight bound for the algorithms time complexity to reach to the optimal ...


1

The update equation for value iteration that you show is time complexity $O(|\mathcal{S}\times\mathcal{A}|)$ for each update to a single $V(s)$ estimate, because it iterates over all actions to perform $\text{max}_a$ and over all next states for $\sum_{s'}$. The sources you have found are probably counting an entire sweep through the state space as an "...


1

It's not completely clear from your question, but it looks like you want to prove that exact inference in a Bayesian Network is both NP-Hard and P-Hard. It appears that you have proven that it is NP-Hard, but are unsure how to show that it is also P-Hard. This is more of a TCS question than an AI question, but shouldn't be too difficult. You just need to ...


1

There are a few technical papers and books on the topic Computational Limitations on Learning from Examples (1988) by Leonard Pitt and Leslie G. Valiant, published in Journal of the ACM Training a 3-node neural network is NP-complete (1992) by Avrim L. Blum and Ronald L. Rivest, published in Neural Networks Computational complexity of neural networks: a ...


1

First thing to remember is time-complexity is calculated for an algorithm. An algorithm takes an input and produces an output. Now in case of neural networks, your time complexity depends on what you are taking as input. Case 1: Input is just the dataset. Architecture and hyperparameters are fixed in the algorithm. Whenever we say time complexity of an ...


1

I found a paper that gives a table of time complexities for different architectures using linear programming-based training: https://arxiv.org/abs/1810.03218


1

A potential disadvantage of gradient-based methods is that they head for the nearest minimum, which is usually not the global minimum. This means that the only difference between these search methods is the speed with which solutions are obtained, and not the nature of those solutions. An important consideration is time complexity, which is the rate at ...


Only top voted, non community-wiki answers of a minimum length are eligible