Fairness-Regularized Online Optimization with Switching Costs

We sincerely appreciate the reviewer’s valuable feedbacks on our paper and we are happy to address the reviewer’s concerns.

Assumptions for Fairness Cost: For the long-term fairness cost, depending if we are minimizing costs or maximizing rewards, convexity or concavity is a commonly adopted assumption in existing literature (e.g. [6], [34]). The convexity for fairness cost is commonly observed in real world applications, such as the min-max fairness consideration in cloud resource provisioning. This is intuitive because the reward or cost doesn’t increase linearly with respect to the actions. Instead, for the rewards, as the law of diminishing marginal utility indicates, the more resource we allocate, the fewer marginal improvements will be, which directly implies concavity. Similarly, the health risks become more and more severe as the air pollution in a certain region increases.

In addition, this convexity is technically essential to our analysis and other related studies (e.g., [6]) that deal with similar long-term fairness regularizers. At a high level, we decouple the long-term fairness cost in Eq(1) to the temporally decoupled costs in Eq(3) using the auxiliary variable $z_t$. During this conversion, it is important to ensure the optimal solutions $x_{1:T}$ in Eq(3) and Eq(1) are identical. If the fairness function $g(\cdot)$ is not convex, when we substitute the optimal solution of Eq(1) into Eq(3), there may existing some sequences of $z_{1:T}$ that further minimizes the $\frac{1}{T} \sum_{t=1}^T g(z_t)$. By rebalancing the fairness costs, hitting costs and switching costs, it’s likely that the optimal solution of Eq(3) is different from Eq(1), which invalidates this essential conversion step. To ensure there is no $z_{1:T}$ sequence that can further minimize the last term in Eq(3), we need to guarantee the average of functions ($\frac{1}{T} \sum_{t=1}^T g(z_t)$) is always larger than the function of the average ($g(\frac{1}{T} \sum_{t=1}^T z_t)$), which directly implies the convexity property. To sum up, convexity for the fairness cost is fundamental in our design as well as other related studies (e.g., [6]) that deal with similar fairness regularizers.

The Lipschitz assumption further bounds the impact of variations in the frame-wise average action across the horizon (denoted by $\delta$) on the overall cost. It's also used to constrain the step-wise cost differences in our proofs. If fairness costs are naturally bounded over their domain, these effects remain controlled. Alternatively, enforcing a stricter benchmark constraint ($\delta=0$) could obviate the need for Lipschitz continuity when bounding the impact of variations. In summary, while relaxing these assumptions would require alternative proof techniques and potentially different results, removing Lipschitz continuity remains technically feasible.

Technical Contributions: First of all, in the presence of switching costs, our algorithm significantly differs from existing methods dealing with long-term fairness. Existing works (e.g., [6], [7]) require the cost objectives (except the long-term cost) to be temporally independent, which is a crucial requirement for their weak duality proofs. In contrast, our objective, after fairness decomposition, is more challenging than [6] due to the switching cost. Specifically, the switching cost breaks the temporal independence, thereby voiding the direct use of existing techniques in [6]. Our novel proof eliminates the need for such independence by focusing on frame-wise optimal action sequences, enabling comparison between different action sequences. Therfore, due to the added switching cost, our proof fundamentally differs from the proofs in [6], which require the per-step cost to be independent of the previous actions once $\kappa_t$ is decided. On the other hand, the proof in [16] for SOCO only allows a difference in $x_{t-1}$ between the online algorithm and optimal offline solution, but cannot allow another decision variable $\kappa_t$ in the per-step objective. Simply combining the proofs for SOCO (e.g. [10],[16]) and fairness regularization (e.g. [6]) does not yield provable bounds.

Secondly, we address the significant challenges in generalizing algorithms designed for standard smooth online convex optimization (SOCO) problems to incorporate long-term fairness costs. This difficulty arises because fairness costs couple all actions within the horizon, unlike SOCO's typical one-step dependence. Specifically, SOCO's per-step objective relies only on the previous action, whereas our per-step objective (Equation 5 in Algorithm 1 in FairOBD) depends on a variable influenced by all prior actions, highlighting the non-trivial nature of integrating fairness into SOCO.

Last but not least, our hardness analysis of the long-term regularizer provides crucial lower bounds for the unconstrained offline optimal benchmark. As demonstrated in Theorems 4.1 and 4.2, we prove that any online algorithm's total regret and competitive ratio will grow linearly (or become infinite) as $T \to \infty$. While some related works (e.g., [6]) consider no swithcing costs and conjectured that no online algorithm could achieve vanishing regret or a finite competitive ratio, our theorems are the first to rigorously prove this inherent difficulty in this setting to the best of our knowledge. Then, building on our lower bounds showing the problem hardness, we establish an important offline benchmark where the offline optimal algorithm is constrained by $(R,\delta)$ constraint. Just as constraining the offline optimal action is needed for online algorithm analysis in other contexts, this constraint is essential for meaningful analysis in our problem. It is also practical, especially in applications like data center scheduling, where contextual information often exhibits natural periodicity, such as diurnal workloads.

The Choice of Hyperparameter: The hyperparameters in FairOBD, such as $(\lambda_1, \lambda_2)$, serve to balance the contributions of hitting cost, switching cost, and long-term fairness cost in determining each per-step action. For example, selecting a larger $\lambda_1$ drives the solution toward maintaining proximity to the previous configuration, thereby reducing switching cost. In practice, these weights can be tuned to reflect the relative importance of the three cost components, depending on the requirements of different applications. Moreover, Theorem 5.2 offers theoretically optimal choices for $\lambda_1$ and $\lambda_2$, providing a principled guideline for parameter selection. The learning rate $\eta$ requires similar consideration: it should be neither too large (leading to instability) nor too small (causing slow convergence), and our theory suggests scaling it inversely with the horizon length. Generally speaking, while our analysis provides important guidance for parameter selection, fine-tuning based on empirical observations remains important for achieving optimal performance in practice and can be of independent interest.

We sincerely appreciate the reviewer’s effort in evaluating our paper and providing insightful feedback. We are pleased that all concerns have been fully addressed.

We're very thankful for the reviewer's careful review and for acknowledging the technical strengths of our work. We're happy to address any concerns and offer additional insights into our motivation and technical approaches.

$(R,\delta)$-Optimal Algorithm: This provides the offline optimal action sequence for minimizing the total cost (e.g., hitting, switching, and fairness) and subject to the $(R,\delta)$ constraint in Line 209. Both Theorem 5.1 and Theorem 5.2 use this benchmark but differ in the specific objectives. Theorem 5.1 highlights the impact of the long-term regularizer on our online algorithm's regret by considering a zero switching cost. We demonstrate that our algorithm achieves sublinear regret even with adversarial context sequences. Theorem 5.2 considers a more general case by incorporating both long-term and switching costs. We establish our algorithm's asymptotic competitive ratio and show its tightness by comparison to the optimally competitive algorithm when there is no fairness cost. Notably, Theorem 5.2 can also recover Theorem 5.1 by setting hyperparameters (e.g., $\lambda_1=1, \lambda_2=0$) appropriately when the switching cost is absent. The comparison of these theorems reveals that the asymptotic competitive ratio $C$ primarily stems from the switching cost, which is inevitable even without the long-term fairness cost (as indicated by Theorem 1 in [16]).

Lower Bound vs Upper Bound: For regret analysis in online algorithms, selecting an appropriate benchmark is crucial, as it defines the strength of the offline optimal comparator. A common choice is the static benchmark, where the offline policy must commit to a single action throughout the entire horizon. This constraint enables meaningful theoretical results, such as sublinear regret bounds in online convex optimization (OCO).

In our setting, we initially considered a stronger benchmark in which the offline policy is unconstrained and may choose arbitrary actions over time. However, we found this infeasible: without knowledge of future contexts, an offline adversary could force any online algorithm to incur unbounded regret. This impossibility is formally shown through our hardness analysis in Theorems 4.1 and 4.2, where we prove that the total regret and competitive ratio of any online algorithm grow linearly (or become infinite) as $T \to \infty$.

The impossibility and hardness analysis (with respect to the unconstrained offline policy) motivates our introduction of the $(R,\delta)$-constrained offline algorithm, which adds some restrictions to the offline policy benchmark. With this new constrained offline benchmark, we derive upper bounds (Theorem 5.1 and Theorem 5.2) for our algorithm under adversarial contexts. Therefore, the upper bounds and lower bounds consider different benchmarks and cannot be directly compared: the upper bounds in Theorem 5.1 and Theorem 5.2 consider $(R,\delta)$-constrained offline algorithm, whereas the lower bounds in Theorem 4.1 and Theorem 4.2 consider the unconstrained offline policy benchmark. Determining whether matching lower bounds exist for the $(R,\delta)$ benchmark is an open problem and a promising avenue for future research.

Technical Contributions: Our work offers four key technical contributions.

First, our hardness analysis of the long-term regularizer provides crucial lower bounds for the unconstrained offline optimal benchmark. As demonstrated in Theorems 4.1 and 4.2, we prove that any online algorithm's total regret and competitive ratio will grow linearly (or become infinite) as $T \to \infty$. While some related works (e.g., [6]) consider no swithcing costs and conjectured that no online algorithm could achieve vanishing regret or a finite competitive ratio, our theorems are the first to rigorously prove this inherent difficulty in this setting to the best of our knowledge.

Second, building on our lower bounds showing the problem hardness, we establish an important offline benchmark where the offline optimal algorithm is constrained by $(R,\delta)$ constraint. Just as constraining the offline optimal action is needed for online algorithm analysis in other contexts, this constraint is essential for meaningful analysis in our problem. It is also practical, especially in applications like data center scheduling, where contextual information often exhibits natural periodicity, such as diurnal workloads.

Third, we address the significant challenges in generalizing algorithms designed for standard smooth online convex optimization (SOCO) problems to incorporate long-term fairness costs. This difficulty arises because fairness costs couple all actions within the horizon, unlike SOCO's typical one-step dependence. Specifically, SOCO's per-step objective relies only on the previous action, whereas our per-step objective (Equation 5 in Algorithm 1 in FairOBD) depends on a variable influenced by all prior actions, highlighting the non-trivial nature of integrating fairness into SOCO.

Finally, in the presence of switching costs, our algorithm significantly differs from existing methods dealing with long-term fairness. Existing works (e.g., [6], [7]) require the cost objectives (except the long-term cost) to be temporally independent, which is a crucial requirement for their weak duality proofs. In contrast, our objective, after fairness decomposition, is more challenging than [6] due to the switching cost. Specifically, the switching cost breaks the temporal independence, thereby voiding the direct use of existing techniques in [6]. Our novel proof eliminates the need for such independence by focusing on frame-wise optimal action sequences, enabling comparison between different action sequences. Therefore, due to the added switching cost, our proof fundamentally differs from the proofs in [6], which require the per-step cost to be independent of the previous actions once $\kappa_t$ is decided. On the other hand, the proof in [16] for SOCO only allows a difference in $x_{t-1}$ between the online algorithm and optimal offline solution, but cannot allow another decision variable $\kappa_t$ in the per-step objective. Simply combining the proofs for SOCO (e.g. [10],[16]) and fairness regularization (e.g. [6]) does not yield provable bounds.

We are grateful for your acknowledgment of the challenges involved in applying a long-term regularizer to smooth online optimization, a problem with significant real-world relevance. We also thank you for your insightful feedback. The mismatch between our upper and lower bounds is, in fact, a central contribution of our work. The lower bounds characterize the inherent difficulty of the problem and hence, by definition, need to consider any possible online algorithm, whereas the upper bounds characterize the performance of our proposed algorithm. Our lower bounds (Theorems 4.1 and 4.2) demonstrate the impossibility of achieving meaningful performance metrics (linear regret and unbounded competitive ratio) against an unconstrained optimal offline benchmark. The lower bounds imply that we have to constrain the offline benchmark for more meaningful analysis. Therefore, we propose and analyze a more appropriate $(R, \delta)$-constrained optimal offline benchmark. With this new benchmark, our algorithm's performance is not only meaningful but also achieves a bounded asymptotic competitive ratio, as shown in our upper bounds (Theorems 5.1 and 5.2). In other words, our upper bound using the new constrained benchmark is in fact a more meaningful and better bound (i.e., hence, a "mismatch") than the pessimistic lower bound that uses the unconstrained benchmark. Such constrained benchmarks are also a recognized approach in other contexts where unconstrained analysis fails to yield meaningful results.

We sincerely appreciate the reviewer’s valuable feedbacks on our paper and we are happy to address the reviewer’s concerns.

Implication of Fairness Objectives: We acknowledge that, in certain scenarios, optimizing for efficiency can naturally enhance fairness, and some fairness objectives may implicitly incorporate efficiency considerations. However, this alignment does not hold universally—particularly for fairness costs evaluated over longer horizons. Solely prioritizing efficiency can inadvertently lead to inequitable outcomes over time. For example, in our empirical study on fair resource provisioning for AI inference across geographically distributed data centers, the hitting and switching costs capture instantaneous system performance. While minimizing these costs motivates selecting the most cost-efficient data center at each time slot, this approach overlooks localized environmental impact, such as air pollution from electricity generation. These public health risks primarily affect nearby communities. Focusing exclusively on efficiency may potentially concentrate workloads in specific locations, thereby imposing disproportionate public health burdens. Consequently, beyond immediate efficiency metrics, it is essential to explicitly incorporate long-term fairness costs to ensure sustainable and equitable system behavior.

Beyond our application, the need to explicitly incorporate fairness regularizers has been recognoized in other contexts such as online resource allocation [6].

Algorithmic Complexity: Our Assumption 3.1 indicates that both hitting and fairness costs are convex, and the switching cost is the standard L2 norm. (See Section 3.1 for discussions on these assumptions.) This ensures that the objective in Eq(5) is convex with respect to $x_t$ and $z_t$. Furthermore, inspired by practical applications, the action sets $\mathcal{X}$ and $\mathcal{Z}$ for $x_t$ and $z_t$, respectively, are bounded (and convex). Consequently, while the specific complexity depends largely on the solvers, our problem at each step in Algorithm 1 is convex optimization, which can be efficiently solved by many established solvers in a polynomial time.

The Advantage of Mirror Descent: Mirror Descent (MD) can be viewed as a generalized form of standard Gradient Descent (GD). At a high level, MD augments GD by introducing a carefully chosen potential, or reference, function (e.g. $h(\cdot)$ in our paper). The algorithm maps the primal variable into a dual space via $\nabla h$, performs a gradient step in the dual space, and then maps back to the primal space through $\nabla h^{-1}$. When $h(x) = \tfrac{1}{2}x^2$, the primal and dual spaces are identical, recovering the standard GD update. By selecting different reference functions, MD adapts the geometry of the optimization problem to improve efficiency. For example, using negative entropy yields the multiplicative weights update (MWU) algorithm, which is particularly well-suited for simplex constraints in probabilities. More broadly, in high-dimensional settings, an appropriate choice of $h$ can substantially accelerate convergence. Thus, while GD remains widely applicable, MD offers a more flexible framework that tailors optimization to the problem’s geometry. For this reason, we adopt the generalized MD in our analysis, which reduces to GD by using $h(x) = \tfrac{1}{2}x^2$.

Related works: We're grateful to the reviewers for highlighting relevant works; we'll be sure to include them in the related works section of our camera-ready version.

We sincerely appreciate the reviewer’s efforts in evaluating our paper and providing constructive suggestions. We hope that all concerns have been successfully addressed, and we are happy to provide any additional information should further questions arise.

We appreciate the reviewer’s response and constructive suggestions.

Point #1: We agree that in some simple settings, where both the fairness function and the hitting cost (or efficiency) are defined at each time slot, optimizing the fairness function may place the outcome on the Pareto frontier. However, in our problem setting, the fairness function is evaluated over the long term, while the hitting cost or efficiency is assessed at each individual time slot. This creates a challenging, yet commonly-studied setup in related works (e.g., [6]). In such cases, optimizing the long-term fairness regularizer does not directly guarantee efficient resource allocation. For example, in the cloud resource provisioning scenario, even if we allocate $N$ units of AI workloads to each location according to the long-term fairness objective, poor temporal allocation of these workloads could still lead to inefficiency. By further optimizing the hitting cost, we can improve the system’s operational efficiency. Moreover, the type of long-term fairness regularizer is a function of the average,$g\left(\frac{1}{T}\sum_{t=1}^T z_t\right)$, which is mathematically different from the average of the function, $\frac{1}{T}\sum_{t=1}^T g(z_t)$. This difference means the long-term fairness regularizer cannot be optimized independently at each time slot. Therefore, both the hitting cost and the long-term fairness cost are essential components of our formulation, and there may not be a direct one-to-one correspondence between fairness cost and system efficiency. Moreover, we also account for the switching cost associated with action changes over time, which adds another layer of challenge to the problem.

Point #2: As shown in ([10], [17]), when switching costs are present, assuming convexity of the hitting cost is essential to achieving a dimension-free competitive ratio for any online algorithm. Motivated by this fundamental challenge, we adopt a similar convexity assumption to obtain meaningful results in this setting, as stated on Line 315 of Theorem 5.2. In contrast, in the absence of switching costs, our algorithm design and analysis are more general, and we do not require this assumption in the theoretical analysis of Theorems 4.1, 4.2, and 5.1. For this reason, we did not explicitly impose convexity of the hitting cost in Assumption 3.1. We acknowledge that in certain cases, non-convex hitting costs may necessitate approximation in the solution at each step (Equation 5 in Algorithm 1). Nevertheless, since the primary focus of this paper is on jointly optimizing hitting, switching, and long-term fairness costs with sequentially revealed context, the problem of efficiently optimizing the per-step cost is orthogonal to our approach.

Point #3: In the empirical study presented in this paper, we select the squared $L_2$-norm as the reference function, which reduces the mirror descent method to standard gradient descent. In future revisions, we will make it clearer what Theorem 5.2 implies in this special case, where standard gradient descent is used. Although we did not adopt the negative entropy reference function to handle action sets with a simplex structure, we believe it is still valuable to keep our analysis general. In other words, our algorithm design and analysis remain applicable even when the standard $L_2$-norm is not chosen as the reference function, such as in real-world scenarios involving simplex constraints, provided that the assumptions are satisfied. Maintaining this generality introduces additional challenges in the theoretical analysis, but we believe it is worthwhile for the community, as it enables application to settings with inherent simplex constraints.

We sincerely appreciate the reviewer's thorough review and the valuable points raised. We are pleased to offer clarifications regarding our technical contributions.

Technical Contribution for Long-term Regularizer: Though decoupling the long-term fairness cost into a sequence of online costs and optimizing the primal and dual variables with online mirror descent has been considered, our algorithm is significantly different from the existing works due to the switching costs. Specifically, for the cost objectives apart from the long-term fairness cost, existing methods (e.g. [6], [7]) require them to be temporally independent. This is a key requirement for the weak duality and the existing proof technique (e.g. [6], [7]), as the inequalities in the proof heavily rely on the optimal solution to a temporally-independent modified objective function at each time slot. In contrast, our objective after the fairness cost decomposition is significantly more challenging than [6] as it does not meet the requirement due to the added switching cost. Our novel proof eliminates the need for such independence by focusing on frame-wise optimal action sequences, enabling comparison between different action sequences. Technically speaking, due to the added switching cost, our proof fundamentally differs from the general proofs in [6], which require the per-step cost to be independent of the previous actions once $\kappa_t$ is decided. On the other hand, the proof in [16] only allows a difference in $x_{t-1}$ between the online algorithm and optimal offline solution, but cannot allow another decision variable $\kappa_t$ in the per-step objective. Simply combining the proofs for SOCO (e.g. [10],[16]) and fairness regularization (e.g. [6], [7]) does not yield provable bounds.

Moreover, we also make other technical contributions such as the hardness analysis by lower bounds on both regret and competitive ratio (Theorem 4.1 and Theorem 4.2), which are the first in the literature to our knowledge.

Relaxed Assumptions For Switching Cost: For the switching cost, though we are considering the L-2 norm for the ease of presentation, it’s technically tractable to consider a more general distance function for the switching cost, such as the Bregman Divergence. The Bregman Divergence is more general than the L-2 norm and it’s also commonly considered [10,16]. When the reference function of Bregman Divergence is the squared function, the switching cost is reduced to the L-2 norm. By making some common assumptions on the reference function of Bregman Divergence (e.g. strong convexity and smoothness), our proof technique can be applied to handle this more general distance function. At the high level, our proof can still convert the action differences between our online algorithm and offline optimal policy to the upper bound of the switching costs. Though technically tractable, due to the space limit, we will explore this direction in our future works.

Relaxed Assumptions For Fairness Cost: For the long-term fairness cost, depending on if we are minimizing costs or maximizing rewards, convexity or concavity is a commonly adopted assumption in existing literature (e.g. [6], [34]). The convexity for fairness cost is commonly observed in many real world applications, such as the min-max fairness consideration in cloud resource provisioning. This is intuitive because the reward or cost doesn’t increase linearly with respect to the actions. Instead, for the rewards, following the law of diminishing marginal utility, the more resource we allocate, the fewer marginal improvements will be, which directly implies concavity. Similarly, the health risks become more and more severe as the air pollution in a certain region increases.

In addition, this convexity is technically essential to our analysis and other related studies (e.g., [6]) that deal with similar long-term fairness regularizers. At a high level, we decouple the long-term fairness costs in Eq(1) to the temporally decoupled costs in Eq(3) using the auxiliary variable $z_t$. During this conversion, it is important to ensure the optimal solutions $x_{1:T}$ in Eq(3) and Eq(1) are identical. If the fairness function $g(\cdot)$ is not convex, when we substitute the optimal solution of Eq(1) into Eq(3), there may existing some sequences of $z_{1:T}$ that further minimizes the $\frac{1}{T} \sum_{t=1}^T g(z_t)$. By rebalancing the fairness costs, hitting costs and switching costs, it’s very likely that the optimal solution of Eq(3) is different from Eq(1), which invalidates this essential conversion step. To ensure there is no $z_{1:T}$ sequence that can further minimize the last term in Eq(3), we need to guarantee the average of functions ($\frac{1}{T} \sum_{t=1}^T g(z_t)$) is always larger than the function of the average ($g(\frac{1}{T} \sum_{t=1}^T z_t)$), which directly implies the convexity property. To sum up, convexity for the fairness cost is fundamental in our design as well as other related studies (e.g., [6]) that deal with similar fairness regularizers.

The I.I.D Setting: In the stochastic setting where the context $\{(f_t, A_t)\}_t$ are sampled from an I.I.D distribution, it’s interesting to analyze the performance of an online algorithm. When there is only a long-term cost without the switching cost, it’s generally possible to obtain a sublinear regret. As Theorem 1 in [6] implies, by carefully choosing the learning rate, the regret can be sublinear. However, as we discussed above, their technique requires the objective functions to be temporally independent. This fundamental limitation restricts their applicability to our problem setting. On the other hand, when there is only a switching cost without long-term cost, additional assumptions or considerations are required to achieve sublinear regret. For instance, we need to consider static benchmarks, where the online algorithm can choose any action but the offline optimal can only choose a static action across the whole horizon. In addition to the static benchmark, another relaxation is constraining the total distance between the subsequent optimal actions, which is also known as the path length in [16]. To sum up, when combining the switching cost and long-term cost altogether, it’s challenging to achieve a sublinear regret even if we consider the I.I.D setting, and further assumptions are required to obtain meaningful results.

Related works: We appreciate the reviewers for complementing the related works and will add them to our related works in our revision.

We sincerely appreciate the reviewer's efforts in evaluating our work and providing such insightful feedback.

While we consider the squared $L_2$ norm as the switching cost, our proof technique can actually be extended to switching costs beyond Bregman Divergence. In particular, our proof technique still applies after modification if the (possibly non-squared) switching cost is convex and smooth. Our current squared $L_2$ norm switching cost satisfies the convexity and smoothness condition. A high-level intuition is that, under the convexity and smoothness condition, the switching cost satisfies the generalized triangle inequality, enabling us to bound the switching cost difference given the action sequence difference. In our revision, we will add details and show how to extend our proof to convex and smooth switching costs.

We fully agree that exploring more general switching costs is a challenging and interesting direction, and hope that our work can inspire the research community.