技術要約：未知のリンク関数を持つ単一インデックスモデルに対する能動回帰

問題定式化

本論文は、一般的な $\ell_p$ 損失 ($p \ge 1$) の下における単一インデックスモデルの能動回帰（active regression）問題を取り扱う。目標は、既知のデータ行列 $A \in \mathbb{R}^{n \times d}$ ($n \gg d$) およびラベルベクトル $b \in \mathbb{R}^n$ に対し、残差を最小化するベクトル $x \in \mathbb{R}^d$ と 1-リプシッツ関数（$\text{Lip}_1$）のクラス内のリンク関数 $f$ を見つけることである：
$$\min_{f \in \text{Lip}_1, x \in \mathbb{R}^d} \|f(Ax) - b\|_p^p$$
この設定は能動的（active）である。すなわち、アルゴリズムは $A$ には完全にアクセスできるが、$b$ には座標クエリを通じてのみアクセスできる。本論文で扱う具体的な課題は、リンク関数 $f$ が未知であるケースであり、これは $f$ が既知であることを前提としていた先行研究とは対照的である。

手法

上界：非適応的サンプリングアルゴリズム

著者らは、線形回帰および既知のリンクを持つ単一インデックス回帰で使用される Lewis weight サンプリングの枠組みを拡張した、非適応的サンプリングアルゴリズム（Algorithm 2）を提案している。

1. Lewis Weight の構築: アルゴリズムは、行列 $A$ の Lewis weight $w_1, \dots, w_n$ を計算する。
2. 行の分割とサンプリング: 概念的には、$i$ 番目の行 $A$ は $k_i \approx w_i \cdot (n/d)$ 個のコピーに分割される。これらの行は、グローバルな確率 $\alpha$ で独立にサンプリングされる。
3. スケッチ化された最適化: アルゴリズムは、スケッチされたインスタンスに対して以下の正則化最小化問題を解く：
   $$(\hat{f}, \hat{x}) := \arg\min_{f \in \text{Lip}_1, x \in \mathbb{R}^d} \|S(f(Ax) - b)\|_p^p + \epsilon \|Ax\|_p^p$$
   ここで、$S$ はランダムな対角サンプリング行列である。

技術的解析：未知のリンクの制御

技術的な核心は、リンク関数 $f$ が未知の場合の一様サンプリング誤差を制御することにある。解析は、集合 $T \subseteq \text{Lip}_1 \times \mathbb{R}^d$ 上の Rademacher プロセス $\Psi$ を制御することに依拠している。

• 対称化と Dudley の積分: 誤差は、Rademacher プロセスに適用された Dudley の積分を用いて抑えられる。
• デカップリングの課題: インデックス集合が積構造（$f$ と $x$ を容易にデカップリング可能）を持っていた従来の作業とは異なり、$(1+\epsilon)$ 近似の要求により、非長方形のインデックス集合となる。著者らは、集合レベルではなく、不等式の連鎖の途中で $f$ と $x$ をデカップリングしている。
• $\text{Lip}_1$ のメトリック・エントロピー: 非標準的な重み付き sup-norm 下での Lipschitz クラスのメトリック・エントロピーの制御は、新たな貢献である。著者らは、$\text{Lip}_1$ の被覆数を $[-1, 1]$ 上の標準的な $L_\infty$ 被覆数によって抑える被覆補題（Lemma 1.3）を導入している。これにより、先行研究の $p=2$ の結果で使用されていた明示的な離散化の技術的オーバーヘッドを回避している。
• ブートストラップ法: 定数倍の近似から $(1+\epsilon)$ 近似へと解を精緻化するために、ブートストラップ引数が用いられている。

下界：困難なインスタンスの構築

タイトネス（tightness）を確立するため、著者らは $p > 2$ における困難なインスタンスを以下のように構築している：

• 球面符号（Spherical Code）: コヒーレンス $\tau$ を持つ $N$ 個のほぼ直交する単位ベクトル。
• 隠れたインデックス: レスポンスベクトル $b$ の中に、一様にランダムに選ばれたインデックス $I \in [N]$ が「植え付けられて」いる。
• ReLU リンク: リンク関数は $f(t) = \max\{0, t\}$ として固定されている。
• ショートリストの保証: 解析により、近似保証を満たすいかなるアルゴリズムも、真の $I$ を含む候補インデックスの「ショートリスト」を特定しなければならないことが示される。ベースライン入力 $b(0)$ と $b(I)$ のクエリ集合を比較することで、Yao のミニマックス定理を用いてクエリの下界を導出している。

主要な貢献と結果

1. 上界 (Theorem 1.1 / 3.2)

本論文は、未知のリンク関数を持つ一般的な $p \ge 1$ に対して、$(1+\epsilon)$ 近似を実現するランダム化アルゴリズムを提示している。

• クエリ計算量: アルゴリズムは、$b$ に対して $O(d^{1 \vee p/2} / \epsilon^{p \vee 2} \cdot \text{poly}(\log n))$ 回の非適応的クエリを行う。
• 意義: この結果は、未知のリンクに関する唯一の先行研究（$p=2$ に限定され、定数倍の近似であった）を厳密に改善しており、$n$ に関する対数因子を除いて、既知のリンクの場合のクエリ計算量と一致している。

2. 下界 (Theorem 1.2 / 4.2)

$p > 2$ の場合、本論文はクエリ計算量のほぼタイトな下界を確立している。

• 計算量: 近似保証を達成するいかなるランダム化アルゴリズムも、最悪の場合、$\Omega_p(d^{p/2} / (\epsilon^p (\log(d/\epsilon))^{p/2}))$ 個の $b$ の要素をクエリしなければならない（$d \gtrsim \log(d/\epsilon)$ と仮定）。
• 意義: これにより $p > 2$ のギャップが埋まり、既存の上界 $\tilde{O}(d^{p/2}/\epsilon^p)$ が、適応的クエリに対しても対数因子を除いてタイトであることが示された。

意義と主張

本論文は、単一インデックスモデルにおける能動的 $\ell_p$ 回帰の残された多くのギャップを埋めることを主張している。

• 汎用性: 線形モデルや既知のリンクを持つ単一インデックスモデルから、より困難な未知のリンク関数を持つ一般的な $p \ge 1$ の設定へと、能動回帰の理解を拡張している。
• 最適性: $p > 2$ に対して一致する上界と下界（対数因子を除く）を提供し、$p=2$ の近似精度を向上させることで、この問題クラスのクエリ計算量を包括的に特徴付けている。
• 技術的新規性: 重み付きノルム下での Lipschitz 関数の被覆補題の開発、および Dudley 積分解析における非長方形インデックス集合の取り扱いは、一般的な $p$ の結果を可能にした主要な技術的進歩として提示されている。

著者らは、Lipschitz 関数の本質的な被覆数に起因して、上界に現在 $\log n$ の因子が含まれていることを明記しており、これらの因子を除去できるかどうかは依然として未解決の課題であるとしている。本論文は、ランダム化数値線形代数の理論的枠組みを超えた、実験的な検証や具体的な実世界への応用を提案するものではない。