29
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 ...
- 406
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 ...
- 41.4k
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 ...
- 41.4k
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 ...
- 563
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,266
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 ...
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 ...
- 281
2
votes
Why should one expect the backward pass to take twice as long as the forward pass?
This is a general fact of automatic/algorithmic differentiation. In the forward transport of tangents as well as any backward transport of gradients, each multiplication node splits in two on the ...
- 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 ...
- 41.4k
2
votes
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 ...
- 411
1
vote
Unable to understand Figure 3.13 Artificial Intelligence: a Modern Approach
The table's "Nodes" column uses rough approximations, as do most of the values in the table, because it is trying to give an intuition about scaling, and not accurate predictive values for ...
- 33.3k
1
vote
Accepted
What does the branching factor mean in the time complexity of Breadth-First Search (BFS)
Math is just fine. Its all about the definition of $\mathrm{O}(\cdot)$. Checkout the wiki page about Big-O Notation.
Basically, your function $T(b) = 1 + b + b^{2} + \cdots + b^{d}$ belongs to the ...
- 915
1
vote
The complexity order of regret (especially in online reinforcement learning)?
I assume your algorithm to loop over $K$ policies (or episodes), for $H$ steps, on each state and action pairs (where $X=|\mathcal S|$ and $A=|\mathcal A|$ denote the size of the state and action ...
- 3,186
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
Prove that in such cases, it is possible to find an ERM hypothesis for $H_n$ in the unrealizable case in time $O(mnm^{O(n)})$
Here's a rough proof sketch that might be clearer, but is probably less precise, than the solution you already have.
We have a sequence of hypotheses classes, but the problem actually only asks us to ...
- 9,392
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,836
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 ...
- 33.3k
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,392
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-...
- 41.4k
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
Only top scored, non community-wiki answers of a minimum length are eligible