arXiv:2512.11131cs.LGcs.AI2025-12NeurIPS被引 2

兼顾公平与动作平滑的在线优化新算法,提升资源分配公平性。

Fairness-Regularized Online Optimization with Switching Costs

  • 引入辅助变量将长期公平性成本转为在线可处理形式
  • 理论证明在长序列下可实现渐近最优竞争力
  • 适用于需公平性的动态资源调度场景

公平性与动作平滑是许多在线优化问题中的关键考量,但尚未被同时处理。本文研究了一种新的、具有挑战性的公平性正则化平滑在线凸优化设置,包含切换成本。首先,我们证明即使不考虑切换成本,随着问题周期长度 $T$ 增加,任何在线算法都无法达到次线性遗憾或有限竞争比。随后,我们提出 FairOBD(公平性正则化在线平衡下降)算法,协调最小化损失成本、切换成本与公平性成本之间的矛盾。具体而言,FairOBD 通过引入辅助变量将长期公平性成本分解为一系列在线成本,并利用该辅助变量对在线动作进行正则化以实现公平结果。基于一种新方法处理切换成本,我们证明 FairOBD 在 $T o ty$ 时对一个新型基准——参数化约束下的最优离线算法——具有最坏情况渐近竞争比。最后,我们在社会负责任的 AI 推理动态计算资源分配的迹驱动实验中评估 FairOBD,结果表明其能有效降低总公平性正则化成本,相比现有基线方案更优地促进公平结果。

原文摘要 · Abstract (English)

Fairness and action smoothness are two crucial considerations in many online optimization problems, but they have yet to be addressed simultaneously. In this paper, we study a new and challenging setting of fairness-regularized smoothed online convex optimization with switching costs. First, to highlight the fundamental challenges introduced by the long-term fairness regularizer evaluated based on the entire sequence of actions, we prove that even without switching costs, no online algorithms can possibly achieve a sublinear regret or finite competitive ratio compared to the offline optimal algorithm as the problem episode length $T$ increases. Then, we propose FairOBD (Fairness-regularized Online Balanced Descent), which reconciles the tension between minimizing the hitting cost, switching cost, and fairness cost. Concretely, FairOBD decomposes the long-term fairness cost into a sequence of online costs by introducing an auxiliary variable and then leverages the auxiliary variable to regularize the online actions for fair outcomes. Based on a new approach to account for switching costs, we prove that FairOBD offers a worst-case asymptotic competitive ratio against a novel benchmark -- the optimal offline algorithm with parameterized constraints -- by considering $T\to\infty$. Finally, we run trace-driven experiments of dynamic computing resource provisioning for socially responsible AI inference to empirically evaluate FairOBD, showing that FairOBD can effectively reduce the total fairness-regularized cost and better promote fair outcomes compared to existing baseline solutions.

在线优化公平性资源调度

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。