# Can you use stochastic gradient descent with a multinomial likelihood?

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.

## 1 Answer

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.