Sparse Representations of Positive Functions via First and Second-Order Pseudo-Mirror Descent
This work addresses optimization in reproducing kernel Hilbert spaces for nonnegative functions, which is incremental as it extends existing mirror descent methods with new techniques for computational efficiency and error handling.
The paper tackles the problem of expected risk minimization with nonnegative constraints, motivated by maximum likelihood estimation and trajectory optimization, by developing first and second-order stochastic mirror descent variants with pseudo-gradients and compressive projections, achieving favorable performance in experiments on inhomogeneous Poisson Process intensity estimation.
We consider expected risk minimization problems when the range of the estimator is required to be nonnegative, motivated by the settings of maximum likelihood estimation (MLE) and trajectory optimization. To facilitate nonlinear interpolation, we hypothesize that the search space is a Reproducing Kernel Hilbert Space (RKHS). We develop first and second-order variants of stochastic mirror descent employing (i) \emph{pseudo-gradients} and (ii) complexity-reducing projections. Compressive projection in the first-order scheme is executed via kernel orthogonal matching pursuit (KOMP), which overcomes the fact that the vanilla RKHS parameterization grows unbounded with the iteration index in the stochastic setting. Moreover, pseudo-gradients are needed when gradient estimates for cost are only computable up to some numerical error, which arise in, e.g., integral approximations. Under constant step-size and compression budget, we establish tradeoffs between the radius of convergence of the expected sub-optimality and the projection budget parameter, as well as non-asymptotic bounds on the model complexity. To refine the solution's precision, we develop a second-order extension which employs recursively averaged pseudo-gradient outer-products to approximate the Hessian inverse, whose convergence in mean is established under an additional eigenvalue decay condition on the Hessian of the optimal RKHS element, which is unique to this work. Experiments demonstrate favorable performance on inhomogeneous Poisson Process intensity estimation in practice.