On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA

Understand

In this paper we focus on the problem of Online Principal Component Analysis in the regret minimization framework.

• For this problem, all existing regret minimization algorithms for the fully-adversarial setting are based on a positive semidefinite convex relaxation, and hence require quadratic memory and SVD computation (either thin of full) on each iteration, which amounts to at least quadratic runtime per iteration.
• This is in stark contrast to a corresponding stochastic i.i.d.
• variant of the problem, which was studied extensively lately, and admits very efficient gradient ascent algorithms that work directly on the natural non-convex formulation of the problem, and hence require only linear memory and linear runtime per iteration.