Fairness-Regularized Online Optimization with Switching Costs
Pengfei Li, Yuelin Han, Adam Wierman, Shaolei Ren
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. 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 novel approach to account for switching costs, we prove that FairOBD offers a worst-case asymptotic competitive ratio against the optimal offline algorithm with parameterized constraints by considering the problem episode length $T\to\infty$. Finally,  we run trace-driven experiments of dynamic computing resource provisioning for socially equitable 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.