Projected Pseudo-Mirror Descent in Reproducing Kernel Hilbert Space

We consider expected risk minimization for strongly convex costs in the case that the decision variable belongs to a Reproducing Kernel Hilbert Space (RKHS) and its target domain must be non-negative, which arises in, e.g., intensity estimation of inhomogeneous point processes. To solve it, we develop a variant of stochastic mirror descent that employs (i) pseudo-gradients and (ii) projections. Compressive projections are executed via kernel orthogonal matching pursuit (KOMP), which overcomes the fact that RKHS parameterizations grows unbounded with time. Moreover, pseudo-gradients are needed, e.g., when stochastic gradients themselves define integrals over quantities that must be evaluated numerically. We derive accuracy/complexity tradeoffs between convergence in mean and bounds on the model complexity of the learned functions under standard assumptions. Experiments then demonstrate favorable tradeoffs for inhomogeneous Poisson Process intensity estimation on real data.