Scale Invariant Power Iteration
This work addresses a theoretical gap in optimization for machine learning practitioners, offering a novel method with proven convergence guarantees for scale invariant problems, though it appears incremental as it builds on existing power iteration frameworks.
The paper tackles the limited theoretical understanding of power iteration's convergence by introducing scale invariant problems and proving they can be efficiently solved with scale invariant power iteration (SCI-PI), which attains local linear convergence with a rate proportional to the top two eigenvalues of the Hessian at the optimum. Experimental results show SCI-PI is competitive with state-of-the-art algorithms and often yields better solutions in applications like independent component analysis, Gaussian mixtures, and non-negative matrix factorization.
Power iteration has been generalized to solve many interesting problems in machine learning and statistics. Despite its striking success, theoretical understanding of when and how such an algorithm enjoys good convergence property is limited. In this work, we introduce a new class of optimization problems called scale invariant problems and prove that they can be efficiently solved by scale invariant power iteration (SCI-PI) with a generalized convergence guarantee of power iteration. By deriving that a stationary point is an eigenvector of the Hessian evaluated at the point, we show that scale invariant problems indeed resemble the leading eigenvector problem near a local optimum. Also, based on a novel reformulation, we geometrically derive SCI-PI which has a general form of power iteration. The convergence analysis shows that SCI-PI attains local linear convergence with a rate being proportional to the top two eigenvalues of the Hessian at the optimum. Moreover, we discuss some extended settings of scale invariant problems and provide similar convergence results for them. In numerical experiments, we introduce applications to independent component analysis, Gaussian mixtures, and non-negative matrix factorization. Experimental results demonstrate that SCI-PI is competitive to state-of-the-art benchmark algorithms and often yield better solutions.