Abstract
機械学習の最も一般的な設定の1つはロジスティック回帰である。ニューラルネットワークを含む多くの分類モデルでは、最終的な予測は線形スコアにロジスティックリンク関数を適用することで得られる。二値ロジスティック回帰では、フィードバックはソフトラベル（蒸留のように、データの真の条件付き確率に対応する）であってもよいし、サンプルされたハードラベル（値が \pm 1 を取る）であってもよい。本稿では、特に好ましい状況でさえ生じる基本的な問題を指摘する。具体的には、形式 \sigma(\mathbf{x}^{\top}\mathbf{w}^{\star}) のノイズのないソフトターゲットを学習することが目的である場合である。過剰制約のケース（すなわち、サンプル数 n が入力次元 d を超える、つまり n>d）で、例 (\mathbf{x}_i,\sigma(\mathbf{x}_i^{\top}\mathbf{w}^{\star})) が与えられていれば、\mathbf{w}^{\star} を復元できれば十分であり、したがってベイズリスクを達成できる。しかし、例が同じ条件付き分布 \sigma(\mathbf{x}_i^{\top}\mathbf{w}^{\star}) からサンプルされたハードラベル y_i によってラベル付けされ、かつ \mathbf{w}^{\star} が s-疎（s-sparse）であるときには、回転不変（rotation-invariant）なアルゴリズムが証明可能に最適ではないことを我々は示す。これらは過剰リスク Omega\!\left(\frac{d-1}{n}\right) を被る。一方で、過剰リスク O(\frac{s\log d}{n}) を達成する、単純な非回転不変アルゴリズムが存在する。最も単純な回転不変アルゴリズムは、ロジスティック損失に対する勾配降下法（早期終了付き）である。上記の上界を達成する疎ターゲット向けの、簡単な非回転不変アルゴリズムは、重み u_i,v_i に対する勾配降下法を用いる。ここで、線形重み w_i は u_iv_i として再パラメータ化される。
