Questions tagged [time-complexity]

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

14 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3
votes
0answers
160 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 ...
3
votes
0answers
146 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 ...
2
votes
1answer
47 views

Why is there a 1 in complexity formula of uniform-cost search?

I am reading the book titled Artificial Intelligence: A Modern Approach 4th ed by Stuart Russell and Peter Norvig. According to the book, the complexity of uniform-cost search is as $$ O(b^{1+\lfloor{...
2
votes
0answers
92 views

How would we get a good estimation of the asymptotic performance of machine learning algorithms?

The following question is from the webbook Neural Networks and Deep Learning by Michael Nielson: How do our machine learning algorithms perform in the limit of very large data sets? For any given ...
2
votes
1answer
125 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 ...
2
votes
0answers
616 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 ...
2
votes
0answers
42 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 ...
2
votes
0answers
202 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 ...
1
vote
0answers
59 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 ...
1
vote
1answer
193 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 ...
0
votes
0answers
20 views

Which kind of RNNs are mostly used in applications: hidden-hidden or actual output-hidden?

I came across two types of RNN while reading the chapter titled Sequence Modeling: Recurrent and Recursive Nets of the textbook named Deep Learning by Ian Goodfellow et al. First type: Recurrent ...
0
votes
0answers
41 views

What is the time complexity of DDPG algorithm?

Suppose we have a DDPG algorithm. The actor has N input nodes, two hidden layers with J nodes, and S output nodes. The critic has N+S input nodes, two hidden layers with C nodes, and one output node. ...
0
votes
0answers
25 views

Counterexample for every agent function being implemented by an agent program

A suggested counterexample for the statement 'Every agent function is implementable by some program/machine combination.' is solving intractable problem (like checking whether two well-formed formulas ...
0
votes
0answers
138 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 ...