Fairness-Regularized Online Optimization with Switching Costs¶

会议: NeurIPS 2025
arXiv: 2512.11131
代码: 无
领域: AI安全
关键词: 在线优化, 公平性正则, 切换代价, 竞争比, 镜像下降

一句话总结¶

提出 FairOBD 算法，首次在平滑在线凸优化中同时处理长期公平性正则项和切换代价，通过引入辅助变量分解长期公平代价并用镜像下降更新对偶变量，证明了渐近竞争比保证。

研究背景与动机¶

在线优化中，动作平滑性（减少突变）和长期公平性（避免歧视）是两个至关重要但此前未被同时考虑的目标：

切换代价：在电网调度、数据中心容量规划、机器人运动规划等场景中，动作的剧烈变化会带来危险或高额成本，因此通过惩罚相邻动作差异来实现平滑
长期公平性：AI 数据中心的环境成本需在不同地区公平分配、资源分配不应歧视弱势群体等，需要对整个动作序列的长期影响进行正则化
核心矛盾：切换代价使每轮目标依赖于历史动作（引入记忆性），而长期公平正则只能在整个 episode 结束后才能评估，两者的结合对算法设计和理论分析提出了根本性挑战
现有公平在线算法（如 DMD 系列）要求每轮目标函数与历史动作无关，无法处理切换代价

方法详解¶

整体框架¶

FairOBD（Fairness-regularized Online Balanced Descent）的核心思想是将不可在线评估的长期公平代价分解为可逐步优化的在线代价，同时平衡命中代价、切换代价和公平代价三者之间的冲突。

问题定义：最小化总代价包含三部分——命中代价 \(f_t(x_t)\)、切换代价 \(d(x_t, x_{t-1}) = \frac{\beta_1}{2}\|x_t - x_{t-1}\|^2\)、以及长期公平代价 \(g(\frac{1}{T}\sum_{t=1}^{T} A_t x_t)\)。

关键设计¶

1. 长期公平代价的在线分解

引入辅助变量 \(z_t\)，将长期公平代价分解为逐步代价 \(\frac{1}{T}\sum_t g(z_t)\)，附加长期约束 \(\sum_t A_t x_t = \sum_t z_t\)。当约束满足时等价于原始问题。通过拉格朗日松弛，将长期约束转化为逐轮可优化的形式。

2. 三代价平衡机制

在每轮 \(t\)，FairOBD 求解包含五项的联合优化：当前命中代价 \(f_t(x_t)\)、加权切换代价 \(\lambda_1 d(x_t, x_{t-1})\)、额外正则项 \(\frac{\lambda_2}{2}\|x_t - v_t\|^2\)（\(v_t = \arg\min_x f_t(x)\)）、公平正则器 \(\kappa_t \cdot A_t x_t\)、以及辅助变量优化 \(g(z_t) - \kappa_t z_t\)。给定对偶变量 \(\kappa_t\) 后，\(x_t\) 和 \(z_t\) 可独立求解。

3. 对偶变量的镜像下降更新

用 Bregman 散度做镜像下降更新 \(\kappa_{t+1}\)，随机次梯度为 \(d_t = z_t - A_t x_t\)。参考函数 \(h\) 的选择不影响理论保证。

损失函数 / 训练策略¶

FairOBD 是确定性在线算法。核心超参数：学习率 \(\eta = \mathcal{O}(T^{-1/3})\)；\(\lambda_1, \lambda_2\) 最优设置时达到竞争比 \(C = \frac{1}{2}(1+\sqrt{1+4\beta_1/m})\)。

理论贡献¶

不可能性结果（Theorem 4.1 & 4.2）：即使无切换代价，任何在线算法的遗憾下界为 \(\Omega(1)\)（常数差，总遗憾线性），竞争比下界为 \(\Omega(T)\)。首次严格证明。

FairOBD 的竞争比（Theorem 5.2）：\(\delta\) 次线性时达到渐近竞争比 \(C\)，与无公平约束时最优竞争比匹配。加性误差 \(\mathcal{O}(T^{-1/3})\)。

实验关键数据¶

主实验：AI推理服务的公平资源调度¶

在 7 个数据中心上使用 LLM 推理请求一周轨迹模拟：

方法	总代价	公平代价	切换代价	与OPT差距
OPT（离线最优）	基准	最低	-	0
FairOBD	在线最低	在线最低	低	最小
ROBD	中等	高	低	中等
DMD	中等	中等	高	中等
HITMIN	高	高	-	大

消融实验¶

学习率敏感性：不同 \(\eta\) 下性能稳健
公平权重影响：增大权重降低公平代价但适度增加命中代价
特殊情况恢复：\(\beta_1=0\) 退化为公平在线优化；公平权重为 0 退化为标准平滑在线优化

关键发现¶

FairOBD 在所有在线方法中达到最低总代价和最小与离线最优差距
在保持低切换开销的同时实现最低公平代价
动态优化长期公平性显著优于忽略公平性或事后处理

亮点与洞察¶

首次形式化：将长期公平正则与切换代价统一到平滑在线凸优化框架
不可能性证明：为该领域奠定理论基础
\((R,\delta)\)-基准：弥合不可能性与可行性的鸿沟
统一性：退化为两个已有设置的最优结果
新证明技术：通过中间基准桥接不同代价函数

局限性 / 可改进方向¶

切换代价限制为 \(\ell_2\) 范数平方，更一般函数有待扩展
命中代价需非负强凸假设
实验仅数据中心调度一个场景
可引入预测进一步降低代价

评分¶

新颖性: ⭐⭐⭐⭐⭐ — 首次形式化+不可能性证明
实验充分度: ⭐⭐⭐ — 场景单一
写作质量: ⭐⭐⭐⭐ — 动机清晰，理论详尽
价值: ⭐⭐⭐⭐ — 理论基础贡献