28 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 ...
M.kazem Akhgary's user avatar
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 ...
nbro's user avatar
  • 40.5k
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 ...
nbro's user avatar
  • 40.5k
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 ...
maaartinus's user avatar
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. ...
NietzscheanAI's user avatar
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, ...
dd123's user avatar
  • 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 ...
nbro's user avatar
  • 40.5k
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 ...
Mike NZ's user avatar
  • 401
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 ...
James V Stone's 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 ...
Fadi Bakoura's 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 ...
scientious's user avatar
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 ...
Neil Slater's user avatar
  • 32.1k
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 ...
pi-tau's user avatar
  • 797
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 ...
Luca Anzalone's user avatar
1 vote

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 ...
Lutz Lehmann's user avatar
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 ...
Thomas's 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 ...
iRestMyCaseYourHonor's user avatar
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 ...
John Doucette's 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 ...
OmG's user avatar
  • 1,816
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 ...
Neil Slater's user avatar
  • 32.1k
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-...
John Doucette's 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-...
nbro's user avatar
  • 40.5k
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
Giorgio Luigi Morales Luna's user avatar

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