Solving Minimax Problems with Bilinear Objectives with ADMM

加速近端梯度法（APG，Accelerated Proximal Gradient）理論收斂率達 O(1/k²)，但在非橢球信賴區間下可能完全失效。本文的核心定理是：當目標函數為雙線性 g = cᵀAβ 時，ADMM（交替方向乘子法，Alternating Direction Method of Multipliers）中原本「與原問題等難」的近端算子（proximal operator），可精確化簡為對信賴集合 S 的廣義投影（generalized projection）——不需任何近似，適用任意凸集。

鞍點框架：點估計之外的穩健最優決策

在行銷預算分配、A/B 測試等決策場景中，數據分析的輸出不只是參數點估計 β̂，還有量化估計誤差的信賴集合 S。只以 β̂ 最佳化的決策 c₀ = argmax g(c; β̂)，論文稱為「天真最優」（naïve optimal）：若期望績效 g(c₀; β̂) 遠高於最壞情況績效 f(c₀) = min_{β∈S} g(c₀; β)，此決策包含可觀的風險。

穩健最優（robust optimal）的做法是求解鞍點問題 max_{c∈C} min_{β∈S} g(c; β)，其中 C 是決策可行集、S 是信賴集合，g 對 c 凹、對 β 凸。鞍點定理保證存在 (c⋆, β⋆) 使 g(c, β⋆) ≤ g(c⋆, β⋆) ≤ g(c⋆, β) 成立：c⋆ 是穩健最優決策，β⋆ 對應最壞情況參數。

論文以 n 個數位廣告渠道的預算分配為示範：lift study（提升實驗）估計各渠道轉換率差 ξᵢ = βᵢᴹ − βᵢᴴ，預算約束在單純形 C = {c: c ≥ 0, Σcᵢ ≤ B} 上，線性模型給出 g(c; β) = cᵀAβ，A 的結構由各渠道到達成本 ρᵢ 決定——這正是雙線性形式。

ADMM 的瓶頸：近端算子等價於原問題

將 maximin 改寫為最小化 f̃(c) + I_C(c)，其中 f̃(c) = sup_{β∈S} {−g(c;β)} 是凸函數，I_C 是決策集的示性函數（indicator function，點在 C 內為 0，否則為 +∞）。引入輔助變數 y，標準 ADMM 三步迭代為：

y 更新：y^{k+1} = prox_{f̃/ρ}(c^k − u^k)
c 更新：c^{k+1} = Π_C(y^{k+1} + u^k)（Euclidean 投影）
u 更新：u^{k+1} = u^k + y^{k+1} − c^{k+1}

c 更新是標準投影，u 更新是純加法；難題在 y 更新：計算 prox_{f̃/ρ}(v) 等價於求解 min_y { sup_{β∈S} {−g(y;β)} + (ρ/2)||y−v||² }——這本身仍是 minimax 問題，一般情況下與原始問題等難。這是 ADMM 直接應用於 minimax 的核心瓶頸。

雙線性結構的精確分解：近端算子化簡為廣義投影

本文的關鍵洞察在此。當 g(y; β) = yᵀAβ 時，正則化目標是凸-凹函數，可套用 Sion (1958) 的鞍點定理，安全地交換 min 與 max 的順序：

min_y max_{β∈S} {−yᵀAβ + (ρ/2)||y−v||²} = max_{β∈S} min_y {−yᵀAβ + (ρ/2)||y−v||²}

交換後先對 y 最小化，一階條件給出閉合解 y⋆(β) = v + (1/ρ)Aβ。代入消去 y 後，對 β 的外層最大化等價於：

min_{β∈S} ‖Aβ − (−ρv)‖²

這正是廣義投影：在線性映射 A 下，找 S 中使 Aβ 最接近 −ρv 的點。當 A = I 時退化為標準 Euclidean 投影，屬廣義投影的特例。計算近端算子因此分兩步：(1) 廣義投影 β⋆ = argmin_{β∈S} ‖Aβ + ρv‖²；(2) 設 y⋆ = v + (1/ρ)Aβ⋆。整個化簡精確，不含任何近似或線性化。

信賴集合 S 可以是橢球形（如常態近似的信賴橢圓），也可以是二項式對數似然比信賴區間（likelihood-ratio confidence region）——後者在轉換率接近 0 時比橢球近似更準確，且恆滿足 β ∈ [0,1]^{2n}，正是本文方法的目標應用場景。

四種方法比較：APG 最快但非萬能，ADMM 穩健普適

論文對比四種求解方法。投影次梯度法（Projected Subgradient）：收斂率 O(1/√k)，需遞減步長，無光滑假設，實務最慢。加速近端梯度法（APG）：收斂率 O(1/k²)，需對偶目標 f(c) 可微——由 Danskin 定理，這要求 argmin_{β∈S} g(c;β) 唯一。對於有平坦面的二項式信賴區間，f(c) 可能不可微，APG 線搜尋因此失效；子問題只達有限精度時，APG 也容易不收斂。Markowitz 二次規劃：S 為橢球時有封閉解，一次迭代完成，最快但適用範圍最窄。本文 ADMM：O(1/k)，無光滑假設，適用任意凸信賴集合。

數值實驗在 n=5 渠道、S 取似然比信賴區間（每組 200–500 次試驗）的 lift study 上驗證：APG 在 50 次迭代內達 duality gap < 10^{-5}；ADMM 在 200 次迭代內達 gap < 10^{-3}；次梯度法 200 次迭代後仍停在 10^{-2} 附近，與理論一致。ADMM 的殘差曲線呈特徵性「階梯」形——每次渠道支撐集（active set，獲正分配的渠道集合）改變時對偶殘差短暫飆升，反映 ADMM 透過連續鬆弛識別最優支撐集的組合結構。

實作上有兩個細節值得注意。事後恢復 β⋆：迭代中的 β^{k+1} 是廣義投影的中間產物，收斂後須另行求解 β⋆ = argmin_{β∈S} g(c^k; β) 才能得到真正的最壞情況參數。暖啟動（warm-starting）：描繪期望績效與最壞情況績效之間的 Pareto 曲線時，依序以前一個問題的解為初始點，可大幅減少迭代次數。

雙線性 g = cᵀAβ 使 ADMM 近端算子精確化簡為廣義投影，無需近似：200 次迭代達 10^{-3} gap，是非橢球信賴集合下穩健決策的可靠求解器。