1. I know that the time complexity of logistic regression can be as low as linear when the optimizer/solver is assumed to be linear, such as L-BFGS (this link)
  2. I know that multinomial logistic regression is the multi-class version of the logistic regression (the so-called maximum entropy classifier).
  3. One of the main applications of the maximum entropy classifier is Natural Language Processing (my field). However, when the number of classes is very high, the maximum entropy is not recommended, there. A clue of the reluctance of text miners to use MaxEnt while dealing with very many classes is brought in the following quotation from the Wikipedia

... and thus may not be appropriate given a very large number of classes to learn [Wikipedia].

The slow performance of MaxEnt while dealing with many classes (despite the potentially linear complexity of its binary version) made me curious about the time complexity of the MaxEnt. However, the more I searched the web the less I could find an article/paper discussing this issue.

I would appreciate if someone please let me know why the time complexity of MaxEnt is not linear. Mathematically speaking, assuming the number of samples as $n$, the number of features of each sample as $m$, and the number of classes as $c$, I am interested in knowing which of the $\{n, m, c\}$ are polynomial in the time complexity (Big $\mathcal{O}$ representation) of MaxEnt.

  • $\begingroup$ It should be noted that time complexity is not a function of the model (i.e., logistic regression), but the computational algorithm used to find approximate the solution (i.e., Newton's Method, Gradient Descent, etc.). $\endgroup$
    – Cliff AB
    Jul 8, 2018 at 15:48
  • $\begingroup$ @CliffAB Thanks; I edited the question accordingly (I am supposing it to be a linear algorithm such as L-BFGS) $\endgroup$
    – hossayni
    Jul 9, 2018 at 2:50
  • $\begingroup$ I wonder if it is true that it isn't used for large number of classes. It has been used for language modeling where the number of classes is several tens of thousands. $\endgroup$
    – Aaron
    Jul 27, 2018 at 5:01


Your Answer

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

Browse other questions tagged or ask your own question.