This might be very basic but I am interested in evaluating the algorithmic complexity of an estimator of the form:

$$\hat{\theta} = \text{argmin}_{\theta} \;\; Q_n (\theta)$$

where $Q_n(\theta)$ denotes some objective function of interest (e.g. - log likelihood) computed on a sample of length $n$. $\hat{\theta}$ is assumed to be obtain through some numerical optimization methods (typically a stepwise procedure). Under this setting, how could I compute the algorithmic complexity of $\hat{\theta}$?

I am really not sure if this makes sense but here is how I approach this problem:

  • Suppose that the numerical procedure used to compute $\hat{\theta}$ requires $S$ steps to converge.
  • Assume that there exist a deterministic function, say $f(p)$, where $p$ denotes the dimension of $\theta$ such that $S \leq f(p)$ and that $f(p) < \infty$ for $p < \infty$.
  • Assume that $\mathcal{O} (Q_n(\theta)) = g(n)$ for all $\theta$.
  • Then $\mathcal{O}(\hat{\theta})$ is simply given by

$$\mathcal{O}(\hat{\theta}) = \mathcal{O}(Q_n(\theta) S) = g(n),$$

since $p$ is assume to be fixed (and bounded). This seems really too simple... Any comments would be more than welcome. Thank you very much.

  • $\begingroup$ You are not using Landau notation properly. I think you mean that $T_Q(n) \in O(g)$ -- but what is $g$? Which cost depends on which parameters? $\endgroup$ – Raphael Nov 13 '16 at 9:29
  • $\begingroup$ It depends on estimator chosen (MLE, MOME etc.), procedure used to obtain in. It will have iterative procedure until some error or fixed number of steps. Can you give exact method? $\endgroup$ – Evil Nov 13 '16 at 20:01
  • $\begingroup$ You seem to have created two accounts. I encourage you to register your account and then merge the two accounts, so you'll retain access to your post and be able to comment on answers. Also, please don't use the 'answer' box to comment on other answers or for anything that isn't directly an answer to the question that was asked. Thank you. $\endgroup$ – D.W. Nov 14 '16 at 14:59

The bound $O(Q_n(θ) \cdot S(p))$ represents only the cost of evaluating $Q_n$ once per step in the "numerical optimization method"; you ignore all other cost that incurs.

Without looking at the whole algorithm, little more can be done.

Note: I very deliberately replaced $S$ with $S(p)$. That is because there is no reason, per se, to believe that $S$ is a constant. You need to be more careful about setting up your cost functions; our reference question may be helpful.

  • $\begingroup$ You seem to have received a comment-as-answer here. $\endgroup$ – D.W. Nov 14 '16 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.