I have a multinomial likelihood of the form:

$$P(\underline n|\underline x) = N!\prod_{i=1}^M \frac{f_i(\underline x)^{n_i}}{n_i!}$$

where $\underline x$ is a vector of parameters, $f_i(\underline x)\ge0$, $\sum_i f_i(\underline x)=1$. The data vector $\underline n$ consists of non-negative integers $n_i$ satisfying $\sum_i n_i=N$.

I intend to infer the parameters $\underline x$ by maximizing $P(\underline n|\underline x)$. Note that the number of parameters is smaller than $M$, so we can't just invert $f_i(\underline x) = n_i/N$, but rather need to do a numerical maximization of the likelihood (or posterior if one wishes to include a prior/regularization term).

Here $M$ can be very large, so I want to know if there is a variant of online learning or stochastic gradient descent that I can exploit, so that I can take steps where only one observation $i$ is used.

But either this is not possible or I don't know what keywords to use to search google, or maybe I am missing a simple trick. Every theorem I've seen on the convergence of stochastic gradient descent assumes that the examples are independent.


Here is a possible trick that I think can work. But I am open to comments.

We can write (I think this is called the Poisson-Multinomial trick):

$$P(\underline n|\underline x) \propto P^*(\underline n|\underline x) = \prod_i\frac{f_i(\underline x)^{n_i}}{n_i!}\mathrm{e}^{-f_i(\underline x)}$$

From the point of view of the inference, it makes no difference that the data $\underline n$ are generated according to $P(\underline n|\underline x)$ or to $P^*(\underline n|\underline x)$, because they only differ in a proportionality constant that is independent of the parameters $\underline x$. But in $P^*(\underline n|\underline x)$ the $n_i$ can be viewed as drawn from independent Poisson distributions with rates $f_i(\underline x)$.

Since under $P^*(\underline n|\underline x)$ we have independence, we can apply standard SGD or Adam or related online learning algorithms to the modified likelihood, feeding the $i$'s one by one, and all the usual convergence theorems will apply.

If someone reads this please let me know what you think and if it seems correct.


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.