Questions tagged [time-complexity]

For questions related to the time complexity (e.g. in Big-O notation) of AI and ML algorithms.

Filter by
Sorted by
Tagged with
3
votes
0answers
45 views

What is the time complexity for training a gated recurrent unit (GRU) neural network using back-propagation through time?

Let us assume we have a GRU network containing $H$ layers to process a training dataset with $K$ tuples, $I$ features, and $H_i$ nodes in each layer. I have a pretty basic idea how the complexity of ...
0
votes
0answers
27 views

What is the time complexity for training a single-hidden layer auto-encoder?

What is the time complexity for training a single-hidden layer auto-encoder, for 1 epoch? You can assume that there are $n$ training examples, $m$ features, and $k$ neurons in the hidden layer, and ...
1
vote
1answer
30 views

Why does CNN forward pass take longer compared to MLP forward pass? [closed]

Let's take a 32 x 32 x 3 NumPy array and convolve with 10 filters of size 2 x 2 x 3 with stride 2 to produce feature maps of volume 16 x 16 x 10. The total number of operations - 16 * 16 * 10 * 2 * 2 *...
1
vote
1answer
54 views

What is the time complexity of the upsampling stage of the U-net?

I am trying to determine the complexity of the neural network we use. The neural network is a U-net generator with an input shape of NxN (not an image but image-like data) and output of the same shape....
1
vote
1answer
266 views

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

How do I determine the computational complexity (big-O notation) of the forward pass of a convolutional neural network? Let's assume for simplicity that we use zero-padding such that the input size ...
1
vote
1answer
52 views

Continuous state and continuous action Markov decision process time complexity estimate: backward induction VS policy gradient method (RL)

Model Description: Model based(assume known of the entire model) Markov decision process. Time($t$): Finite horizon discrete time with discounting factor State($x_t$): Continuous multi-dimensional ...
1
vote
0answers
52 views

Is subsection generation $O(n^4)$

When I say template matching, I'm referring to finding occurrences of a small image (the template) in a larger image. The OpenCV library provides the trivial solution, that slides the template over ...
2
votes
0answers
92 views

What is the time complexity of the forward pass and back-propagation of the sequence-to-sequence model with and without attention?

I keep looking through the literature, but can't seem to find any information regarding the time complexity of the forward pass and back-propagation of the sequence-to-sequence RNN encoder-decoder ...
1
vote
0answers
26 views

How to derive asymptotic run-time of seq2seq RNN? [duplicate]

I want to know the computational complexity of a sequence to sequence RNN in terms of the input and output length. I was wondering how I might go about deriving this in both training and inference.
2
votes
1answer
342 views

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

I am reading through Artificial Intelligence: Modern Approach and it states that the space complexity of the GBFS (tree version) is $\mathcal{O}(b^m)$. While I am reading, at some points, I found ...
4
votes
0answers
42 views

Given an input $x \in R^{1\times d}$ and a network with $s$ hidden layers, is the time complexity of the forward pass $O(d^{2}s)$? [duplicate]

I have a neural network that takes as an input a vector of $x \in R^{1\times d}$ with $s$ hidden layers and each layer has $d$ neurons (including the output layer). If I understand correctly the ...
2
votes
0answers
34 views

What is the complexity of policy gradient algorithms compared to discrete action space algorithms?

I am using a policy gradient algorithm (actor-critic) for wireless networks. The policy gradient-based algorithm helps because it considers continuous action space. But how much does a policy ...
1
vote
1answer
66 views

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)})$

Let $H_1$ , $H_2$ ,... be a sequence of hypothesis classes for binary classification. Assume that there is a learning algorithm that implements the ERM rule in the realizable case such that the ...
8
votes
1answer
1k views

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

How do I determine the time complexity of the forward pass algorithm of a feedforward neural network? How many multiplications are done to generate the output?
2
votes
0answers
136 views

What is the time complexity of an unparellelized Monte Carlo tree search?

I am writing a report where I used a slightly modified version of MCTS (not parallelized). I thought It could be interesting if I could calculate its time complexity. I'd appreciate any help I could ...
4
votes
1answer
58 views

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

I am developing an algorithm that, in certain moment, must explore an exponential number of objects derived from a graph: ...
2
votes
1answer
147 views

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

Which algorithms, between ant colony or classical routing algorithms, have a better time complexity for the shortest path problem? In general, can we compare efficiency of these two types of ...
2
votes
1answer
2k views

What is the time complexity of the value iteration algorithm?

Recently, I have come across the information (lecture 8 and 9 about MDPs of this UC Berkeley AI course) that the time complexity for each iteration of the value iteration algorithm is $\mathcal{O}(|S|^...
2
votes
1answer
356 views

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

I should show that exact inference in a Bayesian network (BN) is NP-hard and P-hard by using a 3-SAT problem. So, I did formulate a 3-SAT problem by defining 3-CNF: $$(x_1 \lor x_2) \land (\neg x_3 \...
2
votes
1answer
72 views

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

In the paper "Provable bounds for learning some deep representations", an autoencoder like a model is constructed with discrete weights and several results are proven using some random-graph theory, ...
23
votes
5answers
19k views

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

Suppose that a NN contains $n$ hidden layers, $m$ training examples, $x$ features, and $n_i$ nodes in each layer. What is the time complexity to train this NN using back-propagation? I have a basic ...
3
votes
0answers
127 views

How can I calculate the number of matrix additions, multiplications and divisions in AlexNet?

I'm a first-year student in machine learning and I really recently started to immerse myself. I need to calculate number of: matrix additions matrix multiplications matrix divisions which are ...
6
votes
2answers
796 views

Neural networks efficiently solve traveling salesmen problems?

I occasionally read papers that show neural networks solving traveling salesmen problems and multi traveling salesmen problems efficiently? 1) Is there any analysis of the meaning of efficiency of ...