The oblivious adversary conjecture for Oja's algorithm
The oblivious adversary conjecture for Oja's algorithm
Let be sufficiently large and let be a sequence of matrices in the space of symmetric matrices, each with spectral norm at most . Fix a step size .
Oja's linear-regret conjecture. There exists such a sequence , chosen obliviously and independently of Oja's initial random vector, for which Oja's algorithm incurs regret linear in with at least constant probability.
The question concerns whether Oja's algorithm can guarantee sublinear regret in the oblivious setting while storing only a vector and receiving only first-order information. The statement asserts that, for every fixed step size and sufficiently large horizon, an obliviously chosen bounded sequence can nevertheless force linear regret with nonvanishing probability.
Sources & referencesView supporting material
Primary source
Dan Garber, “From Oja's Algorithm to the Multiplicative Weights Update Method with Applications”, arXiv:2310.15559 (2023).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.