技術要約：適応的ステップサイズを用いた制約付き最適化のためのランダム化実行可能解法

問題定式化

本論文は、以下の制約付き最適化問題を扱う：
$$\min_{x} f(x) \quad \text{subject to} \quad x \in X \cap Y$$
ここで、$Y \subseteq \mathbb{R}^n$ は「射影が容易な」（例：球体やボックス）閉凸集合であり、$X$ は $m$ 個の凸関数の下位レベル集合の共通部分として定義される：
$$X := \bigcap_{i=1}^m \{x \in \mathbb{R}^n \mid g_i(x) \leq 0\}$$
主な課題は、$m$ が大きい場合に、$X$ への射影が計算上困難になることから生じる。著者らは、目的関数 $f$ に関して以下の2つの異なるレジームを検討している：

1. 強凸かつリプシッツ連続（Lipschitz-smooth）： $f$ は一意の最小値と滑らかな勾配を持つ。
2. 凸かつ非平滑（possibly nonsmooth）である可能性： $f$ は滑らかさや強凸性を欠いている可能性がある。

目標は、毎回のイテレーションで $X$ への完全な射影を必要とせずに、$f$ を最小化しつつ $X$ に対する実行可能性を確保するアルゴリズムを開発することである。

手法

提案手法は、目的関数の最小化と制約充足を、2ステップの反復フレームワークを用いて分離する：

1. ランダム化された実行可能解更新（アルゴリズム1）

複雑な制約 $X$ を扱うために、著者らはポラック（Polyak）のステップに基づくランダム化された実行可能解アルゴリズムを採用している。$X$ 全体への射影を行う代わりに、アルゴリズムは以下を実行する：

• 単一の制約インデックス $\omega_k$ を $\{1, \dots, m\}$ から一様にサンプリングする。
• サンプリングされた制約違反関数 $g^+_{\omega_k}(x) = \max\{0, g_{\omega_k}(x)\}$ の劣勾配を計算する。
• パラメータ $\beta \in (0, 2)$ でスケールされたポラック・ステップによる劣勾配ステップを実行する。
• 結果を「容易な」集合 $Y$ へ射影する。
• 外側のイテレーションごとに、このプロセスを $N_k$ 回繰り返す。ここで $N_k$ は決定的またはランダムである。

この内側ループの出力 $x_k$ は、実行可能集合 $X \cap Y$ への距離を幾何学的に減少させる実行可能解更新として機能する。

2. 適応的ステップを用いた目的関数最小化

外側のループは、実行可能解更新の出力を利用して $f(x)$ を最小化する。論文では、 $f$ の特性に基づいた2つの具体的な戦略を提案している：

• ケース (i)：強凸かつ平滑（アルゴリズム2）
  この手法は、勾配降下ステップとランダム化された実行可能解更新を組み合わせる。著者らは、強凸定数 $\mu$ やリプシッツ定数 $L$ の事前知識を必要としない適応的ステップサイズスキームを導入している。ステップサイズは、勾配ノルムと目標許容誤差 $\epsilon$ に基づいて調整される。

• ケース (ii)：凸かつ非平滑（アルゴリズム3および4）
  非平滑な目的関数のために、論文は DoWG（Distance over Weighted Gradients） 法の変種である DoWS（Distance over Weighted Subgradients） に基づく、完全なパラメータフリーの適応スキームを導入している。

  • アルゴリズム 3 (DoWS)： 実行可能集合 $Y$ が有界であることを仮定する。初期点からのイテレートの最大距離を追跡し、ステップサイズを決定するために重み付き劣勾配ノルムを累積する。
  • アルゴリズム 4 (T-DoWS)： 非有界な集合（例：$Y = \mathbb{R}^n$）向けに設計された「テーミング（tamed）」された変種である。これは、イテレートが有界に留まることを保証するためにステップサイズのスケーリングを修正しており、$Y$ の事前的な有界性を必要としない。

主な貢献

1. 誤差境界と双対マルチプライヤーの理論的結合：
   著者らは、強スレーター条件（Strong Slater condition）の下でのグローバル誤差境界とラグランジュ双対マルチプライヤーの間の関係を確立している。彼らは、$Y$ のコンパクト性を仮定することなく、双対マルチプライヤーの一様な上界が存在することを証明している。この結果は先行研究（Lewis & Pang, 1998; Bertsekas, 1999; Mangasarian, 1998）から導出されているが、ここでは特定の制約構造に明示的に結び付けられている。

2. 強凸問題における線形収束：
   強凸かつ平滑な目的関数に対して、本論文は任意の指定された許容誤差 $\epsilon$ に対する期待値における線形収束を証明している。これは、適応的ステップサイズと、実行可能サンプル数 $N_k$ に関する特定の条件を用いることで達成される。先行研究とは異なり、この結果は制約関数の劣勾配が事前に有界であることを仮定せず、それらがほとんど確実に（almost surely）有界であることを証明している。

3. 非平滑問題のための完全なパラメータフリー手法：
   本論文は、射影なしで問題 (P) を解くための、DoWG（またはそのテーミングされた変種）とランダム化された実行可能解更新を組み合わせた、初の完全なパラメータフリー手法を提示している。

   • 期待値において $O(1/\sqrt{T})$ の最悪ケースのレートを達成する。
   • T-DoWS (アルゴリズム 4) を導入しており、これは $f$ の下位レベル集合が有界であるという仮定の下で、集合 $Y$ が非有界であっても（例：$Y = \mathbb{R}^n$）、イテレートが有界であることを保証し、最適な収束レートを実現する。

4. ランダムサンプリング戦略の分析：
   著者らは、イテレーションあたりの実行可能サンプル数 $N_k$ の影響を分析している。イテレートの実行不可能性がほとんど確実に幾何学的に減少することを示している。また、最適な収束レートを達成するためのサンプルの増大スケジュール（例：ポアソン分布、二項分布、または決定論的な増加）の選択に関する理論的指針を提供している。

結果と実証的評価

理論的保証

• 強凸ケース： アルゴリズムは $O(\ln(1/\epsilon))$ イテレーションで $\epsilon$ 精度の範囲に到達する。実行不可能性のギャップは、サンプル数 $N_k$ に応じて幾何学的に減少する。
• 凸非平滑ケース： 平均化されたイテレートは、期待誤差境界として $O(1/\sqrt{T})$ （集合の直径と初期推定値の比率に依存する対数因子を含む）を達成する。実行不可能性の境界は、サンプリング分布に依存し、特定のサンプリング条件下では $O(1/T)$ の速度で減少する。

シミュレーション

著者らは、3つの問題タイプで手法を検証している：

1. 二次制約付き二次計画問題 (QCQP)： 強凸ケースにおける線形収束、および非平滑ケースにおける Arrow-Hurwicz、Alt-GDA、ACVI と比較した競争力のある性能を示している。
2. サポートベクターマシン (SVM)： 提案されたパラメータフリー手法が、ステップサイズのチューニングのためにクロスバリデーションを必要とすることなく収束することを示している。これは、オンライン設定において高い計算オーバーヘッドに苦しむ原始的・双対法と比較して優位である。
3. グループ公平性制約を伴うロジスティック回帰： 複雑な公平性制約（下位レベル集合の共通部分としてモデル化される）を扱いながら、実行可能性の違反をゼロにし、目的関数の最適値に収束する能力を示している。

すべてのシミュレーションにおいて、提案されたアルゴリズム（アルゴリズム 2、3、および 4）は、特に多数の制約がある場合で、完全な射影が困難なシナリオにおいて計算効率が高いことを示している。これらの手法は、ハイパーパラメータのチューニングや各イテレーションでの副問題の解決を必要とすることなく、最先端のベースライン（ACVI、Arrow-Hurwicz）と同等以上の性能を発揮する。

意義と主張

本論文は、多数の制約を持つ問題に対して、計算効率が高く、理論的に裏付けられた、完全にパラメータフリーなアルゴリズムを提供することで、制約付き最適化の分野を前進させると主張している。

• 新規性： 著者らは、射影なしの制約付き最適化において、DoWG（またはそのテーミングされた変種）とランダム化された実行可能解更新の組み合わせが研究されたのはこれが初めてであると述べている。
• 堅牢性： これらの手法は、問題固有のパラメータ（強凸定数、リプシッツ定数、または最適値）の知識を必要としないため、そのような情報が得られない実用的なアプリケーションに適している。
• スケーラビリティ： ランダム化された実行可能解更新を使用することで、多くの制約への射影という計算上のボトルネックを回避し、高次元の問題に対しても効果的にスケールする。

本研究は、ランダム化された実行可能解法と適応的勾配法との間の溝を埋め、実行可能性の幾何学的減衰を保証しながら、滑らかな目的関数と非平滑な目的関数の両方に適応する統一されたフレームワークを提供している。