Fairness-Regularized Online Optimization with Switching Costs

• URL: http://arxiv.org/abs/2512.11131v1
• Date: Thu, 11 Dec 2025 21:36:34 GMT
• Title: Fairness-Regularized Online Optimization with Switching Costs
• Authors: Pengfei Li, Yuelin Han, Adam Wierman, Shaolei Ren,
• Abstract summary: We study a new and challenging setting of fairness-regularized smoothed online convex optimization with switching costs.<n>We show that FairOBD can effectively reduce the total fairness-regularized cost and better promote fair outcomes.
• Score: 34.87519714070721
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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.

Related papers

• Cost-aware Stopping for Bayesian Optimization [46.95172329282389]
  We propose a cost-aware stopping rule for Bayesian optimization that adapts to varying evaluation costs and is free of tuning.<n>We prove a theoretical guarantee bounding the expected cumulative evaluation cost incurred by our stopping rule when paired with state-of-the-art acquisition functions.
  arXiv  Detail & Related papers  (2025-07-16T17:54:14Z)
• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [70.38810219913593]
  We study the generalized linear bandit (GLB) problem, a contextual multi-armed bandit framework that extends the classical linear model by incorporating a non-linear link function.<n>GLBs are widely applicable to real-world scenarios, but their non-linear nature introduces significant challenges in achieving both computational and statistical efficiency.<n>We propose a jointly efficient algorithm that attains a nearly optimal regret bound with $mathcalO(1)$ time and space complexities per round.
  arXiv  Detail & Related papers  (2025-07-16T02:24:21Z)
• Cost-Sensitive Multi-Fidelity Bayesian Optimization with Transfer of Learning Curve Extrapolation [55.75188191403343]
  We introduce utility, which is a function predefined by each user and describes the trade-off between cost and performance of BO. We validate our algorithm on various LC datasets and found it outperform all the previous multi-fidelity BO and transfer-BO baselines we consider.
  arXiv  Detail & Related papers  (2024-05-28T07:38:39Z)
• Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms [11.029788598491077]
  We study online conversion with switching costs, a family of online problems that capture emerging problems at the intersection of energy and sustainability. We introduce competitive (robust) threshold-based algorithms for both the deterministic and deterministic variants of this problem. We then propose learning-augmented algorithms that take advantage of black-box advice to achieve significantly better average-case performance.
  arXiv  Detail & Related papers  (2023-10-31T16:34:49Z)
• Robustified Learning for Online Optimization with Memory Costs [28.737193318136725]
  We propose a novel expert-robustified learning (ERL) approach, achieving both good average performance and robustness. For any $lambdageq1$, ERL can achieve $lambda$-competitive against the expert algorithm and $lambdacdot C$-competitive against the optimal offline algorithm.
  arXiv  Detail & Related papers  (2023-05-01T06:12:01Z)
• Optimal Parameter-free Online Learning with Switching Cost [47.415099037249085]
  -freeness in online learning refers to the adaptivity of an algorithm with respect to the optimal decision in hindsight. In this paper, we design such algorithms in the presence of switching cost - the latter penalizes the optimistic updates required by parameter-freeness. We propose a simple yet powerful algorithm for Online Linear Optimization (OLO) with switching cost, which improves the existing suboptimal regret bound [ZCP22a] to the optimal rate.
  arXiv  Detail & Related papers  (2022-05-13T18:44:27Z)
• Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
  We investigate an online prediction strategy named as Discounted-Normal-Predictor (Kapralov and Panigrahy, 2010) for smoothed online convex optimization (SOCO) We show that the proposed algorithm can minimize the adaptive regret with switching cost in every interval.
  arXiv  Detail & Related papers  (2022-05-02T08:48:22Z)
• Cost-Efficient Online Hyperparameter Optimization [94.60924644778558]
  We propose an online HPO algorithm that reaches human expert-level performance within a single run of the experiment. Our proposed online HPO algorithm reaches human expert-level performance within a single run of the experiment, while incurring only modest computational overhead compared to regular training.
  arXiv  Detail & Related papers  (2021-01-17T04:55:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.