To circumvent the pessimism of the sequential setting, recent works [1]}, [2]}, [3]}, [4]}, [5]} have studied the smoothed sequential learning paradigm, where the adversary is constrained to choose \(x_t\)  at random from any probability distribution \(p_t\)  with density at most \(1/\sigma \)  with respect to a known measure \(\mu \) . The most current of these results point to a striking statistical computational gap: whereas there exist algorithms which attain regret that scales with \(\sqrt{T\log (/\sigma )}\) , computationally efficient algorithms can only hope for \(\mathrm {poly}(T/\sigma )\)  regret in general, even against a realizable adversary [5]}. In many \(d\) -dimensional settings, natural choices of \(\mu \)  yield \(\sigma = \exp (-\Omega (d))\) , and thus the exponential separation in \(\sigma \)  translates into an exponential separation in dimension. This gap motivates the following question: can the statistical-computational gap be eliminated in more structured settings? In this work, we answer the question affirmatively.
