From Oja's Algorithm to the Multiplicative Weights Update Method with Applications
Oja's algorithm is a well known online algorithm studied mainly in the context of stochastic principal component analysis. We make a simple observation, yet to the best of our knowledge a novel one, that when applied to a any (not necessarily stochastic) sequence of symmetric matrices which share common eigenvectors, the regret of Oja's algorithm could be directly bounded in terms of the regret of the well known multiplicative weights update method for the problem of prediction with expert advice. Several applications to optimization with quadratic forms over the unit sphere in $\reals^n$ are discussed.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Multiplicative Updates for Online Convex Optimization over Symmetric Cones
We study online convex optimization where the possible actions are trace-one elements in a symmetric cone, generalizing the extensively-studied experts setup and its quantum counterpart. Symmetric cones provide a unifyin…
Langevin Multiplicative Weights Update with Applications in Polynomial Portfolio Management
We consider nonconvex optimization problem over simplex, and more generally, a product of simplices. We provide an algorithm, Langevin Multiplicative Weights Update (LMWU) for solving global optimization problems by addi…
global-optimizationManagementLearning compositional functions via multiplicative weight updates
Compositionality is a basic structural feature of both biological and artificial neural networks. Learning compositional functions via gradient descent incurs well known problems like vanishing and exploding gradients, m…
LEMMAAccelerated Multiplicative Weights Update Avoids Saddle Points almost always
We consider non-convex optimization problems with constraint that is a product of simplices. A commonly used algorithm in solving this type of problem is the Multiplicative Weights Update (MWU), an algorithm that is wide…
On Sex, Evolution, and the Multiplicative Weights Update Algorithm
We consider a recent innovative theory by Chastain et al. on the role of sex in evolution [PNAS'14]. In short, the theory suggests that the evolutionary process of gene recombination implements the celebrated multiplicat…