A Learning-Augmented Approach to Online Allocation Problems
Authors: Ilan Reuven Cohen
Debmalya Panigrahi
Venue: NeurIPS 2025 poster ()
Keywords: online algorithm
learning-augmented algorithm
virtual circuit routing
Primary area: theory
TL;DR: A general technique for designing learning-augmented algorithms for online covering problems with applications to routing, scheduling, etc.

Abstract: In online allocation problems, an algorithm must choose from a set of options at each step, where each option incurs a set of costs/rewards associated with a set of $d$ agents. The goal is to minimize/maximize a function of the accumulated costs/rewards assigned to the agents over the course of the entire allocation process. Such problems are common in combinatorial optimization, including minimization problems such as machine scheduling and network routing, as well as maximization problems such as fair allocation for welfare maximization.

In this paper, we develop a general learning-augmented algorithmic framework for online allocation problems that produces a nearly optimal solution using only a single $d$-dimensional vector of learned weights. Using this general framework, we derive learning-augmented online algorithms for a broad range of application problems in routing, scheduling, and fair allocation. Our main tool is convex programming duality, which may also have further implications for learning-augmented algorithms in the future.

A Learning-Augmented Approach to Online Allocation Problems
Mlan Reuven Cohen
Debmalya Panigrahi
Faculty of Engineering
Department of Computer Science
Bar-Ilan University
Duke University Durham, NC, USA. debmalya@cs duke. edu
Ramat Gan, Israel.
ilan-reuven. www.ncbi..nccccccccoococoo.oo
Abstract
In online allocation problems, an algorithm must choose from set of options at each step, where each option incurs set of costs/rewards associated with set d agents. The goal to minimize/maximize function of the accumulated costs/rewards assigned to the agents over the course of the entire allocation process. Such problems are common in combinatorial optimization, including minimization problems such as machine scheduling and network routing, as well maximization problems such as fair allocation for welfare maximization.
In this paper, develop general learning-un augmented algorithmic framework for online allocation problems that produces a nearly optimal solution using only a single d-dimensional vector of learned weights. Using this general framework, we derive
online algorithms for a broad range application prob- lems in routing, scheduling, and fair allocation. Our main tool is convex program- ming duality, which may also have further implications for -ugment- algorithms in the future.
Introduction
In the last few years, tremendous advances in machine learning have triggered much interest and rapid progress in new domain called sarriing-augmnnte online algorithms. In many practical scenarios, one needs solve optimization problems with dynamically evolving requirements (called online algorithms), where uncertainty about the future significantly affects the quality of the solution. use (possibly noisy) machine-learned
The basic premise of the learning- saaminn-auggentedd paradigm predictions as a proxy for the future, and design online algorithms that can take advantage of good predictions while not falling prey to bad ones. (The resulting algorithms are sometimes also referred to as "online algorithms with predictions".) The explosive growth of this new area over the last few years has spanned large variety of domains such as caching, scheduling, matching, clustering, network design, and many others (see related work), and generated much excitement at the intersection of algorithm design and machine learning. While many novel and clever algorithms have been designed in the leaminn--uummnted setting, these are typically tailored to the requirements of a specific problem at hand, and do not generalize to broader problem classes. Indeed, there is surprising absence of unifying algorithmic models and general-purpose tools for online algorithms with predictions, particularly when contrasted with other models of computation where algorithmic progress has largely relied on broad, unifying models and algorithmic techniques.
In this paper, we aim to partially rectify this situation by studying a broad class of problems called online allocation in the learning-augmentt the algorithm presented a set of options and has to choose one of them. Each option is represented by vector, and the final objective is (linear or non-linear) function of the (coordinate-wiss) sum
setting. The setup is the following: in each online step,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

of all the chosen vectors. As we will soon see, this captures a broad range of problems in network routing, scheduling, fair allocation, etc. In this paper, we develop a general algorithmic strategy for this entire class of problems in the learning-augmented setting that obtains nearly optimal (fractional) solution. This is in sharp contrast to strong (super-constant) lower bounds without MI. advice, for almost all problems captured by this framework.
The online allocation problem that we described above has many applications. Among the most important is that of online routing. In this problem, we are given network and in each online step, the algorithm has to choose a route from given source to a destination node. Eventually, the goal to minimize the maximum congestion of any network link, which is defined as the number of chosen routes using that link. This is a classical and well- problem in online algorithms, and it is well-known that the best competitive ratid achievable is logarithmic in the size of the network [ (see also
6 7. In sharp contrast, we obtain a (1 + -aapproximaaionn for any e > 0 using learning augmentation, by modeling the problem as online allocation where each coordinate in the vector represents a network link and the goal is to minimize the -nom of the congestion vector.
A second application domain for online allocation is that of online scheduling problems. Consider the problem of processing jobs online where each job comes with slate of options given by vectors that represent the processing time on different machines. Overall, the goal is to minimize the makespan, i.e., the maximum load on any machine. This problem is also described via online allocation, where the coordinates of the vectors represent machines and the objective is again the &oe -norm of machine loads given by the sum of the selected vectors. Our online allocation algorithm gives (1 + e)- competitive
solution to this problem, which again sharply contrasts with lower bounds that are logarithmic in the number of machines in the absence of learning augmentation [10]
We note that the flexibility of the online allocation framework also allows us to extend these problem formulations immediately to a much broader set of objectives, such as all fy-norm objectives (5] rather than just the -nomm. Another interesting direction is that of maximization problems. In contrast minimization problems where the vector coordinates can be thought of resources whose use needs to be minimized, we now imagine the coordinates to represent value added to agents when a particular option is selected. This allows us to model fair allocation problems, where a set of items have to be assigned in a way that maximizes the minimum value along all agents (or another function such as Nash social welfare, p-means, etc.) [3 1.5 Again, we observe the sharp contrast between the traditional online setting without learning augmentation, where strong polynomial lower bounds exist for these problems 34 18 and the marming-auggmntt setting where our online allocation algorithm immediately yields (1 e) -approoximation for any 0.
We end this section by commenting on the machine-learned parameters that we use in our learning- augmented algorithm for the online allocation problem. As described above, we show that there exists a set of learned parameters that allows us to approximate the optimal objective within a (1 = e) factor of the optimal value. Importantly, we show that these parameters are bounded as a function of and the number of coordinates (rather than the number of steps or options) and, moreover, that our narmmngg algorithm is resilient to small errors in the values of the learned parameters. This allows us to derive PAC-learning results for the learned parameters and to use them in the algorithm to obtain a (1 + approxxppoiiiiioon.
Organization. The formal model and statement of results appear in Section 2 Section presents related work. The main result, which provides the parniing-augmentd algorithm, appears in Section 4 Applications of this result to routing and fair allocation problems are discussed in Section In Appendix C we derive sample complexity bounds for the learned parameters in the PAC model. All omitted details of proofs are in the appendix.
2 Our Contributions
First, we define the online allocation framework:
Online Allocation Problem. In this problem, we receive an initial input of a function f over a bounded domain in Rd. Subsequently, we proceed in steps. At every time step I....,T. we receive a set A, C R4 of d-dimensional vectors. We must select one vector vî E A, before
As is usual in online algorithms, performance of an algorithm is measured via its competitive ratio, which is the worst-case ratio of the algorithm's objective that of an optimal solution.

---

proceeding to time step t + 1, using only information available up to time t. Denote the result vector vio :- Ei vf. The goal is to maximize minimize f f(v(x) for some objective function f(-).
For case of notation, we fix an arbitrary ordering of the vectors in Ag, and denote by Ve,k E R2 the kth vector in A,, i.e., At (V.,1..... Ft, set of indices of these vectors, and for each E K (t), we let vi,,kk denote the ith coordinate of vector 0r in Ag. Our results apply to well-behaved funncionove f(-) that we define as follows:
Accordingly, we define ((t) = {l..... [Ay]} } as the
Well- Behaved Functions. Let f _ - R2 be the objective function defined on the result vector. Then, is well-behaved if it satisfies the following properties:
Monotonicity: f is said to be monotone if for any l' IR4 such that & 2 f for all E [d]. we have f(t) 2 f((").
Homogeneity: f said to be homogeneous if for any E, ll E I4 such that E = a. lg for all i E [d]. we have f((") f(t).
These properties are satisfied by most objective functions studied in the literature including linear functions, p-norms, Nash Social Welfare (which is the geometric mean), p-means, etc.
Our algorithmic scheme will focus developing fractional selection rule, which can be interpreted as probability distribution over the different choices in every step. We formally describe a fractional solution as follows:
Fractional Solution. At step f, the algorithm has to assign a fractional value to each option Lt,k E [0, 1] for k E K(t) such that I|K(A) Tt,k 1. Accordingly, we have
|4 Vi.k -r.k-
Vin
ΣΣ
Note that in some scenarios such as the allocation of divisible items or network flow routing, a fractional solution is already sufficient.
Learning- Based Online Scheme for Allocation Problems. Our main result is that for any d- dimensional instance of the online allocation problem with well-behaved objective function, there exists a vector a Rd such that an online algorithm guided by a achieves a competitive ratio of 1 1+ for minimization or 1 for maximization, for any 0.
Theorem 2.1. Given an instance of the online allocation problem with a well-behaved objective and any > there exists set of learned parameters R.d and an online algorithm that uses such that the resulting fractional solution achieves (1 + (())) (lp))opppriiiaationn
The online algorithm that establishes this result uses simple exponential assignment rule, where given a learned parameter vector a E IRd, the fractional allocation (a)((a) of option k: E K(t) is:
Pet (a) xc exp
a
1ii m,)
where m,(v) min M 0, E [d], l K(t))
We further show that the learned parameters can be bounded as a function of d and c, and that the algorithm is robust to small perturbations in the parameter values. This structure allows the parameter space to be both bounded and discretized in terms of d, e, independent of the time horizon. This property crucial in applications where the number of steps (which may represent flow requests, jobs, or items) is significantly larger than the number of dimensions (which may represent network links, machines, or agents). Moreover, the discretization of the parameter space ensures that the parameters are learnable, and allows us to bound the number of samples required for learning.
Learnability of Parameters. Following the PAC framework of (26). we establish the learnability of parameter vectors for well-behaved objectives, under the additional assumption of superadditivity for maximization subaddirivity for minimization, introduced in (18].
We consider setting in which each online step (i.e., a set vectors) drawn independently (though not necessarily identically) from distribution, and each step contributes only a small fraction of the total allocation. This latter property formalized by the standard small items assumption (see, e.g..
Il 26 24 29). which we state below:
3

---

Ingd such that Dick S 2 for every [d] [T].
Small Items Assumption: There exists and l K (L).
Under this assumption, we derive a sample complexity bound for approximately learning parameter vector that ensures near-optimal performance. The following informal theorem summarizes main learnability result; see Appendix for details:
Theorem 2.2. Under standard PAC assumptions, the small items assumption, and mild regularity conditions on the objective (subadditivity for minimization and superadditivity for maximization), the parameter vector
TRd can be learned from O Tog llog + i.i.d. samples.
Rounding the Fractional Solution. As mentioned earlier, fractional solution is already sufficient for many applications. Furthermore, we show that under the small items assumption (see above), a fractional solution can be converted into a randomized online integral solution with (1 + e) loss the objective value, where the parameter only depends on the parameters of the small items assumption.
Consider the following online randomized rounding algorithm: given an online fractional solution zitk for E [T'. the algorithm chooses option k with probability Tt, Under the small items assumption, standard Chernoff bounds ensure that with high probability, the maximum coordinate in the rounded vector remains within a multiplicative factor of (1 + O()) of its fractional counterpart. We get the following theorem:
Theorem 2.3. Let y be fractional solution, and lel vhne be the integer solution produced by randomized rounding of this fractional solution. Then, under the small items assumption, the following holds with high probability:
max v E[|d] sori S (1+c)
max v
1a,s and iE ld]
min Von 2 (1 c) ke(d
min 1ot.
iE|d]
Now, combining the above theorem with Theorem 2.1 under the small items assumption:
we get the following result for integer solutions
Corollary 2.4. Given an instance of the online allocation problem with well-behaved objective and under the small-item assumption, for any >> 0, there exists set of learned parameters
E gd and an online algorithm that uses a such that the resulting integral solution achieves (1 + -pppaaaaproiniaaion.
Saaustness-Consisteene Tradeoff. Ideally, a saaming-augmenti algorithm should simultane- ously exploit accurate predictions to achieve near-opting optimmlpimal performance (consistency), while also maintaining strong worst-case guarantees when predictions are unreliable (robustness). The (not worst case lower bounds for allocation problems with minimization (resp., maximization) objectives Olog d) (resp., (d)). Formally, an algorithm is said to 7y-consistent and 8-robust if it achieves a-approximation under accurate predictions (consistency). and 8- approximation in the worst case when predictions are unreliable (robustness). In Appendix we give slight modification of our scheme that preserves robustness while achieving consistency for both minimization and maximization objectives.
Theorem 2.5. For minimization objectives, there exists an algorithm that uses Idd, predicted parameter vector, and achieves 1-consistent and Ollog d'-robust approximation.
For maximization objectives, there exists an algorithm that uses E Rd. predicted parameter vector, and parameter X, which achieves
-c-oosiistnnt and X d-robust approximation.
Applications. In Section 5| we illustrate the utility of our framework in handling broad class of objectives by demonstrating its use in two applications. The first is for the online routing problem, where we are given a network and each time-step, there is request to route given value of flow from source to a destination vertex (3] The flow needs to be routed in way that minimizes maximum congestion on any edge cumulatively across all time-steps. We give the first Berning-auggmette algorithm for this problem simple corollary of our general online allocation framework. Next,

---

we consider maximization problem, that of allocating items to agents so as to maximize the Nash algorithm for this problem as a simple corollary of our general framework, matching previous results in [8] We note that our framework applies to many other application problems domains such as scheduling (makespan and f--norm minimization) and fair allocation (Santa Claus and p-means maximization) that we do not state here for brevity.
Social Welfare [3]. Again, we give
3 Related Work
Previous work that is mostly closely related ours is learning-augmentnn online scheduling and assignment problems [23 24 26 18]. These works focus on the assignment of items that arrive online to agents, where each choice affects only a single agent. In our setting, this corresponds to each choice being represented by a d-dimensional vector with a single nonzero dimension, where corresponds to the number of agents.
Lattanzi et al. [3 focused on minimizing the makespan (maximum load) for restricted assignment. They showed that suitable set of learned parameters enables proportional allocation rule that obtains a nearly optimal result. In (24), it was further shown that these parameters are PAC-Icarnable.
Li and Xian [26] generalized this framework to handle unrelated scheduling, Their scheme introduces two learned parameters per machine. The first set of parameters transform the instance into a restricted- related setting, and they show that proportional assignment using the second set of parameters then applies this restricted setting.
Cohen and Panigrahi [8] improved this result by using only a single set of parameters in an exponential allocation scheme, and also extended it handle large number of maximization and minimization objectives.
Our scheme generalizes these previous works to accommodate general vectors, which is crucial for applications such as online routing that cannot be solved using the previous techniques. Furthermore, simplify the previous approaches as well by requiring only single variable per dimension, thereby eliminating the dependence on an additional exponent base which further simplifies the analysis of the existence of such parameters. Our work introduces new set of techniques based on perturbation/sensittie parameters do generalize the case of arbitrary vector options.
analysis because the ideas previously used for bounding the learned
In [4], the authors study the Online Nash Social Welfare problem with predictions. The goal is to compute online divisible allocation of goods among agents in way that balances fairness and efficiency. In their setting, the prediction for each agent is their monopolist value-the the utility the agent would obtain if all resources were allocated solely to them-and their algorithm achieves an Ollog dD-aaproximmtion under this assumption. In contrast, we show that by learning a different d-dimensional parameter vector, it is possible to achieve nearly optimal allocation.
19 20 investigate the robustness consistency tradeoff the context of general packing and covering problems. These algorithms typically introduce an additional parameter E [0, 1] to encode the algorithm's confidence in the prediction. A primal-dual scheme then employed to interpolate between a worst-case baseline and a prediction-driven strategy. Unlike our approach, these methods assume that the prediction consists of the full solution, which is often impractical in real-world settings.
Various papers 12 35
More broadly, the study of narming-augmented online algorithms was initiated by Lykouris and Vassilvitskii (27] in the context of the caching problem and has since grown into prominent research area. This framework enhances online algorithms by incorporating machine-learned predictions about the future, allowing them to surpass pessimistic worst-case competitive bounds. Over the past few years, numerous online allocation problems have been explored within this framework, including applications in scheduling 33
R
9
21 30 online matching 2 17 22). and ad delivery [2 25
For broader overview
online algorithms, we refer the reader to the surveys
by Mitzenmacher and Vassilvitskii [3] 32
5

---

Online Allocation for a Well-Behaved Objective via Learned Parameters
In this section, show that for the general case of the online allocation problem, there exists set of learned parameters that guarantees a near-optimal solution. Specifically, we show the following theorem, which is more refined version of (and establishes) Theorem 2.1
Theorem 4.1. Given an instance of the online allocation problem with a well-behaved objective and any O, there exists set of learned parameters NET (q. s) and online algorithm that a such that the resulting fractional solution achieves a (1 + ((c)))approximatiin
Here, NE s) {s | ( $ denotes a d-dimensional discrete net with parameters q. that are bounded in poly(d,
For the minimization of a well-behaved function, we first consider the MinMax objective, which defined as the minimization of f. where f(v) = max V,. Similarly, for the maximization of well-behaved function, we first consider the MaxMin objective, which is defined as the maximization of f, where f(u) = min V/
In this section, we focus on the MinMax objective. In Appendix E we address the MaxMin objective. In Appendix we explain how to extend these results to general well-behaved objectives.
4.1 Learning-Augmented Online Allocation for the MinMax Objective
We now state the main result for the MinMax objective:
Theorem 4.2. Given instance of the online allocation problem with MinMax objective and any C <> O, there exists a set of learned parameters a E NET L In (#) & and an online algorithm that uses a such that the resulting fractional solution a (1 O(e)) -pproxxaixoi..i.o
To prove this result, we first apply a pre-processing step to convert arbitrary instances of the problem to structured instances that say are balanced. Note that the conversion to balanced instances is an algorithmic technique and not a restriction on the input. We then leverage convex programming duality on max-entropy style convex programming formulation show the existence of learned parameters that can be used to obtain an near-optimal solution online. At this stage, the learned necessarily efficiently learnable. To ensure the latter, need to obtain parameters that belong to NET - In (2) _
parameters can be of arbitrary precision and
We do this in the last step by using tools from perturbation and sensitivity analysis sis in the convex programming literature. Together, these steps establish Theorem 4.2
Preprocessing of MinMax Instances. Recall that the exponential assignment scheme computes online allocations based on the ratio m.(o]. This ratio can be highly sensitive and potentially unbounded under small perturbations to the input, thereby making it impossible execute the last
Vs.ck
step of designing learned parameters of bounded precision. To overcome this difficulty, we introduce pre-processing step that transforms the original instance into balanced instance, incurring only small loss in the objective value.
instance 7(ū, K') said to be balanced if it satisfies the following condition for all [T], i [d], and & E K(t):
Üick
tojufa (a+ee) be z+ n 1ogi+e
d
(0) U
Note that in a balanced instance, we have Uhttk 2. Moreover, by omitting redundant options, we
m((1)
may assume that the number of options per step is bounded, i.e., In [K(t)] O (d In(d/e)). We
construct balanced instance T(ū, K) as follows:
Given an instance T(v, K).
1. Define such that
0
if maxy Re
Mask
Ozk
Clak
otherwise.

---

2. Define K by removing option k' from step whenever there exists another option &s with
max 0s, > d
max ds,,k-
3. Define as follows: if 6eck = O, then set 0isk = O; otherwise, set
Tiek (0) +)+ logi+e Beck
)
By definition, T(ū, K) is balanced instance. In Appendix into 1 (ū, K) incurs only a (1 + O(e)) loss in the objective value.
show that transforming T(v, K)
Lemma 4.3. Let I (V, K) be instance of the allocation problem with the MinMax objective, and let e O. Then, any (1 c)-approximate solution the balanced instance [(ū K) constructed via the pre-processing algorithm yields a (1 + + (.0(ee)--prrximmal solution to I(v, K).
Learned Parameters for Balanced Instances. In light of Lemma 43 suffices to only consider balanced instances in Theorem 4.2 We restate this goal as follows:
Lemma 4.4. Given a balanced instance of the online allocation problem with a MinMax objective and there exists set of parameters a E NET [o_ In (+) c such that the fractional solu-
tion defined by the exponential assignment scheme with parameters is a (1 apprrxxiixnn to the optimal objective.
The remainder of this section gives proof of Lemma 4.4 We do this in steps. First, prove the existence of parameters (=) that bounded as function of d, using which the exponential assignment scheme produces an (1 + appprooxieete optimal solution. (For the special case of 0, the solution is precisely optimal but the parameters may be unbounded.) Then, show that small errors (up to 2/d") in the parameter values incur only (1 + O()) loss in the objective value,
enabling discretization of the learned parameters to NET ( (
We use I to denote the optimal MinMax value, and define the following convex program for c >> 0:
min
Σ m²(v)
Itk (In Fekk 1) kEK())
Σ
1E/2
s.t.
Vitk S L (1+
Vi [d],
tE|2 (t)
Σ Itk =1 kEk())
Vt e [T],
Tttk 0,
Vk E K(t),t [T]
Figure 1: Convex Programming Formulation for the MinMax Objective
Lemma 4.5. Given an instance of the online allocation problem with the MinMax objective and any e Z O, there exists a vector () E Rd such that the fractional solution defined by the exponential assignment scheme with parameters (s) is -app(c)aapprxxxmmaee optimal.
Proof. Given such instance and for fixed e consider the convex program of Figure I assumption, L* is the optimal MinMax objective therefore there exists feasible solution for the convex program for any 0. Accordingly, define the Lagrangian L(x, a. B) as
By our
(w)
Σ (E
Jekk In
Teek
Σ Σ
USeR - I." (1++)))
Σ 3.11
Σ F.k). AEK())
EE|T]
#E[d
FE[T] (EK())
1E[T]
From the KKT conditions for the optimal solution to the convex program function of
(+)) (+), g(e), the solution that allocates according to z(t) is (1 + e) approxximatii to the optimal
7

---

objective L", and a 2 0 for all i E [d]. Furthermore,
dL -0 for all & E K(),, which gives mv) In(x(() (c) + m((v) Σ a Usck =B1
dr
For any two options k, (t),, obtain:
(() In(x + Σ ai
(c)
Dish me(v) In In( (c)
+ Σ Lalo
Vaty
(e)
Therefore,
Vier
Σ
Viek
Coupled with
Σ kE (ER(
[e) = 1, we get
m (v)
m.(v) (v)
(c) Itk
Σ 0
(c)
Vitk
exp
m2(v)
Bounding the Learned Parameters, For O, the learned parameters (() in the previous lemma may be unbounded. However, for <> O, we show that each a²)) can be bounded as a function of and e. Our main tool is perturbation and sensitivity analysis, following the framework of Boyd et
al. [66. (See Appendix for details of perturbation and sensitivity analysis.)
Lemma 4.6. Let x(6), a (00,,((4) gi4) be the optimal solution to the convex program in Figure for some 0. Then, for all i e [d], it holds that ag I L In (1)
Proof. We need the following claim:
Claim 4.7. For an dimensional vector Ek In 2 -1-- -ln..
1 have [0, 11 such that E Tz
Proof. By Jensen's inequality, we have
Σ Sp.B.. Di
Σ p(U)), where p: 0, Σ 1, and is concave.
to
The desired bound now follows by setting p(x) In(x), pt n, and yi 1/24.
We define perturbed convex program based on Figure where u, corresponds to the constraint ag For each E [d]. setting u; = - L and uy = 0 for + +i ensures that constraint i the perturbed problem matches the original constraint, thereby guaranteeing feasible solution. By Lemma B.I
D" 00,00 2 p" v) a. L", which implies
( c. 1' < (0.0) p" (u, mn In
LE|T]
where the last inequality follows from Claim 4.7
Σ ml (v) mi(t)= -==mmon mi()) _
Σ r < ΣΣ
Fik Σ UsEk = ΣΣΣ Cak Di S
K
where the first equality holds because x² is feasible solution, the first inequality follows since there must be at least one nonzero coordinate and by definition of (v),,, and the second inequality follows from the linear program constraint for dimension i.
By our assumption on the instance, have
[(tt] < d [logite
))
d²
d -
Therefore, a. < d
d
< d
In
8

---

Diseretizing the Learned Parameters and Noise Resilience. In order to prove Lemma 4.4 need to ensure that the learned parameters ( belong to the discrete set NET In This may not be true of the Lagrangian multipliers derived above. We show that in discretizing the learned parameters, the competitive ratio only worsens by (1 O()).. In particular, if we replace the c; oj
we
Lagrangian vector (+ with perturhed vector o; where the assignment fractions change by at most + 4c. Note that this lemma is also important from a noise resilience perspective: if the learned parameters have small error, this lemma shows that the resulting allocation is still approximately optimal.
(e) I 27 for all E [d], then
Lemma 4.8. Let a E IRd be a vector, and let á E Rd be a perturbed vector such that (ā; 03 S for all E [d]. Then, the fractional assignment z(x(ā) satisfies d
(1 4c) xxx((")) I Fea (ā) = (1 4c) xek""") for all l K(t,ttE))
Proof. We need the following claim:
Claim 499. For any >> 0, if we are given two sets of K weights a, ER such that 1 - S 2 S
1+ c, then for x. x' E [0, 1]K such that E Th = Ek Ek=1 2/. and æg x ag and 2 d' we
have 1 - 4c $ < 1 + 4e.
Proof. Consider the assignment fractions Tg.- By definition, we have the following:
1te
(1 4e) -
Ok
0
+
1
0g
-1
-1
d'
1 1
2 (1 4E) 2
Fk
ak
0
1+e
0k
(- Σ; Or
Define Orx = exp
me(v]]
Then, we have
ask (a") (a)
(-
Σ (a4 a.)
Wisk mu)
exp
By the assumption that the instance is balanced, we have Mitk
2 which implies
Otk (<x( aex
1 1- 2c S exp(-c)
< exp(c) S 1 + 2c.
Thus, by Claim 4.9 the assignment fractions using â differ from those using a by at most 41+) L
Finally, we now put all the pieces together to establish Lemma 4.4
Proof of Lemma 4.4 Fix balanced instance [vv, K) and >> 0. By Lemma 4.6 there exists
parameter vector a such that a²)) E 0, d In (9) for all [d]. Therefore, there exists
vector à NET - In
such that |ā, a.11 f for all i e [d]. By Lemma 4.8 the
exponential assignment rule with ā achieves (1 0(e))-approximation
5 Applications
Our framework applies broadly to a variety of online allocation problems. We briefly highlight two representative applications: online routing and Nash Social Welfare maximization.
Online Routing. In online routing (e.g., 3), requests arrive over time and must be assigned to paths in network to minimize congestion delay. Each option (path) contributes load to

---

network edges, and the goal is to minimize the maximum edge utilization, which corresponds to the MinMax objective. Our approach uses vector of learned edge-weight parameters to guide allocation decisions, combining strong worst-case guarantees with improved performance when input patterns are predictable.
Formally, we are given as input a directed graph G = EV, At each time step E [T], flow request of amount rr between two vertices S; and tr, along with a set of candidate paths P.= = (Pr,,, Pr...... J. is revealed. Here, each P.. is path from S, to & in the graph. The algorithm must assign values qt,k to each path such that Σ. 9t.k = rt. The load on an edge E is given by (c( E, EP. Qt,k, and the objective is to minimize the maximum congestion on any edge, i.e., min e (Ee(g) Σx Qt.k r for all E [7]).
We note that online routing is a special case the online allocation problem, where A S (z: fIfe 10, 2 E RR
}. and the objective is minimize f(u) max4e]]] 84-
Our main result for online routing follows as a corollary of Theorem 4.1
Corollary 5.1. Given instance of online routing and any > 0, there exists set of parameters
d²) a E NET - (2) =3 such that the fractional solution Tik xx exp E; 0z
Sax), for t E
[2'] approximates the optimal objective within a factor of (1 + O(e)).
Online Nash Social Welfare. As mentioned, our scheme also applies to maximation problems where, each step, a divisible resource has be distributed among set of agents. The objective is to design an online algorithm that balances fairesss and efficiency. At the start of each step t, the algorithm observes the value Us of each agent for that resource, and then irrevocably determines the allocation without knowledge of future values, If agent i is allocated fraction Fi,t, their utility increases by 1,, The total utility of agent is then given by ux(x) = E. Vi,
The Nash Social Welfare (NSW) objective is known to provide a natural balance between fairness and efficiency. It is defined as the geometric mean of the agents' utilities: NSW(x) (TI, uy (x(x)) 1/d By applying our method for maximizing well-behaved objectives, we obtain the following corollary:
Corollary 5.2. Given an instance of online NSW maximization and any ists a set of parameters or E NET - (2), ( such that the fractional solution Ft,k xx exp (Σ, 04 - v.,N), for L E [T], approximates the optimal objective within a factor of (1-))))).
O, there
Note that using our results, we may further generalize this to options with vector utilities, i.e., where an option can add (possibly different amounts of) value multiple agents simultancously.
6 Closing Remarks
In this paper, we gave a general technique for designing online algorithms with predictions that applies to the entire spectrum of problems that can be modeled via the online covering framework. This has value in two respects. First, gave the first augmeeted results for important problems like online routing and scheduling that goes beyond simple assignment, and were beyond the scope of previous techniques. Second, and perhaps more importantly, it opens the door to the design of even more general- purpose methods for the design of online algorithms with predictions. For instance, can we give a technique for online step reveals new constraint in the LP? Techniques such as the online primal dual method that apply to this class of LPs have been hugely influential in the classical online algorithms literature (without predictions), which makes it tempting proposition to explore similarly powerful tools in the Baaming-augmment setting.
algorithms that applies to any covering L.P where each
Acknowledgments and Disclosure of Funding
Ilan Reuven Cohen's research was supported by the Israel Science Foundation grant No. 1737/21. Debmalya Panigrahi's i's research supported in part by NSF grants CCF-1955703 and CCF-2329230.
10

---

References
[1] Shipra Agrawal and Nikhil R Devanur. Fast algorithms for online stochastic convex program- ming. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 1405-1424. SIAM, 2014.
[2] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev, Secretary and online matching problems with machine learned advice. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 2020.
[3] James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, and Orli Waarts. On-line routing of virtual circuits with applications to load balancing and machine scheduling. Journal of the ACM (JACM), 44(3):486- 1997.
[4] Baruch Awerbuch and Yossi Azar. Competitive multicast routing, Wirel. Networks, 1(1):107- 114, 1995.
[5] Baruch Awerbuch, Yossi Azar, Edward F. Grove, Ming- Yang Kao, P. Krishman, and Jeffrey Scott Vitter. Load balancing in the lp norm. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA. 23-25 October 1995, pages 383-391, IEEE Computer Society, 1995.
[6] Baruch Awerbuch, Yossi Azar, and Serge A. Plotkin. Throughput-compette on-line routing. In 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993, pages 42-40. IEEE Computer Society, 1993.
[7] Baruch Awerbuch, Yossi Azar, Serge A. Plotkin, and Orli Waarts. Competitive routing of virtual circuits with unknown duration. In Daniel Dominic Sleator, editor, Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, Arlington, Virginia, USA, pages 321-327 ACM/SIAM, 1994.
[8] Yossi Azar, Stefano Leonardi, and Noam Touitou. Flow time scheduling with uncertain processing time. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing. pages 1070-1080. ACM, 2021.
[9] Yossi Azar, Stefano Leonardi, and Noam Touitou. Distortion-oblivious algorithms for mini- mizing flow time. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 252-274. SIAM, 2022.
[10] Yossi Azar, Joseph Naor, and Raphael Rom. The competitiveness of on-line assignments. J. Algorithms, 18(2):221-237 1995.
[11] Étienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. Learning augmented energy minimization via speed scaling. Advances in Neural Information Processing Systems 33, NeurlPS 2020, 2020.
[12] Etienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. Advances in Neural Information Processing Systems, 33:20083-20094 2020.
[13] Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy Jin. Online nash social welfare maximization with predictions. Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 1-19. SIAM, 2022.
[14] Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy Jin. Online nash social welfare maximization with predictions. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithmss (SODA), pages 1-19. SIAM, 2022.
[15] Siddharth Barman, Arindam Khan, and Amab Maiti. Universal and tight online algorithms for generalized- welfare. In Thirty-Siahh AAAI Conference on Artificial Intelligence, pages 4793-4800. AAAI Press, 2022.

---

[16] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[17] Justin Y. Chen and Piotr Indyk. Online bipartite matching with predicted degrees. CoRR, 2021.
[18] Ilan Reuven Cohen and Debmalya Panigrahi. A general framework for Ceaming-augmentt online allocation. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th Inter- national Colloquium on Automata, Languages, and Programming. ICALP 2023, July 10-14, 2023, Paderborn, Germany, volume 261 of LIPles, pages 43:1-43:21, Leibniz-Zentrrum für Informatik, 2023.
Schloss Dagstuhl
[19] Elena Grigorescu, Young-San Lin, Sandeep Silwal, Maoyuan Song, and Samson Zhou. Learning- augmented algorithms for online linear and semidefinite programming. Advances in Neural Information Processing Systems, 35:38643-38654, 2022.
[20] Elena Grigorescu, Young-San Lin, and Maoyuan Song. Leamiing-augmented algorithms for online concave packing and convex covering problems. arXiv preprint arXiv:2411.08333 2024.
[21] Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Non-clairvoyant scheduling with predictions. In SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6-8 July, 2021, pages 285-294. ACM, 2021.
[22] Ravi Kumar, Manish Purohit, Aaron Schild, Zoya Svitkina, and Erik Vee. Semi-online bipartite matching. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, volume 124 of LiPlcs, pages 50:1-50:20. Schloss Dagstuhl- Seibniz-Zeentumn für Informatik, 2019.
[23] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online schedul- ing via learned weights. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 1859-181 1877. SIAM, 2020.
[24] Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu. Learnable and instance- robust predictions for online matching, flows and load balancing. In 29th Annual European Symposium Algorithmss ESA 2021, volume 204 of LIPlcs, pages 59:1-59:17, 2021.
[25] Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu. Using predicted weights for ad delivery. In Applied and Computational Discrete Algorithms, ACDA 2021, 2021.
[26] Shi Li and Jiayi Xian. Online unrelated machine load balancing with predictions revisited. In Proceedings of the 38th International Conference on Machine Learning, ICMI. 2021, 2021.
[27] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. J. ACM, (8(4):24:1-24.27 2021.
[28] Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi. Online optimization with uncertain information. ACM Trans. Algorithms, 8(12: 2012.
[29] Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized es, online matching. Journal of the ACM (JACM), 54(5):22 es, 2007.
[30] Michael Mitzenmacher. Scheduling with predictions and the price of misprediction. In 11 Innovations in Theoretical Computer Science Conference, ITCS 2020, volume 151 of LIPles, pages 14:1-14:15 Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2020.
[31] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. In Beyond the Worst-Case Analysis of Algorithms, pages 646-662. Cambridge University Press, 2020.
[32] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Commun. ACM, 65(7)333-35, 2022.
[33] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via MI predic- tions. In Advances in Neural Information Processing Systems 31, NeurIPS 2018, 2018.
12

---

[34] Max Springer, MohammadTaghh Hajiaghayi, Debmalya Panigrahi. and Mohammad Reza Khani. Online algorithms for the santa claus problem. In Sanmi Koyejo. S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022.
[35] Nguyen Kim Thang and Christoph Durr. Online primal-dual algorithms with predictions for packing problems. arXiv preprint arX1:2210000031, 2021.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
scheme for online allocation and thoroughly proves its guarantees and applicability.
Justification: The paper develops a
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, the paper discusses the limitations by outlining the modeling choices and assumptions under which the results hold. It clarifies the settings where the approach is applicable, such as the well-behaved objective functions and distributional assumptions for learnability.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
14

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Yes. The paper clearly states all necessary assumptions for each theoretical result and provides complete and correct proofs throughout.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
15

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://mips.co
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
7 //nips. htcp//blccggudeeeeeeeeeeeeeeeeee
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
16

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttp::://orrpps..ccpppbbttttttt
Answer: [Yes]
Justification: Yes.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no socictal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neurd/: /00p://ccc...cc.eeeee//////////0 for what should or should not be described.
20

---

A Preprocessing for the MinMax Objective
We begin by introducing preprocessing step for the MinMax objective. Given an instance [(v, K), let MinMaxx1; K) denote the optimal value of the corresponding MinMax objective. Specifically, we construct an instance (ū, K) that e-approximates given instance [v, K) as follows:
Definition A.1. An instance T(ū K) is said e-approximate an instance T(u, K) if:
k(j) _ K()) for all E N,
MinMaa((e. K) MinMax((e, K) (1 c).
For any feasible allocation è. for T(ū, R),, if the load in any dimension is at most with respect then the corresponding load with respect to most L +)..
(Note that è remains feasible allocation for [u, K) since K(j) K())))
Using this definition, we prove that in order to achieve (1 + O(e)) to the instance I(e, K) it is sufficent acheive (1 + e) approximation to K).
Corollary A.2. Let [v, K) be given instance. Suppose the instance is transformed into an approximate instance (,, K). Ifa (1 + e)-approximate allocation is computed for the transformed instance [(ū K), then this allocation guarantees -approxmaiinno for the original instance
Proof. Let x be feasible solution for I(ū, K) such that
Σ
Σ
Fek Uak S MinMax K) (1+c).
kER())
Using Definition A.I
we obtain:
Σ
Σ
Feh Wiek S MinMax K) +))²
kE((()
MinMax(y, (). (1+
We now show that each of the three steps defined in the transformation produces an e-approximate instance with respect to the original instance.
Claim A.3 (Step (1) of the preprocessing). Given an instance [(v K) let i such that
Witk
d'
Üitk
max, otherwise.
Witk
the the instance [(6 K) e-approximate the instance 1(v, K).
Proof. By definition, MinMax(i, R) MinMax(y, K). Next, given solution such that for all i [d].
Σ Fek Jisk S L,
we prove that
ΣΣ AER())
S D - +
For fixed coordinate i [d], define
(t(t) {K K(t) Uick Tickh
21

---

which represents the set of options for item t where the load on coordinate is modified by the transformation. For an item and an option & E (t). let
arg max Dirk deld
denote the coordinate that experiences the maximum load for option & of item Observe that if le E (t), then
Ditk S d
Uume st.
Thus, we have:
Σ tk
Lik Vick
Σ Usk Dsek +
Σ
Σ
Ziih : Vick
tk
RER
< L +
Σ
Σ
Ztk: Vick
(ER,())
L + ΣΣ
Σ
Ftk Ustk
Ped (0IK
S + ΣΣ E
Esk d Uyak
PEd kO);
L+ ΣE Σ
d
Feke Tick
KOR, =1
< L + ΣΣ
Tik Tiekk
/ed
S T, + Σ I.
PE(d]
= L (1 + E),
where the first and final inequalities follow from the definition of x, and the second inequality follows from the transformation definition.
The
Claim A.4 (Step (2) of the Preprocessing). Given an instance [v, K), let I(U, K') be the instance obtained by removing option k' from item whenever there exists another option K K(1) such that
d
max
max
where wik = maxxeed] V1,tk
Then [v, K") an e-approximation of the instance [(v, K).
Proof. Clearly, an assignment with load most for all E [d]] in T(ū, K) results in a load of at most I. in T(v, K), since the retained options have identical loads. We now show that if an allocation achieves makespan of in [(, K). then there exists a transformed allocation f that achieves makespan at most L (1 11+e e) [ K).
We explicitly construct such an assignment à and show that it satisfies the required bound. Define
min arg min U.
22

---

as the option with the smallest maximum load for item t, breaking ties by selecting the smallest index. Let
maa Ek
arg max US,AA
denote the coordinate where option l of item t imposes the maximum load. Next, define the
d
R(t) (k E K(t)
U2A
}
which identifies options with disproportionately high loads relative to the smallest maximum load. We then construct the transformed allocation å for each item t [n]] as follows:
Fik + EWER()) Tek
if k kmiin
if R(I),
otherwise.
This transformation ensures that options in R(t) are reallocated to the option with the smallest maximum load, maintaining feasibility while ensuring that the makespan increases by at most factor of (1 + c). Specifically, we have:
Σ
Lit Uisk
Σ Ttk Uerk Σ
E
MER(()
< L +
Σ
Tie á
WER(L)
L + d
Σ
Σ
Σ
Dek 1.
P. MER(()) Pinn
S + d
ΣΣ
Fik Uy
< Σ L. d
= L (1 +),
where the first and final inequalities follow from the definition of x, and the second inequality follows from the fact that for k E R(t),
d
max
U/max JtR
Claim A.5 (Step (3) of the Preprocessing). Given an instance 1 [v, K)
if Uatk = 0, then set Uuk 0; otherwise, set
Tak m)(u) (1 + logi+o (i(t)) )l.
Lick
Then 166 K) is an e-approximation of the instance I(v, K).
Proof. By definition,
0uk S Uik & (1 (1+6) c) Gak- Therefore, I(0, K) is an c-approximation of the instance T(v, K).
By applying Claim
A.3 Claim
A.4 Claim A.5 and Corollary A.2
proved the Lemma 4.3
23

---

B Perturbation and Sensitivity Analysis
One of our main tools for bounding learned parameters perturbation and sensitivity analysis, following the framework of Boyd et al. [16]
B.1 Perturbed Convex Programs
Consider a convex program represented by a tuple hf, where Rd - R for i e [0, ml and h4 IR R for i [1, All formulated as:
minimize fo(x) subject to fi(x) S 0, i [],
h,(x) ie [1,
We define the perturbed version of this problem follows. Let E T and v R Define perturbed constraints:
f((x)= fi(2) ui h1(x)) h₂(x) 2z.
The perturbed problem becomes:
minimize fo(x)
subject to fi(x) S uss
i [1, m]
h,(x) Us
i E [1, nt].
This coincides with the original problem when u = 0 and e = 0. Positive u, relaxes the ith inequality; negative u, tightens it. The vector perturbs the right-hane hand sides of the equality constraints.
Let p" (u, v)) denote the optimal value of the perturbed problem. If the problem is infeasible, we define p" (u, v) = co. When the original problem is convex, p" (u, v) is convex in both u and
B.2 A Global Inequality via Duality
Assume strong duality holds and that the dual optimum is attained (which the case under Slater's condition). Let (X*,u*) denote optimal dual solution to the original problem. Then the following global bound holds.
Lemma B.1 (Perturbation Inequality, [6].. For all R and R
p" (0 2 xu TT.
B.3
Proof Sketch
To derive this inequality, consider any feasible solution to the perturbed problem, i.e.,
f((x) S ue,
Vi [1,
hx(x) = vi [1,
By strong duality:
(0,00)) = ,(A',00)
S fo(x) + Σ xff(()) + Eithi
So(()) x a + n 0,
where the last inequality follows from fi(x) S ui 1111z)
U/. and x > 0.
Rearranging, we conclude:
fo(x) 2 p" (0. 0) - \ T 4 v'
This inequality quantifies how much the objective value may change response to perturbations of the constraints, depending linearly on the dual multipliers.

---

C Learnability of the Prediction Vectors
We consider the learning model introduced by [24]. and show that under this model, the dual vector can be learned efficiently from sampled instances. Specifically, we consider the following model: the ith step (i.e., the values of 22 (Ui,e E [d], k E K(t)) is independently sampled from (discrete) distribution Dj.
We up the online allocation problem for the MinMax objective; the setup for the MaxMin objective is very similar and is omitted for brevity. Let L = Ep-D MinMax P)] be the expected value of the MinMax objective in the optimal solution for instance P drawn from DD
Morally, we would like to say that we can obtain the vector a that gives a nearly optimal solution (in expectation) using vector allocation (i.e., MinMax objective of (1 + L in expectation for some error parameter e) using a bounded (as a function of e) number of samples. Similar to 224. we need the following assumption:
Small Items Assumption: Conceptually, this assumption states that each individual item has a small utility compared to the overall utility of any agent in an optimal solution. Precisely, we need Vitk S {
for every E [d], E [T]. and & E K (t) for some value Ç (= θ
log d
We show the following PAC learning theorem for the MinMax objective:
Theorem C.1. Fix an > 0 for which the small items assumption holds. Then, there is an (learming) algorithm that samples O (1ggd loog )) independent instances from DD and outputs (with high probability) prediction vector such that using in the allocation scheme gives a MinMax objective of at least (1 + O(e)) in expectation over instances P DD
Proof Sketch. Recall that in PAC theory, the number of samples needed learn function from family of N functions is about Olog N). Indeed, restricting a to be in the class NET(K, K, S) serves this role of limiting the hypothesis class to a finite, bounded set since [NTT(K, S)] = SK) where S K (ppoly(d, e))- Using standard PAC theory, this implies that using about Od K) Od log ) samples, can learn the "best" vector in NET (K, S). Our main technical work is to show that this "best" vector produces an approximately optimal solution when used.
C.1 Details of PAC Learning
Given an instance P, Let 4(P, a) the value of the ith dimension of v after applying our scheme on the instance P with the parameters Let K = and S d²
Let us consider a combination of all instances in the support of the distribution D. For L processing matrices p(1), p(2),.__... ...., P(L), We define pall = + p(r) to be the instance defined by the n L items. For every & [L] and E [T], have step {() with values D2 (e)
The following observation is immediate (subadditivity):
Observation C.2. MinMax(Pell) < E/= MinMax(P(r)).
Using this observation, we can prove the following lemma, by considering the combination of all instances in D. scaled by their respective probabilities.
Lemma C.3. There exists a E NET(K, S), such that for every E [d], we have
I Ep-D(((()))] & (1 c)+ LI"
Proof. Consider the instance P Prp[PP P where PP][P] is the probability mass of P in D, and [P] is the matrix multiplied by Prp] P). By Observation C.2 we have
MinMax(P) < Σ
Prp (Mp(P)))aax(P))
P
= E MinMax
25

---

We can apply Lemma 4.4 to the combined instance to show there exists a" (EE(KK, such that for every E [d], we have,
Σ (F,,") Par & (1 + MinMax(() & (1 (1+6)-13
th
where t indexes over all steps in IP. Notice that tt, (P, a²) depends on the utility vector for step t, which is part of the instance P DD that t belongs to. Therefore, the left side of the above inequality is exactly
ΣΣ P 1,k
FeR (P,((P,))) Pro[P] Piçck
-EPDD
Σ
EPDD (((P,a),,
EE[T]
as required.
For any real numbers A, e,e, C. we use A ReC B denote |A B| Se max C). The lemma appears in [26]: Lemma C.4 (Lemma D.6 in in (66).. For any E NET(K, with high probability over P D, we have
E [d] (((,a) RE,L- Ep-Dli(P',o)
The learning algorithm. We sample И =0 d
log instances P2........ 1 Σ (,(Ph, ā).
. PH independently
log
and randomly form D. We output à NET(K,,) that maximizes minge и The next lemma also appears in (26]:
Lemma C.5 (Lemma D.7 in (26)). With probability at least [K-Sjm for every a NET S)
and for every i E [d]. have
Σ
((Ph. Re. Ep.Dli(Paa).
H
1=1
Now assume the event in Lemma happens. NET(K, S) such that
Then by Lemma
C.3
there exists some
min kE(m
((Ph, a) S (1+6)2 L..
H
1=1
In particular, since ā maximizes minjg[m] H 2 (((Ph, â) for à E NET(m, c), conclude that
"
min eE(m]
<
H
A=1
Applying Lemma C.5
again, get
min Ep-pl (P,a) < .* (E[m]
We now apply Lemma the following holds:
C.4 to We have that with high probability over ~ D, for every E [m]
(P,ã))
EpwDL((P ā) +e max(L",EExxpiii Ep (P)))) <
(1+1)*.1' Lt.
Therefore, MinMax(P.a) < (114 I(c)) L* This completes the proof of Theorem C.I
26

---

D Robustness-Cnnisteenyy Tradeoff
In this section, show that and robustness, achieving near-optimal performance when predictions are accurate while retaining strong worst-case guarantees when they not.
scheme can be modified to balance consistency
Recall that an algorithm said to be y-consistent and ô-robust it achieves a 7-approximation under accurate predictions (consistency), and d-approximation in the worst case when predictions are unreliable (robustness).
For allocation problems with minimization objectives. the worst-case approximation ratio without any predictions (log d), and for maximization objectives it is (dd) where d is the number of agents.
We show that tradeoff.
scheme can be modified satisfy this
Modified Algorithm for Minimization Objectives. Let E Rd be the predicted parameter vector. The algorithm operates in two phases:
1. Prediction Phase: At each time step, use the exponential assignment scheme with parame-
ters a.
2. Fallback Phase: Monitor the cumulative objective value. If exceeds the optimal value by a factor larger than Oloo d), the algorithm switches standard worst-case online algorithm.
Let 7 be the approximation factor achieved using Then, the final approximation ratio is min(1, Ollg d)), ensuring both consistency and robustness.
Modified Algorithm for Maxinization Objectives. Let Rd be the predicted parameter vector, and let À E [0, 1] be a confidence parameter reflecting trust in the prediction. The algorithm allocates each item as follows:
Allocate a fraction 1 of the item using the exponential assignment scheme with parameters
2. Allocate the remaining À fraction using a worst-case robust algorithm (e.g., uniform alloca- tion greedy).
This strategy guarantees:
Consistency:
The portion allocated by the learned parameters achieves an approximation
ratio of (1 - (1 - c), assuming the predicted parameters yield (1 c) approoxiiation
The worst-case portion contributes most d, matching the lower bound of known worst-case algorithms.
Robustness:
Hence, the algorithm achieves (1 -) (o(1-c)-consiiiie consistent and X d-robust guarantee.
E Learning-Augmentedd Online Allocation for the MaxMin Objective
In this section, we prove our main result for the MaxMin objective.
Theorem E.1. Given an instance of the online allocation problem with a MaxMin objective and any > 0, there exists set of learned parameters
d
Q E NET log
and an online algorithm that uses the exponential assignment scheme with -a, such that the resulting fractional solution is a (1 -apro--aprxiiiaatio
To prove this theorem, we proceed similarly to the MinMax case: we begin with preprocessing step that transforms the instance into a balanced form. However, the details of the preprocessing differ in the MaxMin setting.
27

---

E.1 Preprocessing for the MaxMin Objective
We begin by describing transformation that modifies the input instance into balanced form suitable for our learning- augmented algorithm. The transformation has two steps:
Beaming--uummente
Step 1: Remove agents with large monopolist values.
For each step t [T]. define
D max
Vitks kEK(I)
kit = arg max Ustk- kEK(t)
Define the monopolist value of agent as a; EvErry U/ and let Omin minte(d O,. For each agent such that
2
Omin:
we allocate an c/d fraction of the resource at each step to their preferred option kü--
Step 2: Zero out negligible values. For the remaining instance (with the reduced set of agents),
define new instance by zeroing out small entries:
if
Pish
Diek
max,
Cask
otherwise.
Let J(tt) C (t) be the set of options that were modified for agent at step f, and define
max
Wark-
(t)
Step 3: Quantize values to form balanced instance.
Define the final preprocessed values as: if Dick O, otherwise.
Dstk (v) (1 + (e+ 1081+
Masa
This rounding ensures that all nonzero values are restricted to a logarithmic grid defined by the base 1 + e, thereby yielding balanced instance.
Lemma E.2. Let [vv ()) be an instance of the allocation problem with the MaxMin objective, and
let O. Then, the transformed instance [(,, K), obtained via the three-step preprocessing, satisfies the following: any ----))apprxxiaatt solution for 1(,, K), when combined with the allocations reserved in Step I, yields (1 -(()) apprrxxmmae solution for the original instance I(v, K).
Proof. We begin by analyzing the impact Step The utility of any agent removed during this step guaranteed to be at least
d a; 2 amin MaxMin(2) K),
so these agents fully satisfied by the reserved allocation. Moreover, the total amount of resource allocated to these agents is at most an e-fraction of the total, ensuring that the remaining instance is affected by at most - c) loss in the objective value.
Now consider the remaining agents the modified instance [(ū K). In Step 2, we zero out negligible values reduce the dynamic range. Let Cü maxke)(1)) Uaek, where (t()) is the set of coordinates zeroed out for agent at step f. For each E [d]. we bound the total value removed as:
Σ Tia
Ee max, Uytk - Σn Egar S d
Omin <e Me-Maxiine,, K),
d/e
d/c
where the last inequality uses the fact that MaxMin(U, K) 2 amin/ dd as each agent can receive 1/d share of their monopolist option.
Hence, the approximation loss from zeroing out small values is bounded by MaxMin(e, K), and the resulting instance ((0 K)) differs from the original by at most an O(c) factor.
Finally, Step 3 introduces geometric rounding of values to the nearest power of (1 c). As shown in the MinMax case, this quantization step results in an additional loss of at most a (1 -c) factor.
Combining the effects of the three steps, the overall degradation in objective value is at most (1 O(e)) factor. Thus, a (1 e) -ppppooxie solution to the preprocessed instance yields (1 (((e)--aprrxxin solution for the original instance.
28

---

E.2 Existence of Discretized Parameters for Balanced Instances for MaxMin
In light of Lemma E.2 to prove Theorem suffices to consider balanced instances, as stated in the following lemma:
Lemma E.3. Given a balanced instance of the online allocation problem with MaxMin objective and O, there exists set of parameters
d -
(d)
ds
RENET
such that the fractional solution defined by the exponential assignment scheme with parameters - is (1 aaprrxxtiioiiiio to the optimal objective.
As in the MinMax objective, we define a slightly perturbed convex program (see Figure 2). L to denote the optimal MinMax value, and define the following convex program for >> 0:
We use
min
Σ mu(
E
Iek In
Jitk
rE/27
REK())
s.t.
Vitk Tikk 2 L ()-
Vi E [d].
(E|T)AKKI
Σ kEK())
1,
VI E [7],
.Ttk 2 0, Figure 2: Convex Programming Formulation for the MaxMin Objective
Vk E K(t,, t E [T]
Lemma E.4. Given an instance of the online allocation problem with the MaxMin objective and any 2 O, there exists a vector (t E Rd such that the fractional solution defined by the exponential assignment scheme with parameters (t) (1 - ---))((()pppoiiiii
optimal.
Proof. Given such instance and for fixed consider the convex program of Figure 2 assumption, L is the optimal MaxMin objective therefore there exists feasible solution for the convex program for any 0. Accordingly, define the Lagrangian L(x, a, 3) as
By
(v)v)
Σ Tek In (()(()
Σ
anl (L-(e Σ
Catk
+
Σ 3,(1- [E[2]
Σ Tek). kEK())
KE[T]
#E|d
LE[T] (E
From the KKT conditions for the optimal solution the convex program as function of
(1), 300)) the solution that allocates according to (()) is (1 + approximaaii to the optimal
objective L", and a;
(c) 2 0 for all i E [d]. Furthermore,
dLL for all E K(),, which gives m,(v) In(x - mi(v) Σ a Uick = 1((0)
dr
For any options k,r E (t),, obtain:
mv( In(xx(e) (e)
Σ
Uus = mi(v) In(x (e)
Σ (c) Mar-
Therefore, In
tk
my(v)
Witk
m, (v)
Pite
Coupled with
Σ ke
Lth
[c)
= 1, we get
(c) Fik
Σ
Witk my (v)
x exp
Bounding the Learned Parameters. the MinMax objective, we bound the learned parameters using perturbation and sensitivity analysis techniques.

---

Lemma E.5, Let ael0,aa0, ,,00)())) be the optimal solution to the convex program in Figure 1 for some O. Then, for all i [d], holds that og log
Proof. We define perturbed convex program based on Figure where us corresponds to the constraint at-
For each E [d]. setting i, = -c L and uy for ensures that constraint i the perturbed problem matches the original constraint, thereby guaranteeing feasible solution. By Lemma B.1
00, 2 p" (u, a e- L", which implies
d (7)
I, 500 (0,0) v), v
Σ ma(e) In [())) S d L log
tE[T]
where the second inequality follows from Claim 4.7 and the third inequality by E, mx(v) S d - and log [()) < log (
Finally, we now put all the pieces together to establish Lemma
Proof of Lemma E.3 Fix a balanced instance [v,, K) and >> 0. By Lemma E.5 there exists
parameter vector (1)) such that
0, d log (5) for all i E [d]. Therefore, there exists
vector à NET E log
such that (á; ag S - for all i E [d]. By Lemma 4.8 the exponential assignment rule with ā achieves a (1+ approxxappo.......n.....
(
F Generalization to Well-Behaved function
We now complete the proof of Theorem
Proof of Theorem 4.7
Fix an objective function f and an instance [(v, KV) ) Let é! denote the load in the ith dimension in optimal solution for objective function f. Also, let z denote the fraction at step assigned to option in this optimal solution.
Now, consider the instance I(ū, K), where Üick Susk of
By the monotonicity property of f. the
optimal objective value for is 1. Therefore, by Lemma 4.4 there exists à such that using an allocation, we get ea (ī, a:) 2 for maximization and t- (I,a) < 1 + for minimization.
By the definition of the allocation, ...x& proportional
exp Σ Uge.k ā; exp - ViLkk
Thus, if we define such that a de then the corresponding allocation gives approxiiae 2.
solution for maximization and a (1 + -)approoxee solution for minimization.
30


Reviews:
[{"review_id": "CUQzZcZ22N", "reviewer": "Reviewer_cbL3", "summary": "The paper studies a general framework to solve online allocation problems via convex programming in the algorithms-with-predictions  model.  In the online algorithms with predictions framework, the goal is to leverage machine-learned predictions to make improved decisions when dealing with an online problem.  The goal is to achieve a better competitive ratio compared to a worst-case algorithm without any predictions.  The paper uses this model to provide an algorithm for a general online optimization problem such as online routing in which the algorithm is provided a prediction vector \\alpha (with one parameter per edge) and goal is the minimize a global objective such as minimizing the max congestion one each edge.   Without predictions,  the best known competitive ratio for algorithms covered in this framework is logarithmic in the size of the input and the proposed learning-augmented algorithm achieves a (1+/- \\eps) competitive ratio under prefect predictions.  To achieve robustness with respect to prediction errors, they propose a modified algorithm that essential reverts to the worst-case algorithm if the error accumulates.\n\nTheir framework, algorithm and results follow closely that of Cohen and Panigrahi [17] and generalize it to handle inputs that are vectors and use it solve problems that are not covered by [17] such as routing and fair allocation.\n\n\nMinor typos:\nLine 46 typo:  is logarithmic in the \"number of size\" of the the network [2]", "questions": "All my questions are about my only concern:  identifying the overlap with past work: citation [17] in the paper.  The following questions are trying to get more details about this.\n\n1. What is the difference between the PAC learnability proof (Theorem 2.2) from the learnability bounds in [17]?\n2. What is the main technical difference between the problems that cannot be handled by the framework in [17] vs the current paper?  The description that [17] cannot handle general vector needs explanation:  one way to interpret the divisible weights p_{i, j} in [17] is to view it as a d-dimensional vector (one per agent) that is received each time an item j appears.  \n3.  On line 177, the paper says in comparison to [17] \"we simplify the previous approaches as well by requiring only a single variable per dimension\":   it appears that [17] also requires one learned-parameter per dimension d so this needs further clarification. \n4.  Is the fair allocation problem with Nash Social welfare objective already covered by the framework in [17]?  What does \"matching previous results in [17]\" mean on line 154 in the paper.\n\nI am willing to raise my score to accept if this overlap is sufficiently addressed by the authors clarifying the new insights/contributions provided by this paper over [17].", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths: \n-  The paper provides a way to solve general online convex optimization problems in the algorithms-with-predictions model.\n-  Applying their general framework to online nash social welfare with predictions improves upon the prior best-known competitive ratio from logarithmic to (1+/eps).\n-  They provide the first learning-augmented algorithm for the online routing problem which is a fundamental optimization problem \n-  The paper shows that the predictions are PAC learnable, as well as provide new techniques such as perturbation analysis which are of independent interest to the community.\n\nWeakness:\n - The main weakness of the paper is that it does adequately address the overlap with prior work Cohen and Panigrahi [17] in the current write up.  The framework and algorithm borrow significantly from [17] and the new ideas and insights are not clearly addressed.   See questions below.", "was_revised": true, "final_justification": "I am raising my score as the authors response adequately address my questions and concerns.", "rebuttal": "We are glad that the reviewer liked the paper and appreciate the insightful comments. Below, we address each question in detail and conclude with a concise summary of the main differences between our work and [17] as requested by the reviewer.\n\n*Q: What is the difference between the PAC learnability proof (Theorem 2.2) from the learnability bounds in [17]?*\n\nBoth works establish PAC learnability by restricting to a finite hypothesis class and applying standard finite‑class generalization bounds. The crux in both settings is to bound the parameter space. In prior work [17, 22, 25], a simple rescaling of the learned parameters yields an equivalent (or near‑equivalent) allocation, so one can cap parameter magnitudes with only a negligible loss. In our vector setting, this rescaling trick fails. Instead, we bound the parameters via a max‑entropy dual and a coordinate‑wise sensitivity analysis.\n\n*Q: What is the main technical difference between the problems that cannot be handled by the framework in [17] vs the current paper? The description that [17] cannot handle general vector needs explanation: one way to interpret the divisible weights p_{i, j} in [17] is to view it as a d-dimensional vector (one per agent) that is received each time an item j appears.*\n\nIn [17], for each arriving item $j$, each option assigns it to a single agent $i$ with value/cost $p_{i,j}$. Our paper is more general. Here, for each arriving item $j$, each option $k$ corresponds to an entire vector $v_{j,k}\\in\\mathbb{R}^d_{\\ge 0}$ that adds value/cost for multiple agents simultaneously. This captures coupled, multi‑coordinate effects within a single choice. So, [17] is a special case of our setting where each vector has a single non-zero entry. In comparison, we allow “general vectors”.\nSuch a coupled choice is necessary in applications like online routing. Here, each option is a path which adds load on each edge of the path. This can be modeled in our framework by encoding edges as coordinates. For example, suppose there are three edges $e_1,e_2,e_3$ and the feasible path vectors (i.e., the options) are $v_1=(1,1,0)$ and $v_2=(0,0,1)$. (So, one path comprises the first two edges and the second path comprises only the third edge.) Our model can choose between $v_1, v_2$ or a convex combination of these two options. For instance, if one chooses fraction $\\tau$ for the first option and fraction $1-\\tau$ for the second option, then the load on the edges increases by $(\\tau,\\tau,1-\\tau)$. The model in [17] can only capture the situation where every path is a single edge. If a path has multiple edges, then the options correspond to vectors with multiple non-zero entries, which cannot be captured by the model in [17]. \nIn terms of techniques, [17] uses a form of proportional allocation. Unfortunately, proportional allocation cannot handle coupled, multi-coordinate effects due to general vectors in our setting.\n\n*Q: On line 177, the paper says in comparison to [17] \"we simplify the previous approaches as well by requiring only a single variable per dimension\": it appears that [17] also requires one learned-parameter per dimension d so this needs further clarification.*\n\nIn our framework, there is a single learned vector over resource coordinates which is also there in [17], but we do not have any global exponent or auxiliary scaling vector which are both present in [17].\n\n*Q: Is the fair allocation problem with Nash Social welfare objective already covered by the framework in [17]? What does \"matching previous results in [17]\" mean on line 154 in the paper.*\n\n[17] provides a near‑optimal fractional guarantee for online Nash Social Welfare (NSW) where every option allocates the item to a single agent and adds value to the agent. Our result matches the bounds for this case, but we also generalize it further to options having vector utilities, i.e.,  where an option can add (possibly different amounts of) value to multiple agents simultaneously. In other words, choosing an option adds a utility vector to the agents. This coupled, multi‑beneficiary setting is captured by our vector framework but is not handled in [17]. We will clarify this in the paper.\n\n\nIn summary, the following are the key differences between our paper and [17]:\n\n1. Scope of the model: [17] is an assignment model in which each item has to be split across agents; our framework handles general vector options that update many coordinates jointly, enabling coupled applications such as online routing and vector‑utility NSW that [17] does not encode. \n\n2. Parameterization: We use a single learned vector over resource coordinates without any auxiliary global exponent or per‑agent scaling, both of the latter being present in [17]. \n\n3. Techniques: The rescaling trick used in [17, 22, 25] does not work for vectors; we instead derive parameters from a max‑entropy dual with a coordinate‑wise sensitivity bound giving an explicit box $0 \\le \\alpha_i \\le \\tfrac{d^2}{\\varepsilon}\\log(d/\\varepsilon)$, which yields a robust finite net and PAC guarantees. Indeed, the connection that we draw to the max-entropy convex program and the subsequent use of convex programming duality is a novel contribution that we believe does not appear in this line of work prior to our paper.\n\nTo highlight these differences, we will add a focused comparison paragraph and a routing example to make the distinction clear."}, {"review_id": "eX0TT3nAaH", "reviewer": "Reviewer_e2Ps", "summary": "This paper develops a unified learning-augmented framework for online allocation problems. The key contribution shows that a single learned parameter vector α enables an exponential assignment rule achieving (1±ε)-approximations for well-behaved objectives (routing, scheduling, fair allocation). Using convex programming duality and perturbation analysis, the authors prove existence of bounded, learnable parameters.", "questions": "Can you 1.provide concrete examples where fractional solutions are directly applicable without rounding? The paper's main guarantees are for fractional solutions, yet most applications (routing, scheduling) require integral decisions.\n\n2.The three-step preprocessing appears quite aggressive, potentially changing the instance structure significantly. For example, provide an example where the algorithm fails without preprocessing? Also, it's helpful to quantify how much the preprocessing changes typical instances (what fraction of options are removed in Step 2)?\n\n3.Provide the explicit algorithm for learning α from samples?", "limitations": "The authors partially address limitations throughout the paper but would benefit from a dedicated \"Limitations\" section consolidating:\n\nKey restrictions: Fractional solutions only, required preprocessing that alters problem structure, i.i.d. assumption, and limitation to monotone/homogeneous objectives\n\nPractical applicability gap: The theoretical unification is elegant but preprocessing and fractional nature limit direct deployment. The \"learning\" aspect is somewhat misleading—it's really about proving good fixed parameters exist rather than adaptive learning.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\nUsing convex duality to derive the exponential assignment rule from KKT conditions provides good theoretical grounding. The perturbation analysis showing dual variables can be bounded and discretized to poly(d,1/ε) is also well-executed. \n\nWeakness: \nThe convex program requires knowing the entire instance, making the \"learning\" aspect somewhat artificial. The paper solves fractional problems, with integral solutions in the appendix. The (1±ε) guarantees are relative to fractional problems, not integral ones. There seems to be a mismatch of what the paper claims to contribute. The three-step balanced instance transformation also requires better motivation. It is essential to bound the exponential terms but deviate from reality it claims to model.", "was_revised": true, "final_justification": "Issues Resolved:\nPreprocessing misunderstanding: Clarified as algorithmic technique, not input restriction; guarantees apply to original instances\nFractional solutions: Provided compelling real-world applications (SDN, load balancing, ad pacing)\nLearning framework: Distinguished analysis tool (convex program) from actual algorithm (ERM)", "rebuttal": "We thank the reviewer for their careful reading of our manuscript and for the insightful feedback. Below, we address each question and weakness raised by the reviewer in detail.\n\n*Q: Can you provide concrete examples where fractional solutions are directly applicable without rounding? The paper's main guarantees are for fractional solutions, yet most applications (routing, scheduling) require integral decisions.*\n\nWe give examples of applications where fractional solutions are directly applicable:\n\n- Traffic engineering / SDN: requests (or flows) are commonly split across multiple paths; fractional solutions translate directly to per‑path splitting ratios, see e.g.,\n\n*Salimifard, K., & Bigharaz, S. (2022). The multicommodity network flow problem: state of the art classification, applications, and solution methods.*\n\n*Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., & Naor, J. (2006). A general approach to online network optimization problems. ACM Transactions on Algorithms.*\n\n - Cloud and datacenter load balancing: tasks/data shards are shared across machines or queues using probabilistic routing; fractional rates are implemented by hashing or randomized assignment, see e.g., [17], [23].\n\n - Online advertising / budget pacing: budgets are split fractionally across channels/segments; the objective is smooth (Nash welfare or $\\ell_p$) over aggregate spends, see e.g., [24]  and \n\n*Buchbinder, N., Jain, K., & Naor, J. (2007). Online primal-dual algorithms for maximizing ad-auctions revenue. In European Symposium on Algorithms.*\n\nMoreover, there has been prior work on learning-augmented algorithms that obtain fractional solutions, see e.g., \n\n*Anand, K., Ge, R., Kumar, A., & Panigrahi, D. (2022). Online algorithms with multiple predictions. In International Conference on Machine Learning.*\n\n\n*W: The paper solves fractional problems, with integral solutions in the appendix. The (1±ε) guarantees are relative to fractional problems, not integral ones.*\n\nWe have already discussed applications where fractional solutions can be directly applied. For applications that require integral solutions, we provide a rounding algorithm in Appendix D. We emphasize that after rounding, we get a $(1\\pm \\varepsilon)$ approximation for integral solutions as well under the standard small items assumption. In real systems, “small items” are typical or can be enforced through light batching. The atomic units—packets or flowlets in networks, requests or shards in services, impressions in online advertising—each have negligible impact relative to total capacity. Consequently, traffic or budget is already split across options at fine granularity. In practice, operators also aggregate decisions over short time windows to smooth variability; this keeps each step small enough that averages remain stable, sampling‑based learning is reliable, and randomized implementations (hashing, probabilistic routing, paced spending) track their targets closely. If a light tail of large items exists, those few can be handled explicitly—either by reserving capacity or by routing them individually—while the vast majority stay small, preserving both learnability and concentration guarantees.\n\n*Q: The three-step preprocessing appears quite aggressive, potentially changing the instance structure significantly. For example, provide an example where the algorithm fails without preprocessing? Also, it's helpful to quantify how much the preprocessing changes typical instances (what fraction of options are removed in Step 2)?*\n\n*W: There seems to be a mismatch of what the paper claims to contribute. The three-step balanced instance transformation also requires better motivation. It is essential to bound the exponential terms but deviate from reality it claims to model.*\n\nWe believe there is a misunderstanding of the result. We emphasize that our algorithm applies to all instances and not just balanced instances. The preprocessing that converts a general instance to a balanced instance is a part of our overall online algorithm. Conceptually, it removes options that should not be considered by the allocation. Subsequently, the algorithm for balanced instances is applied to the transformed instance and this constitutes the final solution for the original instance. Once again, we emphasize that the conversion to balanced instances is an algorithmic technique and not a restriction on the input, and the final solution and bounds are for the original instance, not the transformed (balanced) instance.\n\nIn fact, this idea of preprocessing is also used in prior work such as [25]. To see why this is necessary, consider an instance of a makespan minimization problem where one option has $p_{i_1,j}=1$ and $p_{i_2,j}\\to\\infty$. Then, without preprocessing, we must have $\\alpha_{i_1}/\\alpha_{i_2}\\to\\infty$, making the parameter space unbounded.\n\n*Q: Provide the explicit algorithm for learning α from samples?*\n\nIn the appendix (lines 591–594), we present the learning algorithm: an ERM procedure that outputs the parameter values on the discrete net with minimum empirical loss.\n\n*W: The convex program requires knowing the entire instance, making the \"learning\" aspect somewhat artificial.*\n\nFinally, the convex program is used in the analysis to establish the existence of suitable parameters and to derive tight, coordinate-wise sensitivity bounds. It is not part of the online algorithm, which simply applies a fixed exponential rule using a learned vector $\\alpha$. As shown in the paper, $\\alpha$ can be estimated from data via finite-class empirical risk minimization (ERM) over a bounded net constructed from the sensitivity bounds. So, the learning is via the use of ERM on data as usual, but learnability of the parameters and the fact that the learned parameters yield a near-optimal solution are established via the convex program."}, {"review_id": "YfEcf5gZZR", "reviewer": "Reviewer_ijy6", "summary": "This paper introduces a new, general framework for learning-augmented online allocation problems. Online allocation problems involve an algorithm making choices from a set of options at each step, which are represented as vectors, with the goal of minimizing or maximizing accumulated costs or rewards for a set of agents. This is represented by the value of an objective function on the sum of the vectors chosen at each step by the algorithm. Some problems that can be formalized in this way include machine scheduling, network routing (minimization), and fair allocation (maximization). \n\n\nThe proposed framework uses a single d-dimensional vector $\\alpha$ of learned weights to produce a nearly optimal solution using an exponential assignment rule. The main result achieves a (1+$\\epsilon$)-approximation for minimization or (1−$\\epsilon$)-approximation for maximization for any $\\epsilon>0$.  To that end, It leverages convex programming duality and a preprocessing step to convert the instance to a so-called “balanced” one. The authors also provide a modified algorithm to achieve a trade-off between consistency (performance with accurate predictions) and robustness (worst-case guarantees with unreliable predictions). The paper finally demonstrates the applicability of this framework to various problems in routing, scheduling, and fair allocation including online routing and online Nash Social Welfare maximization. \n\n\nMinor comments: \nI would suggest adding the relevant references to the first paragraph (e.g lines 24-25) of the introduction for clarity.", "questions": "1. Can you be more precise on the consistency robustness trade-off? Specifically, how is the confidence parameter $\\lambda$ chosen and what is the dependence on the error of the learned parameter vector?  Is there an adaptive mechanism to set the confidence parameter dynamically based on the perceived accuracy of predictions, rather than a fixed value?\n\n2. Could the convex programming formulation be adapted to handle different types of constraints or other settings beyond allocation problems?\n\n3. For problems requiring integral solutions, how significant is the \"small items assumption\" in practice, and what are the implications if it doesn't hold perfectly?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper's main strength is its development of a general learning-augmented algorithmic framework for online allocation problems, which can be widely applicable. The results leverage machine learned predictions to achieve almost optimal allocations with no prediction error while being robust to prediction error as well. In terms of techniques, the novel application of convex programming duality could also influence future research in the field. On the other hand, I would like to see more justification for the “small items assumption”, which is required both for learnability of the predictions and the rounding of the fractional solutions.", "was_revised": true, "final_justification": "The authors have answered my question in a satisfactory way. Therefore, I am keeping my recommendation for acceptance.", "rebuttal": "We are glad the reviewer liked the paper and appreciate the insightful comments. Below, we address each question in detail.\n\n*Q: Can you be more precise on the consistency robustness trade-off? Specifically, how is the confidence parameter $\\lambda$ chosen and what is the dependence on the error of the learned parameter vector? Is there an adaptive mechanism to set the confidence parameter dynamically based on the perceived accuracy of predictions, rather than a fixed value?*\n\nThe use of a confidence parameter follows standard practice in learning-augmented algorithms, see e.g. [11], [31], and other papers such as \n\n*Gollapudi, S., & Panigrahi, D. (2019). Online algorithms for rent-or-buy with expert advice. ICML 2019.*\n\nAs in prior work, the confidence parameter is application-dependent and typically tuned from data—for example, based on the number of prior samples or the discrepancy between predicted and actual performance on a validation window. It balances consistency (staying close to the learned policy) with robustness (falling back to a worst-case baseline). Fully automatic, near-optimal tuning is precluded by lower bounds without further assumptions. In practice, adaptive schemes work well: by tracking prediction error over time, the confidence level can be adjusted dynamically.\n\n*Q: Could the convex programming formulation be adapted to handle different types of constraints or other settings beyond allocation problems?*\n\nYes, we believe our techniques can extend to broader classes of problems. Our max‑entropy template should extend cleanly to additional linear side constraints, and with appropriate smoothing or convex conjugates it may also handle certain separable concave terms (e.g., diminishing‑returns utilities). Formal guarantees would need a careful re‑derivation of the dual sensitivity bounds, so this is a good follow‑up direction for future work.\n\n\n*W: On the other hand, I would like to see more justification for the “small items assumption”, which is required both for learnability of the predictions and the rounding of the fractional solutions.*\n\n*Q: For problems requiring integral solutions, how significant is the \"small items assumption\" in practice, and what are the implications if it doesn't hold perfectly?*\n\nIn real systems, “small items” are the norm or can be achieved with light batching. The atomic units—packets or flowlets in networks, requests or shards in services, impressions in online advertising—individually have small impact relative to total capacity. So, splitting traffic or budget across options already operates at fine granularity. Operators also aggregate over short time windows to smooth variability; this makes each decision step small enough that averages are stable, learning from samples is reliable, and randomized implementation (hashing, probabilistic routing, paced spending) stays close to targets. \n\nIf the small items assumption doesn't hold perfectly, then the approximation factor of our algorithm degrades gracefully with increase in size of the largest item. Furthermore, when there’s a light tail of large items, those few can be handled separately, e.g. by reserving capacity, while the vast majority remain small, preserving both learnability and concentration in practice.\n\nIndeed, the small items assumption is quite standard in the literature for allocation problems, see e.g.,\n\n*Mehta, A., Saberi, A., Vazirani, U., & Vazirani, V. (2007). Adwords and generalized online matching. Journal of the ACM.*\n\n*Devanur, N. R. & Hayes, T. P. (2009). The adwords problem: online keyword matching with budgeted bidders under random permutations. EC 2009.*\n\n*Gollapudi, S., & Panigrahi, D. (2014). Fair Allocation in Online Markets. CIKM 2014.*\n\n*Agrawal, S., & Devanur, N. R. (2014). Fast algorithms for online stochastic convex programming. SODA 2014.*"}, {"review_id": "fnF3APjW5p", "reviewer": "Reviewer_NQoi", "summary": "The paper considers the online resource allocation problem, where the objective is to maximize the cumulative reward of an allocation strategy, with each allocation yielding a corresponding reward. The focus is on learning-augmented algorithms, where machine learning is used to predict future inputs, and these predictions are incorporated into the algorithmic design. The paper analyzes the problem within a unified framework by considering the existence of learnable parameters and strategies that can achieve a $1 + O(\\epsilon)$ approximation. It also examines the sensitivity and robustness of the algorithms under small perturbations to the input or predictions. The paper highlights two specific applications—online routing and Nash social welfare—and presents corollaries of the main theoretical results in these contexts.", "questions": "Please see the above weakness section.", "limitations": "NA", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength \n\n- The technical results are new, especially the construction of the balanced instance,\n\n- The paper considers a relatively general class of online resource allocation problem, and shows a unified framework of learning-augmented online algorithms, by characterizing the approximation ratio. \n\n- The paper also conducts the sensitivity analysis by considering the perturbation. \n\nWeakness\n\n- The paper could benefit from another round of polishing and it current form at is less ready for publication, since the current structure is a bit hard to follow with respect to the logic connections. For example, the introduction part focuses on heavily on the applications, but the applications mentioned in Section 5 do not match these applications exactly. One can get easily lost in the last two paragraphs before the Organization in Introduction. These two paragraphs do not help introducing this paper and its main theme. Also, merging the problem formulation with the contributions is somewhat confusing. Having a separate section of the problem formulation would make things clearer. \n\n- The proof of Lemma 4.4 is missing, or I may miss something. It would be helpful if the authors could point to the place. \n\n- MaxMin and MinMax are not defined with mathematic rigor. \n\n- I assume that the balanced instance is $\\tilde{I}$ instead of $I$ in the statements of the theorems. \n\n- The paper seems to over claim the contributions in the introduction, since essentially the results hold for balanced instances, instead of all the instances in the online resource allocation problems. It would be helpful to clarify these, to avoid ambiguity. \n\n- the concept of agents do not seem to appear in the general problem formulation. This necessitates further clarifications.", "was_revised": true, "final_justification": "I believe that the writing of the paper could benefit from substantial changes/rewriting, as the current version is not easy to follow and the necessary modifications remain unclear based on the current rebuttal. So I would recommend borderline reject, given that we would like the publications to be clear enough to the community, and to the audience.", "rebuttal": "We thank the reviewer for the careful review. Below, we address each question in detail.\n\n*Q: The paper could benefit from another round of polishing and it current form at is less ready for publication, since the current structure is a bit hard to follow with respect to the logic connections. For example, the introduction part focuses on heavily on the applications, but the applications mentioned in Section 5 do not match these applications exactly. One can get easily lost in the last two paragraphs before the Organization in Introduction. These two paragraphs do not help introducing this paper and its main theme. Also, merging the problem formulation with the contributions is somewhat confusing. Having a separate section of the problem formulation would make things clearer.*\n\nThe last two paragraphs before the organization in the introduction are integral to the paper. \n\nThe penultimate paragraph motivates the maximization problems (MaxMin, Nash Social Welfare, $p$‑means, etc.): it explains the “value to agents” viewpoint and asserts that our vector framework yields $(1-\\varepsilon)$ guarantees there, contrasting with strong lower bounds without learning. This constitutes one half of the results in this paper, complementing the results for the minimization problems. Due to space limitations, the maximization proofs are in Appendix F. One of the two applications in Section 5, Nash Social Welfare, falls in the maximization category.\n\nThe final paragraph describes the learnability core: we prove the existence of bounded, robust parameters—scaling with the number of coordinates and $\\varepsilon$—and use this to obtain PAC learnability and stability to small estimation noise. Again, these are key contributions of the paper. The detailed proofs for learnability are in Appendix C.\n\n*Q: The proof of Lemma 4.4 is missing, or I may miss something. It would be helpful if the authors could point to the place.*\n\nAfter the statement of Lemma 4.4, the entire remaining part of Section 4 is dedicated to the proof of Lemma 4.4. The sentence “The remainder of this section gives a proof of Lemma 4.4” opens a proof sketch, and the proof is concluded at the end of the section (bottom of page 8, lines 311–314).\n\n*Q: MaxMin and MinMax are not defined with mathematic rigor.*\n\nMaxMin and MinMax are formally defined in lines 211–214. MinMax is the minimization of $f(v)=\\max_{i\\in[d]} v_i$, and MaxMin is the maximization of $f(v)=\\min_{i\\in[d]} v_i$.\n\n*Q: I assume that the balanced instance is $\\tilde{I}$ instead of $I$ in the statements of the theorems.*\n\nWe use the notation $I(\\tilde{v},\\tilde{k})$ for the transformed (balanced) instance, i.e., it is the instance with inputs $\\tilde{v},\\tilde{k}$.\n\n*Q: The paper seems to over claim the contributions in the introduction, since essentially the results hold for balanced instances, instead of all the instances in the online resource allocation problems. It would be helpful to clarify these, to avoid ambiguity.*\n\nWe believe there is a misunderstanding of the result. We emphasize that our algorithm applies to all instances and not just balanced instances. The preprocessing that converts a general instance to a balanced instance is a part of our overall online algorithm. Conceptually, it removes options that should not be considered by the allocation. Subsequently, the algorithm for balanced instances is applied to the transformed instance and this constitutes the final solution for the original instance. Once again, we emphasize that the conversion to balanced instances is an algorithmic technique and not a restriction on the input, and the final solution and bounds are for the original instance, not the transformed (balanced) instance.\n\nIn fact, this idea of preprocessing is also used in prior work such as [25]. To see why this is necessary, consider an instance of a makespan minimization problem where one option has $p_{i_1,j}=1$ and $p_{i_2,j}\\to\\infty$. Then, without preprocessing, we must have $\\alpha_{i_1}/\\alpha_{i_2}\\to\\infty$, making the parameter space unbounded.\n\n*Q: the concept of agents do not seem to appear in the general problem formulation. This necessitates further clarifications.*\n\nOur general formulation is stated in terms of resource coordinates. The familiar notion of agents is simply a special case: in maximization or fairness settings (e.g., Nash social welfare) we identify each coordinate with one agent, so the cumulative value of coordinate $i$ is exactly agent $i$’s utility. We already introduce this agent view in the Introduction and use it again in Section 5; in the revision we will add a brief sentence in the formal problem‑formulation section to make this mapping explicit and avoid any ambiguity."}]

Author rebuttal:

Meta-review: The submitted paper introduces a learning-augmented algorithmic framework for online allocation problems, aiming to achieve near-optimal solutions using a single-dimensional vector of learned weights. The framework applies to a wide range of combinatorial optimization problems, including routing, scheduling, and fair allocation for welfare maximization. The approach leverages convex programming duality as a key tool.

**Strengths**
* Novelty: The paper provides a way to solve general online convex optimization problems in the algorithms-with-predictions model. Applying their general framework to online Nash social welfare with predictions improves upon the prior best-known competitive ratio from logarithmic to (1+/eps).
* Practical applicability and relevance: The framework is applicable to a wide range of relevant problems, including routing, scheduling, and fair allocation, with real-world examples provided for fractional solutions (e.g., traffic engineering, cloud load balancing, and online advertising).
* Robustness and consistency: The proposed algorithm achieves a trade-off between robustness (worst-case guarantees) and consistency (performance under accurate predictions).


**Weaknesses**
* Clarity and presentation: Several reviewers noted that the paper's structure and writing could be improved. The introduction, in particular, was criticized for being hard to follow, with some sections lacking clear connections. Also the necessity of preprocessing to handle balanced instances was initially misunderstood as a restriction on the input, which could have been better explained in the main text.
* Overlap with prior work: While the authors clarified the distinctions from Cohen and Panigrahi [17], the initial write-up did not sufficiently highlight these differences, leading to confusion among reviewers. This distinction must be made clear in a revised version of the paper.
* Assumptions: The "small items assumption" for obtaining integral solutions was questioned, though the authors provided satisfactory justifications in the rebuttal (which should be added to the final paper).

**Discussion**
The following key points were discussed:
* Overlap with [17]: The authors clarified that their framework generalizes [17] by handling vector-based inputs and coupled effects, which are essential for applications like online routing. They also highlighted novel techniques, such as the use of max-entropy duals and coordinate-wise sensitivity analysis.
* Fractional vs. integral solutions: The authors provided real-world examples where fractional solutions are directly applicable and explained how integral solutions can be obtained with a small approximation loss under standard assumptions.
* Clarity Improvements: The authors committed to revising the paper to improve clarity, including restructuring the introduction and explicitly defining key concepts like agents and balanced instances.

**Recommendation**
While the paper has some weaknesses in presentation and clarity (which can be easily resolved), its technical contributions were unanimously appreciated by the reviewers. The authors have also addressed most of the other reviewers’ concerns convincingly. The framework's generality, theoretical rigor, and practical relevance make it a valuable contribution to the field. Hence, in line with the clear majority of the reviewers, I am recommending the acceptance of the paper.
Decision: Accept (poster)