Research map / Bandits and online learning / Online convex optimization and games
Fairness-Regularized Online Optimization with Switching Costs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes FairOBD, an online algorithm for fairness-regularized smoothed online convex optimization with switching costs, which decomposes the long-term fairness cost via an auxiliary variable and mirror-descent dual updates, and proves an asymptotic competitive ratio against an (R,δ)-constrained offline optimum.
Problem
Online convex optimization with a long-term fairness regularizer evaluated over the whole action sequence, combined with per-round hitting costs and switching costs that create action memory; prior fair online methods assume per-round objectives independent of past actions.
Approach
Introduce an auxiliary variable z_t to convert the long-term fairness cost into online costs, relax the resulting long-term equality constraint via a Lagrangian whose multiplier is updated by mirror descent, and use the multiplier as a fairness regularizer in a balanced-descent update for x_t that accounts for switching-cost memory.
Key results
- Default setting: FairOBD (eta=1e-2) total cost 237.07 versus 298.64 for ROBD and 317.15 for DMD, with OPT at 230.93.
- FairOBD attains fairness cost 41.36 among online methods, versus 111.85 for ROBD and 54.16 for DMD.
- Theory: asymptotic competitive ratio of (1/2)(1+sqrt(1+4 beta_1/m)) against (R,delta)-OPT as T grows, matching the best-known ratio for switching-cost-only smoothed OCO.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use FairOBD rather than the online baselines | AI inference provisioning · AI inference provisioning, u3=3.5 | Total Cost: 237.07 vs 298.64 (ROBD); 237.07 vs 317.15 (DMD); 237.07 vs 343.62 (HITMIN) | Helped |
| use FairOBD rather than the online baselines | AI inference provisioning · AI inference provisioning, u3=1.75 | Total Cost: 216.41 vs 242.71 (ROBD); 216.41 vs 290.07 (DMD); 216.41 vs 273.56 (HITMIN) | Helped |
| use FairOBD rather than the online baselines | AI inference provisioning · AI inference provisioning, u3=7 | Total Cost: 278.62 vs 410.49 (ROBD); 278.62 vs 371.31 (DMD); 278.62 vs 483.75 (HITMIN) | Helped |
| use learning rate η=10^-3 instead of η=10^-2 (ablation) | FairOBD · AI inference provisioning, u3=3.5 | Total Cost: 237.07 -> 246.36 | Hurt |
| use learning rate η=10^-4 instead of η=10^-2 (ablation) | FairOBD · AI inference provisioning, u3=3.5 | Total Cost: 237.07 -> 248.31 | Hurt |
| use learning rate η=10^-3 instead of η=10^-2 (ablation) | FairOBD · AI inference provisioning, u3=1.75 | Total Cost: 216.41 -> 220.84 | Hurt |
| use learning rate η=10^-4 instead of η=10^-2 (ablation) | FairOBD · AI inference provisioning, u3=1.75 | Total Cost: 216.41 -> 221.97 | Hurt |
| use learning rate η=10^-3 instead of η=10^-2 (ablation) | FairOBD · AI inference provisioning, u3=7 | Total Cost: 278.62 -> 297.41 | Hurt |
| use learning rate η=10^-4 instead of η=10^-2 (ablation) | FairOBD · AI inference provisioning, u3=7 | Total Cost: 278.62 -> 300.99 | Hurt |
Surprising findings
- Even without switching costs, no online algorithm achieves sublinear regret or a finite competitive ratio against the unconstrained dynamic offline optimum under long-term fairness regularization.
- FairOPT, the offline fairness-only optimum, has very high switching cost (about 351 vs 23 for OPT).
Limitations
- Assumes non-negative hitting costs and squared l2-norm switching costs, and strong convexity for the analysis.
- The positive result relies on an (R,delta)-constrained offline benchmark rather than the unconstrained optimum; delta must be sublinear in T.
- Experiments are limited to a single trace-driven simulation with seven data centers.
Experimental setup
Datasets: Azure LLM inference trace (May 10-16, 2024) WattTime health price data electricity prices and PUE values for seven US data centers
Benchmarks: Azure LLM inference trace simulation
Metrics: total cost hitting cost switching cost fairness cost
Baselines: OPT FairOPT HITMIN ROBD DMD
Builds on: Regularized Online Balanced Descent Dual Mirror Descent smoothed online convex optimization
Closest papers by meaning
- Dynamic Regret in Online Convex Optimization with Indicator Switching Costs (NeurIPS 2026 · similarity 0.87)
- Time Fairness in Online Knapsack Problems (ICLR 2024 · similarity 0.86)
- FairDICE: Fairness-Driven Offline Multi-Objective Reinforcement Learning (NeurIPS 2025 · similarity 0.86)
- Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality (NeurIPS 2025 · similarity 0.86)
- Gradient-Variation Online Adaptivity for Accelerated Optimization with Hölder Smoothness (NeurIPS 2025 · similarity 0.86)
- Gradient-Variation Online Learning under Generalized Smoothness (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.