First Order Stochastic Optimization with Oblivious Noise
First Order Stochastic Optimization with Oblivious Noise
复制标题
DOI：
--
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Ilias Diakonikolas;Sushrut Karmalkar;Jongho Park;Christos Tzamos
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas;Sushrut Karmalkar;Jongho Park;Christos Tzamos
我们通过忽略的噪声启动随机优化的研究，在我们的设置中广泛概括了标准的重尾噪声。不一定是居中的，我们假设访问X的随机梯度的噪声，X返回vector∇f（γ，x） +ξ，其中γ是有界的方差观察噪声和ξ是独立于γ和X的唯一假设，从理论上讲，当inliersα的分数小于1 /2时，恢复接近目标的单个解决方案是不可能的。另一方面，其中一个靠近真实的解决方案，如果α= 1 -ϵ，其中0 <ϵ <1/2足够小，则算法沿着途中恢复了一个解决方案。基于拒绝采样的算法可以执行噪声位置估计，这可能具有独立感兴趣。
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 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 ∇ f ( γ, x ) + ξ , where γ is the bounded variance observation noise and ξ is the oblivious noise that is independent of γ and x . The only assumption we make on the oblivious noise ξ is that Pr [ ξ = 0] ≥ α for some α ∈ (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 α is less than 1 / 2 . Our main result is an efficient 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 α = 1 − ϵ , where 0 < ϵ < 1 / 2 is sufficiently small constant, 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.