27
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 ...
- 386
11
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 ...
- 37k
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 ...
- 523
5
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 ...
- 37k
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.
...
- 7,176
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 ...
- 364
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 ...
- 271
2
votes
Accepted
Why is the time complexity of the Triplet Loss $O(N^3)$
For each anchor data point $x_i^a$ in class $j$, the intra-distance should be computed $g_j$ times, where $g_j$ is the sample size of that class and the inter-distance should be computed as $N$ times, ...
- 36
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 ...
- 37k
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 ...
- 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 ...
- 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 ...
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 ...
- 1,723
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 ...
- 26.5k
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-...
- 9,037
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-...
- 37k
1
vote
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
1
vote
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible