First Order Stochastic Optimization with Oblivious Noise

We initiate the study of stochastic optimization with oblivious noise, broadly generalizing the standard heavy-tailed noise setup.In our setting, in addition to random observation noise, the stochastic gradient may be subject to independent \emph{oblivious noise}, which may not have bounded moments and is not necessarily centered. Specifically, we assume access to a noisy oracle for the stochastic gradient of f at x, which returns a vector abla f(\gamma, x) \xi, where \gamma is the bounded variance observation noise and \xi is the oblivious noise that is independent of \gamma and x . The only assumption we make on the oblivious noise \xi is that \Pr[\xi 0] \ge \alpha, for some \alpha \in (0, 1) .In this setting, it is not information-theoretically possible to recover a single solution close to the target when the fraction of inliers \alpha is less than 1/2 . Our main result is an efficient {\em list-decodable} learner that recovers a small list of candidates at least one of which is close to the true solution. On the other hand, if \alpha 1-\epsilon, where 0 \epsilon 1/2 is sufficiently smallconstant, the algorithm recovers a single solution.Along the way, we develop a rejection-sampling-based algorithm to perform noisy location estimation, which may be of independent interest.