arXiv cs.LGが2026年11月3日(現地時間)付けで公開した論文「Agnostic Learning by Imitating」は、機械学習における判別モデルの訓練と生成モデルの訓練という二つの基本的な計算タスクが、計算複雑度において同等であることを証明した。この研究は、特定の機械学習モデルクラスとバイナリラベル付きデータ分布へのサンプルアクセスが与えられた状況下で、どちらのタスクがより難しいかという問いに対し、両者が密接に関連するだけでなく、実際に等価であると結論付けている。
この論文は、Sílvia Casacuberta、Parikshit Gopalan、Varun Kanade、Omer Reingold、Konstantinos Stavropoulos、Pranay Tankalaの各氏によって執筆された。
研究では、最適なクラスメンバーと同様に正負のラベルを区別する判別モデル（discriminative model）を訓練するタスクと、その出力がクラスの全メンバーによって実際のデータと区別できない生成モデル（generative model）を訓練するタスクが計算学習理論（computational learning theory）において提示された。これまでこれら二つのタスクの等価性については一方の方向が知られており、複雑性理論における規則性補題が、区別不可能性タスク（multiaccuracy）から判別タスク（agnostic learning）への効率的なオラクル削減（oracle reduction）を提供していた。
本研究の主要な貢献は、この逆方向における効率的なオラクル削減を提示した点にある。研究者らは、multiaccuracyオラクルが非常に強力なプリミティブであり、agnostic learningだけでなく、より要求の高い学習目標も同様に効率的かつ直接的な構築を通じて達成できることを示した。研究結果は、オラクルへの適応的なクエリを行う能力を決定的に利用しており、単一のmultiaccurate predictorの事後処理では、弱い形式の学習ですら不十分であるとした先行研究とは対照的な見解を示している。技術的には、この問題とオンライン設定におけるno-regret learningのバージョンとの関連付けを行い、follow-the-leader型アルゴリズムを用いてラベル分布を変更し、multiaccuracyオラクルの予測を集約している。
参考: arXiv cs.LG (アーカイブ) — 2026年11月4日 03:45 (JST)
原文ハイライト"Our main contribution is an efficient oracle reduction in the other direction."