Recent research has focused on obtaining learning-augmented algorithms for many online problems to overcome pessimistic lower bounds in competitive analysis. In this paper, we consider the online allocation framework in the learning-augmented setting. In this framework, a set of (divisible) items have to be allocated online among a set of agents, where each agent has a non-negative utility/cost for each item. This framework captures a broad range of classic problems depending on the objective one seeks to optimize. In load balancing (also called makespan minimization), the goal is to minimize the maximum (MinMax) cost of any agent. A more general goal is to minimize the ℓ p -norm of the cost vector defined on the agents, for some p ≥ 1. Both makespan minimization (which is ℓ ∞ -minimization) and ℓ p -minimization are classic problems in scheduling theory and have been extensively studied in competitive analysis. In a different vein, the online allocation framework also applies to information about the problem instance (we call these learned parameters) can help overcome these lower bounds and obtain a near-optimal solution. In this paper, we answer this question in the affirmative. In particular, we give a simple, unified framework for obtaining near-optimal (fractional) allocations using a single learned parameter for every agent. Our result holds for both maximization and minimization problems, and applies to all objective functions that satisfy two mild technical conditions that we define below. Indeed, the most interesting aspect of our techniques and results is this generality: prior work for online allocation problems, both in competitive analysis and beyond worst-case algorithms, has typically been specific to the objective at hand, and the techniques for maximization and minimization objectives bear no similarity. In contrast, our techniques surprisingly handles not only a broad range of objectives but applies both to maximization and minimization problems simultaneously. We hope that the generality of our methods will cast a new light on what is one of the most important classes of problems in combinatorial optimization.
Before proceeding further, we define the two technical conditions that the objective function of the online allocation problem needs to satisfy for our results to apply. Let f : R m >0 → R >0 be the objective function defined on the vector of costs/utilities of the agents.
Then, the conditions are:
Monotonicity: f is said to be monotone if the following holds: for any ℓ, ℓ ∈ R m >0 such that ℓ i ≥ ℓ i for all i ∈ [m], we have f (ℓ) ≥ f (ℓ ).
Homogeneity: f is said to be homogeneous if the following holds: for any ℓ, ℓ ∈ R m >0 such that ℓ i = α • ℓ i for all i ∈ [m], then we have f (ℓ ) = α • f (ℓ).
We say an objective function is well-behaved if it is both monotone and homogeneous. All online allocation objectives studied previously that we are aware of are well-behaved, including the examples given above.
We now state our main result below:
Theorem 1 (Informal). Fix any > 0. For any online allocation problem with a well-behaved objective, there is an algorithm that achieves a competitive ratio of 1 -for maximization problems or 1 + for minimization problems using a single learned parameter for every agent.
We remark that the role of in the above theorem is to ensure that the learned parameter vector is of bounded precision.
Comparison to Prior Work. Lattanzi et al. [17] were the first to consider online allocation in a learning-augmented setting. They considered a special case of the load balancing problem called restricted assignment, and showed the surprising result that a single (learned) parameter for each agent is sufficient to bypass the lower bound and obtain a nearly optimal (fractional) allocation. This result was further generalized by Li and Xian [20] to the full generality of the load balancing problem, but instead of a single parameter, they now required two parameters for every agent. At a high level, their algorithm first uses one set of parameters to restrict the set of agents who can receive an item, and then solves the resulting restricted assignment problem using the second set of parameters. A a corollary of Theorem 1, we improve this result by obtaining a near-optimal solution using a single learned parameter for every agent. In both these papers, as well as in our paper, the (fractional) allocation uses proportional allocation. In the setting of online optimization, proportional allocations were used earlier by Agrawal et al. [1] for the (weighted) b-matching problem. As in our paper, they also gave an iterative algorithm for computing the parameters of the allocation.
However, because the two problems are structurally very different (e.g., matching is a packing problem while our allocation problems are covering problems), the iterative algorithm in the Agrawal et al. paper is different from ours. To the best of our knowledge, our results for the other problems, namely Santa Claus, Nash welfare maximization, ℓ p -norm minimization, and other objectives that can be defined in the online allocation framework are the first results in learning-augmented algorithms for these problems.
We now state our additional results.
A key desiderata of learning-augmented online algorithms is resilience to errors in the learned parameters. In other words, one desires that the competitive ratio of the algorithm should gracefully degrade when the learned parameters used in the algorithm deviate from their optimal values. For well-behaved objectives for both minimization and maximization problems, we give an error-resilient algorithm whose competitive ratio degrades gracefully with prediction error:
Theorem 2 (Informal). For any online allocation problem with a well-behaved objective, there is an (learning-augmented) algorithm that achieves a competitive ratio of O(α) when the learned parameter input to the algorithm is within a multiplicative factor of α of the optimal learned parameter for every agent. This holds for both minimization and maximization objectives.
The above theorem is asymptotically tight for the MaxMin objective. But, interestingly, for the MinMax objective we can do better:
Theorem 3 (Informal). For the load balancing problem (MinMax objective), there is an (learning-augmented) algorithm that achieves a competitive ratio of O(log α) when the learned parameter input to the algorithm is within a multiplicative factor of α of the optimal learned parameter for every agent. Moreover, the dependence O(log α) in the above statement is asymptotically tight.
An analogous statement was previously known only in the special case of restricted assignment [17].
Remark 4. We use a multiplicative measure of error α similar to [17]. Learnability of Parameters. We also study the learnability of the parameters used in our algorithm. Following [20] and [18], we adopt the PAC framework. We assume that each item is drawn independently (but not necessarily identically) from a distribution, and show a bound on the sample complexity of approximately learning the parameter vector under this setting. For the MaxMin and MinMax objectives, we show the following:
Theorem 5 (Informal). Fix any > 0. For the online allocation problem with MaxMin or
MinMax objectives, the sample complexity of learning a parameter vector that gives a 1 -
We note that a similar result was previously known for the MinMax objective (Li and Xian [20]). We also generalize this result to all well-behaved objectives subject to a technical condition of superadditivity for maximization or subadditivity for minimization. All the objectives described earlier in the introduction satisfy these conditions.
Our learning-augmented online algorithms for both minimization and maximization objectives follow from a single, unified algorithmic framework that we develop in this paper. This is quite surprising because in the worst-case setting, the online algorithms for the different objectives do not share any similarity (indeed have different competitive ratios), particularly between maximization and minimization problems. First, let us first consider the MinMax and MaxMin objectives. To use common terminology across these problems, let us call the cost/utility of an item j to an agent i the weight of item j for agent i and denote it p i,j . Our common algorithmic framework uses proportional allocation according to the learned parameters of the agents. Let w i denote the parameter for agent i. Normally, proportional allocation would entail that we allocate a fraction x i,j of item j to agent i where x i,j = wipi,j
. But, this is clearly not adequate, since it would produce the same allocation for both the MaxMin and MinMax objectives. Specifically, if p i,j is large for a pair i, j, then x i,j should be large for the MaxMin objective and small for the MinMax objective respectively. To implement this intuition, we exponentiate the weight p i,j by a fixed value α that depends on the objective (i.e., is different for MaxMin and MinMax) and then allocate using fractions x i,j =
. We call this an exponentiated proportional allocation (or EP-allocation in short), and call α the exponentiation constant.
Let us fix any value of α. It is clear that for both the MinMax and MaxMin objectives, an optimal allocation has uniform cumulative fractional weights (called load) across all agents.
(Note that otherwise, an infinitesimal fraction of an item can be repeatedly moved from the most loaded to the least loaded agent to eventually improve the competitive ratio.) Following this intuition, we define a canonical allocation as one that sets learned parameters on the agents in a way that equalizes the loads on all agents. We show that the canonical allocation always exists and is unique. Indeed, this is true not only for all EP-allocation algorithms, but for a much broader class of proportional allocation schemes that we called generalized proportional allocations (or GP-allocations). In the latter class, we allow any transformation of the weights p i,j before applying proportional allocation. Thus, EP-allocations represent the subclass of GP-allocations where the transformation is exponentiation by the fixed value α. We also give a simple iterative (Sinkhorn-like) algorithm for computing the optimal learned parameters, and establish its convergence properties, for GP-allocations. GP-allocations give an even larger palette of proportional allocation schemes to choose from than EP-allocations, and we hope it will be useful in future work for problem settings that are not covered in this paper (e.g., non-linear utilities).
Finally, we need to set the value of α specifically for the MinMax and MaxMin objectives. Intuitively, it is clear that we need to set α to a large positive value for the MaxMin objective and a large negative value for the MinMax objective. Indeed, we show that in the limit of α → ∞ and α → -∞, the canonical allocation defined above recovers optimal allocations for the MaxMin and MinMax objectives respectively. We also show a monotonicity property of the optimal objective (with the value of α) that can be used to set α to a finite value (function of ) and obtain a 1 -(resp., 1 + ) approximation for the MaxMin (resp., MinMax) objective, for any > 0.
Now that we have described the EP-allocation scheme for obtaining nearly optimal algorithms for the MinMax and MaxMin objectives, we generalize to all well-behaved objective functions. This is quite simple. The main advantage of the MinMax and MaxMin objectives that is not shared by other objectives is the property that the optimal solution has uniform load across all agents. Now, suppose for a maximization objective, the load of agent i in an optimal solution is s i (we call this the scaling parameter for agent i). For now, suppose these values s i are also provided offline as a second set of parameters. Then, we can first scale the weights p i,j using these parameters to obtain a new instance q i,j = pi,j si .
Clearly, the optimal solution for the original instance has uniform load across all agents for the transformed instance. Indeed, by the monotonicity of the maximization objective, this solution for the transformed instance is also optimal for the MaxMin objective. Using the above analysis for the MaxMin objective, we can now claim that there exist learned
gives an optimal solution to the original instance of the problem. Now, note that
It follows that by using learned parameters w i in an EP-allocation on the original instance, we can obtain an optimal solution for the original maximization objective. (The case for a minimization objective is identical to the above argument, with the MaxMin objective being replaced by the MinMax objective.) Finally, using the homogeneity of the objective function, we can also set α to a finite value (function of ) and obtain a 1 -(resp., 1 + ) approximation for the maximization (resp., minimization) objective, for any > 0.
Learning-augmented online algorithms were pioneered by the work of Lykouris and Vassilvikskii [21] for the caching problem, and has become a very popular research area in the last few years.
The basic idea of this framework is to augment an online algorithm with (machine-learned) predictions about the future, which helps overcome pessimistic worst case lower bounds in competitive analysis. Many online allocation problems have been considered in this framework in scheduling [27,5,6,8,15,24], online matching [2,13,16], ad delivery [22,19],
etc. The reader is referred to the survey by Mitzenmacher and Vassilvitskii [25,26] for further examples of online learning-augmented algorithms. The papers specifically related to our work are those of Lattanzi et al. [17] and Li and Xian [20] that we described above, and that of Lavastida et al. [18] that focuses on the learnability of the parameters for the same problem. As mentioned earlier, Agrawal et al. We now give a brief summary of online allocation in the worst-case model. For minimization problems, two classic objectives are makespan (i.e., ℓ ∞ norm) and ℓ p norm minimization for p > 1. The former was studied in several works (e.g., [7,3]), eventually leading to an asymptotically tight bound of Θ(log m). This was later generalized to arbitrary ℓ p norms, and a tight bound of Θ(p) was obtained for this case [4,12]. For maximization objectives, there are Ω(m) lower bounds for many natural objectives such as MaxMin (see, e.g., [14]) and Nash welfare [9]. Some recent work has focused on overcoming these lower bounds using additional information such as monopolist values for the agents [9,10]. While this improves the competitive ratio to sub-linear in m, lower bounds continue to rule out near-optimal solutions (or even constant factor approximations) that we seek in this paper.
Organization. For most of the paper, we only consider the MinMax and MaxMin objectives. We establish the notation in Section 2 and give an overview of the results.
Then, we prove these results by showing properties of GP-allocations in Section 3 and of EP-allocations in Section 4. Next, we give noise resilient algorithms in Section 5 and discuss learnability of the parameters in Section 6. Finally, in Section 7, we extend our results to all well-behaved objective functions via simple reductions to the MaxMin and MinMax objectives.
We have n (divisible) items that arrive online and have to be (fractionally) allocated to m agents. The weight of item j ∈ [n] for agent i ∈ [m] is denoted p i,j and is revealed when item j arrives. We denote the weight matrix
A feasible allocation is given by an assignment matrix
Note that every item has to be fully allocated among all the agents. We use X to denote the set of feasible solutions. The total weight of an agent i corresponding to an allocation X (we call this the load of i) is given by
x i,j • p i,j , and the vector of loads of all the agents is denoted ℓ(P, X).
The load balancing problem is now defined as
while the Santa Claus problem is defined as
50:7
Our algorithmic framework is simple: when allocating item j, we first exponentiate the weights p i,j to p α i,j for some fixed α (called the exponentiation constant) that only depends on the objective being optimized. Next, we perform proportional allocation weighted by the learned parameters w i for agents i ∈ [m]:
We call this an exponentiated proportional allocation or EP-allocation in short.
Our main theorem is the following: Theorem 6. For the load balancing and Santa Claus problems, there are EP-allocations that achieve a competitive ratio of 1 + and 1 -respectively, for any > 0.
The Canonical Allocation. In order to define an EP-allocation and establish Theorem 6, we need to specify two things: the vector of learned parameters w ∈ R m >0 and the exponentiation constant α. First, we focus on the learned parameters. For any fixed α and a weight matrix P , we use learned parameters w ∈ R m >0 that result in equal load for every agent. We call this the canonical allocation. The corresponding learned parameters and the load of every agent are respectively called the canonical parameters (denoted w * ) and the canonical load (denoted ℓ * ).
Apriori, it is not clear that a canonical allocation should even exist, and even if it does, that it is unique. Interestingly, we show this existence and uniqueness not just from EP-allocations but for the much broader class of proportional allocations where any function f : R >0 → R >0 (called the transformation function) can be used to transform the weights rather than just an exponential function. I.e.,
We call this a generalized proportional allocation or GP-allocation in short.
We show the following theorem for GP-allocations:
Theorem 7. For any weight matrix P ∈ R m×n >0 and any transformation function f : R >0 → R >0 , the canonical load for a GP-allocation exists and is unique. Moreover, it is attained by a unique (up to scaling) set of canonical parameters.
We prove Theorem 7 algorithmically by giving a simple iterative (offline) algorithm that converges to the set of canonical parameters (see Algorithm 1). We will show later that the canonical allocations produced by appropriately setting the value of the exponentiation constant α are respectively optimal (fractional) solutions for the Santa Claus and the load balancing problems. Therefore, an interesting consequence of the iterative convergence of this algorithm to the canonical allocation is that it gives a simple alternative offline algorithm for computing an optimal fractional solution for these two problems. To the best of our knowledge, this was not explicitly known before our work.
An interesting direction for future research would be to explore other natural classes of transformation functions, other than the exponential functions considered in this paper. Since problem since it is a minimization problem. Indeed, the second property that we show is that in the limit of α → ∞, the canonical load converges to the optimal objective for the Santa Claus problem (we denote this optimal value ℓ SNT ) and in the limit of α → -∞, the canonical load converges to the optimal objective for the load balancing problem (we denote this optimal value ℓ MKS ).
For a fixed α, let X(P, α, w) denote the assignment matrix and ℓ(P, α, w) the load vector for a learned parameter vector w. Let ℓ * (P, α) denote the corresponding canonical load. We show the following properties of canonical EP-allocations:
Theorem 8. For any weight matrix P ∈ R m×n >0 , the following properties hold for canonical
The monotonicity property: For
The convergence property:
Clearly, Theorem 8 implies Theorem 6 as a corollary when α is set sufficiently large for the Santa Claus problem and sufficiently small for the load balancing problem.
In the rest of the paper, we will prove Theorem 7 and Theorem 8.
In this section, we prove Theorem 7. For notational convenience, we define a transformation
where G(i, j) = f (p i,j ) for the transformation function f . Using this notation, we denote by x i,j (G, w) the fractional allocation of item j to agent i, and by ℓ i (P, G, w) the load of agent i (we use ℓ(P, G, w) to denote the vector of agent loads) under the GP-allocation corresponding to the transformation matrix G and learned parameters w.
We say two sets of learned parameters w, w are equivalent (denoted w ≡ w ) if there exists some constant c > 0 such that
The following is a simple observation from the GP-allocation scheme that two equivalent sets of learned parameters produce the same allocation:
We also note that GP-allocations are monotone in the sense that if one agent's parameter decreases while the rest increase, then the allocation on this agent decreases as well.
Similarly, we show that if the canonical load exists (i.e., a load vector where all loads are identical), it must be unique.
Here, the second equality is by Observation 9, and the inequality is by Observation 10, since ŵk = w k , and ŵi ≤ w i for i ∈ [m].
The rest of this section focuses on showing the existence of a canonical allocation for GPallocations. We do so by showing convergence of the following simple iterative algorithm (Algorithm 1):
Algorithm 1 The iterative algorithm showing the existence of a canonical allocation for GP-allocations.
Initialize:
where ℓ i (P, G, w (r) ) is the load of agent i under the GP-allocation with transformation matrix G and learned parameters w (r) . Set w (r+1) as w
Here, γ (r) ∈ R >0 is a scaling factor whose value does not affect the load (by Observation 9). But, by using, e.g., γ (r) = ℓ (r) 1 , we can ensure that the algorithm terminates with a single set of learned parameters instead of repeatedly finding equivalent sets of parameters after it has converged.
Note that Algorithm 1 ensures that if the loads of all agents are uniform at any stage, then the iterative process has converged and the algorithm terminates. So, it remains to show that for any P, G ∈ R m×n >0 , this iterative process reaches a set of parameters w * ∈ R m >0 such that ℓ i (P, G, w * ) = ℓ i (P, G, w * ) for all i, i ∈ [m].
Our proof has two parts. The first part shows that the maximum and minimum loads are (weakly) monotone over the course of the iterative process. For this, we focus on a single iteration. For a vector ℓ ∈ R m >0 , let ℓ max = max i∈[m] ℓ i and ℓ min = min i∈[m] ℓ i be the maximum and minimum coordinates of ℓ. We will show that if ℓ where
min for some ∈ (0, 1]. Then, in the next iteration, we have ℓ
min for some constant c > 0 that only depends on P and G.
Using Lemma 13 and Lemma 14, we complete the proof of Theorem 7.
Proof of Theorem 7. We are given fixed matrices
min denote the maximum and the minimum load respectively in iteration r of Algorithm 1. Let c > 0 be the constant (that depends only on P, G) in Lemma 14.
For a non-negative integer a, let r a be defined recursively as follows:
We will show for any a, in any iteration r ≥ r a , we have ℓ (r) max/ℓ (r) min ≤ 1 + 2 -a . First, we prove it for a = 0. If there exists some r ≤ r 0 such that ℓ (r) max/ℓ (r) min ≤ 2, then this also holds for r ≥ r 0 by Lemma 13. Otherwise, for all r ≤ r 0 we have ℓ (r) max/ℓ (r) min > 2. Then, using Lemma 14 with = 1, we get ℓ
max by our choice of r 0 . This contradicts Lemma 13, thereby showing that ℓ (r) max/ℓ (r) min ≤ 2 for any r ≥ r 0 . Now, we show the inductive case. Assume the inductive hypothesis that ℓ (r a-1 ) max /ℓ (r a-1 ) min ≤ 1 + 2 -(a-1) . We will prove that ℓ (ra ) max/ℓ (ra )
. The proof is similar to the base case of a = 0. If there exists some r ≤ r a such that ℓ (r) max/ℓ (r) min ≤ 1 + 2 -a , then this inequality also holds for any r ≥ r a by Lemma 13. Otherwise, for all r ≤ r a we have
Then, for all r a-1 ≤ r ≤ r a , using Lemma 14 with = 2 -a , we have ℓ
min . By our choice of r a , this implies ℓ
For ease of description, we assume that G and w are normalized in the following sense:
This transformation is local to the current iteration, and only for the purpose of this proof. First, we explain why this change of notation is w.l.o.g. Suppose Ĝ, ŵ represent the actual transformation matrix and learned parameters respectively. Now, we define G as follows:
and our new learned parameters is given by 1 m .
Note that the fractional allocation remains unchanged, i.e., x i,j ( Ĝ, ŵ) = x i,j (G, 1 m ) = g i,j , and therefore the loads are also unchanged:
In the normalized notation, the new parameters are w i = ℓ1 ℓi . Again, the allocation is unchanged whether we use the original notation or the normalized one:
, and we have,
The case of Two Agents. First, we consider the case of two agents here, i.e., m = 2.
Later, we will show the reduction from general m to m = 2.
We have
and the parameter for the second agent after the update is given by: w 2 = ℓ1 ℓ2 (note that
Accordingly, the loads after the update are given by:
and
.
Assume w.l.o.g that ℓ 1 < ℓ 2 . First, note that, from monotonicity (Observation 10) we have:
.
Next, we have to show that
The proof of the lower bound on ℓ 1 is similar and is omitted for brevity.
We use the following standard inequality:
Fact 15 (Milne's Inequality [23]). For any a, b ∈ R n , we have
(a j + b j ) .
In using this inequality, we set for any j ∈ [n],
First, we calculate each term in Milne's inequality separately:
Using Fact 15, we get
By our assumption that ℓ 1 < ℓ 2 , and therefore w 2 < 1. We now get Equation ( 1) by rearranging terms. This completes the proof for the lemma for the case of two agents.
In this section, we prove the monotonicity and convergence of EP-allocations (Theorem 8).
First, we establish monotonicity of EP-allocations (first part of Theorem 8). We compare two EP-allocations with arbitrary learned parameters but different exponential constants.
We show that with a larger exponent, at least one agent's load will be higher, regardless of the parameters used.
Lemma 16. Fix a weight matrix P ∈ R m×n >0 . Let α, α ∈ R such that α > α . Now, for any two sets of learned parameters w α , w α ∈ R m >0 , there exists an agent k ∈ [m] such that
Proof. Let ∆ denote the vector of differences of loads of the machines in the two allocations, namely ∆ i = ℓ i (P, α, w α ) -ℓ i (P, α , w α ). Our goal is to show that ∆ has at least one nonnegative coordinate.
To show this, we define a vector in the positive orthant c ∈ R m >0 as follows:
, where ρ = α -α > 0 and show that this vector c has a nonnegative inner product with the vector ∆. Note that this suffices since the inner product of a vector with all positive coordinates and one with all negative coordinates cannot be nonnegative. In other words, we want to show the following:
Let us denote the fractional allocation of an item j in the two cases by x i,j and x i,j respectively. Then, Equation ( 2) can be rewritten as
Changing the order of the two summations, we rewrite further as
We will prove this inequality separately for each item j ∈ [n]. Namely, we will show that
Fix an item j. Since the item is fixed, we will drop j from the notation and define u ∈ R m as
So, we need to show that
We have
where
Now, on the right hand side of the above equation, we replace α by α + ρ and w α,i by
This gives us:
where
Rearranging the summations on the two terms on the right hand side, we get
2 0 2 3 50:14 A General Framework for Learning-Augmented Online Allocation Now, let z i = a 1/2 i , and
, and θ = |ρ-1| ρ+1 . Then, we have
In the last equation, the first term follows directly from
The second term is more complicated. There are two cases.
then the roles get reversed and we get
Now, note that T ≥ 0. So, to establish i c i • u i ≥ 0, it suffices to show that the right hard side of the equation is nonnegative. We do so by employing Callebaut's inequality which we state below:
Fact 17 (Callebaut's Inequality [11]). For any y, z ∈ R n and θ ≤ 1, we have
Note that we can apply Callebaut's inequality because ρ ≥ 0 implies that θ ≤ 1. This completes the proof of the lemma. Using Lemma 18, we complete the proof of Theorem 8.
Theorem 8. First by Lemma 11, there exists w * α and w * α , such that, for all i ∈ [m], ℓ i (P, α, w * α ) = ℓ * (P, α) and ℓ i (P, α , w * α ) = ℓ * (P, α ). Now, if ℓ * (P, α) < ℓ * (P, α ), it would contradict Lemma 16. And combining Lemma 16 and Lemma 18, we completed the proof the second part of Theorem 8.
In this section, we show the noise resilience of our algorithms, namely that we can handle errors in the learned parameters. First, we will show that for both objectives (MaxMin and MinMax), an η-approximate set of learned parameters yields an online algorithm with a competitive ratio of at least/at most η. Second, for the MinMax objective, we show that it is possible to improve the competitive ratio further in the following sense: using a set of learned parameters with a multiplicative error of η with respect to the optimal parameters, we can obtain a O(log η)-competitive algorithm. (This was previously shown by Lattanzi et al. [17] but only for the special case of restricted assignment.) We also rule out a similar guarantee for the MaxMin objective, i.e., we show that using η-approximate learned parameters, an algorithm cannot hope to obtain a competitive ratio better than η/c for some constant c.
Finally, we show that noise-resilient bounds can be obtained not just for the MinMax and MaxMin objectives but also for any homogeneous monotone minimization or maximization objective function. Formally, a weight vector w is η-approximate with respect to a weight vector to w * , if for any two agents i, i ∈ [m], w i wi ≤ η • w * i w * i . First, we show a basic noise resilience property that holds for both the MinMax and MaxMin objectives: Lemma 19. Fix a weight matrix P ∈ R m×n >0 and a transformation matrix G ∈ R m×n >0 . For any two parameter vectors w * , w ∈ R m >0 , such that w is η-approximate to w * , we have that for any agent k:
Proof. Let y i,j = x i,j (G, w * ) and z i,j = x i,j (G, w) be the respective fractional allocations under proportional allocation using the transformation matrix G. For an agent i, let τ i = w i /w * i . Then for any two agents i, k, we have that
Hence, y i,j /η ≤ z i,j ≤ y i,j • η. Finally, the lemma hold by summing over all items.
The next theorem follows immediately by using a proportional allocation according to the parameter vector w: Theorem 20. Fix any P, G ∈ R m×n >0 . Let w be a learned parameter vector that gives a solution of value γ for the MaxMin (resp., MinMax) objective using proportional allocation.
Let w be η-approximate to w for some η > 1. Then, there exists an online algorithm that given w generates a solution with value at least Ω(γ/η) (resp., at most O(ηγ)).
In particular, if w is the optimal learned parameter vector in the above theorem and w is an η-approximation to it, then we obtain a competitive ratio of Ω(1/η).
The rest of this section focuses on the MinMax objective for which we can obtain an improved bound. In the next lemma, we establish an upper bound on the load, using
Lemma 19 and monotonicity. Lemma 21. Fix a weight matrix P ∈ R m×n >0 and a transformation matrix G ∈ R m×n >0 . For any two parameter vectors w * , w ∈ R m >0 such that there exists an agent k ∈ [m] for which w * k /2 ≤ w k ≤ w * k and for all other agents i = k, we have w i ≥ w * i /2, then the following holds: ℓ k (P, G, w) ≤ 2 • ℓ k (P, G, w * ). Proof. Define w where w k = w * k (i.e., the maximum in its allowed range) and w i = w * i /2 for all i = k (i.e., the minimum in their allowed ranges). Now, by monotonicity (Observation 10), we have x k,j (G, w) ≤ x k,j (G, w ), and therefore, ℓ k (P, G, w) ≤ ℓ k (P, G, w ). Note that for w , for any two agents i 1 , i 2 , wi 1 wi 2 ≤ 2 • w * i 1 w * i 2 . Therefore, by Lemma 19, we have ℓ k (P, G, w ) ≤ 2 • ℓ k (P, G, w * ). By combining the two inequalities, we have ℓ k (P, G, w) ≤ ℓ k (P, G, w ) ≤ 2 • ℓ k (P, G, w * ), as required. I C A L P 2 0 2 3
We first generalize Theorem 6 to all well-behaved functions.
Theorem 26. Fix any instance of an online allocation problem with divisible items where the goal is to maximize or minimize a monotone homogeneous objective function. Then, there exists an online algorithm and a learned parameter vector in R m >0 that achieves a competitive ratio of 1 -(for maximization) or 1 + (for minimization).
Proof. Fix an objection function f and a matrix P ∈ R m×n >0 . Let ℓ f i denote the load of agent i in an optimal solution for objective function f . Also, let x i,j denote the fraction of item j assigned to agent i in this optimal solution. Now, consider the matrix P , where pi,j = pi,j ℓ f i .
By the monotonicity property of f , the optimal objective value for P is 1. Therefore, by Theorem 8, there exist α and w, such that using an EP-allocation, we get ℓ * ( P , α, w) ≥ 1 -
maximization and ℓ * ( P , α, w) ≤ 1 + for minimization. Let x * i,j be the fraction of item j assigned to agent i in this approximate solution. By the definition of EP-allocation, x * i,j is proportional to pα i,j • wi = pi,j ℓ f i α • wi = p α i,j • wi (ℓ f i ) α . Thus, if we define w such that w i = wi (ℓ f i ) α , then the corresponding EP-allocation gives a (1 -)-approximate solution for maximization and (1 + )-approximate solution for minimization.
Next, we consider noise resilience for well-behaved functions, i.e., we generalize Theorem 20 to all well-behaved objective functions. This follows immediately from Lemma 19 and the observation that if all loads are scaled by η, then the objective value for a well-behaved objective is also scaled by η. We state this generalized theorem below: Theorem 27. Fix any P, G ∈ R m×n >0 and any monotone, homogeneous function f . Let w be a learned parameter vector that gives a solution of objective value γ using EP-allocation.
Let w be η-approximate to w for some η > 1. Then, the EP-allocation for w gives a solution with value at least γ/η for maximization and at most ηγ for minimization.
Finally, we consider learnability of parameters for well-behaved functions, i.e., we generalize Theorem 23 and by assuming additional property of the objective function:
For a maximization objective f , we need superadditivity: f ( r ℓ r ) ≥ r f (ℓ r ).
For a minimization objective f , we need subadditivity: f ( r ℓ r ) ≤ r f (ℓ r ).
Theorem 28. Let f be a well-behaved function. If f is superadditive, the following theorem holds for maximization of f , while if f is subadditive, the following theorem holds for minimization of f . Let T be the expectation of the maximum value of f over instances sampled from D. Fix an > 0 for which the small items assumption holds. Then, there is an
In this paper, we gave a unifying framework for designing near-optimal algorithm for fractional allocation problems for essentially all well-studied minimization and maximization objectives in the literature. The existence of this overarching framework is rather surprising because the corresponding worst-case problems exhibit a wide range of behavior in terms of the best competitive ratio achievable, as well as the techniques required to achieve those bounds.
It would be interesting to gain further understanding of the optimal learned parameters introduced in this paper. One natural conjecture is that these are optimal dual variables for a suitably defined convex program (for instance, such convex programs are known for restricted assignment and b-matching [1]). Another interesting direction of future work would be to explore other polytopes beyond the simple assignment polytope considered in this paper, such as that corresponding to congestion minimization problems.
We consider the learning model introduced by[18], and show that under this model, the parameter vector w can be learned efficiently from sampled instances. Specifically, we consider