让系统在多个连续目标间自动平衡,减少调整频率。
Beyond Binary: Continuous State Optimization with Graph-Structured Objectives
- 用图结构建模目标依赖关系,优化连续参数。
- 实测调整次数减少三倍以上,损失几乎不变。
- 适合需要稳定运行的推荐、广告等复杂系统。
大规模学习系统常需权衡多个可能冲突的目标,如公平性、准确率和延迟。尽管已有研究将此问题形式化为二元状态下的优化,但许多实际控制参数(如公平性阈值、多样性混合率或资源预算)是连续的。本文将框架扩展至连续状态空间,将问题建模为在移动成本惩罚下最小化线性目标之和。通过依赖图(或因子图)捕捉目标的局部结构,每个目标由部分状态属性决定。为缓解探索与稳定性的矛盾,提出懒惰图LinUCB算法,通过延迟更新降低切换成本,同时保持近似最优遗憾。此外,引入三种利用图结构的高级机制:(1) 异步更新调度,消除稀疏图中的同步开销;(2) 自适应算法,从数据中学习图结构;(3) 联合估计器,通过相关目标间数据共享显著收紧遗憾边界。实验表明,在异构系统中,这些结构利用可使移动成本降低超过三倍,同时保持相近累积损失。
原文摘要 · Abstract (English)
Large-scale learning systems often face the challenge of balancing multiple, potentially competing objectives, such as fairness, accuracy, and latency. While recent work has formalized this as an optimization problem over binary states, many real-world control parameters, such as fairness thresholds, diversity mixing rates, or resource budgets, are continuous. In this work, we extend the framework to \emph{continuous state spaces}. We model the problem as minimizing a sum of linear objectives subject to \emph{movement costs} that penalize system instability. We capture the local structure of the objectives using a \emph{dependency graph} (or factor graph), where each objective is determined by a subset of the state attributes. To address the tension between exploration and stability, we propose \emph{Lazy Graph-LinUCB}, an algorithm that performs lazy updates to minimize switching costs while maintaining near-optimal regret. Beyond stability, we introduce three advanced mechanisms to exploit the underlying graph structure: (1) an \emph{asynchronous} update schedule that eliminates synchronization overhead in sparse graphs; (2) an \emph{adaptive} algorithm that learns the graph structure from data; and (3) a \emph{joint estimator} that leverages data sharing among correlated objectives to significantly tighten regret bounds. Empirically, we demonstrate that these structural exploitations reduce movement costs by more than a factor of three in heterogeneous systems while maintaining similar cumulative losses.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。