技術要約：凸関数のサンプリングと再構成

1. 問題設定

本論文は、単位立方体 $\Omega = [0, 1]^d$ 上で定義された多変量凸関数の**最適回復（optimal recovery）**問題を取り扱う。$n$ 個の点サンプル集合 $\Lambda = \{x_1, \dots, x_n\}$ と、対応するデータベクトル $w = (f(x_1), \dots, f(x_n))$ が与えられたとき、目標は $L_p$ ノルム（$1 \le p \le \infty$）における最悪ケースの回復誤差を最小化する近似関数 $\tilde{f}$ を構築することである。

本研究では、以下の2つの特定のモデルクラスに焦点を当てる：

1. クラス $B(\Omega)$: 1によって一様に有界な凸関数（$|f(x)| \le 1$）。
2. クラス $L(\Omega)$: 1によって一様に有界であり、かつ劣勾配が一様に有界な凸関数（すべての $x$ に対して $|v| \le 1, v \in \partial f(x)$）、これは1-リプシッツ連続であることと同等である。

主要な目的は、可能なすべてのサンプルサイトの選択およびすべての回復アルゴリズムに対する最悪ケース誤差のインフィマムであるサンプリング数 $\rho_n(K)_{L_p}$ を決定することである。また、回復アルゴリズムが線形に制限される場合の線形サンプリング数 $\rho_n^\ell(K)_{L_p}$ についても調査を行う。

2. 手法

著者らは、近似理論、凸幾何学、および確率論的手法を組み合わせて、サンプリング数の上限および下限を確立している。

2.1 テンソル積格子と線形手法

まず、標準的な一様テンソル積格子と区分的マルチリニア補間の性能を分析する。

• 上界: クラス $L$ に対しては、一様格子を用いることで $r = 1 + 1/p$ となる誤差率 $O(n^{-r/d})$ が得られる。クラス $B$ に対しては、同じ率を達成するために、境界付近で次数を調整した（graded）非一様テンソル格子が必要となる。
• 下界: 著者らは、テンソル積格子または線形回復手法に限定されている場合に、これらの率が最適であることを証明するために、特定の反例（「ヒンジ」関数や修正された凸関数を使用）を構築する。

2.2 非線形および非テンソル・サンプリング

真の最適率を決定するために、本論文はテンソル格子を超えた議論を展開する。

• 最適集合の存在: 確率論的な議論を用いて、以下の2つの重要な幾何学的性質を満たす特定のデータサイト集合 $\Lambda_n^*$（これはテンソル積格子ではない）の存在を証明する：
  1. 内部にサンプル点を持たない任意の閉凸集合の体積は、$O(\frac{\log n}{n})$ で抑えられる。
  2. この集合は $\epsilon \approx n^{-1/d}$ となる $\epsilon$-ネットを形成する。
• 誤差解析: これらの特定のサイト上で一致する2つの凸関数の差を分析することにより、サンプリング数のより鋭い上界を導出する。これには、関数が異なる領域を凸集合で被覆し、劣勾配および極集合の性質（マーラーの不等式への言及を含む）を利用することが含まれる。

2.3 構成的回復アルゴリズム

最適率の存在は非構成的な確率論的証明に基づいているが、第6節では計算可能で、近似的に最適な回復アルゴリズムを提案している。

• 上限特性: アルゴリズムは、クラス $L$ および $B$ が点別上限（pointwise suprema）に関して閉じているという性質を利用する。
• 定式化: 回復写像 $A_\Lambda(w)$ は、データ制約（および有界性制約）を満たすモデルクラス内のすべての関数の点別上限として定義される。
• 実装: この無限次元の最適化問題は、有限次元の問題へと還元される。回復関数は、線形（$B$ の場合）または錐（$L$ の場合）の制約を満たすアフィン関数の集合の上限であることが示されている。これにより、回復は線形計画法（$B$ の場合）または錐計画法（$L$ の場合）を通じて計算可能となる。

3. 主な貢献と結果

3.1 標準的手法の劣特性

凸関数において、古典的な滑らかさのクラス（ソボレフ空間やヘルダー空間など）に対して最適である標準的な手続きは、**劣最適（suboptimal）**であるという点が中心的な知見である。

• テンソル格子: $1 < p < \infty$ かつ $d \ge 2$ の場合、一様テンソル積格子上のサンプリングは $n^{-(1+1/p)/d}$ の率を与える。しかし、真の最適率はより速い。
• 線形手法: 線形回復手法は、非線形手法よりも著しく劣る。具体的には、$p=2$ のとき、線形サンプリング数は $n^{-3/2d}$ で減衰するが、最適な非線形率は（対数因子を除いて）$n^{-2/d}$ である。

3.2 最適サンプリング率

本論文は、サンプリング数 $\rho_n(K)_{L_p}$ の最適な減衰率（対数因子を除いて）を確立している：

• $1 \le p \le d$ の場合: 率 $n^{-2/d}$。
• $p \ge d$ の場合: 率 $n^{-(1+d/p)/d}$。
• 統合: 最適な率は $n^{-\tilde{r}/d}$（ここで $\tilde{r} = \min\{2, 1 + d/p\}$）によって特徴付けられる。

これらの率は、特定の非テンソル積サンプリング集合と非線形再構成手法を用いることで達成される。

3.3 特定のケース

• $p=1$ および $p=\infty$: 最適な率は、テンソル積格子と線形手法を用いて達成可能である。
• $p=2$: 線形サンプリング数 $\rho_n^\ell(L)_{L_2}$ は $n^{-3/2d}$ で減衰するが、最適な非線形率は $n^{-2/d}$ である。これは、凸関数における線形回復と非線形回復の間の重大なギャップを浮き彫りにしている。
• クラス $B$ 対 $L$: $L \subset B$ であるが、$p < \infty$ において両クラスの最適なサンプリング率は実質的に同じである。しかし、$p=\infty$ の場合、$B$ のサンプリング数はゼロに収束しない（$\rho_n(B)_{L_\infty} \asymp 1$）のに対し、$L$ の場合は $n^{-1/d}$ として減衰する。

4. 意義と主張

本論文は、凸関数のサンプリング数の最適な減衰率を特徴付けることで、標準的な格子ベースの手法と理論的な最適値との間の乖離を解決したと主張している。

• 非線形性の不可欠性: 本研究は、凸関数において、非線形再構成手法が、ほとんどの $p$ 値において線形手法や標準的なテンソル格子サンプリングよりも大幅に優れていることを示している。これは、線形手法がしばしば最適となる古典的な滑らかさのクラスとは対照的である。
• エントロピーとの関連: 導出された最適なサンプリング率（$p \le d$ における $n^{-2/d}$）は、これらのクラスのエントロピー数の減衰率と一致している。このことは、凸関数のサンプリング数が、一部の古典的な滑らかさのクラスとは異なり、エントロピーと同じ複雑性の尺度によって支配されていることを示唆している。
• 構成的アルゴリズム: 論文は、凸最適化（アフィン関数の上限）に基づく、実用的で安定した、かつ近似的に最適な回復アルゴリズムを提供しており、これはノイズを含むデータにも適用可能である。

著者らは、最適なサンプリング集合の存在は確率論的手法によって証明されているものの、そのような集合の明示的な構成は依然として未解決の領域であると述べている。ただし、提案された回復アルゴリズムは、任意のサイトに対して機能し、サイトが理論的な要件に従って選択されている場合には近似的に最適な性能を発揮する。