応答に対する適応的汚染を伴う頑健回帰：最適率と計算上の障壁

要旨: 本論文では、共変量はクリーンである一方、応答は適応的な方法で汚染され得る汚染モデルのもとで、頑健回帰を研究する。古典的なハーバーの汚染モデルとは異なり、そこでは共変量と応答の両方が汚染され得て、汚染割合が0とならない定数である場合には、一貫した推定は不可能である。しかし、クリーンな共変量の設定では統計的保証が厳密に改善されることが分かる。具体的には、クリーンな共変量に含まれる追加情報を注意深く活用することで、ハーバー汚染のもとで達成可能な推定レートよりも良い推定レートを達成する推定量を構成できることを示す。ハーバーモデルと対照的に、この改善されたレートは、汚染が定数であっても一貫性を意味する。マッチするミニマックス下界は、ファノの不等式と、m>2 個の分布を同時に一致させる汚染過程の構成を用いて確立する。これは、ハーバー設定における従来の2点下界の議論を拡張するものである。情報理論的観点からハーバーモデルに対する改善が得られるにもかかわらず、本論文では、統計的問い合わせ（Statistical Query）および低次数多項式（Low-Degree Polynomial）の下界という形式で、問題が強い情報—計算ギャップを示すことに対する形式的な証拠を提示する。本結果は、情報理論的な改善が多項式時間アルゴリズムによっては達成できないことを強く示唆し、クリーンな共変量を伴う頑健回帰における情報理論的限界と計算的限界の間に本質的な隔たりがあることを明らかにする。