Semi-optimal on-line learning for restricted gradients

Noboru Murata
Waseda University

It is known that a well designed on-line algorithm asymptotically converges to the solution as fast as any other algorithm. In a simple case where infinitely many i.i.d. training samples are obtained and the cost for training is likelihood, the convergence speed reaches the Cramer-Rao bound with Newton-Raphson gradients or Gauss-Newton gradients and 1/t annealing. On the other hand, in some practical cases, e.g. Elo rating system for evaluating the relative skill levels of players, only a few elements of the parameter are allowed to be updated at each training step, therefore optimally designed gradients cannot be applied.
In this talk, we consider the case where gradients are restricted in a specific subspace and discuss practically optimal designs of on-line algorithms in terms of convergence speed.

Presentation (PDF File)

Back to Stochastic Gradient Methods