We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [time-complexity]

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

3 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2
votes
0answers
54 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
24 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
26 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 ...