ガウス分布の下での同次ハーフスペースに対する学習の準最適な暗号学的困難性
arXiv cs.LG / 2026/4/30
📰 ニュースIdeas & Deep AnalysisModels & Research
要点
- 本論文は、特徴量がガウス分布に従う状況で、同次ハーフスペースをラベル付き例から同定する学習・監査タスクを扱います。
- 例として、非有利（agostic）学習、片側の信頼可能学習、フェアネス監査の3設定を考え、それぞれに対応する損失指標で最良に近い同次ハーフスペースの出力を目指します。
- 著者らは、広く信じられているLearning With Errors（LWE）問題に基づく帰着により、準最適な計算困難性の結果を証明します。
- 既存研究が主に一般のハーフスペースを対象としていたのに対し、本研究は同次ハーフスペースにも困難性を拡張し、特にガウス分布の下での非有利学習における上界と下界のギャップを大きく縮めます。
- 全体として、LWE仮定の下でこれらのガウス・ハーフスペース学習およびフェアネス関連問題が計算的にどこまで可能かを、より強い理論的限界として示す点が主な貢献です。
