The oblivious adversary conjecture for Oja's algorithm

Let TT be sufficiently large and let A1,,AT\boldsymbol{A}_1,\dots,\boldsymbol{A}_T be a sequence of matrices in the space of symmetric n×nn\times n matrices, each with spectral norm at most 11. Fix a step size μ\mu.

Oja's linear-regret conjecture. There exists such a sequence A1,,AT\boldsymbol{A}_1,\dots,\boldsymbol{A}_T, chosen obliviously and independently of Oja's initial random vector, for which Oja's algorithm incurs regret linear in TT 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.