# Beyond Binary: Continuous State Optimization with Graph-Structured Objectives

arXiv: https://arxiv.org/abs/2608.09366 · HTML: https://mlsanity.com/paper/2608.09366/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 38 of its 54 references that are in the map.
- First posted on arXiv 10 Aug 2026.

## Builds on (most cited first, 30 of 38)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Multi-Task Learning as Multi-Objective Optimization](https://mlsanity.com/paper/1810.04650/) (2018)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Fairness Without Demographics in Repeated Loss Minimization](https://mlsanity.com/paper/1806.08010/) (2018)
- [AI Fairness 360: An Extensible Toolkit for Detecting, Understanding, and Mitigating Unwanted Algorithmic Bias](https://mlsanity.com/paper/1810.01943/) (2018)
- [Delayed Impact of Fair Machine Learning](https://mlsanity.com/paper/1803.04383/) (2018)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Fairness in Recommendation Ranking through Pairwise Comparisons](https://mlsanity.com/paper/1903.00780/) (2019)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Fairness in Reinforcement Learning](https://mlsanity.com/paper/1611.03071/) (2016)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Ranking with Fairness Constraints](https://mlsanity.com/paper/1704.06840/) (2017)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Robust Optimization for Fairness with Noisy Protected Groups](https://mlsanity.com/paper/2002.09343/) (2020)
- [Online Learning with an Unknown Fairness Metric](https://mlsanity.com/paper/1802.06936/) (2018)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Pairwise Fairness for Ranking and Regression](https://mlsanity.com/paper/1906.05330/) (2019)
- [Two-Player Games for Efficient Non-Convex Constrained Optimization](https://mlsanity.com/paper/1804.06500/) (2018)
- [Equalizing Recourse across Groups](https://mlsanity.com/paper/1909.03166/) (2019)
- [Training Well-Generalizing Classifiers for Fairness Metrics and Other Data-Dependent Constraints](https://mlsanity.com/paper/1807.00028/) (2018)
- [Average Individual Fairness: Algorithms, Generalization and Experiments](https://mlsanity.com/paper/1905.10607/) (2019)
- [Probabilistic Verification of Fairness Properties via Concentration](https://mlsanity.com/paper/1812.02573/) (2018)
- [Decisions, Counterfactual Explanations and Strategic Behavior](https://mlsanity.com/paper/2002.04333/) (2020)
- [Calibrated Fairness in Bandits](https://mlsanity.com/paper/1707.01875/) (2017)
- [Noise-tolerant fair classification](https://mlsanity.com/paper/1901.10837/) (2019)
- [Bandits with Switching Costs: T^{2/3} Regret](https://mlsanity.com/paper/1310.2997/) (2013)
- [Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent](https://mlsanity.com/paper/1803.10366/) (2018)

## Abstract (arXiv)

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.