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
1
vote
1answer
20 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 ...
4
votes
1answer
173 views

What is the time complexity of the forward pass algorithm of a 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
51 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
52 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: ...
1
vote
1answer
106 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
742 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|^...
1
vote
1answer
204 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
52 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, ...
14
votes
2answers
8k 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 ...
5
votes
2answers
170 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 ...