Projected Gradient Methods for Nonnegative Matrix Factorization

by Chih-Jen Lin

This paper proposed an optimization technique for NMF problems, which I think could also be extended to more general Bregman divergence. The idea is based on optimization. It is pointed out that most algorithms can converge to local stationary points not local minima. The multiplicative updating rule only ensures the convergence, whether it be stationary point (let alone local minima) or not. The proposed algorithm is quite simple, merely eliminating those coords out of the feasible domain (i.e. set those negative values to 0). The result looks better than the multiplicative updating rule.

Adaptive Online Gradient Descent

by Peter L. Bartlett, Elad Hanzan and Alexander Rakhlin

In this paper, we are looking for a game-like optimization problem. We have to pick up a x_t for an unknown objective f_t(x), which might be a loss the adversary might ompose upon us. To evaluate the final result, the accumulated loss w.r.t time t = 1, ..., T is compared with a fixed action x, that minimize the total lost. The difference of the two is hence called regret (why not wait until the last f_t is given),

There are several results with with problem:

• Zinkevich showed for linear function, the regret will increase as sqrt(T) using his proposed online gradient descent algorithm.
• Hazan et al showed under the assumption of strong convexity, the regret will increase as log(T).

This paper has several results:

• With a regularization technique, they propose an adaptive online gradient descent algorithm, which ensures 1-6 times regret when the coefficients for the regularizer are determined offline for the lowest regret.
  
• It might be proved that for linear functions and strongly convex functions, likewise rates, O(sqrt(T)) and O(log(T)), are to be achieved.
  
• There exists a similar algorithm for general L^p norm, with the help of Bregman divergence generalization, from L² in
  
  
  
  The Bregman divergence is