Entropy-Smooth Convex Optimization Cannot Be Accelerated

技術要約：エントロピー平滑凸最適化における加速の不可能性

問題設定
本論文は、標準的な単体 $\Delta_d$ 上の負のシャノン・エントロピーに対して $L$-平滑な凸関数の最小化に関する、一次近似（first-order）最適化手法の収束率を調査するものである。具体的には、著者らは、目的関数 $f$ の負のエントロピー $h(x) = \sum x_k \log x_k$ に対するBregmanダイバージェンスが、$h$ 自身のBregmanダイバージェンスの $L$ 倍で抑えられるという条件を満たす関数クラス $\text{Ent}_d(L)$ を検討している。

標準的なミラー降下法（mirror descent）は、このクラスに対して $O(L \log d / T)$ の収束率を達成するが、自然な疑問として、「加速された」手法（ユークリッド空間におけるNesterovの加速に相当するもの）が $O(1/T^2)$ の率を達成できるかどうかが挙げられる。Dragomirら（2022年）による先行研究では、相対的平滑性（relative smoothness）の下では加速が不可能であることが示唆されていたが、彼らの反例は、困難なインスタンスと並行して敵対的に構築された病理的なプロキシ関数（prox-function）に依存していた。ここで扱われる中心的な問いは、実用において広く用いられている、非常に構造化されたプロキシ関数である「負のエントロピー」に対して、加速が不可能であるかどうかである。

手法
著者らは、決定論的な一次近似手法に対する収束率の下限を証明するために、「抵抗力を持つオラクル（resisting oracle）」を構築するブラックボックス複雑性フレームワークを採用している。彼らの手法の核心は以下の通りである：

1. 困難なインスタンスの構築： 座標アトムのシフトした最大値（$g(u) = \max_k \{-u_{j_k} - b_k\}$）として定義される一連の「バックボーン（backbone）」関数を構築する。
2. 右Bregman-Moreauエンベロープによる平滑化： 困難なバックボーンが $\text{Ent}_d(L)$ クラスに属することを保証するため（これは相対的平滑性を要求するが、境界での非微分性を許容する）、著者らは右Bregman-Moreauエンベロープを適用する。この平滑化メカニらズムは、ユークリッドおよびKLダイバージェンスの場合に特有の性質である、カルバック・ライブラー（KL）ダイバージェンスの共同凸性に決定的に依存している。
3. 適応的なクエリ応答： 抵抗力を持つオラクルは、アルゴリズムの現在のクエリ点における質量が最小である座標に対応する新しい座標アトムを選択することで、任意のアルゴリズムと相互作用する。これらのアトムのオフセットは、新しいアトムが以前のクエリの近接点付近で「局所的に見えない（strictly dominated）」状態を維持するように増分される。
4. トランスクリプトの一貫性： Bregman-Moreauエンベロープの局所的な性質（補題4）を用いて、最終ステップで構築された平滑化関数が、すべての以前のオラクル応答と一貫していることを証明し、これにより下限が相互作用全体に適用されることを保証する。

主な結果
本論文は、以下の主要な定理を確立している：

• 単体最適化の低限界（定理1および5）： $T$ 回のクエリを行う任意の決定論的一次近似手法に対して、次を満たす関数 $f \in \text{Ent}_d(L)$ が存在する：
  $$f(x_{T+1}) - \min_{x \in \Delta_d} f(x) > \frac{L}{4(T+1)}$$
  ただし、次元 $d = \Omega(T^2)$ とする。この結果は、このクラスに対して加速された $O(1/T^2)$ の収束が達成不可能であることを示している。したがって、標準的なミラー降下法のレート $O(L \log d / T)$ は、次元が十分に大きい場合、対数因子を除いて最適である。
• 量子拡張（定理11）： この結果は、スペクトラヘドロン（密度行列）の非可換設定へと拡張される。負のフォン・ノイマン・エントロピーに対して $L$-平滑な関数の場合、同じ $\Omega(L/T)$ の下限が保持される。これは、対角成分を持つ困難なインスタンスを行列空間に埋め込み、Lindbladのデータ処理不等式を利用することで証明される。
• 補間条件（セクション5）： 著者らは、Dragomirの博士論文の結果を一般化した、$\text{Ent}_d(L)$ クラスの明示的な点別最小補間関数（pointwise minimal interpolants）を導出している。これらの条件は、与えられた一次データに適合する関数がクラス内に存在するために必要である。

意義と主張
本論文は、エントロピー平滑最適化において加速が可能かという未解決の問いに決着をつけることを主張している。著者らは、自らの結果が以下の理由から重要であると述べている：

• 経路的なプロキシ関数ではなく、特定の、好ましいプロキシ関数（負のエントロピー）に対して加速が不可能であることを示した。これは、潜在関数が加速を阻止するために特別に構築されていた先行研究の否定的な結果とは対照的である。
• このクラスに対するミラー降下法の最適性を裏付けており、上界（$O(L \log d / T)$）と下限（$O(L/T)$）の間の対数的なギャップは、アルゴリズムの欠陥ではなく、問題の次元性に起因している可能性が高いことを示唆している。
• 非ユークリッド幾何学における**性能推定プログラム（PEP）**の限界を浮き彫りにしている。PEPは病理的な反例を構築できる一方で、単体とエントロピーのような構造化された設定には苦慮することを示している。

著者らは、下限と既知の上界との間に対数的なギャップ（$\log d$）が残っていることを謙虚に認めている。彼らは、セクション5で導出した補間条件を、最近の原始・双対（primal-dual）フレームワークと組み合わせることで、この欠落している因子を回収できる可能性があると示唆しているが、現在の研究においてこのギャップを埋めたとは主張していない。さらに、極端に高次元な場合（$d = \exp(T)$）には、加速が形式的に排除されているわけではないが、そのような領域は実用上の関心が限定的であるとも述べている。