For questions related to the space complexity analysis of artificial intelligence algorithms.
Questions tagged [space-complexity]
11 questions
3
votes
2 answers
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 GBFS similar to DFS. It expands the whole branches…
iRestMyCaseYourHonor
- 141
- 1
- 6
2
votes
0 answers
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 algorithm it's natural to attempt to define a notion…
FoundABetterName
- 71
- 7
2
votes
1 answer
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 using back-propagation?
I know how to find the…
Ritika Gupta
- 121
- 1
- 3
2
votes
1 answer
What is the space complexity of breadth-first search?
When using the breadth-first search algorithm, is the space complexity $O(b^d)$, where $b$ is the branching factor and $d$ the length of the optimal path (assuming that there is indeed one)?
user42125
2
votes
0 answers
What is the memory complexity of the memory-efficient attention in Reformer?
When I read the paper, Reformer: The Efficient Transformer, I cannot get the same complexity of the memory-efficient method in Table 1 (p. 5), which summarizes time/memory complexity of scaled dot-product, memory efficient, and LSH attention.
The…
tsu
- 501
- 4
- 5
1
vote
1 answer
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 maximum depth of the graph. But it is not obvious why, for…
Zaratruta
- 111
- 2
1
vote
1 answer
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:
for step, eachBatch in enumerate(dataloader):
...
loss = loss_func(ytrue, ypred)
…
LSM
- 11
- 2
1
vote
1 answer
What is the space complexity of bidirectional search?
Is the space complexity of the bidirectional search, where the breadth-first search is used for both the forward and backward search, $O(b^{d/2})$, where $b$ is the branching factor and $d$ the length of the optimal path (assuming that there is…
user42125
1
vote
1 answer
What is the space complexity of iterative deepening search?
When using iterative deepening, is the space complexity, $O(d)$, where $b$ is the branching factor and $d$ the length of the optimal path (assuming that there is indeed one)?
user42125
1
vote
1 answer
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 and the output size are the same.
mftgk
- 19
- 1
- 1
- 2
0
votes
1 answer
Unable to understand Figure 3.13 Artificial Intelligence: a Modern Approach
I'm currently studying the functionality of BFS and the AIMA book shows
.
I am unable to replicate them using some trivial calculations.
For example, if the BFS generates $10^6$ nodes per second and I have $10^6$ nodes, it would be obvious that it…
