Beyond Binary: Continuous State Optimization with Graph-Structured Objectives

Corinna Cortes, Yishay Mansour, Mehryar Mohri
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:21437-21466, 2026.

Abstract

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 continuous state spaces. We model the problem as minimizing a sum of linear objectives subject to movement costs that penalize system instability. We capture the local structure of the objectives using a 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 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 asynchronous update schedule that eliminates synchronization overhead in sparse graphs; (2) an adaptive algorithm that learns the graph structure from data; and (3) a 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-cortes26a, title = {Beyond Binary: Continuous State Optimization with Graph-Structured Objectives}, author = {Cortes, Corinna and Mansour, Yishay and Mohri, Mehryar}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {21437--21466}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/cortes26a/cortes26a.pdf}, url = {https://proceedings.mlr.press/v306/cortes26a.html}, abstract = {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 continuous state spaces. We model the problem as minimizing a sum of linear objectives subject to movement costs that penalize system instability. We capture the local structure of the objectives using a 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 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 asynchronous update schedule that eliminates synchronization overhead in sparse graphs; (2) an adaptive algorithm that learns the graph structure from data; and (3) a 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.} }
Endnote
%0 Conference Paper %T Beyond Binary: Continuous State Optimization with Graph-Structured Objectives %A Corinna Cortes %A Yishay Mansour %A Mehryar Mohri %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-cortes26a %I PMLR %P 21437--21466 %U https://proceedings.mlr.press/v306/cortes26a.html %V 306 %X 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 continuous state spaces. We model the problem as minimizing a sum of linear objectives subject to movement costs that penalize system instability. We capture the local structure of the objectives using a 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 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 asynchronous update schedule that eliminates synchronization overhead in sparse graphs; (2) an adaptive algorithm that learns the graph structure from data; and (3) a 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.
APA
Cortes, C., Mansour, Y. & Mohri, M.. (2026). Beyond Binary: Continuous State Optimization with Graph-Structured Objectives. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:21437-21466 Available from https://proceedings.mlr.press/v306/cortes26a.html.

Related Material