Near-Optimal Smoothing of Structured Conditional Probability Matrices
Utilizing the structure of a probabilistic model can significantly increase its learning speed. Motivated by several recent applications, in particular bigram models in language processing, we consider learning low-rank conditional probability matrices under expected KL-risk. This choice makes smoothing, that is the careful handling of low-probability elements, paramount. We derive an iterative algorithm that extends classical non-negative matrix factorization to naturally incorporate additive smoothing and prove that it converges to the stationary points of a penalized empirical risk. We then derive sample-complexity bounds for the global minimzer of the penalized risk and show that it is within a small factor of the optimal sample complexity. This framework generalizes to more sophisticated smoothing techniques, including absolute-discounting.
Given two discrete random variables X and Y (each taking k values), the paper considers the problem of estimating the k X k matrix P defined by P(i, j) = P(Y = j| X = i) from n i.i.d observations (X_s, Y_s), s = 1,..,n under the assumption that P can be factorized as AB for two similar stochastic matrices A and B of orders k X m and m X k respectively. The paper proposes an alternating optimization scheme for estimating P. A complication arises from the fact that many of the observed counts may be zero and the author propose at least two different ways of tackling it. 
If my understanding is correct, Theorem 1 of the authors does not quite apply to their algorithm ADD-1/2-Smoothed Low-Rank. Instead, it applies to the non-computable algorithm where they assume that they have a minimizer of the objective function in Theorem 3. It is not clear if the alternating optimization algorithm proposed in the paper is guaranteed to converge to a minimizer of the objective in Theorem 3. If this is true, the authors should mention this before stating Theorem 1 to avoid misleading the reader.   The "discounting" seems important from the Experiments section but this is not described in the main paper. If this is so important, the authors should make room for this in the main paper.   The main results  (Theorem 1 and 2) are not so surprising given that this is almost a parametric estimation problem with ~mk parameters (so the rates should be km/n). The interesting aspect here is if there would be log terms in the minimax rate. Theorem 1 has log-factors while Theorem 2 has none. It will be great if the authors can determine if there should be a log term or not in the minimax rate.   It would also be helpful if the authors can comment on how to choose m somewhere in Section 5. It appears from their experiments that they do this via cross validation but a careful specification in Section 5 would be appreciated.