Fast Algorithms for Packing Proportional Fairness and its Dual
Authors: Francisco Criado
David Martínez-Rubio
Sebastian Pokutta
Venue: NeurIPS 2022 Accept (2022)
Keywords: proportional fairness
packing constraints
acceleration
width-independence

Abstract: The proportional fair resource allocation problem is a major problem studied in flow control of networks, operations research, and economic theory, where it has found numerous applications. This problem, defined as the constrained maximization of $\sum_i \log x_i$, is known as the packing proportional fairness problem when the feasible set is defined by positive linear constraints and $x \in \mathbb{R}_{\geq 0}^n$. In this work, we present a distributed accelerated first-order method for this problem which improves upon previous approaches. We also design an algorithm for the optimization of its dual problem. Both algorithms are width-independent.

Fast Algorithms for Packing Proportional Fairness and its Dual
Francisco Criado
David Martinez-Rubio" Zuse Institute Berlin and TU Berlin Berlin, Germany
TU Berlin
Berlin, Germany
criado@mat aalaooomathhtttbbeeee. in.de
ma nez
Sebastian Pokutta
Zuse Institute Berlin and TU Berlin
Berlin, Germany vokutta@zib...
Abstract
The proportional fair resource allocation problem is a major problem studied in flow control of networks, operations research, and economic theory, where has found numerous applications. This problem, defined as the constrained maximization of Σ, log T;, is known as the packing proportional fairness problem when the feasible set defined by positive linear constraints and R In this work, we present a distributed accelerated first-order method for this problem which improves upon previous approaches. We also design an algorithm for the optimization of its dual problem. Both algorithms are width-independent.
Introduction
The assignment of bounded resources to several agents under some notions of fairness is topic studied in networking, operations research, game theory, and economic theory. The allocation obtained by the maximization of the function E log(z;)) over convex set C R% known proportional fair allocation, is an important solution that arises under a natural set of fairness axioms [BFT11; La]+10]. It corresponds to Nash bargaining solutions [Nas50] and it also has applications to multi-resource allocation in compute clusters [BR15; JH18; Joe+ 12], rate control in networks [Ke197] linear objectives (no fairness), the
and game theory [JV 10; JV07]. Other important allocations max-min allocations [MW00]. or o--airr allocations [Atk70; MW00; McC+14), which generalize all of the others. Proportional fairness corresponds applications require, are positive linear constraints. This results in the packing proportional fairness problem, also known the 1-fair packing problem. The main focus of this paper on solving this problem and its dual via first-order methods. Given A E Mmxxn (Rx)) the 1-fair packing problem is
1. A natural restriction, that many of these
max R
f(x)
log Ax < 1.
(IFP)
We also study the optimization of its Lagrange dual, that can be formulated, cf. Lemma A. as
min X
a(A)
log( A A)x n log
(IFP-Dual)
Equul contribution. Most of the notations this work have a link to their definitions. For example, if you click or tap on any instance of you will jump to the place where it is defined as the i-th vector of the canonical base.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

where Am End (MERR Ex=1,>00 is the m-dimensional (probability) simplex. We focus on width-independent algorithms that additively s-approximate the optimum of those problems. For the 1-fair packing problem that means, respectively, that we can find ã in time that depends at most polylogarihmiicaly on the width p of the matrix A, and that it satisfies f f( S E, where f" is the optimal value. Note that (IFP) has unique optimizer, by strong, concavity. By the same reason, for every two minimizers '1 X2 of (IFP-Dual), we have A X1 = A X2. The width p of A is defined as max{A,;) // ( ). the maximum ratio of the non-zero entries of A. Note that in general width- setth-dependent& algorithmss are not polynomial. Smoothness and Lipschitz constants of the objectives do not scale volylogarithmicalyy with p and thus, direct application of classical first-order methods leads to non-polynomial algorithms. As in packing and covering LP, an approximate solution for our primal problem does not necessarily yield one for the dual problem, cf. [AK08], so we need study them separately. The current form of our techniques does not generalize to o-fair problems with * 1, but generalizing them to these settings is interesting future direction of research. We note that previous works treat in [0, 1), {1}. or (1, o0) separately, due to the structure of the problems being different. Most works dealing with a-fair functions assume, without loss of generality, that A is given so that the minimum non-zero entry of A is 1 and the maximum entry is p. However, in this work, we assume without loss of generality that
max [Aij] = 1, for all j E [n]. XX [m)]
(1)
We can do so because, for our problem, we rescale each primal coordinate multiplicatively. rescaling the columns of A accordingly, which only changes the objectives by an additive constant. Thus, the additive guarantees we will obtain are also satisfied in the non-scaled problem.
Our primal algorithm solves the problem in a distributed model of computation with v agents. Each agent j E [n] controls variable zy and only has access to global parameters like m, n, or the target accuracy E, to the j-th column of A, and in each round it receives the slack (Ar); - of all the constraints in which j participates. This is standard distributed model of computation. We refer to [KY14; AK08) for its motivation and applications.
Notations We let e; be the vector with 1 in coordinate i and O elsewhere. We denote by A, a row of A. For is N, we use the notation [k] duf {1.2....,kk k). Throughout this work, log(-) represents the natural logarithm. For e E R", the notation exp(v) means entrywise exponential. We use @ for the entrywise product. Given 1-strongly convex map rà, we denote its Bregman divergence by De(x, v) def Vab(a) - Veh(y) - (Ve((y) x - v). We denote by N the number of non-zero entries of the matrix A. The notation (-) hides logarithmic factors with respect to m, 1/c and p. But note that the rates of our algorithms do not depend on p.
Related Work Despite the importance and widespread applicability of fairness objectives, width- independent (and thus polynomial) algorithms for many a-fair packing problems were not developed until recently. -ntee--ndependentt algorithms were first designed for 0-fair packing, i.e., for packing linear programming (LP). that have a longer history [LN93]. For this problem there are currently nearly linear-time width-inddepndent iterative algorithms [AO19] and distributed algorithms [A015; DO17]. [MSZ16] studied the width-inddeendent optimization of a-fair packing problems for any E [0, oo] with stateless algorithm and [DFO20] gave better rates with non-stateless algorithm. Both works use the same distributed framework as ours. For the particular case of 1-fair packing, the latter work obtains an unaccelerated algorithm that runs in O(n"/e²) distributed iterations. [Bec+1 14] study the optimization of the dual problem by using Nesterov's 's accelerated method, and then they reconstruct primal solution. However, both primal and dual solutions depend on the smoothness constant of the dual problem, which in the worst case is proportional to p², and therefore it is not polynomial algorithm. In contrast, our algorithms do not depend on P at all. Obtaining a priori lower bounds each of the coordinates of the optimizer is of theoretical and practical interest, since it provides certain amount of resource that can be assigned to each agent before solving the problem. These were studied in [MSZ16] and were improved by [Al[+18]. In Lemma B.I, we show lower bound of this kind for our problem when it is normalized as in (1).
Contribution and Main Results Our contribution can be summarized as follows; See Table 1 for a comparison with previous works.
Accelerated algorithm for 1 1-fair packing. We design a distributed accelerated algorithm for 1-fair packing by generalizing and extending an accelerated technique, designed for packing LP, that

---

Table 1: Comparison of algorithms for 1-fair packing and its dual. The work of one iteration is linear
in N, the number of non-zero entries in A.
Paper
Problem
Iterations
Width-dependencee
[Bec+14]
Primal
Q
Yes
[MSZ16]
Primal
Oen O(n2/E²) Ö(n/s)
nearly No (polylog)
[DFO20]
Primal
nearly No (polylog)
This paper (Theorem 2.5)
Primal
No
[Bec+14]
Dual ((pymn/E)
Yes
This paper (Theorem 3.4)
Dual
0(n²/E)
No
uses truncated gradients of a regularized objective [AO19]. In contrast with this technique, ours yields an algorithm and guarantees that are deterministic. We exploit the structure of our problem to obtain a distributed solution, while for packing LP obtaining distributed or just parallel algorithm that is accelerated and width-independent an open question [DO17]. We make use of a different regularization and an analysis that yields additive error guarantees as opposed to multiplicative ones.
The dual problem. We consider the dual of the 1-fair packing problem. We reduce the problem to optimizing proxy function by using the Plotkin-Shmoys-Ture Tardos (PST) framework [PST95; AHK 12] with a novel geometric separation oracle. Critical to obtaining fast convergence is showing that the oracle parameters decrease when we obtain better solutions. This fact allows to reduce the dependence on E, and as a result, our width width- andth-independent algorithm enjoys a convergence rate of (nn//s) iterations for this problem.
2 A distributed accelerated algorithm for 1-Fair Packing
In this section, we present the main steps of our algorithm for the primal problem, which is deterministic accelerated descent method that optimizes an objective coming from the 1-fair packing problem, and that encodes the constraints in the form of a barrier. Our algorithm approximates the objective additively and allows to compute each iteration in a distributed manner. We note that [DFO20] also made use of this objective for the 1-fair packing problem with different constants, but as opposed to their solution, we allow to compute unfeasible solutions during the course of the algorithm, and we proceed with different techniques that allow to achieve acceleration and thus an algorithm with better convergence rates. We defer the proofs to Appendix B. We reparametrize Problem (IFP) so that the objective function is linear at the expense of making the constraints more complex. That is, we define the function ff R" + R, + f(exp(z)) = (In. The optimization problem becomes
(f()) (In,2): A Aexp(x) S 1m
max
RER
Then, we regularize the negative of the reparametrized objective by adding a fast- barrier:
fx(x) der - (11,,
(eex((z)) vzf((z) = -11+ Σ (Aex(())) an exp(zz),
where / Gn log(2mn /8) this way, we can work with an unconstrained minimization problem. The resulting function is not globally smooth but when the absolute value of a coordinate of the gradient is large, positive, and in that case we able take small gradient descent step and decrease the function considerably. The intuition is that if the gradient is large, then the function value along the segment of the gradient step, as function of the step, can decrease fast. But it cannot increase fast since there are no large negative gradient coordinates. We depict fr in Figure 1 in Appendix B. The barrier also allows to maintain almost feasibility, as we show Proposition 2.1 below. It is chosen to grow fast enough so that a point satisfying (A exp(x)); > + e/n, for some i [n], will have an optimality gap that is greater than the required accuracy. On the other hand, the regularizer is very small in the feasible region that is not too close to the boundary.
3

---

Figure 1: Regularized objective fr (left) and its gradient (right), for a sample matrix A E Max2(R2o). For visualization purposes we show log(f((x) and log( V (+)))l) represented by color, and we indicate the direction of the gradient with normalized arrows. Also, note that we show the results in the original space (i.e., before reparametrizing, so the constraints appear to be linear) but the gradient was computed as originally defined (i.e., after reparametrizing).
Let 8" be the maximizer of f, let x=' exp()*) be the solution to Problem (1FP), and let x; be the minimizer of fr. We have 5" E |- (og(n),0]' 0J" by Lemma B. Let w def log(mmn/(1 s/n)) and define the box B [-w,0] 0) We restrict ourselves to this domain and formulate our final problem, that we will minimize with accelerated method:
min f=()). B
(1FP-primalReg)
Note fx) 2 if x E B. We add the redundant and simple box constraints B in order to later guarantee a bound on the regret of the mirror descent method that runs within the algorithm. We show that it suffices to obtain e-minimizer of Problem (LFP- (LFP-primalRe) in order to obtain (E)) miiiiiieeee for the original Problem (IFP).
Proposition 2.1. [L] Lete (0, n/2). Let x,, be the minimizer of (IFP-primalReg) and let x B be an E-minimizer of this problem. Then the point ú exxp(xf)(1++))) (1++)/))) satisfies f(x*) - f(ū) S 5e and Au 1m where x² is the maximizer of f.
det
The intuition about this proposition is that of is also point with low f value. By the aforementioned barrier guarantees, is almost feasible, i.e., A exp(=:5) S 11+ s/n, and dividing the corresponding exp(x;) by 1 E/n, and thus making it feasible, can only increase the objective f by s.
In the sequel, we will present the different parts of Algorithm 1 and their analyses. In particular, the notation and definitions used are compatible with the choices in the algorithm and most of the parameter choices naturally occur throughout the arguments. Our optimization algorithm starts the points (D) (0) 20) log(mm/ - Ln, and updates each of these variables (k)), (k) and (k) once in each iteration. They remain in B, ef. Lemma B.2. The role of the three variables is the following: z() will be mirror point and y will be a gradient descent point, in the sense that in order compute them apply mirror descent and gradient descent. Then, the point (R) will be convex combination of both, that will balance the regret of (4k) with the primal progress of (k), effectively coupling these two algorithms.
It is important to note that we do not use the gradient fzx(x) ) for our mirror descent loss. Instead, we use a truncation of the gradient. More precisely, the loss we perform the mirror descent step on is the truncated gradient V (x) R defined as
(x)) der min(1, (x)) for all i E [m].
(3)
Note that (x)) E [-1, 1 because (fr(x) E oo] for any x E R", as the regularizer has positive gradient; also definition of fz) and its gradient. The truncation allows mirror descent

---

to control one part of the regret, which will not depend on the global Lipschitz constant. Gradient descent will compensate for both such regret and the part that not controlled by mirror descent.
lla-projection map of a point onto a convex set X. The mirror descent update can be written in closed form as any of the two following equivalent ways
Let (-) be the ||
((k) f 11
wry V (x))
(4)
(k) + 11 1| (k-1) Will V (z)a() for all i E [m].
That is, projecting back to the box, in case of the || ll2. consists of simply clipping each coordinate. We bound the regret coming from this mirror descent step by modifying the classical analysis of mirror descent, cf. Lemma B.3. Lemma 2.2 (Mirror Descent Guarantee). [1]] Let u E B and choose L as in Algorithm 1. We have:
(nk (8) 2(8-1)
1 12(1-11) - u112 - u) S L (8) ,, - (k)) + 2w
[1 - -l1
2w
Next, will analyze the role of the gradient descent step. We show in the following lemma lower bound on the progress of our descent step. Note that this progress could not be greater than fV (k) - ( by convexity, so this is a strong descent condition.
Lemma 2.3 (Descent Lemma). [4] Given (k) and yih) as defined in Algorithm I, the following holds:
1 - fx 2 2 (V))( - 2 0.
-y(0)
Algorithm 1 Accelerated descent method for 1-Fair Packing
Input: Matrix A E Mmxxn (Rzo)) normalized as in (1), Accuracy E E (0, n/2].
5 1: B + 6n 10 W + log( T-e/m ); L = max
man
(w((+
16n log (2m)) + $13 + Ö(m/E)
B
3e
2: fo < 3r; C2 = 3m L: T -- Tk = /r = 35.
3: T t [log( In log(3mm))) )/ log( (1-)1 S [3L in log(2mm)) )1 Ö(n/s)
4: x0) t (0)) + (0) t wl
5: for k = 1 to T do
6:
77 + C2 Cx11 I-r -- ---1
7:
x (1)) + Tz(1 + (1 -1-1 ---Tyy -)y
8:
2(h) - arg min EBB { 2 ||= -(k-1) + (14 (T((((()),
o Mirror descent step
9: (k) + (1)
+ We I.
_ (z(l))
2((111)
Gradient descent step
10: end for
II: return del exp(y (11++
Output: ((z) f(x)) S E and 5 feasible, i.e., Ar S 1. The total number of iterations is Öm//))
to obtain -aprrxxaaee solution.
2.1 Coupling Mirror Descent and Gradient Descent
We first prove a lemma that shows we can compensate for the regret coming from mirror descent as well as for the rest of the regret. Note the total weighted instantaneous regret (1) V (z())) (kh-1) (((-1)_u)) -u) bounded by the left hand side of (5) up to difference of potential functions, by Lemma 2.2. This a critical part of the analysis: using the truncated gradient for mirror descent makes its corresponding
regret not to depend on the smoothness constant, but there a remaining regret that, erucially, can be compensated by our strong descent condition.
Lemma 2.4. [1] Let C2 del 3n I,, and let (ik det ()((())))))) (+(((())) 10, For all u B,
we have
(2),()2((0010 u) + L (Z))) -k(()) S (c(()(((()) ())(()))))) (5)
5

---

With these tools at hand, we can now use linear coupling argument to establish an accelerated convergence rate. Note that the algorithm takes the simple form of iterating mirror descent step. gradient descent step and a coupling, after a careful choice of parameters. All of which depend on known quantities.
Theorem 2.5. [4] Let & S nn2 and let x² be the solution to (IFP) and let x. be the minimizer of (IFP-primalReg). Algorithm I computes point y E B such that fr(y(t) - fe(x,) S in number of iterations T ((n/)) Besides, det exp(y))))(1 + e/n) is a feasible point of (IFP),
i.e, Aø S Lm, such that f (x²) - f(ø) - 5==
3 Optimizing the dual problem
In this section, we reduce the dual problem (IFP-Dual) to the feasibility problem of packing LP, which we call the proxy problem. Then, we show how we can use the PST framework [PST95] to approximately solving the proxy. Our algorithm relies on a carefully built geometric oracle whose width parameters can be guaranteed to decrease with the optimality gap. We perform sequence of restarts, and after each of them we can guarantee lower oracle width. This allows for reducing the overall complexity.
3.1 The dual 1-fair packing problem as feasibility packing I.P
Let P def {xr Bo Ar S Im) be the feasible region of the primal problem (1FP). In this section, we identify (non-negative) covering constraints of the form (h, 2) S 1 with vector h R Recall we assume without loss of generality that A satisfies (1), that is, the maximum entry of each column 1. This implies that e; P for all i [m). and P [0, 1J". For this reason, we also assume in this section and without loss of generality that A contains the constraints {e: i.e., x; S 1, for i E [n]. For convenience, we assume they are the first rows of A.
Let Am be an optimal solution of Problem (IFP-Dual) and let h By strong duality of the Lagrange dual, we can reconstruct the optimal primal solution as x² = (1/(nh)") ),.n))")(mm)))) 3" j). This motivates the definition of the centroid map:
AT R
1 n/1 nh,
1)
chh
c
TLE
where h, x R are constraints and points, respectively. Despite the two maps above being the same function we distinguish between e and c- to unambiguously refer to constraints or points. The name of the centroid map is motivated by the fact that, for any constraint h E Rg the point c(h) the geometric centroid of the simplex {ar R8 (h, 1). Given À E m define its associated constraint h~ der AT X. In addition, define the centroid pd der c(AT>) c(h²). Note that we can efficiently compute h pd from X, and i from pd and viceversa. However, we cannot obtain the coefficients À efficiently from h or pA, as this amounts to solving a linear program.
An important property is that AA*' is the unique constraint the form h such that c(h>) E P. for some À E A Th is the optimizer because if h^* has c(h^*) ) E P, then (p^ x²) satisfies the optimality conditions. It is unique because of strong convexity of - llgg(-): any other dual optimizer X" will have ATX r = x" The following lemma shows an approximate version of this property.
Lemma 3.1. [4] Let h for À A", such that Ap < (1 + =) Let X be the minimizer of Problem (IFP-Dual), of objective function Then, g( - g(>*) S n log(1 (1 + e) I ne.
This lemma motivates the minimization of max (A, a( x)) for À E A A
a proxy for solving Problem (1FP-Dual). Furthermore, if we optimize over the set {p^ cf c(A²))) X A"), we end up with a feasibility problem in a packing LP. However, this set not convex in general, which is requirement of the PST framework over a larger and convex set while preserving the minimizer. Indeed, define the sets of constraints conv( ( (A1..... And) and D def (AT) / 2 0 À E Am / R50) = (h E R h < A², for A E D). For a constraint h E Rzu. we have by polyhedral duality that h E D if and only if x) < 1 for all x P. In other words, D is exactly the set
intend
Fortunately,
optimize
D def {ATX= A E Am)

---

c(D+)
D D
D
(() S c(D7)
P
Figure 2: Left, the dual polytope D containing D. The centroid c(-) maps dual points (i.e., constraints) to primal points. Right, P and the image of D and D via c. Note c(D+) n exactly one point, which is also contained in c(D). And note c(D) can be non-convex, but e(D+) is convex.
of positive constraints (h,x) < 1 with E R that are feasible for P. We can think about the optimization of Problem (IFP-Dual)
min {- Σ log(h²)) n log(n)} ED
min {- logog(h) log(h:) log(n)). MED+
1=1
2=1
where ! comes from the following observation: since D if and only if there is h with S A,,, and the expression Σ log(h;) - n log(n) is strietly decreasing in every h then no D D could ever minimize the right hand side. Consequently, the minimizer of both problems is the same. This results in the following proxy, motivated by Lemma 3.1:
pEc(D+) {o(p) def max ( (As,p)
min
(1FPD-Proxy)
sE(m]
By Lemma 3.1, the optimizer of this problem must be '² Note "(p²") 1 that ((p) I1+ We solve this as an approximate feasibility problem a packing LP by using the PST framework over c(D+), which is convex, according to the following lemma.
p such
Lemma 3.2. [4] Let p()) (()., be points in c(D), and let Ç E A be coefficients. Then, have (CGic-(p'") + ..... + SLc (p( S (ip(1) ..... (k)( Consequently, c(D't) is convex.
3.2 The PST algorithm
Plotkin, Shmoys, and Tardos designed framework (PST) for solving LP [PST95]. This result was improved by [AHK12] 12] for the case of packing and covering LP. We can use this framework to solve Problem (IFPD-Proxy) we can provide good feasibility oracle, as explained in the sequel. The PST framework focuses checking the feasibility of Ap S 1m, with in a convex set X. Then, obtains either a certificate of infeasibility of the problem or computes point X' such that Ap < (1 + <) m, for some given > O. The PST framework works by calling an oracle which solves the simpler feasibility problem of finding
P E X' such that (ATA, < 1,
(6)
for some distribution A e "" That is, given single constraint ftA, written convex combination of the constraints defined by A, the query asks for a point p E X' that satisfies the constraint. In our case, we apply the framework X' c(D+) find point p E c(D*) with Ap < (1 + 1 We can apply PST because c(D*) is convex. Our oracle subproblems are always solvable because 'dA E P satisfies them all. We use the following formulation of the PST and multiplicative weights (MW) algorithms for packing IP, which a slight variation of (AHK12]. The MW algorithm and its guarantees are presented in Lemma C.I.
7

---

Algorithm 2 Optimization of the dual of 1-fair packing with oracle D
Input: Matrix A Mmxx (R:0) normalized in (1). Accuracy E (0, (n 1)m]
1: ( <- concat (1n/n, O mm-n)= EA;; 8-1
o p is an 6 --nimiiieee of ğ
2: for 0 to T def max (2gg(2/(e/n))) do
3: I + {i E [m] (At.p* x10) 2 1426, 1 22
14
o Remove redundant constraints
4: if' is then E, f m2 else E, x E
Next target accuracy o Restart MW
5: A(I) + 17,11
6:
for k = 1 to K2 def
log(( = Ö(n/e;; do
1(k), pxt)) - (qquery A 114) /||A current solution { index set 4) (A c(D))
7:
8:
g(k) t- 11-l1 A A,
9:
A(++1) t 2 (Ex/(ATe, ,e, .)) -)))))
MW step
10: end for
11: ((++)) K. D ((a)
12: end for
13: return Ā def (T+1)
Output: Ap S (1 + 1/n)1m that is, k(x²) < + 8/n. Hence g(t) - g(**) S
Lemma 3.3 (PST guarantee). [1] Let 0, E. R For target accuracy E (0, 4 min T},, run the MW algorithm of Lemma C.I with = E/2, losses ((h) dut 1mm Ap!h) assumed to be in [-o, r r/mh. where ((8) is the point the oracle outputs at iteration k when the constraint that is queried given by A (A (R) /11A(()))))) and where A6) are the weights computed by the MW algorithm. Then, after
K 320r log(m) iterations, obtain a solution p dol (x=)p()) that satisfies 9(p) 11+E.
2
In order to give solution of Problem (IFP-Dual), we are also interested in recovering some À E A such that "(p²) is small. Assume the oracle returns point p(() p> (k) for some ( it can also provide. Then, even if p e D+ D, we have by Lemma 3.2 that Ā K > (a) defines a point pd E D such that xd < p. Hence "(r²) < ((p) < 1 + s, so Ā can be used our dual solution.
Algorithm 3 Feasibility oracle D
Input: An approximate solution 8 def A (() E A", g(c(s)) S 1 6. Query constraint
a = A() X E Am. Precision parameter < w S 2, default value w 2. Index set of non-redundant constraints I = {i [m]: (A,, c(s) 2 1+ahn+Vwon
1+5
Output: (1o) E A and point o def c( (A (lo) E c(D) such that
1. is covered by q, i.e., (q.0) < 1.
2. If E 7 then (A,, o) E [1 [1-T, T, 1 +o] where o = minnvwon++wh 1t min(3/wönn 1).
max 8, 11),
I48
satisfies all redundant constraints, i.c., (A,,0) S i, [m] L.
1: if (s, c(q)) <
1tw6 I4.8 then return (0) = =1(0) = =cc(q)
2: else if (q. c(s)) < 1 then return (00) =(() 0 c(s)
3: else Find μ (0, s.t. (s, c((1 n)s + +g)) E (1,
Ltwd via the bisection method
148
4: end if
5: return ( = () + px(1), o = c((1 u)s + nq)
Thus our task is to construct an oracle with good enough a and T. which are called the width parameters of the oracle. We also need make sure that E S 4 min(a, r). and that we can output a point pA in D, and corresponding x. Regardless, this algorithm runs in Ö(aT/E?) iterations, which is slower than what aim for, for constant a and Our approach to obtain a fast algorithm is to design an adaptive feasibility oracle. We provide our best solution (0) to the oracle, which

---

satisfies ((px)) X00 S 1 ö, for some ò > 0. Given such 8-approximate solution we identify set of indices 1, S [m] such that the constraints {A,, & Ie} are redundant, in the sense that the oracle is guaranteed to return points satisfying them even if they these constraints since they would yield large values T. Hence, we can run our MW algorithm with the remaining [4] constraints. Denote A,, the matrix that has (A, : E 1 rows, in increasing order of v. this case if A A we denote A A7,AA and p <(Af, A) accordingly. Our oracle, when given query h uses both constraints h and h to return point p satisfying the oracle condition (6) and such that the loss 1|r,1 P is in [-o6, Ta] 71). with
removed from the problem. We remove
2un + 2ôn
8 2 if 8 >
del (3 1}.
0g
14:28
max (1/hg²
In fact, ds can be defined as the minimum of its two expressions above, regardless of the value of &. But we shall use this definition for our algorithm. In the next section, we present the construction and analysis of such oracle and the set J.. We observe that, because the parameters depend on 8, we can restart the MW algorithm, and run in several stages, indexed by = 0, .......7 This allows for prove
incrementally reducing the width parameters and obtaining a better overall complexity, the following theorem.
Theorem 3.4. [4] Let (0, 1)]. Suppose we have feasibility oracle D satisfying (6) and (7), when we filter constraints according Algorithm 2. Then, Algorithm 2 computes, in O /e) iterations, a point Ā which an e-minimizer of g. Moreover, Yd is an (E/ni)-minmiize) of 9.
c(D*)
c(s)
Co(e)
P
Figure 3: The lens Cs(v) given by a feasible solution s, for w 1. the actual algorithm, we have 1, which defines larger set in which the affine part is translated upwards.
3.3 The PST oracle and the redundant constraints
In order to give fast solution for Problem is, it should satisfy (6), and should output better points already knows a good approximate solution. Generically, assume that the oracle has access to feasible constraint
we want to design adaptive oracle. That
(*)) E D,
with ( m satisfying A0 c(s) is point with ((pA(o) S 1 d. In other words, c(s) is a d-approximate solution to Problem (IFPD-Proxy). Let q (4) E E with ale) E Am query constraint. In Algorithm 2, (+) and (1) correspond to 7(0 and A (|) respectively, where the latter is interpreted as having coefficients equal to zero for constraints i I.
The main geometric idea that by using the solution s, we can define region whose size depends on containing the optimum pd of Problem (IFPD-Proxy). We will guarantee the oracle returns points in this region, which in turn means that the oracle returns points close to the optimum. We call this geometric object the lens of a point:
(v)(r) del {u R (c (x), < $1 (c) S ww),

---

where w [] is a parameter; we chose = 2 in the algorithm. We depict the lens in Figure in Appendix C. We apply this definition the point ((s) S + 8 implies that c(s)/(1 + 6) E P.
der c(s)/(1 8), which in because
We show in Lemma C.2 that, by using the bisection method, combination (1 - (b) + pr that will result constraint, whose centroid is the point we output. satisfies the first oracle condition, and in the lens. Also, we can recover (0) as (1 - p) + p)(7), (4),
efficiently find convex
If the oracle can output a point o in the lens, we will have low width parameters for the constraints A; that do not cover the lens, as we show in Proposition C.4. That is, for one such constraint A, the corresponding loss is - (A, o) E T. The other constraints could be problematic in terms of width parameters because (Ai, o) could be much smaller than 1, forcing 7 to be large. However, we do not need to optimize over these constraints because 2 1, so these constraints do not contribute to the max its definition. This leads to the set of non-redundant constraints 7, which efficiency reasons, relax to those indices of constraints A, that do not cover box that contains the lens, cf. Lemma C.3. We prove this is good enough in terms of the width parameters. The computation of I, which is done before each restart phase, requires ((N) operations and each query to the oracle takes (og (ا=1)á + 12 operations, cf. Lemma C.2.
Acknowledgments and Disclosure of Funding
We thank Elias Koutsoupias for some suggestions and discussions that started the line of research of this work. David Martinez-Rubio and Francisco Criado were partially funded by the DFG Cluster of Excellence MATH+ (EXC-2046/1, project id 390685689) funded by the Deutsche Forschungsge- meinschaft (DFG). David Martínez- Rubio was also partially supported by EP/N50971 1/1 from the EPSRC MPLS division, grant No 2053152.
10

---

References
[AHK12] Sanjeev Arora, Elad Hazan, and Satyen Kale. "The Multiplicative Weights Update Method: Meta-Algorithm and Applications". In: Theory Comput. 8.1 (2012), pp. 121- 164 (cit. on pp. 7).
[AK08]
Baruch Awerbuch and Rohit Khandekar. "Stateless distributed gradient descent for positive linear programs". In: Proceedings of the 40th Annual ACM Symposium Theory of Computing. Victoria, British Columbia, Canada, May 17-20, 2008, Ed. by Cynthia Dwork. ACM, 2008, pp. 691-700 (cit. on p. 2).
[AII+18] Zaid Allybokus, Konstantin Avrachenkov, Jérémie Leguay, and Lorenzo Maggi "Lower Bounds for the Fair Resource Allocation Problem". In: CoRR abs/1802 100.009922222 (2018) (cit. on p. 2).
[AO15]
Zeyuan Allen-Zhu and Lorenzo Orecchia. "Using Optimization to Break the Epsilon Barrier: A Faster and Simpler Width-Indeeendeen Algorithm for Solving Positive Linear Programs in Parallel". In: Proceedings of the Twenty-Sixe Anmual ACM-SIAM Sym- posium on Discrete Algorithms. SODA 2015, San Diego, CA, USA, January 4-6, 2015. Ed. by Piotr Indyk. SIAM, 2015. pp. 1439-1455 1456 (cit. on 2).
[AO19]
Zeyuan Allen-Zhu and Lorenzo Orecchia. "Nearly linear- packing and covering LP solvers Achieving width-inddeendenne and V/epsilon-convergence"" In: Math. Program. 175.1-2 (2019), pp. 307-353 (cit. on pp. 2, 3).
[Atk70]
Anthony B Atkinson. "On the mcasurement of inequality". In: Journal of economic theory 2.3 (1970), pp. 244-263 (cit. on p. 1).
[Bec+14]
Amir Beck, Angelia Nedic, Asuman E. Ozdaglar, and Mare Teboulle. "An O(1K) Gradient Method for Network Resource Allocation Problems". In: IEEE Trans. Control. Netw. Syst. 1.1 (2014), pp. 64-73 (cit. on pp. 2).
[BFT11]
Dimitris Bertsimas, Vivek F. Farias, and Nikolaos Trichakis. "The Price of Fairness'. In: Oper. Res. 59.1 (201 I), pp. 17-31 (cit. on p. 1).
[BR15]
Thomas Bonald and James W. Roberts. "Multi-Resee Resource Fairness: Objectives, Algo- rithms and Performance". In: Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, Portland, OR, USA, June 15-19, 2015. Ed. by Bill Lin, Jun (Jim) Xu, Sudipta Sengupta, and Devavrat Shah. ACM, 2015, pp. 31-42 (cit. on 1).
[DFO20]
Jelena Diakonikolas, Maryam Fazel, and Lorenzo Orecchia. "Fair Packing and Covering on a Relative Scale", In: SIAM J. Optim. 30.4 (2020), pp. 3284-3314 (cit. on pp. 2, 3, 17).
[DO17]
Jelena Diakonikolas and Lorenzo Orecchia. "Solving Packing and Covering LPs in O(1/22) Distributed Iterations with a Single Algorithm and Simpler Analysis". In: CoRR abs/1710009000 (2017) (cit. pp. 2,
[JH18]
Youngmi Jin and Michiaki Hayashi. "Trade-off between faimeess and efficiency in dominant alpha-fairness, family". In: IEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops, INFOCOM Workshops 2018, Honolulu, HI, USA, April 15-19, 2018. IEEE, 2018, pp. 391-396 (cit. on 1).
[Joe+12]
Carlee Joe- Wong, Soumya Sen, Tian Lan, and Mung Chiang. "Multi-resource allocation: tradcoffs in a unifying framework". " In: Proceedings of the IEEE INFOCOM 2012, Orlando, FI., USA, March 25-30, 2012. Ed. by Albert G. Greenberg and Kazem Sohraby. IEEF, 2012, pp. 1206-1214 (cit. on p. 1).
[JV07] Kamal Jain and Vijay V. Vazirani. "Eisenberg-Gare Gale markets: algorithms and structural properties". In: Proceedings of the 39th Annual ACM Symposium Theory of Com- puting, San Diego, California, USA, June 11 11-13, 2007. Ed. by David S. Johnson and Uriel Feige. ACM, 2007, pp. 364-373 (cit. on p. 1). Kamal Jain and Vijay V. Vazirani. "Eisenberg- -Gale markets: Algorithms and game- theoretic properties". In: Games Econ. Behav. 70.1 (2010), pp. 84-106 (cit. on p. l). Frank Kelly. "Charging and rate control for elastic traffic". In: Eur. Trans. Telecommun. 8.1 (1997). pp. 33-37 (cit. on p. 1).
[JV10]
[Ke197]
[KY14]
Frank Kelly and Elena Yudovina. Stochastic networks. Vol. 2. Cambridge University Press, 2014. ISBN;
(cit. on p. 2).
11

---

[Lan+10] Tian Lan, David T. H. Kao, Mung Chiang, and Ashutosh Sabharwal. " "An Axiomatic Theory of Fairness in Network Resource Allocation". In: INFOCOM 2010. 29th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 15-19 March 2010 San Diego CA, USA.
IEEE, 2010, pp. 1343-1351 (cit. on p- 1).
[LN93]
Michael Luby and Noam Nisan. "A parallel approximation algorithm for positive linear programming" In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing. May 16-18, 1993, San Diego, CA. USA. Ed. by S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal. ACM, 1993, pp. 448-457 (cit. on p. 2).
[McC+14] Bill McCormick, Frank Kelly, Patrice Plante, Paul Gunning, and Peter Ashwood-Sminn Smith. "Real time Hlpha--farreee based traffic engineering". In: Proceedings of the third work- shop Hot topics in software defined networking. HorSDN '14, Chicago, Illinois, USA, August 22, 2014. Ed. by Aditya Akella and Albert G. Greenberg. ACM, 2014, pp. 199- 200 (cit. p. 1).
[MSZ16] Jelena Marašević, Clifford Stein, and Gil Zussman. "A Fast Distributed Stateless Algo- rithm for alpha-Fair Packing Problems". In: 43rd International Colloquium on Automala, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy Ed. by Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi. Vol. 55. LIPIcs. Schloss Dagstuhl- Zentii- für Informatik, 2016, 54:1-54:15 (cit. pp. 3).
[MW00]
Jeonghoon Mo and Jean C. Walrand. "Fair end-to-end window- based congestion con- trol". In: /EEE/ACM Trans. Netw. 8.5 (2000), pp. 556-567 (cit. on p. 1). John F. Nash. "The Bargaining Problem". In: Econometrica 18.2 (1950), pp. 155- 162.
[Nas50]
ISSN: 00129682, 14680262 (cit. on p. 1).
[PST95]
Serge A. Plotkin, David B. Shmoys, and Éva Tardos. "Fast Approximation Algorithms for Fractional Packing and Covering Problems". In: Math. Oper. Res. 20.2 (1995), pp. 257-301 (cit. on pp. 3, 6, 7).
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See the introduction, where we
talk about other a-fair problems.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
12

---

(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' roure using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "icarjHMR0Aw", "reviewer": "Reviewer_nmUR", "summary": "This paper studies proportional fair resource allocation problem and develops first-order methods", "questions": "Can the algorithms be generalized to other optimization/learning problems?\n\nTheorem 2.5 depends on big constants, which can be exponential in n?", "limitations": "The developed first-order method is limited to the problem itself.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The analysis is solid and the problem is interesting.\n\nWeakness: The developed first-order method is limited to the problem itself.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "G3VmQ_0jZeS", "reviewer": "Reviewer_539K", "summary": "This paper studies the proportionally fair optimization problem (i.e., $\\max f(x) = \\sum_i \\log x_i$) under packing constraints ($A x \\leq 1$ for a matrix A of nonnegative entries). The main contribution is a distributed accelerated algorithm for fair packing. The algorithm is width independent and produces (additively) approximate solutions for both primal and dual.\n\nWidth is defined as max ratio of positive entries in the matrix A. First order width-dependent methods don't readily lead to polynomial-time algorithms because smoothness constants do not scale logarithmically with width. In addition, approximate solutions of primal and dual are not easily translatable. In light of this, designing width-independent approximation algorithms for both primal and dual sounds challenging.\n\nThis is done by extending a general technique for packing LPs and exploiting problem structure to design a distributed algorithm. Distributed width-independent algorithms for general packing LPs are not yet known. Unlike prior work, the new algorithm is determinstic, has additive (not multiplicative) error, and uses a different regularization. The new algorithm uses $O(n/\\epsilon)$ iterations, a factor n smaller than the best prior method.", "questions": "none", "limitations": "n/a", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Primal and dual algorithms are both width independent. (Translating approximate solutions between primal & dual is not easy.)\n\nWeaknesses:\n- No discussion of concrete applications, hence no experimental study to show practical benefits, runtime and error bounds.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AIXepM2WBc", "reviewer": "Reviewer_wjuT", "summary": "**The problem and its importance** \n\nThe paper presents an *accelerated, width-independent algorithm* for the $\\alpha$-fair-packing problem with $\\alpha = 1$, in the distributed model of computation. The problem is motivated by that of fair allocation of (non-negative) resources and falls under the broad umbrella of $\\alpha$-fair-packing problems, which are an important problem class encompassing, for example, the standard packing LP, which has seen a long line of work (for example, by Luby-Nisan, Fleischer, Plotkin-Shmoys-Tardos, Awerbuch-Khandekar, Young, Koufogiannakis-Young, Allen-Zhu-Orecchia, Wang, Mahoney-Rao-Wang-Zhang, etc.) in both theoretical computer science (most significantly in the context of multicommodity flow problems) and machine learning that have led to developments of techniques that are now widely used in optimization in general. Therefore, this paper definitely studies a very important problem. \n\nThe paper further studies the dual of this algorithm and applies it to obtain an improved analysis of the classical Yamnitsky-Levin algorithm. \n\n**The technical outline** \n\nThe paper solves the primal problem by building upon the work of Diakonikolas-Fazel-Orecchia and AllenZhu-Orecchia. Specifically, the problem reformulation and parts of analysis (the gradient descent progress) is drawn from DFO, whereas the framework of ``truncated gradients in mirror descent coupled with gradient descent'' comes from AZO. We explain these a bit more next. \n\nThe notion of ``fairness'' is captured in the objective via maximizing the *product* of allocated resources (and taking the log to formulate it as a convex minimization problem), which results in the problem $\\max_{x\\geq 0, Ax \\leq 1} \\, \\sum_{i = 1}^n \\log x_i$. The final reformulated problem involves the following modifications to this problem: (1) reparametrizing the problem variable to make the (initial) objective linear; (2) moving the packing constraints into the objective via an exponential penalty; (3) adding a box constraint based on properties of the optimal point. We note that these modifications were first done in DFO. \n\nFor this reformulated problem, the gradients lie (coordinatewise) in $[-1, \\infty)$. The algorithm proceeds as follows. It takes a mirror descent step using the squared-loss mirror map and on the linear term defined by the *truncated* gradient. The truncation is essential for obtaining a regret that is independent of the width of the problem, and this idea stems from AZO. Next, the algorithm takes a ``gradient descent step'' with the amount of update scaled proportional to the amount of movement via the mirror descent step. Following the gradient descent analysis of DFO, the paper shows a minimum bound on the progress via this step. Finally, the iterates obtained via the mirror descent and gradient descent steps are coupled in a convex combination (and their analysis performed analogous to that in AZO). This gives a primal algorithm with $\\epsilon$-additive optimal point in $O(n/\\epsilon)$ iterations. \n\n**Contributions** \n\n1. The paper's main result is an $O(n/\\epsilon)$ iteration algorithm for the stated primal problem. The previous best result by DFO was $O(n^2/\\epsilon^2)$, making this paper's contribution in terms of results very clearcut. Further, in achieving this iteration count, the paper becomes the first to achieve both width-independence and acceleration for the $1$-fair-packing problem, which is quite a significant and a highly non-trivial contribution in this line of work. \n\n2. While the paper definitely builds upon the work of DFO and AZO (as described above), the way it combines them is novel (which is what gives it its new, improved result). \n\n\n\n\n", "questions": "0. Please see the **Weaknesses** section above for other questions. \n\n1. My first obvious question is, why doesn't this algorithm extend to the case $\\alpha \\neq 1$? Or, if it does, then what is the iteration complexity? It would make the paper more complete to explain this as well. ", "limitations": "I very much appreciate the authors being upfront about the paper not generalizing to the $\\alpha \\neq 1$ case. Given that this is a theoretical paper, I do not foresee any negative societal impact of the paper and have no suggestions to this end. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths** \n\n1. Achieving both width-independence and acceleration for $1$-fair-packing is quite a significant result. In my opinion, just the first component of the paper (the primal result) is a strong result in itself. \n\n2. The paper's primal algorithm is very clean, with very clearcut operations (mirror descent, gradient descent, and coupling) along with their corresponding analyses. The *reasons* for various steps in the algorithm (example, gradient truncation) and why the analysis works (example, the progress by gradient descent compensating the regret bound via the truncated gradient) is also all explained very transparently. \n\n3. The previous best result on this problem (DFO) achieves their result by a different technique (approximate dual gap technique), so it is quite nice that this follow-up work follows a different technique.  \n\n**Weaknesses** \n\n1. Given that the paper greatly builds upon the work of DFO (for the primal algorithm), I think one way to make this paper even more transparent would be to (if possible) try and frame DFO's algorithm in this paper's language. More concretely, can you write DFO's algorithm in the ``coupling'' framework of this paper (which in turn draws this from AZO) and show exactly what steps of DFO (in this framework) were changed to achieve this paper's result? \n\n2. I think the main body (the primal section) could do a slightly better job of giving more complete justifications/attributions. As examples, \n\n    * it's not immediate from the algorithm in the main body that the iterates all lie in the box (though this is justified in the appendix); perhaps a pointer to this lemma would be good. \n\n    * Further, I think it's important to clearly state in the main body what parts of the problem formulation and analysis are derived from DFO and AZO (for example, Lemma 2.3 is basically that of DFO). Having these attributions clearly stated will more clearly shine a light on the paper's novelty, without taking away the contributions of DFO and AZO. \n\n3. I found the dual algorithm/analysis way more dense than the primal part. Is it possible to simplify this section's exposition? \n\n**My overall verdict** \n\nI think this is a worthy problem, with a simple, clean algorithm for the primal case, a creative one for the dual case, and an interesting application to a classical algorithm (Yamnitsky-Levin) that I had been unaware of. \n\nIn addition to its primary contributions (the primal and dual algorithms and analysis), the final contribution adds value to the optimization/ML literature by bringing to fore a (possibly) less-known classical algorithm. This would therefore be a nice contribution to NeurIPS '22. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4xLQLwEu6AY", "reviewer": "Reviewer_2so1", "summary": "The paper solves the so-called 1-fair packing problem via first-order methods. The main results are computational complexity of O(n/epsilon) for the primal problem and O(n^2/epsilon) for the dual problem. These results are not width dependent (where the width is the ratio of largest to smallest elements in matrix A), which is a plus.", "questions": "I am not too familar with the literature on this problem; perhaps a in-depth discussion about pros and cons of the developed algorithms compared to the state-of-the-art would be helpful to readers.", "limitations": "The authors did not address the limitations and potential negative societal impact of their work but it is okay given the nature of this work.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength is that the paper studies a fairly important problem in resource allocation. I like the results overall. The weakness is that the method developed follows closely to Allen-Zhu and Orecchia (Math. Prog. 2019). It seems that it simply customized their approach to this specific setting. The computational complexity results are good but at the expense of solving more difficult oracles.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept