26 votes
Accepted

What is the time complexity for training a neural network using back-propagation?

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 an MLP using back-propagation is ...
user avatar
9 votes
Accepted

What is the time complexity of the forward pass algorithm of a feedforward neural network?

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 ...
user avatar
  • 33.8k
5 votes

What is the time complexity for training a neural network using back-propagation?

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 ...
user avatar
3 votes

What is the computational complexity of the forward pass of a convolutional neural network?

What is the time complexity? The time complexity of an algorithm is the number of basic operations, such as multiplications and summations, that the algorithm performs. The time complexity is usually ...
user avatar
  • 33.8k
3 votes

Can machine learning be used to improve the average case complexity of an algorithm?

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. ...
user avatar
2 votes

What is the time complexity for training a neural network using back-propagation?

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
user avatar
2 votes

What is the time complexity for training a neural network using back-propagation?

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 ...
user avatar
2 votes

Can neural networks efficiently solve the traveling salesmen problem?

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 ...
user avatar
2 votes
Accepted

Can neural networks efficiently solve the traveling salesmen problem?

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 ...
user avatar
2 votes
Accepted

What is the time complexity for testing a stacked LSTM model?

The time complexity of an algorithm always depends on its implementation (e.g. searching in a red-black tree has a different time complexity than searching in an unbalanced binary search tree). This ...
user avatar
  • 33.8k
1 vote
Accepted

What is the most computationally efficient genetic algorithm?

First of all, for a lot of realistic problems, the fitness function evaluation is usually orders of magnitude greater in complexity than the rest of the genetic algorithm. This is not always true, but ...
user avatar
  • 391
1 vote

Why is the space-complexity of greedy best-first search is $\mathcal{O}(b^m)$?

I was struggling with the same question. This is what I came up with after thinking it through. With depth-first-search, you backtrack to a node that is a non-expanded child of your parent (or the ...
user avatar
  • 11
1 vote
Accepted

Why is the space-complexity of greedy best-first search is $\mathcal{O}(b^m)$?

After spending some time on the problem, I concluded that it is due to the fact that we need to store the heuristic function evaluations for all nodes during the traversal. So, one might claim that it ...
user avatar
1 vote
Accepted

Which algorithms, between ant colony or classical routing algorithms, have a better time complexity for the shortest path problem?

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 ...
user avatar
  • 1,663
1 vote
Accepted

What is the time complexity of the value iteration algorithm?

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 ...
user avatar
  • 23.9k
1 vote

Why is exact inference in a Bayesian network both NP-hard and P-hard?

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-...
user avatar
1 vote

What are some resources regarding the complexity of training neural networks?

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-...
user avatar
  • 33.8k

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