Questions tagged [computational-complexity]

The amount of resources required to run a given algorithm in relation to a given task.

Filter by
Sorted by
Tagged with
35 votes
7 answers
8k views

What are examples of promising AI/ML techniques that are computationally intractable?

To produce tangible results in the field of AI/ML, one must take theoretical results under the lens of computational complexity. Indeed, minimax effectively solves any two-person "board game"...
k.c. sayz 'k.c sayz''s user avatar
6 votes
1 answer
293 views

What does "hard for AI" look like?

In theoretical computer science, there is a massive categorization of the difficulty of various computational problems in terms of their asymptotic worst-time computational complexity. There doesn't ...
Stella Biderman's user avatar
5 votes
1 answer
693 views

Why multiplayer, imperfect information, trick-taking card games are hard for AI?

AI reached a super-human level in many complex games such as Chess, Go, Texas hold'em Poker, Dota2 and StarCraft2. However it still did not reach this level in trick-taking card games. Why there is no ...
Cohensius's user avatar
  • 413
4 votes
1 answer
1k views

Would it take 1700 years to run AlphaGo Zero in commodity hardware?

From this link, AlphaGo would take millennia to run in regular hardware. They generated 29 million games for the final result, which means it's going to take me about 1700 years to replicate this. ...
BlueMoon93's user avatar
4 votes
1 answer
335 views

Is time/space estimation of possible actions required for creating an AGI?

Given infinite resources/time, one could create AGIs by writing code to simulate infinite worlds. By doing that, in some of the worlds, AGIs would be created. Detecting them would be another issue. ...
Răzvan Flavius Panda's user avatar
4 votes
0 answers
72 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 ...
Jonathan Azpur's user avatar
4 votes
0 answers
354 views

When using hashing in tile coding, why are memory requirements reduced and there is only a little loss of performance?

In the book "Reinforcement Learning: An Introduction" (2018) Sutton and Barto explain, on page 221, a form of tile coding using hashing, to reduce memory consumption. I have two questions ...
F.M.F.'s user avatar
  • 311
3 votes
2 answers
5k 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 ...
iRestMyCaseYourHonor's user avatar
3 votes
0 answers
55 views

Do we need as much information to know if we can can answer a question as we need to actually answer the question?

I am reading The Book of Why: The New Science of Cause and Effect by Judea Pearl, and in page 12 I see the following diagram. The box on the right side of box 5 "Can the query be answered?" ...
Lerner Zhang's user avatar
3 votes
0 answers
2k views

How much time does it take to train DQN on Atari environment?

I am trying to build a DQN model for the Atari Pong game, but I am not sure whether the model is learning at all. I am using the architecture described in the paper Playing Atari with Deep ...
Ach113's user avatar
  • 161
2 votes
1 answer
107 views

How to know if a real-time classifier is achivable in a low-power emdedded system?

Say I have an Machine/Deep learning algorithm I developed on a desktop pc to achieve a real-time classification of time series events from a sensor. Once the algorithm is trained and performs good, I ...
Hattori's user avatar
  • 201
2 votes
1 answer
993 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 \...
xava's user avatar
  • 423
2 votes
0 answers
496 views

Is there a literature on the time complexity of Neural Networks?

There exist various blog posts describing the time complexity of Fully Connected Neural Networks (1, 2, 3, 4); Convolutional Neural Networks (CNN) (5) and of Long Short-Term Memory (LSTM) networks (6)....
Daniel's user avatar
  • 21
2 votes
0 answers
133 views

Why do off-policy algorithms suffer from worse computational or time efficiency compared to on-policy algorithms?

When I run Soft-Actor-Critic (off-policy) in my Environment, the calculation of gradient updates takes almost twice the time compared to using PPO (on-policy). I also saw that ACER has a higher time ...
kitaird's user avatar
  • 115
2 votes
0 answers
358 views

What is symbol-to-number differentiation?

I recently came across symbol-to-symbol and symbol-to-number differentiation, out of which symbol to symbol seemed fairly straightforward - the computational graph is extended to include gradient ...
ashenoy's user avatar
  • 1,409
1 vote
1 answer
408 views

How to estimate the cost and time to complete an AI Project [closed]

If you are a freelancer, when a client asks to create a website we can easily measure how much the total cost is needed based on the requirements of the client. (the backend, UI/UX design, features, ...
malioboro's user avatar
  • 2,819
1 vote
1 answer
423 views

Instead of accumulating the gradient, can we accumulate loss values?

I have read and used Gradient Accumulation as a method to handle large batch size on smaller memory restrictions. It is described as following: ...
LSM's user avatar
  • 11
1 vote
1 answer
3k views

What is the time complexity for testing a stacked LSTM model?

In the data preparation phase, we have to divide the dataset into two parts: the training dataset and the test dataset. I have seen this post regarding the time complexity for training a model. ...
Anik Islam Abhi's user avatar
1 vote
1 answer
107 views

If Least-Squares TD is computationally more expensive, then why is it more data efficient than semi-gradient TD(0)?

In Sutton-Barto (Section: 9.8 Least-Squares TD, page 228): Authors say that Least-Squares TD is the most "data efficient" form of linear TD(0). Later, in this section, they say the ...
user3489173's user avatar
1 vote
1 answer
544 views

Given an input of shape $(3, 32, 32)$, which is convolved with a $(3 \times 3)$ kernel, how do I calculate the FLOPS?

I have an input tensor of shape $\mathbf{(3, 32, 32)}$ consisting of 3 channels, 16 rows, and 16 columns. I want to convolve the input tensor using $\mathbf{(3 \times 3)}$ kernel/filter. How can I ...
Mhasan502's user avatar
1 vote
1 answer
3k views

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

Suppose that a simple feedforward neural network (FFNN) contains $n$ hidden layers, $m$ training examples, $x$ features, and $n_l$ nodes in each layer. What is the space complexity to train this FFNN ...
Ritika Gupta's user avatar
1 vote
1 answer
74 views

Why the space complexity of depth-first search is O(bm)?

In "Artificial Intelligence: A Modern Approach", the authors say that the space complexity of depth-first search is proportional to O(bm), considering b as the branching factor and m the ...
Zaratruta's user avatar
  • 111
1 vote
0 answers
459 views

Does iterative deepening depth-first search expand at most twice as many nodes as breadth-first search?

My understanding is that iterative deepening search is roughly equivalent to breadth-first search, except instead of keeping all visited nodes in memory, we regenerate nodes as needed, trading off ...
xojfqa's user avatar
  • 101
1 vote
1 answer
118 views

What consequence would a polynomial time algorithm for SAT have on AGI?

$P$ vs $NP$ is a famous problem. We generally believe $P\neq NP$. However suppose there is a polynomial time algorithm of order say $O((n+m)^2)$ or $O((n+m)^3)$ (a low degree polynomial complexity ...
Justaperson's user avatar
1 vote
0 answers
55 views

Why does research on faster Transformers focus on the query-key product?

A lot of recent research on Transformers has been devoted to reducing the cost of the self-attention mechanism: $$\text{softmax}\left(\frac{Q K^T}{\sqrt{d}} \right)V,$$ As I understand it, the runtime,...
Betterthan Kwora's user avatar
1 vote
0 answers
2k views

What is the computational complexity in terms of Big-O notation of a Gated Recurrent Unit Neural network?

I have been digging up of articles across the internet in context of computational complexity of GRU. Interestingly, I came across this article, http://cse.iitkgp.ac.in/~psraja/FNNs%20,RNNs%20,LSTM%...
rahul tomar's user avatar
1 vote
0 answers
81 views

What is the efficiency of trained neural networks?

Training neural networks takes a while. My question is, how efficient is a neural network that is completely trained (assuming it's not a model that is constantly learning)? I understand that this is ...
Anton's user avatar
  • 111
1 vote
1 answer
569 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....
Ruli's user avatar
  • 153
0 votes
1 answer
10k 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 ...
mftgk's user avatar
  • 9
0 votes
1 answer
152 views

Why is the time complexity of the Triplet Loss $O(N^3)$

The triplet loss function uses an anchor, positive, and negative examples. If $N$ are the number of examples in the training set with $C$ classes, then I think that the time complexity should be $O(...
wd violet's user avatar
  • 103
0 votes
1 answer
35 views

Is size of trained model on disk a good measure of model complexity?

I am writing a research paper on my own custom CNN model for image classification. I am comparing my model architecture with pre-trained architectures, like DenseNet121 and InceptionV3. I want to ...
Dawood Ahmad's user avatar
0 votes
1 answer
23 views

How to estimate Time vs Memory trade-off prior to modelling

It is often the case when the time vs memory trade-off is underestimated prior to using ML/DL for solving a particular task. Taking into account the type, size and format of the available data and ...
Deyan's user avatar
  • 1
0 votes
0 answers
41 views

Pyramid Vision Transformer V2: Complexity of spacial reduction attention (SRA)

I'm currently reading the paper PVT v2: Improved Baselines with Pyramid Vision Transformer, where the authors improve a transformer architecture that can be used as a backbone for multiple computer ...
Christian Singer's user avatar
0 votes
0 answers
211 views

Issues with larger context lengths in a transformer model like GPT

Based on my understanding, one of the issues with longer context lengths is the computational complexity of attention mechanism which is quadratic. But is this really a problem on modern hardware with ...
rahul's user avatar
  • 101
0 votes
0 answers
9 views

Why is avoiding normalized models a practical solution for reducing the complexity in NNLM?

In the paper Efficient Estimation of Word Representations in Vector Space, the authors say that "avoiding normalized models completely by using models that are not normalized during training"...
Propr's user avatar
  • 1
0 votes
0 answers
46 views

Are autoencoders computationally cheaper than MLPs with the same number of neurons?

Are autoencoders computationally cheaper than other neural networks such as MLP with the same number of neurons? I have read in some papers that autoencoders train the network faster, and I could ...
Jesus M.'s user avatar
0 votes
1 answer
70 views

How is the training comlexity of NNLM word2vec calculated?

I was reading this paper on word2vec, and came around the following description of a feedforward NNLM: It consists of input, projection, hidden and output layers. At the input layer, N previous words ...
MDescamps's user avatar
-1 votes
1 answer
246 views

computational complexity for batch normalization technique [closed]

Could you please let me know weather it is possible to have a computational complexity formula for batch normalization technique or not? If someone can help me in this regard I will be appreciated.
code_lover's user avatar