Noisy Dual Mirror Descent: A Near Optimal Algorithm for Jointly-DP Convex Resource Allocation
Authors: Du Chen
Geoffrey A. Chua
Venue: NeurIPS 2024 poster (2024)
Keywords: joint differential privacy
resource allocation
near optimal algorithm
mirror descent
Primary area: privacy
TL;DR: we propose an algorithm to (near) optimally solve convex resource allocation problems under joint-DP

Abstract: We study convex resource allocation problems with $m$ hard constraints under $(\varepsilon,\delta)$-joint differential privacy (Joint-DP or JDP) in an offline setting. To approximately solve the problem, we propose a generic algorithm called Noisy Dual Mirror Descent. The algorithm applies noisy Mirror Descent to a dual problem from relaxing the hard constraints for private shadow prices, and then uses the shadow prices to coordinate allocations in the primal problem. Leveraging weak duality theory, we show that the optimality gap is upper bounded by $\mathcal{O}(\frac{\sqrt{m\ln(1/\delta)}}{\varepsilon})$, and constraint violation is no more than $\mathcal{O}(\frac{\sqrt{m\ln(1/\delta)}}{\varepsilon})$ per constraint. When strong duality holds, both preceding results can be improved to $\widetilde{\mathcal{O}}(\frac{\sqrt{\ln(1/\delta)}}{\varepsilon})$ by better utilizing the geometric structure of the dual space, which is neglected by existing works. To complement our results under strong duality, we derive a minimax lower bound $\Omega(\frac{m}{\varepsilon})$ for any JDP algorithm outputting feasible allocations. The lower bound matches our upper bounds up to some logarithmic factors for $\varepsilon\geq \max(1, 1/(n\gamma))$, where $n\gamma$ is the available resource level. Numerical studies further confirm the effectiveness of our algorithm.

Noisy Dual Mirror Descent: A Near Optimal Algorithm for Jointly-DP Convex Resource Allocation
Du Chen" Geoffrey A. Chua
Nanyang Business School, Nanyang Technological University, Singapore, 639798 chen14438e ntu. edu gbachua@ntu. edu.
Abstract
We study convex resource allocation problems with m hard constraints under (s, 8)- joint differential privacy (Joint-DP JDP) in an offline setting. To approximately solve the problem, propose generic algorithm called Noisy Dual Mirror Descent. The algorithm applies noisy Mirror Descent to a dual problem from relaxing the hard constraints for private shadow prices, and then uses the shadow prices to coordinate allocations in the primal problem. Leveraging weak duality
theory, we show that the optimality gap is upper bounded by O /m
and constraint violation is no more than O mm per constraint. When
strong duality holds, both preceding results can be improved to Ö //n by better utilizing the geometric structure of the dual space, which is neglected by existing works. To complement our results under strong duality, we derive a minimax lower bound ! () for any JDP algorithm outputting feasible allocations. The lower bound matches our upper bounds up to some logarithmic factors for max 1, 1/ (nr)). where ny is the available resource level. Numerical studies further confirm the effectiveness of our algorithm.
Introduction
The resource allocation problem classic optimization problem and has many applications in machine learning, such as Internet advertising and personalized recommendation, among many others. The problem is typically modeled maker has to properly allocate m types of limited resources to agents in order to maximize the total utility of all agents. Each agent's data 2; == (u,()), a.(-), X)) consists of three elements: (i) utility function R + E that maps an allocation æ; to utility scalar; (ii) a consumption function a, I - ITT that maps an allocation æ; to consumption vector; and (iii) feasible set X; S R that may capture the agent's 's special requirements. With dataset D = {2; ) of n agents, the problem is modeled as
utility maximization problem, where the central decision
(Resource Allocation Problem)
mAX (my Ti
(x;)))
s.t.
Σ a, (x())) ) S nybb im
(2)
2; E X;
Vi = 1, 1,
(3)
where n76 > 0 is the available level of m types of resources. Evidently, the goal in (1) is to find the best allocation æ; for each agent subject to resource-coupling constraints (2) and to personal
Cooresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

requirement constraint (3), When (.) is concave, and a.),), X; are both convex, the problem reduces to a convex constrained problem that has been widely studied in optimization literature.
However, an emerging issue in allocation problems is data privacy. Because constraint (2) couples agents, the allocation decision one agent would affect the allocation to another agent. When group of agents collude, they can infer other agents' data by analyzing their received allocations. For example, when allocating limited budgets among education agencies to support students in poverty, a simple rule is to allocate budgets proportional to the number of students in poverty [SLWA22]. Agencies who notice a change in received funding may infer the financial status of students in other agencies. Realizing this potential leakage of its students' financial status, an agency the number of its students in poverty, compromising the original intention of the financial support.
misreport
To overcome privacy concerns in such cases, joint differential privacy (Joint-DP or JDP, for short), which is relaxation of differential privacy (DP), has been adopted. It is found that JDP is more suitable than DP for the considered allocation problems [HHR + 14]. Essentially, JDP ensures agent i's data cannot be accurately inferred by group of collusive agents without guarantees that the allocations received by the collusive agents are insensitive to agent i's data. Considering that the allocation decision æ; is usually private to agent herself, the privacy guarantee by JDP is hence meaningful and sufficiently strong. The most handy way to achieve JDP is by the well-known Billboard Lemma [HHR* 14]: publish a DP public signal on a billboard accessible to all agents, and compute the allocation for agent i based on the DP public signal and agent i's own data only; then the final allocations (z), (......, . F.,)) satisfy JDP. The Billboard Lemma has wide applications, ranging from convex optimization [HHR- 14, HHRW 16, HZ.18), to multi- bandits [SS18, HLIL+22], to reinforcement learning VVBKW20) We also use it for privacy analysis. For clarification purposes, we highlight that, in problem (1), dataset {= == ((u,()), a. ()), X)) is the private information to protect; resource level ny is treated as public information.
While important and fundamental, resource allocation problems under JDP are far from being well understood, in terms of both algorithm design and theoretical analysis. For algorithm design, most existing works adopt a "dual decomposition" idea [HHRW 16, HZ18], which dualizes the coupling constraint (2) and iteratively seeks private minimizers of a dual problem to coordinate the allocation process in the primal problem. However, the primal -dual relationship and the geometric structure of the dual space are not well exploited, leaving substantial room for improvement. In terms of theoretical analysis, both privacy accounting and optimality analysis are short of modern standard. For privacy accounting, existing works [HHRW1G 16, HZ18, HZ19] all use Advanced Composition, which suggests unnecessarily large noise to be injected, significantly hindering algorithm practicability. For optimality analysis, [HHRW16] fails to take full advantage of strong assumptions made, and the analysis by [HZ18] is specific to linear packing problems. More importantly, there is no formal understanding of the fundamental trade-off between privacy and optimality in resource allocation problems under JDP, i.e. minimax lower bounds. Motivated by these gaps in the literature, we focus our study on the following three questions.
1. Can we design generic algorithm for resource allocation problem (1), and provide better privacy and optimality analysis?
2. Can we better utilize the primal-dual relationship to improve performance?
3. Is our algorithm (near) optimal? What is the minimax lower bound?
Our contributions First, propose generic algorithm Noisy Dual Mirror Descent, which follows a similar dual decomposition idea. We tighten the privacy analysis through Rényi DP, and analyze performance (both optimality and constraint violations) by better utilizing the primal-dual relationship. Second, for many cases where strong duality holds, we further improve performance by leveraging on the & geometry of the dual space. Last, we complement previous analysis with a matching minimax lower bound for s 2 max [1, 1/ (nr)), suggesting near optimality of our algorithm. We further conduct numerical experiments show the effectiveness of our proposed algorithm. Table summarizes our contributions and compares them with results in the literature.
Our interpretation of algorithm performance Because the algorithms considered may output infeasible solutions, when assessing their performance, we should take into account both suboptimality in utility and constraint violations, i.e., the last two columns in Table 1. We therefore treat the sum of them as the ultimate performance. This idea admits social welfare interpretation: when the central

---

Table I: Comparison of various works resource allocation problems under (c, d)-JDP
problem setup
theoretical results
u
(.).)
X
assume strong duality?
LB
utility loss UB
total constraint violation
linear probability
my In myIn (1/6)
my (mvlnniu (1/5)
[HHRW16]*
linear
(Theorem 3.3, w.h.p.)
(Theorem 3.3, w.h.p.)
[HZ18]$
linear
linear
[0, 1
v m In (1/6)
Ö
m 3/2 Vin (1/8)
(Thenrem 1.1, w.h.p)
(section 3.2.2, w.h.p.)
Vm (1/8)
Lm (1/5)
This work
concave convex
convex
o
(Theorem 3.5)
(Theorem 3.6)
v in (1/8)
m In (1/5)
Ω
(Theorem 4.3)
(Theorem 3.10)
(Teeremm 3.10)
Notes. All results in the table are stated for S. In (1/5) for couciseneas; m, n. T are the number of constraints, agents, and iterations, respectively. Tilde symbol Ô hides poly-log factors in m; for results in [HHRWI6, HZ18J, Ô additionally hides poly-log terms in v and T. LB=lower bound, UB-upper bound, w.hp=with high probability. TThe algurithm in HHHRY 16] can be practically applied to general convex problems.
supporting Lemma (Theorem 2) they used derive analytical results only valid linear problems with solutions in prohahility simplex. An lower hound f2( vmn ) can he derived from [H7718, Theorem 1.2]. But their original statement is for the minimal supply, not for suboptimlity as we considered. The lower bound is for algorithms outputting feasible allocations, while upper bounds
by algorithmm that may output infeasible allocations. So, e max(1, ((a) where (0, l).
bound could higher. lower bound holds only
decision maker (e.g., government) desires to implement an infeasible allocation, she may purchase additional resources from an emergency supplier to make the allocation feasible. Then, the total loss in social welfare is the sum of (i) the loss in utility of agents and (ii) the decision maker's ss expenditure on extra resources. If we only look at suboptimality, we may mistakenly conclude that the gap could be arbitrarily small. Following our interpretation of performance, our proposed algorithm is near optimal.
Related work JDP was initially proposed by [KPRU14] as relaxation of differential privacy [DR14], which better fits the nature of privacy issues in zero-sum games, such as allocation problems [HHR* 14, CKRW15], Following this stream, the most relevant works ours are [HHRW1L 16, HZ18], both of which designed their algorithms with dual decomposition idea. [HHRW16 16] proposed the first generic method, dual gradient descent, for solving allocation problems. For the special case of linear packing problem, [HZ18] designed a dual multiplicative weight update algorithm, and extended to online setting. [GU22] further provides an economic interpretation of payoff sharing. Our work is also closely related to Mirror Descent (MD) [NY83], a generalization of projected gradient descent to Ruc-Euclidean settings. Its private version, Noisy MD, has recently found many applications in non-Euclidean DP stochastic convex optimization [AFKT21, BGN21] and saddle-point problems [GGP24]. We further apply Noisy MD to JDP resource allocation problems.
2 Preliminaries
Definition 2.1 (Differential privacy, [DR14]), A mechanism M: 2" P (c, diifffrrnnil private if. for any pair of neighboring datasets D ~ D' that differ in one data point, and for any subset of output S C P, we have [M((D E S] < P [MD(D)) E +
Throughout the work, we use the subscript -; to indicates variables without agent i. For ex- ample. X-: = Xi x ... -. x X x Xn, is a feasible space without i, and M(D) := (M(D), 1............... ... M(D), M(D) M(D))
M(D),. is the view from other agents without i.
Definition 2.2 (Joint differential privacy, [KPRU14]). A mechanism. M: 2n - X is (e, 8)-jnin differentially private if for any pair of neighboring datasets D ~ DD' that differ in datapoint i [n]. and for any subset of outputs S C X-i, we have IP [M(D)-+ S] E PPM(DD) S)+
3

---

Lemma 2.3 (Billboard Lemma, [HHR 14)). Suppose M: : 2" + P is (E, For any given function f P + X, denote the output of on individual i's data as ft == f(z,, M(D)). Then, (J1,...,fu) fa) is (s, 6)-IPP
Definition 2.4 (a-strong convexity). Let a > 0. Function & : Rm - R is said to be a-strongly convex w.E.t.
Il.Ipp over set W, if (a) 2 (yy) + (Ve(y). y) + || y Va. W.
Primal problem in condensed form
........ Fn be the collection of allocations. For a given dataset DD let F(x)) == Σi=1 (x,)) be the total utility when allocation is æ. Let a(x) := >i= a, (x3z) be the total consumed resource, and let X' := & X ... x Xr be the feasible region. Then, the resource allocation problem (1), referred to as "primal problem" later, can be written in a condensed form:
Let
(Primal Problem)
max (F(x) a(x) S myb. =EX
(4)
The optimal allocation denoted as x= == arg max (F(x) a(x) s nyb).
Dual problem By dualizing the coupling constraint with shadow prices 2 0, we get Lagrangian function minp20 max (F(x)) (p, nr.b a(x))) Thus, the Lagrangian dual problem is
(Dual Problem)
min D(p),
(5)
p20
where D(p) == maXgex (F(x) + (p,nyb - a(x))} It is easy to see that, given p 2 0, the dual problem is decomposable across agents, i.e., D(p) = E e {u;( (p. b (xx))))) Let us denote the dual problem's 's minimizer by p == arg minp20 D(p).
When there are multiple xt and p", we can break ties arbitrarily. Let Il-IIp denote the p-norm of vector, and let [n] [I....,n] n be running set. We impose some assumptions dataset D to make both primal and dual problems interesting.
Assumption 2.5 (Interesting instances). For dataset == {(u,)), (,,,),),))))) a.), we assume
1. Convexity: for each i E [n], utility function u, is concave on X,, consumption function a, is convex on X₁ and X₂ a convex set:
2. Boundedness: 3 >> 0 and bounded b>> with |lbl|2 S B such that u.( ) E [0, ū| and a;(x:)) E [0, b). Vaz; E Xg i E [n]] Specially, if0 E X, then u,(0) = 0 and a; (0( 0;
3. Limited resource:
the constant y in (4) is assumed to be in the interval (0, 1). The primal problem (4) feasible, and optimal x" is attainable. Under x", at least one of m constraints in (4) is binding. Moreover, the optimal shadow prices p to dual problem (5) are not all zeros, i.e., I|p" 1I, A 0:
4. Compulsory request allowed: request i be compulsory in the sense that X, 3 0, only if max,,ex; (u,(x.) + (p", , ax(x)))) 2 0.
These assumptions very mild. The first assumption restricts our attention convex problems. The second one assumes both utility and consumption functions are non-negative and bounded from above, and are both zeros if no resource is allocated. The third one assumes the non-private problem is indeed resource-constrannel and not ill-posed. The constant controls available resource levels, and my means the number of agents whose requests can be fully fulfilled. In practice, usually 7 2 1/n. The fourth one allows agents to propose compulsory requests with minimal requirements strictly greater than 0, as long as allocating resource to the agent beneficial. Our assumptions are weaker than those in the literature [HZ18, BLM20, BLM23] by allowing compulsory requests.
3 The algorithm and analysis
Our algorithm a private version of Mirror Descent applied to the dual problem (5). Mirror Descent (MD) [NY83] is generalization of Projected Gradient Descent (Proj-GD) that can better cater to the geometry of the problem at hand by the proper choice of a strongly convex potential function + : W + t. The potential function chosen should meet some conditions below.

---

Condition 3.1 (Potential Functions). The potential function c W - R.+ chosen should be (i) differentiable on int(W). i.e. the interior of its domain W C R=. and (ii) a-strongly convex with respect to ll-Ilp on W. For a given Φ, let Bo Bo( (v. := (b ( (Vb(y). x - y) be the Bregman divergence between & E W, y E in((W).
With the primal problem (4) and dual problem (5) in mind, and a well-chosen potential function, we are ready to present the algorithm, Noisy Dual Mirror Descent. The algorithm is an iterative
Algorithm Noisy Dual Mirror Descent for Resource Allocation Problems, A
Parameters: privacy parameters (s, 6), variance g²; stepsizes {n)()][ potential function (-)) W + R. that is a-strongly convex with respect to fp-norm; conjugate index & s.t. 1/9 + 1/p number of iterations T,, feasible region of shadow prices P RT.
1: Set initial point p!!) E E (nii))(W))
2: for 1 to T do
3: Get intermediate allocation decision (+() + arg m F(xx) + (p!1),mb ymb a(x))
4: Draw noise vector (t) (N o Lmxm)
5: Update private shadow prices according to Noisy Mirror Descent:
p (1+1) f- arg min
(1(0) (8") + +n p)) + Bo Bo(D.
(6)
PEPrI
where (d)) = myb ())
6: Final allocation decision A == (x1 ....,.. xx) f E x0
7: Output a; to agent i, for all i [m]]
algorithm, and in each iteration, we first calculate allocation decisions based on current shadow prices p()) i.e. Step 3. Then, we update the shadow prices by Noisy Mirror Descent update rule (6). The gradient (()) used is exactly the gradient of the dual problem ((p()) according to Danskin's theorem. After T iterations, we output the averaging allocations across all iterations. In other words, we basically apply Noisy Mirror Descent to solve the dual problem, and use the sequence of shadow prices to coordinate allocations in the primal problem. Intuitively, the shadow prices are implicitly pricing each resource to ensure that limited resources are allocated to agents most in need.
Recall the Billboard Lemma, if we can privatize the entire sequence of shadow prices in DP manner, then the final allocation decisions will be JDP. Compared to existing works invoking Advanced Composition, provide tighter privacy accounting through Rényi DP.
Theorem 3.2 (JDP Guarantee). Given e > 0,8 (0, 1) and T 2 1, if noise variance o² = T C2.6 with Ce.6 ==
|b]| (2 (1/8) + +) then Algorithm 1 A is (s, 6)-JDP
To better align with expressions in DP literature,
assume S In (1/5). Then, the magnitude [ (1/6) magnitude of Gaussian Mechanism that frequently appears in DP literature. Moreover, the privacy analysis via Rényi DP significantly lowers the variance level. For example, when 1, 5 10 and ||b|[ [ 1, the variance indicated by Theorem 3.2 is 14.8T, compared to approximately 121.67 by [HHRWI6 16, Theorem 3.2], [HZ18, Lemma 3.1].
of Ge.á becomes In
3.1 Performance upper bounds
We now move analyze the utility optimality gap F(x=") IEAA [F(arA]] The following weak duality lemma bridges the primal and dual problems.
Lemma 3.3 (Weak duality). For any p 2 0, the objective value of dual problem (5) is always greater than or equal to that of primal problem (4), i.e., D(p) Z max (F(x): a(x) < nrb,, vp 2 0.
An immediate result of weak duality ((p()) 2 F(xx"), Vt. Hence, applying weak duality and Jensen's 's inequality, the optimality gap F(x") ) F(xxAA can be upper bounded as follows, provided
5

---

the randomness dice of A is fixed.
T
T
F(x²) - F(ar1) S T
((p) - -F(x!)))
nyb -a(x!0))
T
T
1 T Σ p gg (0)
Σ
p
(0)
where the first equality is by definition of the dual problem, and the second equality is by definition of gradient g()), Taking expectation with respect to removes the subtrahend, since (f) is independent
of (t) and zero-mean, which gives F(x²) E, [F(x*)] S EA + (p ((() [0) The
inner term is closely related to stationarity gap [GL13, ABG 23] in nonconvex optimization. It is well-known that Proj-GD guarantees a small stationarity gap in both non-private [JNG 21] and private [ABG+25 23] cases. Not surprisingly, MD also achieve small stationarity gap.
Lemma 3.4 (Cumulative stationarity gap of MD). Suppose stepsizes of()) = MD update rule (6) are the same for all [T], and let (g(t) ) be gradients used for update. Then the cumulative stationarity gap Ei= (p(t) -pg (t) for any anchor point PnW is upper bounded as
T
n E 1=
1 +
Bo(p.p
Σ
p - p.
ApEPnW.
20
7
With Lemma 3.4 and proper stepsizes, we can control the optimality gap. Denote 7 := maxfn, 1-7). G = n²n [[bli and let ~ (O, m be a standard Gaussian random vector. For given potential function & and an initial point p()), denote Co (p(()) = (0. (())/a.
Theorem 3.5 (Utility guarantee). Set stepsizes Ty())
(0.()))))) BI Vt [T]. Suppose
potential function's domain includes O, i.e. 0 E W. Then running algorithm A with iterations
G and o² chosen in Theorem 3.2 yields
0 []]]]
F(xx) - EA (FA < 4Co(p())
E [|=1|]]]
VCr.s
An instantiation of the utility guarantee is by Φ(.) 11- which is 1-strongly convex w.r.t. f2-norm on RT Then, the upper bound in (7) becomes 2/2mm || 1|2 /Ce,5, which depends on the choice of initial point p It seems the bound can be arbitrarily small if p() is close to O. But in fact, the theorem itself does not reflect the whole picture, since A could be infeasible. Therefore, have to further examine A's feasibility guarantee.
Theorem 3.6 (Feasibility guarantee). Given allocation decision xA, denote the violation levels as B := (a(xA) -n-bb)+ where positive part operator (.)+ applies element-wisely. In addition to Condition 3.1, additionally assume the domain W of potential function &b contains || ej Vj e
[m]. Then, running algorithm A with the same setting as in Theorem 3.5 yields
2 E 1
(p
EA 1|
+ 2V Inm
(8)
Va.
|p-|1
pn( ())0.p()mmmm +max.er, Be Ba e1) (1)
where Co (p())
set E, == {e [0,1) (1,e) $
(D)
The proof idea is to sandwich the cumulative stationarity gap Σ -p. at properly chosen anchor point = 2 ||pp"|| еÿΛ E P W (the constant 2 is chosen arbitrarily, it can be any value strictly greater than 1), and then comparing the upper bound and lower bound in the sandwich inequality gives the desired result. The base vector EGd with single 1 on j'h position

---

indicates which constraint j E. [m]] is most severely violated. One may notice that the anchor point p := 2 ||p" I11 2, needs to be in P W, which implicitly imposes one additional condition on the domain W of potential function Φ. While the capability of computationally calculating lpp" ]| is not needed for deriving (8), on a practical note, we may need to adjust W accordingly so that W contains all possible anchor points 2 ||p"|| 11, e VjA almost surely. When doing so, we should be very careful because p" depends on dataset D and thus, such an adjustment may leak privacy.
Again, one may think (()) = 2/2 I1-12 is the ideal potential function, because its domain W th contains all anchor points of interest, does not depend on p", and therefore no privacy leakage risk. As shown in the first row of Table 2, the guarantees under squared f2 are only comparable to, not better than, those in the literature summarized in Table 1. Nevertheless, being comparable is already a significant improvement because our results are derived from weak duality only, whereas existing works all assume strong duality. Moreover, since anchor points p = 2 ||pp ||, eja are related to L norm of p we can find data-independent upper bound for the value of ||p" I| we might be able to adjust W accordingly without privacy concerns and may further improve performance. We do so in the next subsection.
Table 2: Examples of theoretical guarantees under specific choices of hyperparameters.
Potential Function
Theoretical Guaranlees
function
domain
strong evx.
init. pt.
opl. gap
total constr. viol.
name
(p)
W
w.nt IlIp
(
F(x=)
(((=)))
mB
squared &
1 |1pl
R
w 1-ll2
Vm 1 O
V mm (1/0)
O
m 3/2 (1
negative entrupy (ne)
E Py lupy
Ax w. K =
I W.L.L.
11-11
1
Kō
KÖ
m myTw1171
parameterized ne
Σ bypy la (b Ax w. K 2u
I1-11
Vj
KÖ
m [wiz
Notes. Results squared fa inegative entropy) are from Section 3.1 (Section 3.2). Strong duality necessury for theoretical guarantees (pa- mmeetrized) negative entropy. Abbreviations in column titles: evx cconexxtyy init.pt. point, opt.gap optimality gap, contrs mconstrant violations. The (scaled) simplex set Ax (b) with radius K is defined as Ax == {p 2 (b, p) S J: the standard simplex is
AK == Ax(a (1). Squared &a function is strongly convex on whole space X while negative entropy functions only on their respective domains. Results in the first and second rows highlighted us the main contributions in Table 1.
3.2 Improvements by strong duality
Indeed, there exists space for improvement, if we assume strong duality holds.
Assumption 3.7 (Strong duality holds). Strong duality between primal problem (4) and dual problem (5) holds, i.e., F(xx*) = D(p"), where x² and p" are optimal solutions to (4) and (5), respectively.
While weak duality always holds, strong duality does not universally hold. However, there are many applications where strong duality naturally holds. For example, when the dualized constraint a(x) < n is linear in æ, strong duality holds. If the constraint is not linear, one can check strong duality by Slater's ' condition, which essentially says that if the primal problem (4) has strictly fcasible solutions, then strong duality holds. The strong duality assumption here is also very mild, and all examples previously considered in the literature satisfy strong duality, for example [HHRW 16, Section 4] and [HZ18]. However, these works fail to take full advantage of strong duality. We fill the gap by noticing that strong duality actually restricts p" to an E space.
Lemma 3.8 (Strong duality implies bounded p²). Let p" : arg minp20 D(p). Then, under assumptions 2.5 and 3.7, we have (b,p") < " and (1, < a with b = min,((,))
7
76
The above lemma indicates that p" lies in the interior of a scaled simplex, suggesting the best choice of potential function could be the negative entropy function, which better fits the l geometry. However, negative entropy (ww) = >" Wy In wy is widely known to be 1-strongly convex only
on the probability simplex A := (w > 0 (1. w = 1}. To tailor it for our studied problem, we parameterize the negative entropy (ww; 0) := Σ Tf (0,w,) In (0,w;) with 0 > O, and show that also strongly convex in scaled simplex.
Lemma 3.9 (Strong convexity of parameterized negative entropy). Let the parameterized negative
entropy d (w: 0)= ;= ΣT= (0jw,) In (0,w;) be defined on RT, where we define yi = 0 and 0 In 0 0
7

---

by continuity. Then (ww: 0) is (oin)(0 Ktstrongly convex in w w.t.t II-Il in a scaled simplex A int (0) == { > 0 (0, w) < K}. K
is immediate see that if we set 0 1 and K then Lemma 3.9 recovers the well-known result that negative entropy is 1-strongly convex. For our studied problem, we can let the negative entropy be parameterized by b, and use ((u;; b) = د (b,wy) ( In (bywy) for the Mirror Descent update step (6). This does not compromise privacy, since b is universal upper bound and is not associated with any specific agent. Now, we are ready to improve the algorithm's 's performance.
Theorem 3.10 (Improved utility& & feasibility guarantees). Let b == maxz(b;), & miny (b,}. Under assumptions 2.5 and 3.7, running algorithm A with parameterized negative entropy ((w; b) with radius K :- 23/ Pj (1) K/(mb,), Vj E [mm] and same T, o² as in Theorem 3.5 yields
8v27 VIn (2m)
(utility guarantee) F(x") - EA [F(x
Ce,
b6
A 22 In (2m) [2 + b. (In (mb) 1)_1
(feasibility guarantee)
E 0
Ce,5.
?b 11-1pp111
Compared to the results in Theorems 3.5 and 3.6 where both dependencies on number of constraints are vm, the results here have better dependencies of In m. Moreover, following our interpretation of algorithm performance discussed in the Introduction, Theorem 3.10 implies that the algorithm's ultimate performance is Ö (CE,5) + m Ö (VE.s Ô (m/C5,5) The additional m factor comes from m constraints, since the feasibility guarantee in Theorem 3.10 is for any single constraint.
4 The lower bound
Some post-pre post-processing lemmas for JDP are necessary to prove the lower bound.
Lemma 4.1 (Self post-processing for JDP). Let M 2n + Xn be an (e, 8)-JPP mecha- nism and denote its output by M(D) == (M(D),,..,,MO) an arbitrary (randomized) function that can be applied element-wisely to M's output. Then, (f(M(D),, 21),..., f(M)...,[[(({) f(M(D)) (n))))))))) Zn)) is (E, 8).DP
Let f X x 2 + y be
Lemma 4.2 -Post-processing for JDP). Let M Z" + Xx be an (E, 6DDP mechanism and denote its output by M(D): := (M(D) .(.))...()),,,,.
+ Let f :f:x x=-11, + be arbitrary (randomized)
function that can be applied to any collection of n - 1 elements of M's 's output. Then, for any k [m]. ((M(D)-x) and (LM(D'))x) are (e,8)-indistingee -innisstinguishable."
Lemma 4.1 confirms that processing each JDP output with the agent's own data preserves JDP. Lemma 4.2 says applying any operation to elements of two n-length JDP outputs obtained from a pair of neighboring datasets will be indistinguishable.
To see how these two lemmas help, we consider the allocations A= (xr xx) outputted by JDP algorithm A: nh -> X". By Lemma 4.1, their consumptions (a, (a )... an (mx)) are also JDP. Furthermore, for any collusive group without agent k, their total consumption Lige a, (ar²)) should be insensitive to agent k's allocation by Lemma 4.2. To ensure insensitivity, intuitively but informally, any algorithm A outputting feasible allocations should reserve some resource exclusively for agent k. But the reserved resource is wasted in some scenarios, which leads to the lower bound.
Theorem 4.3 (Minimax lower bound). For E Z max(1, (/(n),))000 0 < 8 < 1/2, there exists dataset D satisfying assumptions 2.5 and 3.7 such that any (e, 6)DDP algorithm A outputting feasible allocations will lead to a utility loss at least m/(4s) Therefore, the minimax lower bound is
inf sup (F(x" - EA (F(a)(D))) 2 A JDJ
m 4E
The lower bound here nearly matches upper bounds given by Theorem 3.10 up to some logarithmic factors in m and 1/5. Therefore, Noisy Dual Mirror Descent is near optimal, under our interpretation
Twwo random variables X, Y are (s, 6) indistinguishable if both Pr[X E 8] < Pr [Y E S] + 8 and Pr E S] Pr S] + hold for any subset S.
8

---

of algorithm performance. However, the result is limited to max(1,1/(m)) and it is interesting derive lower bounds for other We provide a promising direction in the Appendix, which involves a lower bounding optimization problem with hockey-stick divergence constraints. We conjecture that couplings and divergences employed by [BBG18] are promising tools for this purpose.
5
Numerical experiments
5.1 Workforce scheduling
Workforce scheduling is about establishing a shift schedule for a given period to maximize workers' to- tal preference while meeting worker availability and shift coverage requirements. Workers' preference and availability are private data to protect. We consider simple case of scheduling n workers for m 14 days with data publicly available [Opt24]. In this case, (i) each worker has preferences C, E 2. and utility function is u, (æ,) = (c., 24); (ii) shift requirement Ty E Σ+ is imposed on each day j E [m]] ie.. the number of workers needed for day j. which couples all workers; and (iii) workers' availability and shift limits described by polyhedral set X; == {a; E [0, 1 : S (1, æ)) S u The problem
modeled as max |Σ Di=1 (c,, Z.i) Σ, x; r: I; E X, Vi}. While this is small case, it is suitable for visualizing decisions and understanding the impact of JDP. Moreover, since the optimal non-private p [0. 3, 1, 0, 2, 0, 0, 4. 2, 0, 0| is sparse vector, one can expect MD equipped with negative entropy to perform better.
Figure shows the final decisions under various e, where the rightmost is the optimal non-private decision where value of 1 means arranging the person to that day. Private decisions are fractional
10
20
Zillin
Pauirn
Mansumi
Day1
0.
10
00
57
00
0
00
BC
A
NO
1
00
0
8
0
10
1.0
Day2
13
8.6
0.0
0.0
8.0
6.5
100
00
00
10
0.
12
0.
0.9
0.0
69
67
1
61
0.0
00
05
Dayd
10
10
50
122
10
5.0
10
10
CU
0.8
08
0.0
0.0
00
0.
09
50
Days
0.5
Day7
000
3D
Daya
09
52
0.3
03
CL
Days
10
0.5
5.0
00
67
00
0.0
0.0
Cn
004
Day10
0:
6B
1:5
00
2.
00
0.0
00
0.5
05
0.8
1.
C0
0.0
0.
30
D.Y
0C
C.I
Day11
09
0.0
0.9
1.0
1.0
1.
0.8
50
8
10
03
10
0.9
0.
0
1.0
02
1.0
07
0.
0
10
0.1
10
Day12
13
0.1
9.5
01
80
00
1:
60
00
1
10
00
00
Day13
T3
00
02
Day14
0.0
Figure 1: 7-person, 14-day rosters under various E. Algorithms parameters: potential function is negative entropy parameterized by b = 1; K = 1.1u/(>)), 5 = .01, T = 10a Other settings follow Theorem 3.10. Results reported are averages of 50 runs. Strong duality holds due to linearity.
and can be interpreted as probabilities. It is not hard to see that private decisions are in similar pattern to non-private decisions, and many private decisions are exactly the same as their optimal non-private counterpart. Moreover, private decisions different from their non- non-private counterpart converge gradually as & -> oo, see for example, the decision of (Dayl, Marisa), (Day2, Marisa), and (Day4, Vincent). Optimality gaps and constraint violations are shown in Figure (left panel). For all
K. constant=1.1
K constant=2.0
25
optimality gap (%))
total violations
20
15-
10-
5-
2
8
10
10
8
Houee (290)
MO.P (oun)
Mouse
MD.P MD.
Figure 2: v.s.optimality gaps constraint violations. More discussions in Appendix C.

---

curves, the lower the better. It is clear that our algorithms have significantly smaller optimality gaps slightly higher constraint violations.
One may notice that the constant of K is 1.1 rather than 2 suggested by Theorem 3.10. This is the consequence of parameter tuning, and show its impact in Figure (right panel). Comparing the two plots in Figure 2, it is obvious that larger K_constant leads to conservative decisions: fewer constraint violations but higher optimality gaps. Moreover, when K_ __onsttttt is 2, our algorithms achieve lower optimality gaps at the same level of constraint violations.
5.2 Assignment problem
We next consider three large-scale assignment problems with (m, n) (8, 800), (15, 1500), (30, 3000), aiming to maximize aggregated utility by assigning at most one unit to each agent. The problem is modeled as max (Ei=) (c;, T.) E; mx S my æ; X; Vi) with X; {æ; [0, 1]" : (1, a S } being unit simplex and mxn" := [m...., [m] being a consumption matrix concatenated from n/m m identity matrices. Raw data of e; are available [Bea04]. In this assignment problem, p' > 0 is strictly non-zero. We run experiments and report results in Table 3.
Table 3: Algorithm performance, mean:ssd
Optimality gap
F(we) F F(
x 100%
Total constraint violation
|| |
||
Alg.
6=1 1
2
5
10
=
2
5
10
800
[HHRW16 16]
-1.8+26
4.3432
5.3428
3.8+15
84.8
46.2+168
19.0
11.0.5..2
MD 12 (ours)
1,8+39
1.3+23
0.8+0.8
0.5+05
27.7+120
12,7+8.3
5.1
2.7+1.6
MD ne (ours)
2.1
2.0+22
0.7+0.9
0.4+0.
23.9+13.
9.2+6.7
4.7+3.4
2.6+1.5
1500
[HHRW 16]
-6.9415
1.8+14
13.8+13
12.3=0.9
256.72160
156.8420.8
30.3-108
15.7+667
MD 12 (ours)
4.3+33
2.8+23
1.2+0.8
0.7+0.7
54.6+18.5
15.1+14.8
12.644.6
7.2+3.3
MD (ours)
6.0+44.1
3,0+2.1
1.1:00
0.6
47.8+23.0
25.8+1200
13.4+5.9
4.5+:2.5
3000
HHRW16]
-29.4
-18,9
6.9
8,2+110
> 10
> 10
743, +25.7
680. 1+:4944
MD 12 (ours)
4.3+5.1
3.0+24
2.0+1.
1.5
193.9+54.1
97.2+23.9
39.8-126
22. 22.0
MD ne (ours)
10.4+5.
6.1+3.0
3,0+11
1.6+0.6
134.5+56.4
65.4+25.1
27.948.4
18.1+6.0
Notes. Parameters for our algorithms: K 1.17/(12).
.01. T 10 Other settings follow Theorem 3.10. MD_I and MD_nn 800, 1500, 3000,
level y 1. 0.05, 0.02, respectively, For all values in the table, the lower the better. Bold-better. More results are deferred to Appendix C.
that polential function squared 2g and negative entropy, respectively. For three
From the table, we observe MD_ 12 has lower gaps and reasonable constraint violations for small E; and MD_ ne almost dominates others for large Both our algorithms outperform existing methods.
6 Discussion and conclusion
Limitation of our work. One significant limitation is the restriction of E 2 max(1,1/(m)) to make the lower bound hold. However, we identify promising direction to overcome this limitation in Appendix B.4. Once the limitation is overcame, the analysis may further uncover lower bounds on online cases [SS18], a long-stann stagsiinning open question in private online optimization [CDE-2) 224.
In this work, we considered convex resource allocation problems under joint differential privacy. To solve the problem approximately, we proposed algorithm Noisy Dual Mirror Descent, which privatizes dual variables of hard constraints, and then uses private dual variables to coordinate allocations. A significant merit of the algorithm is its ability to better leverage the geometric structure of the dual space; thus, it is provably near optimal for a large range of privacy parameters. There are many interesting directions for future study. For example, getting rid of the limitation discussed previously is a fruitful endeavour. Identifying a proper DP manner to tune the constant of K is of more practical interest.
Acknowledgments and Disclosure of Funding
We sincerely thank the anonymous Area Chair and reviewers for their valuable feedback that signifi- cantly improved this work. This research is supported by the Ministry Education, Singapore, under its MOE ACRF Tier (RG117/23)
10

---

References
[ABG*23] Raman Arora, Raef Bassily. Tomás González, Cristóbal A Guzmán, Michael Menart, and Enayat Ullah. Faster rates of convergence stationary points in differentially private optimization. In International Conference on Machine Learning, pages 1060-1092, PMLR, 2023.
[AFKT21] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in 11 geometry. In International Conference on Machine Learning, pages 393-403. PMLR, 2021. 3
[BBGI8] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances neural information processing systems, 31, 2018. 9, 23
[Bea04] Beasley. Or-library, assignment problem. http://people. brunel.ac.us juuuel.....u//mmastj/////ee
grribbassignnt html, 2004. Accessed: 2024-May-8. 10
[Bec17] Amir Beck, First-order methods in optimization. SIAM, 2017. 14
[BGN21] Raef Bassily, Cristóbal Guzmán, and Anupama Nandi. Non-euclidean differentially private stochastic convex optimization. In Conference on Learning Theory, pages 479-499. PMLR, 2021.
[BLM20] Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. Dual mirror descent for online allocation problems. In International Conference Machine Learning, pages 613-628. PMLR, 2020. 4
[BLM23] Santiago R Balseiro, Haihao Lu, and Vahab Mirrokni. The hest of many worlds: Dual mirror descent for online allocation prohlems. Operations Research, 71(1):101-119, 2023. 4, 18
[CDE*24] Rachel Cummings, Damien Desfontaines. David Evans, Roxana Geambasu, Yangsibo Huang, Matthew Jagielski, Peter Kairouz, Gautam Kamath, Sewoong Oh, Olga Ohrimenko, Advanc- ing differential privacy: Where we are now and future directions for real-world deployment. 2024.
10
[CKRW15] Rachel Cummings, Michael Kearns, Aaron Roth, and Zhiwei Steven Wu. Privacy and truthful equilibrium selection for aggregative games. In Web and Internet Economics: 11th International Conference, WINE 2015, Amsterdam, The Netherlands, December 9-12, 2015, Proceedings 11, pages 286-299. Springer, 2015. 3
[DR14] Cynthia Dwork and Aaron Roth. algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 9(3 9(3-4):211 10-221--11177 407, 2014.
[GGP24] Tomás González, Cristóbal Guzmán, and Courtney Paquette. Mirror descent algorithms with nearly cammension-indppenden rates for snfferentialll-prrivaa stochastic aadlee-point problems. arXiv preprint arXiv:2403.02912 2024. 3
[GL13] Saeed Ghadimi and Guanghui Lan. Stochastic first-and ordet methods for nonconvex stochastic programming. SIAM journal optimization, 23(4):2341-233 2013.
[GU22] George Gilliam and Nelson A Uhan. Computing payoff allocations in the approximate core of linear programming games a 2022. 3
manner. Operations Research Letters, 50(1):64-77
[1] Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, and Zhiwei Steven Wu. Private matchings and allocations. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing. pages 21-30 2014. 2,
[HHRW16] Justin Hsu, Zhiyi Huang, Aaron Roth, and Zhiwei Steven Wu. Jointly private convex programming. In Proceedings of the twenty seventh annual ACM-SIAM symposium Discrete algorithms, pages 580 599. SIAM, 2016. 3, 5, 7, 10, 24, 25,
[HLL* Yuxuan Han, Zhicong Liang, Zhipeng Liang, Yang Wang, Yuan Yao, and Jiheng Zhang. Private streaming sco in Ip geometry with applications in high dimensional online decision making, In International Conference on Machine Learning, pages 8249-8279. PMLR, 2022.
[HZ18] Zhiyi Huang and Xue Zhu. Near optimal jointly private packing algorithms via dual multiplicative weight update. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages SIAM, 2018. 5,

---

[[1Z19] Zhiyi Huang and Xue Zhu. Scalable and jointly differentially private packing. In 46th International Colloquium Automata, Languages, and Programming (ICALP 20/9). Schloss-Dagstuhl-Leibbee Zentrum für Informatik, 2019.
[NG Chi Jin, Praneeth Netrapalli, Rong Ge. Sham M Kakade, and Michael I Jordan. On nonconvex optimization machine learning: Gradients, stochasticity, and saddle points. Journal of the ACM (JACM), 68(2):1299, 2021. 6
[KPRU14] Michael Kearns, Mallesh Pai, Aaron Roth, and Jonathan Ullman. Mechanism design large games: Incentives and privacy. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 403-410 410, 2014. 3
[Mir17] Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposiun (CSF), pages 263-275, IEEE, 2017. 13
[NY83] Arkadij Semenović Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983. 3,4
[Opt24] Gurobi
Optimization.
Workforce scheduling.
https:// //
gurobi optiiizatin gurrbi-uor---oo - optimods. r readthedocs www.thhhooc-hhoeddccooo com/en/////////c coom//n/aatet///////a mods/workforce. html, 2024. Accessed: 2024-April-33
[SLWA22] Ryan Steed, Terrance Liu, Zhiwei Steven Wu, and Alessandro Acquisti. Policy impacts of statistical uncertainty and privacy. Science, 377(6609):928- 931,, 2022.
[SS18] Roshan Shariff and Or Sheffet. Differentially private contextual linear bandits. Advances in Neural Information Processing Systems, 31, 2018. 2, 10
[VBKW20] Giuseppe Vietri, Borja Balle, Akshay Krishnamurthy, and Steven Wu. Private reinforcement learning with pac and regret guarantees. In International Conference on Machine Learning, pages 9754-9764. PMLR, 2020. 2
12

---

A Proofs for Section 3
A.1 Proof of Theorem 3.2
Proof. Since each individual's ' allocation a depends on all shadow prices (pl)) training trajectory and the individual's own data, by Billboard Lemma 2.3, it suffices to verify the whole sequence (p("), ,.... .) (e, (). We characterize the DP guarantee through Rényi Differential Privacy [Mir17]. Below are some useful lemmas on Rényi DP.
p(T) on the
Definition A.1 ((a, Rényy Differential Privacy, [Mir17]) Let M : + P be a randomized mechanism. For any neighboring datasets 'D ~ D', let P., P' be the distribution (D) and M(D"), respectively. Then, M is said to be s-Rényi differentially private of order a, or (a, RRDP for short, it holds that
Da (I
VD ~ D'
where D. (P (1 = a In
Eq
P(a) Ua
is the Rényi divergence between P and Q.
Lemma A.2 (Gaussian Mechanism is RDP, Proposition 7 in [Mirl7])- Let f :: + Z be a vector- valued function whose global sensitivity is GS == supDwD' [I[ [(D'))l then the Gaussian Mechanism M(D) == F(D) + o(0,,²1) is (a, a-GS² )-DP, for any a > 1.
2n
Lemma A.3 (Composition for RDP, Proposition in [Mir17]). Let M1 + P1 be (a, E1)- RDP and M2 DD x PI P2 be (at, ED).D.. Let X M1(D) be the output of Mi and
== MM, be the output of M2, then the adaptive composition (X, Y) satisfies (o,EE + 62)- RDP.
Lemma A.4 (From RDP to DP, Proposition 3 in [Mir17]). I is an (a,,)-RDP mechanism, it also In (1/8) DD, for any 8 (0.
satisfies (s + a-1
For iteration 4, we notice that data only plays role in the gradient g(p!0; D) nyb (()) through intermediate allocation decision =pp();; arg max F(xx) - (p)))((x)) immediate to show that the Global Sensitivity of gradient function
a(rr)) It is
GS sup [l)(; g(p; D')ll p.DwD''
sup (x:(2:())))) - (p; 21 S |bll (9)
where the last inequality is by assumption that serving one individual consumes most b resource (see assumption 2.5). Then, injecting a zero-mean Gaussian noise n!()) ~N o f) into gradients
g(t) = (0) D) can guarantee (a. a-11b]2 RDP by Lemma A.2.
20
Moreover, the algorithm comprises T' iterations, and each iteration takes as input the shadow price in previous iteration; therefore, T'fold iterations form a sequential composition. Applying Composition
Lemma A.3, we immediately conclude that (g + (2) .....g'!! g(T) + (T)) satisfies (a, To-llb/
26
RDP. As the noisy mirror descent update step in (q.(6) is merely post-processing after obtaining
(g()) (2),, "....,((?)) + n (T),, the sequence (p( " (TT) is thus also (a, Ta-llblá RDDP. Lastly, by Lemma A.4, (a: pair of (e, 8), if we assign privacy budget in the following way:
To-11b11, RRDP implies [Ta||bbI
-0" + (1/6) 8)-DPPPPPP 45 E (0, 1). Thus, for a given
20
Tollb 2
2x² e/2; (1/8)
=//2
we can get
21 (1/8) 1
0² = T 1b61/
+
62
which is the desired variance level.
13

---

A.2 Proof of Lemma 3,4
Proof. For any gradient (()) used for the mirror descent update step Eq.(6), shadow prices p(1) and updated shadow prices p(++1, there exists inequality linking them together (Lemma 9.13, [Bec17]):
p D)
BB(p.p()) B& (D Vt, 17(1)
2a
Summing up the above inequality in telescoping way over t l..... ......To.. gives
T
77
0 2
Bo(p,p(1) Bo(p.p!' (Tt)))
pp - D)
20
1y11)
17
1
Bl(p.
+
1)(l11)
n
When stepsizes 10 17 are the same for all t, the inequality becomes
T
p)5 "
B$ (p.p.2 p())
Σ g (00
1pp0)ppp
20
1
A.3 Proof of Theorem 3.5
Proof. Let us first fix sequence of noises [n()]= Recall that the final allocation decision a: is the average over all decisions along the trajectory and the objective function is concave; therefore, by Jensen's s inequality, F(x-A) 2 + Σ F(x(9). Moreover, by weak duality, F(x=) I ((p(t), Vt. With the above results, the optimality gap F(x*) ) F(x*) can be upper controlled as:
F(x*) F(x-1)
(t) F(x(())
+ Σ F(z)(t)) + (p(().'() - -F(x:(1))
(by definition of dual problem D)
1 Σ
g() (() -0)
1
(t) p(t))
T -
Taking expectation with respect to noises (n on both sides, we can remove the second term on the right hand side in preceding inequality, because (!) is gero-mean and is independent of p(), This leads
F(xx) EA [F(z))] s EA Σ
1
(t) 0
g
The inner summation can be upper bounded by applying Lemma 3.4 with p 0 and () 1) 0, VI; we therefore obtain
T
2
g
F(x") FA [F(x)1) s EA
+ nTT
Bo (0, 200)
(10)
2aT
Here are some helpful inequalities:
(2) + [0
S 2 |g(0) 1? + 22|n001
9
g (1)
mb a( || S sm 1bb|,
14

---

Denote G := ?==² 1b]12 and GA + Et=1
|n(
Using above helpful inequalities, we
upper bound + + || as
2
T
T
Σ
S
AG
(11)
Plugging (11) back into (10), we further reach an upper bound:
EA [F(ard)] - 7 (G EC+EAAC GAl) F(x²)
1 nT
Bo (0.
a
Because GA = + Di=1 (+) and (!) ~ NO, o² mxm) with Tc,,s: Vl, direct calculation
gives E [GA] = o²E ||=1|]] with NNO, I mx)) being standard Gaussian random vector.
Therefore,
F(x²) - EA (F(xd) S n' of
+
Bo (0,0p rT
a
Let Co(p(1)) (0. p(1)//)))a. Then, plugging in the stepsize
a (..pp.)()) TE(===
leads to
(G+0²B [1=11e] (0,
-A [F(x*)] s $21
aT'
VG VT
(x)
+ Voe,o
V [|=1|]]]
(by 0² Tce,s) (12)
Lastly, if we run sufficiently many iterations T
get the stated result in the theorem.
|
A.4 Proof of Theorem 3.6
Proof. We first briefly introduce the idea for the proof. We will find lower bound and upper bound for the cumulative stationarity gap Σ (g((() (()) - p) Lemma 3.4. With properly chosen p E RT n W as a bridge, comparing these two bounds leads to the desired conclusion.
For a given final allocation decision a we denote the resource underage level by
0 = (a(x - -
where the positive part operator (-)+ applies demeent-wise It is self-evident that w > 0 by definition, and 4 implies no constraint violation. Let j = arg max [uz*] be the index of the most-severely violated constraint. Specially, if j = 0, then we know b 0, and we are done. Otherwise, we EjA be an indicator vector with 1 on its (jA)'s position and 0 on others.
Choose p == Ceja E RT cumulative stationarity gap Σt= (g(t), (t) Ceea) into
W with a constant C' to determined later, we reformulate the
(t) Ceju
Σ g (t) (()
(g())
-Cegs)
Σ n (t) -Ce.,)
(1x)
(xe*)
and control the three terms one by one.
15

---

(+): First, rewrite (*) into function of dual form:
(+) Σ F(x)1)) + , g0)) F(ar!)) = Σ D()l - F(all)) 2T. (D''D(p") - F(xx*)]
(13)
where the last inequality is from D(p(0) 2 D(p") and applying Jensen's inequality to F(-). Next, we turn to control F(z-). We observe that if more resource v becomes available for the original allocation problem, then 2 will be feasible allocation. Hence, can upper bound the value of F(**)) with another problem having more resources. Denote the set of feasible allocations when resource available by (b)
(ar (æ1,.... Fn) 1 a(x) S b). We have
F(x*1) S
max xEX(mpb+or)
F(x)
(x is feasible)
max
{F(x) + (p, + 0 a(x))}
(weak duality, Vp P)
# N
D(p) (p. vら
(dual form)
(14)
Let p (14) be p = p", and plug (14) back into (13), we obtain
(+) z T (p" v -7 -T|||~~ ||p
(**):
The second term (**) helps characterize constraint violations:
T
I
(**) =
8 egu = CT
Σ
alx(1)) myb, esa
1=1
1=1
2 CT (a(x*) nyb, eja)
(by assumption a(-) is convex)
=CT 1|
(by definitions of A and e,a)
(#o*): The third term (* *) involves zero-mean Gaussian noise vectors (n("), } that are in- dependent of p(), While Eja is dependent noise vectors, the dependence is not big is- sue here, since eja E Ej = {e E 10m (e, 1}. and the Gaussian Complexity ((E,) = Ei, [suPeeF, (e, of the set E₁ can be well controlled:
((Ea) = (z~A((, (m [max (21, (21,...,, 3m s 22 mn.
Therefore, the term (* +) admits lower bound in expectation w.r.t. A as shown below:
T
10 eja )
T Σ
>)
EA (* + =0 - OCC.E. C.A
Σ
2 CC EA
sup cEE
(0) e
1=
-VTTo G(Ei)
2 -CVTo V2lmm
=-T V mnm.
(by o /Ta,,)
Finally, replacing three terms back and taking expectation w.r.t. A, we obtain a lower bound on the cumulative stationarity gap:
T
g (()) -CecCea) | [|o [p) (oil1)-Cr - CT Vce, 2 m. (15)
EA
Σ
Now, we turn to another side and bound the cumulative stationarity gap from above. Suppose we can choose a proper > such that Ceja R W almost surely, the expected cumulative stationarity gap thus can be bounded from above by employing Lemma 3.4:
T
(+) ()) Cee,) )
D
T
11
1
EA
Σ
< EAA
- Ba (CezA,
2
1
16

---

Similarly, denote G == =2? |b|2
and GA == EZ= 1 /T. Then EA [ا v
with z being standard Gaussian vector. Plugging these values back, we (G [1=1(²)
27.
get
T Ceeu S
rT.
( ( +
OZ [1]1]] a
E
g0 0''pp''
EA Bo [Bo(Ce).
BB (0, T-(G+o -
Lastly, using stepsize
results in
T (G ( o
Bs (0, + EA [Bo (eeA,,())))
EA
Σ
g
(t) pp - Ceju)
s
a
v ((.)
T (G + + H
Be (0.0p!))) + maXecr, Bo Bo,Ce.pl
v (0.
-Co,1(p(4))
(16)
Comparing the lower bound (15) with the upper bound (16) and using 0² = Tc,,5, 5, we immediately obtain
Co.(p!")
TEA
| (C 105-1121 -1--'ll'))-)))))) CT /C. Ce.8
2lm S
VTG
E
[|21|
Va
Rearranging the above inequality yields (assume
C> >>1n"|11>
(p(1(
(VG
G + Voe. / [=]
CV2ln
E - 11 S (C- (C-Ipp-hh) I
+ C
Vo.5.
1p'11
(17)
When T 2
6e 5 [==1?]] (17) implies
2 |||=11]] Co, (p()))()) Va- (C - 1p
CV2 m
EA [1|0 ||000
Vce,b-
(18)
C - 1p
The inequality (18) gives an upper bound on the expected maximal constraint violation.
However, the above analysis holds only when constant C' satisfies (i) C > ||p"|, and (ii) Ceja
RT n W for any j E [m]. To this end, we can simply let C 2 2||p" Il, and replacing C' with 2 ||p"|| gives the desired result:
2 E [|=]??]]
(p()
EA [|10~11
+ 2v Inm
(19)
Va. - 1pp
A.5 Proof of Lemma 3.8
Proof. For any agent i, the objective value its individual dual problem is always positive, i.e., max (u, (p* (xx))))) by Assumption 2.5 part 4. With this inequality, are ready to show bounded shadow prices:
ny (b,p") + + (n>b.p") max (F(x) (p", a()))) = nz.
(by strong duality)
17

---

Dividing both sides by my results in (b. I g Similarly, my (1.p"") I (neb, p²) +0
(nyb, p=)
max (F(x)) - (p" a(x)))
ming bj
minj bj
D(p") min, b
F(xx*) min, bj ming bj
(by strong duality)
which implies (1,p") < "y minn by
A.6
Proof of Lemma 3.9
Proof. By the definition of strong convexity, it suffices to show
(miny{0,}) |pp 1p-
(Vo(p:0) 0) (: 0) q)
all. vp.q E A
(20)
K
According to the definition of parameterized negative entropy function, its gradient is (ppp; 0)5
0j In (p;0,) 0j, Vj [m]. By the well celebrated Hermite-Hadamann inequality ʃ( 1( S
1 b-a So f(x) dr, if we use convex function f(t 1. vt > O, we immediately have 2 which implies
a+b S lab-lna
b-a
2 a)² b + a
(In b a) - a) 2
va 0,
(21)
where the case 0 6 = 0, both are obtained by continuity and the conventions that g 0 and 0l 0. we set = P,0 and a = 9j0; for (21), we can get
(In (),0,) In (1) 0,(P; 4) 2 20,(1) (v) 4;)²
Vj E [m]
(22)
Pj + 9j
Summing over j E [m]. we have
20 - -3)
LHS of (20) Σ (In (p,0,) In (.,0,))-86(2 9,)
(by (22))
Pj + 4
j=1
It remains further lower bound the summation the r.h.s. We follow the proof idea of Lemma in [BLM23] to complete our proof:
20, (p, -,)2
05(p; + 9j)
[pj ?
= 2,0.p+
Pj +
0. ②)
(Dz q2)²
2
0f(p; + 93)
[p; 4i
2
(by Jensen's inequality)
(0. p + 9)
Pj + qj
Σ j=1
0g lp; - 45
= (0. +ptoo q)
2
0j PPj 9sl
(since p. Ann (0))
K
(min,
1|p q13
K
18

---

A.7 Proof of Theorem 3.10
Proof. The proof follows the general proof of Theorem 3.5 and 3.6 for any potential function Φ. remains to properly modify results for the & chosen. When the potential function is the parameterized negative entropy & := & ((w: b) Σj= myb, In (wyb,) defined on A (b) := {(w > 0 (b, w) v 2v, 3. the conjugate index oc, strong convexity parameter /2/KK K. Moreover, direct calculation gives the Bregman divergence B& (() - (b. Because we choose (1) = K/ (mbb)) Vj E [m]] we thus have Bx ((t) = K. Pj
}} with K
Utility Guarantee: It is evident that (p v (0((0,(())/ VK/(/K)- K/L. Therefore, the utility upper bound (7) becomes
-(x*)-Ex EA [F(x*)] 4Cx(p"))
B [1=1 Vc,,5
K
22 (2m)- Vce.o= = 8/2 / In (2m) b
VC,,6
74
Feasibility Guarantee: We can work from (19) and first figure out (p Direct calculation gives (Ce,, p()) = (O, p()) + Cb. (InCC/p5)) -1 1) vj E [m]] Plugging C' = 2 |'|||
we can upper bound (p as:
(o.((11)))= = (0, (1) + max, By (Cee.
(0,
|| 11 max, {os- In
2 Jimb K
- -1).0)
= 2VK +
(since p3") = KK(mb;,)
VK
- <2VK K + VK- max (b. (In (mb;) - 1)
(K 2 2 ||p" 11 Lemma 3.8)
3 <2VK VKb. (In (mb) 1)+
Substitute Co, (p back into (19) with K g. we get
EA 11 ||a] S 4th / ln (2m)- [2 + b. (In (mb) - -1}+]
Vce,ō-
yb 11
B Proofs for Section 4
B.1 Proof of self post-processing Lemma 4.1 for JDP
Proof. The proof is for a deterministic function f. The result on randomized functions follows imme- diately as any randomized mapping can be decomposed into convex combination of deterministic functions. The proof here largely follows the same idea for the proof of Billboard Lemma. For any [(xx = 1); ....,.. J (In, za)). For any subset S C y let (S; k) = {a= E x=-1; f(x
X let f(x D D_ = (f .1),.... ((FF--1= ",
fa=+A.1 AA. D-+)) E S} be the preimage
of S with respect to the mapping f(, R). Then, we can show that
Pr (f D_x) e S]
Pr E < e Pr f + (M(.) is (E, (IDP)
e Pr E$
e - (+( D's)) E +5, (D=+= DD-
which confirms JDP guarantee after self post-processing
19

---

B.2
Proof of post-processing Lemma 4.2 for JDP
Proof. Similarly, the proof is for deterministic function f. Let (-) be the preimage of S. For
any S yy:
Pr()(M(D)=+) e - Pr [M(D) S E Pr [M(D) + (M(-) is (s,
= - (
B.3 Proof of Theorem 4.3
The proof consists of several steps: (i) construct "hard" distribution of datasets; (ii) identify necessary conditions on the JDP algorithm A with the help of Lemma 4.1 and 4.2; (iii) reformulate the minimax lower bound into a better form that aligns these necessary conditions; (iv) combine all steps together. Without loss of generality, we assume b 1.
Step 1: Construct "hard" distribution of datasets.
Let Id(-) the identity function, and let and be vectors of and 0's whose lengths are m. Define three types of requests:
2 = (x: + (1,z) Id(-), fix : E [0, 1}});
z = x + (1,x). Id(-), {1x : min
= (x - (1,z). Id(-), x 0}).
All three types of requests are the same in their utility and consumption functions, both taking linear forms. It is also easy to verify that all three types of requests satisfy Assumptions 2.5 (part and 2). In what follows, we construct datasets that satisfy Assumption 2.5 (part and 4) and Assumption 3.7 well.
Based on these requests, we construct pair of neighboring datasets that differ agent n only:
Do , 2²);
D1 2 2²-.
requests
requests
is easy to verify that part of Assumption 2.5 is also met, i.c., the primal problem is always feasible, and the optimal shadow price is p' 1. which are non-zeros. The result p' is by noticing that one unit increase available resource will increase the objective value of the primal problem by 1. Since p' 1, it immediate (xxx)) + (p", (x,)) becomes (1. x;) + (1, -z;), which always non-negative for any æ; E X;- Moreover, the constraint to be dualized is a linear constraint; thus Assumption 3.7 strong duality holds.
that part 4 of Assumption 2.5 also holds, because
the function
Lastly, let dataset 'D be drawn from Uni D. i.e. uniformly distributed over these two datasets.
Step Identify necessary conditions on JDP algorithm AA
Let AD) = (D) x (D)) be the output of (e, 6)JDP algorithm A. The self post- processing Lemma 4.1 says that if we process each x: with i's own data, the resulting output is still JDP. That implies (Id(2))),... Id.(())()))))) should also be (e, d)DJP. Moreover, the post- processing Lemma 4.2 indicates that the aggregated consumption, excluding agent n's, should be indistinguishable even if agent n's data is changed, i.e.,
Pr Σ Id(a (D)) E
Σ (M(a((D))) E + VS S [0, int
Instantiating the above inequality with D Do. D' = DT, and = (my1 - cl, ny1] with min(1,ng) noy leads to
Pr Σ of (m1 c1,
S Se
Σ xD((D E (ny1 c1, +
in
izfn
20

---

We can simplify the preceding inequality by changing decision variables from bold format 2; to normal format z4. because by construction requests 2, 2 22, each decision vector æ; = 1r, is fully determined by single scalar This leads to the following equivalent inequality,
(Di) E (ny - -mmm +
Pr
Σ x (Do) E (my - c, Enf
P Σ iggt
-,,
(23)
Moreover, when dataset is D1. agent should always be assigned e unit, forcing resource available for others to be at most nyy c. Thus, if A an (e, 6JDDP algorithm outputting a feasible allocation with probability 1, then Eign 27 (D1) ny w.p. 1, and (23) becomes:
Pr
Σ oe (Do) (n7 e, n7l S
(24)
Therefore, get necessary condition (24) for any A being (e, 8)-JPP when dataset is Do. Algorithm A should not assign many resources to other agents, and only with a small probability 8, other agents can get at least ny resources.
Step 3: Reformulate the minimax bound
Let A E [0, nyy] be constant to be determined later, and let S = (n1 - A ny). S = 0, A] be two disjoint regions partitioning the interval [0, ny)- Let E {0, 13 be an indicator so that 1 in j's position implies (E= >;)); E S otherwise, in S Let event Ex == ((11....,an) v.)
{(E 2;55 E ) = I, Vj E [m]] With these notations and the law of total probability, we first rewrite the expression of Algorithm A's utility when dataset is Do as:
EA [F(x (Do)) =
E
EA
Σ (1, 2z (Do))
(Do(D)) E Ex - Pr (Do) E Ez]
(0.1))
iiml
m ΣΣ
Σ
EA
a (Do),,
(^( Bx
Pr Pr(x<(Do) E Ez]
IE(O.1)"M
m
Σ
EA
Σ
Σ
x^(Do) Ex
Pr (DA( e Er]
IE(O.1)
observe that when event Ex happens, the resource consumed (Ei= az (Do)), no more than either ny A or nty, depending on Iy. Hence, we can reach an upper bound expressed by Zy:
EA [F(x (F())(DD))] <
Σ
EA
Σ
- = ny (I, = =13] Ex
Pr [D) E Er]
ZE (0.1)
5=1
Σ
EA
mmr Σ
Al (I, 0 Ex
Pr x (Do) E Ezl
j=1
mny
Σ
Σ
E 11,-= =
Ez Pr (a(o) E Ez]
1=1 [
= -myy - A
EA [1 -I
j=1
mny - A
Σ Pr
Σ x (Do)
E E
,
21

---

Due to the construction of Du that axd == 1xz,, the probability terms in the preceding inequality should be the same among all j 1,..., my thus, have
E [F(x* & mnry mA Pr
Σ x (Do) (Do) E S
Moreover, with Do, the allocation agent should be 2,/ 0, modifying the preceding inequality into
EA [F(x* S mny mA Pr
Σ
(Do) ESA inghn
(25)
We note that with either dataset Do or D1, the optimal utility obtained in the non-privatt setting is always mny, i.e., (Do)) F(x=((1)) mny. As result, the minimax regret is lower bounded as follows:
inf sup (F(x*(D) - EA [F(x
inf As (e. JDD
(n- [F(x* (D)) EA
A (e, 6DP D
1)
1
inf
mny
mmn mA Pr
ΣaA(Do) E 55
2
A (c, ().6)-
it
mA
inf A (e, 6)-JPP
Pr
Σ (Do) 10, A] (26)
ifn
where the second inequality is by considering Dg and plugging in (25).
Step 4: Combine all together
Suppose
E 2 max(1, 1 (mr)). If we set A = 1. the r.h.s. of (26) becomes Since 1/e s min(1, my) c, it follows that
inf Pr Σ iinn (Do) 10,
1/
Pr Σ 2 10,ny 1/=]
> Pr
Σ (Do) 10, - d
ifn
ifn
= 1 - Pr
1 (Do) E (n7 c, n7)
if
2 8 2
(by (24) and E (0, 1/2))
Plugging the preceding inequality back into (26) immediately leads
inf sup (F(xx(()) - EA [F(zA 2 46 A (e. D
m
which completes the proof.
B.4 Discussion lower bounds for general
The lower bound in Theorem 4.3 only holds for e 2 max only use feasibility of A to prove the lower bound: "we reserve some resource exclusively for agent k." The optimality condition of A in the minimax expression inf supp is not used. Noticing this oversight, we provide lower bounding problem that fills this gap.
1/(m))] max(1,1/(m7)),
Intuitively, this is because we
We start with expressing DP in terms hockey-stick divergence. Suppose I and p are two probability measures that absolutely continuous with respect to each other. Let Hx,(X, == + Jsez du (z) c²) dp'(z) be the hockey-stick divergence between two random variables X, Y. app
22

---

Let MM be an (E, 6)-DP mechanism, and let elements projected to others than agent Here are some relationships among indistinguishabiiity; DP, and JDP.
:= =- be the random vector of n 1
(e, 8) indistingguihhabblltyy.. if He (X, & 6, then is said to be (e, 6) -iniistinguisaable from Y:
(c, 6)-DP for mechanism M, if suPDwD' Hos (M(D) S o, we say M is (e, 6)- DP [BBG18];
(e, 6)JDPP for mechanism M. if supp He (M(D) M(D')- S 8, we say M is (..D).
It is self-evident from these relationships that DP requires indistigguisaabiiity between outputs for any pair of neighboring datasets, while JDP requires indistigguishabiiiy between projected outputs without agent k for any pair of neighboring datasets.
To obtain another lower bound exploiting optimality of A. we can follow the idea and notation in the proof of Theorem 4.3, but consider different neighboring datasets:
D = (2" 2....,.), n.l requests
D.+ (2 2,...,3), 22, Dl+22 = (2
n- requests
n-2 requests
It is obvious D ~ Di+ and D'- ~ + are pairs of neighboring datasets. Let (=xxx>
Eijer 2z be the total consumption excluding agent By the definition of (e, JJDDP, any JDP algorithm A should satisfy following necessary constraints:
H& 1 s 6;
(27)
Ha ()( ())) s
5;
(28)
H. (==(_=)(=1((+++))))
))) S <;;
(29)
Her
(30)
The variable (A(+++22)) in both constraints (28) and (29) should the same, and thus links both constraints. Moreover, the variable x (D'-) in constraints (27) and (30) are the same. Therefore, the four constraints form a loop restricting each other.
The four constraints (27)-(30) are necessary conditions for any JDP algorithm. Furthermore, the dataset D here is essentially the same as Do the proof of Theorem 4.3; thus all analysis for Do can be borrowed. Consequently, following the same analysis for (26), we get a lower bound expressed by an inf problem:
1
inf sup (F(=* (D)) A is (c. JDP D
(D) - EA [F)))
inf Pr S (_ e (0, n7 2e Ast. (T)
We believe analyzing the inf problem with tools in [BBG18], such couplings, is promising. After this base case, one can easily extend the set of constraints (27)-(30) to take account of more loops.
C Additional results of numerical experiments
All experiments were run on PC with an AMD 3700X CPU, 16GB memory: no GPU was used. The algorithm was implemented in Python 3.11, and optimization was solved by scipy.optimize.mnnie minimiize method. Source code is available in supplementary materials. Datasets are publicly available as discussed in the main text.
C.1 Workforce scheduling
When running the algorithm, the only parameter different from Theorem 3.10 is K : 1.1u/(7b). where Theorem 3.10 suggests K == 2 (rk). The constant factor modified from 2 to 1. result of hyperparameter tuning. We discuss the tuning and its impact later.
We first report optimality gaps in Table 4. It is clear that our algorithm, equipped with either potential
23

---

Table Optimality gap (F(x*) -(xx)) x 100%. meantsd
Algorithms
MD ne
MD 12
[HHRW166], Algo 1
8 [
2.14
9.1 9.1-3.8
3.8
21.5 1.2
2.8+2.1
7.4
21.8=1.2 1.2
1.9
6.6 4.7
22.4 1.0
E 10
2.8-2.1
5.3=4.1
23.3= 1.0
8 20
2.8-2.44
4.2-2.9
24.2=1.0
Notes. run our algorithm Noisy Dual MD two potential functions: negative entropy (abbr. ne) and squared f2-norm function (abbr. E2). Settings are the same as in Figure 1. bold=hetter
functions, always outperform the existing method. However, the performance "A w. neg.entr" seems independent of and the performance of [HHRWIO 16] seems worse when increases, both of which are strange. The observations here are because the optimality gap itself does not reflect the whole picture, for example, constraint violations are not reflected. We thus report constraint violations Table below. It should be clear from Table 5 that constraint violations are reduced
Table 5: Constraint violations, meantsd. Settings are the same as in Figure
Total violation
Max violation
MD ne
MD 12
[HHRW16, 16]
MD nne
MD 12
[HHRWI6, 16]
7.9
6.7
4.940.77
2.7+00.4
2.840.6
2.0
8
7.0 1.2
6.7
4.6.E0.7
2.4:0..5
2.74:0.7
1.94:0.4
E
6.4
5.6
4.3:50.9
2.140.44
2.44:0.6
2.0
10
1.1 4.1+1.5
3.4--0.8
1.8400.4
1.7+-0.5
1.6-10.4
20
1.2
2.9+11.0
2.1
1.4:10.4
1.2.10.4
1.2.10.4
when e increases, which indicates that our algorithm can maintain good optimality performance while better reducing constraint violations. While [HHRW 16] has the lowest constraint violations, our algorithms' constraint violations are only slightly worse.
Runtime For this workforce scheduling problem, the runtime of our algorithm varies from potential function to potential function, see Table
Table 6: Mean runtime (in seconds) per thousand iterations
MD ne
MD_12
[HHRW16]
19.6
2.2
1.0
8 19.9
2.2
1.1
E ==
19.7
2.1
1.1
10
20.6
2.1
1.0
= 20
21.2
2.2
1.1
Impact "K constant" From our experiments, we found that the constant factor K significantly impacts algorithms' performance. To avoid confusion, we want to point out that the algorithm by [HHRW16] set K_constant to be 2, a fixed value. But for all results Appendix here, we let their K_constant change well, in order gain more understandings of its impact. We find that, when the constant close to 1, the final allocations are more likely to achieve a smaller optimality gap, but violate constraints more severely. On the other side, when the constant increases, the final allocations will violate fewer constraints, but end with a larger optimality gap. In other words, the constant of K trade-offs between optimality and constraint violations. To see the trade-off more clearly, we draw Figure 3. The x-axis represents the constant of K, the left y-axis is optimality gap, and the right y-axis is total constraint violation; and for all curves, the lower the better. It evident that when K. constant is small, we get smaller gaps but higher constraint violations. Additionally, when takes large values (say, e 5, 10), constraint violations of all algorithm are at almost the same levels, but our algorithms have better optimality performance. One may notice that when K_ constant=1,, the optimality gap negative, which means F(x=A) F(x=). Considering A may violate some constraints, this phenomenon is possible.
24

---

10
optimelity gap (%6
20-
violetionns
1.00
1.2
2,00 1.00
1.50
2,00 1.00
1:30
2.00
1.00
1.25
1.00
1.70
K_
Konosttnnt
K_constant
K_ K_constant
"__oosstant
ID,R))
30um)
(Dum)
Figure 3: K_ constant optimality & constraint violations. Settings are the same as in Figure 1 except K_ constant. Shadow areas and error bars indicate 95% confidence interval.
C.2 Assignment Problems
We repeat Table 3 below for discussion convenience. When reading the table, we should keep in mind
Table 7: Algorithm performance, mean (this table is copy of Table 3)
Optimality gap
F(xe") )
100%
Total constraint violation
F(
72
Algo.
E = 1
10
E
2
5
10
800
[HHRW16 16]
-1.8
4.3
5.3128
3.8115
84.81184
46.2.116.
19.019.3
11.01:5.
MD 12 (ours)
1.8119
1.31223
0.8.0.8
0.5
27.71120
12.718.3
5.1
2.7:1.6
MD_ne ne (ours)
2.1440
2.0+22
0.7409
0.4
23.9
9.2+6.7
4.7
2.6+1.5
1500
[HHRW1 16]
-6.91115
1.8:144
13,811.3
12.3=09
256.7
156.8.208
30.3
15.7
MD 12 (ours)
4.3.134
2.8.23
1,2.108
0.7.0.7
54.6118.5
35.1
12.6146
7.2
MD ne (ours)
6.044.1
3.0+2.1
1.1:09
0.640.6
47.8+230
25.8+12.0
13.445.
4.5
3000
HHRWI6
-29.4+0.9
-1.9
+1.2
#1.2
8.2+1.
>> 100
> 10
743.8
680. 299.4
MD 12 (ours)
4.3+5.1
3,0+24
2.0+13
1.5+0.7
193,9454.1
97.2+23.9
39.8-126
22.0+6.3
MD (ours)
10.4+55
6.1+3.
3,0+11
1.6=:0.6
134.5+36.4
65.4:25.1
27.9
18.1
potential function is squared &a and negative entropy, respectively. For three cases n = 800, 1500, 3000, we set resource Level = 0.1, 0.05, 0.02, respectively. For all
Notes. Algoritim parameters:
1110((bb) 01. 10".
Other settings follow Theorem 3.10. MD and MD
table, lower better. Bold=belter.
that optimality gaps should be understood together with constraint violations. Some observations from the table are:
When e is small (s 1, 1, while [HHRW 16) achieves the lowest optimality gaps in most instances, it achieves them at severe constraint violations, which might be not acceptable in practice. In contrast, our algorithms have reasonably satisfying optimality performances and much smaller constraint violations.
2. When E gradually grows, our algorithms have a clear pattern of convergence, i.c., smaller optimality gap and fewer constraint violations; but the pattern for [HHRW 16] is not clear enough. We conjecture that this is because of hiri-variance noises injected.
3. If constraint violation matters, MD_ne most preferred.
Runtimes reported in Table 8. Compared to existing methods, algorithms do not observe a significant increase in runtime. Moreover, as we set = 10 we can in fact complete training within one hour, even for the largest case with 3000.
Runtime
Dual convergence Figure 4 shows the progress of dual variables convergence. The y-axis is the gap between dual variables by algorithms and the optimal dual variables, while x-axis is the training progress. Shadow areas indicate standard deviations. It is evident that when e is larger, dual variables converge faster to optimal values, and stay around the optimal values in remaining iterations. When a is small, say 1, dual variables still show a converging tendency. Moreover, dual variables by MD ne converge much faster, which further justifies its better performance observed earlier.
25

---

Table 8: Runtimes per thousand iterations, seconds
Algo.
1
2
5
10
800
[HRWWIG 16]
47.0
49.1
49.3 3
48.9
MD 12 (ours)
49.2
50.6
48.7
50.0
MD_ (ours)
52.9
54.5
56.0
52.4
1500
HHRWI61
161.1
163.5
158.1
171.3
MD_II 12 (ours)
236.0
242.6
242.3
228.1
MD_ ne (ours)
248.1
227.3
250.8
249.9
3000
HHRWI61
321.3
348.1
368.9
379.3
MD_ (ours)
345.6
312.9
333.6
321.0
MD ne (ours)
335.7
331.8
326.4
326.7
800
1500 1.0
1500 Varegs 2.0
1500 Vareps 5.0
1500 10.0
upcale, 2Vl
md.5 2
3000 vareps 1.0
n- 3000 Varegs - 2.0
n- 3000 varegs 5.0
3000 vareps 10.0
10-
03 80
20
80
80
100
23
40
60
100
20
40
60
100
Training progress 5/7 10005
training progress x/Tx 100%
tnaining progress x/Tx 100%
training progress C/T 100%
Figure 4: (prefix averaging) dual variables converge.
26

---

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]
Justification: Theoretical results claimed in the abstract and introduction are summarized in Table 1, wherein cross-references are provided to point to specific theorems and sections.
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 the paper and important assumptions and limitations. A No or 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.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discussed limitations in Section 6 with a paragraph starting with Limitation our work.
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 a 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn 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 on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be 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 low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an 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
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
27

---

Answer: [Yes]
Justification: For assumptions applied to most theorems in this paper, we give a summary in Assumption 2.5. For theorems needing more assumptions (or specific parameters), clearly stated these assumptions.
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 the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to 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 supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: In the main text, we disclosed dataset source, hyperparameter values used for experiments, and algorithms. For the sake of limited space of the main text, we deferred more implementation details to Appendix C, such as PC specs, coding language, environments, and etc. Moreover, we also provide source code supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending 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, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a 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 NeurlPS does not require releasing code, the conference does require 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 partieular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
28

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Datasets used for experiments are publicly available. We pointed to these data website with proper hyperlinks and references in the main text, see Section Numerical experiments. Also, source code is released part of supplementary material of this submission.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips cc/ mublic/guides https//oooSummmsiiionniom
for more details.
While we encourage the release of code and data, we understand that this might be possible, "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 NeurIPS code and data submission guidelines (https: //nips "nips.ccpppii wwtpccccppppccceccccccccccccceee / ssionPolicyy for more details.
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. If 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 the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
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 understand the results?
Answer: [Yes]
Justification: In our case, experiment settings/details are mainly about algorithm hyperpa- rameters. We clearly state them in captions of corresponding figures.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: all figures and tables, indications of statistical significance, such as standard deviations and confidence intervals, are properly reported.
Guidelines:
29

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi-
dence intervals, or statistical significance tests, at 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 run with given experimental conditions).
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.
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 not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative етror rates).
If error bars are reported in tables or plots. The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide computer resource information in Appendix C at the very begin- ning. Also, runtimes are reported for each experiment in Appendix C.
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 make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : /tt//nnursp...// httpppl///ttissuiiiiiiieeaaa
Answer: [Yes]
Justification:
We have reviewed the NeurIPS Code of Ethics thoroughly.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
30

---

Justification:
This is theory paper. It hard to judge its societal impact.
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.
The conference expects that many papers will be foundational research and not tied to 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 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 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 is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification:
Not applicable, as our work is theory paper.
Guidelines:
The answer NA means that the paper poses no 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 to 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses 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: Our work is theory paper. And experiments do not need existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
31

---

The name of the license (e.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 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.
If this information is available online, the authors are encouraged reach out to the asset's 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:
Not applicable to our theory paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing 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 as details about compensation (if any)?
Answer: [NA]
Justification: Our work does not involve crowdsourcing nor human subjects.
Guidelines:
The answer NA means that the paper does 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 in 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: Our work does not involve crowdsourcing nor human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
32

---

Depending on 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 we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "6w06a28UVd", "reviewer": "Reviewer_kLe8", "summary": "The submission studies jointly differentially private algorithms for resource allocation problems, which are a broad generalization of packing linear programs. The work addresses this challenge by considering a primal-dual formulation of the problem, and running a noisy mirror descent algorithm on the dual. Standard analyses of the mirror descent method and the impact of noise addition then provide bounds on the suboptimality and approximate feasibility of the method. The most interesting result is that under strong duality, the approach yields bounds which are polylogarithmic on the number of resources. The intuition behind this result is that strong duality provides bounds on the magnitude of an optimal dual solution. This suffices to more accurately locate the dual fesible region, which allows the use of entropy regularization for the noisy mirror descent method. The paper also provides lower bounds, which yield some insight on the possible near optimality of the method.", "questions": "MAJOR QUESTIONS:\n1. About point 1 in weaknesses, it would be more consistent if the authors try to:\na) Provide high-probability results for the constraint violation upper bounds (this should be easy, using the high probability tail bounds of Gaussian noise addition).\nb) Provide lower bounds for joint DP resource allocation problems.\n2. About the upper bounds without strong duality, it is unclear to me how the set $\\mathcal{W}$ should be chosen in this case. I think that under quadratic potential they can just let $\\mathcal{W}$ to be the whole space, but please clarify.\n\n\nMINOR QUESTIONS:\n1. In page 3, I don't understand why is it claimed that the dual may not be convex. The dual objective is written as a maximum of functions which are affine in p, so it should always be convex.\n2. The paper does not accurately represent the work done on differentially private versions of mirror descent. The authors should make a more thorough search about this topic, in order to put their work in context.\n3. If I understand correctly, the vector $b$ represents the resource capacities, which it is reasonable to expect them to be public information. Either way, I believe the comment right before theorem 3.10 comes way too late, and the discussion about what is private and what is public it should be brought up much earlier.\n4. The paragraph right after Theorem 3.10 about \"purchasing resources\" I also found it very confusing. Please make efforts to clarify it.\n5. The last comment at the proof ot Theorem 3.6 should not be in the appendix (neither in the proof). This is a more practical consideration that does not belong to the proof, and it should be in the main file instead.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The generality of the class of allocation problems considered.\n2. The insights derived from duality and the mirror descent algorithm.\n3. Numerical results are encouraging.", "weaknesses": "1. I am confused about how the lower bound of Theorem 4.3 compares to the upper bounds. The upper bounds of the paper provide in-expectation guarantees for both suboptimality and infeasibility; moreover, the latter is quantified in an $\\ell_{\\infty}$-sense (which I think it's the right approach in this case). By contrast, the lower bound is expressed for algorithms which are almost surely feasible, leading to the expression that only involves the objective. Since the upper bounds do not contain linear factors in m, I don't see how this lower bound is optimal (or that it gives insight on the efficiency of the upper bound).\n\n2. I also left some more specific comments in the questions section. I believe clarifying these it is very important for the submission to be publishable (and I also think these should be easy fixes).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer kLe8, \n\nWe sincerely thank you for reviewing our work and for your valuable feedback. Below, we respond to the concerns you raised one by one. Please feel free to let us know if you have any further follow-up questions. We are more than happy to take them.\n\n**Weaknesses**\n1. **Response:** Thanks for the comment. We want to first express our sincere apology for a typo in the lower bound (Theorem 4.3): the bound is supposed to be stated for an in-expectation gap $F(x^*) - E_\\mathcal{A}[F(x^{\\mathcal{A}})]$. But somehow we missed out the expectation symbol in the main text, though we indeed did the proof for in-expectation guarantee (see line 605). We feel sorry for any confusion caused, and the typo has been fixed.\n\n    Regarding lower and upper bounds. When reading upper bounds, we should read optimality gap bounds and constraint violation bounds together, because the optimality gap bound itself \"_does not reflect the whole picture_\" (line 180). As we discussed in our response to all reviewers, we therefore treat the (perhaps, weighted) sum of both gaps, i.e., optimality gap + constraint violations, as the ultimate upper bounds in our mind. The idea here follows our \"purchasing resources\" statement you mentioned in your next comment, and it admits a social welfare interpretation: the loss in total social welfare is the sum of (i) loss in total utility of agents and (ii) the decision maker's expenditure on extra resources.    \n\n    Nevertheless, we agree with you and think our current presentation fails to make this interpretation clear. We thus decided to bring this interpretation up to the Introduction as a new paragraph **Our interpretation of algorithm performance**. The content of this new paragraph can be found in our response to all reviewers above. We sincerely thank you again for this valuable comment.\n\n2. **Response:** Thank you very much. More replies coming below.\n\n**MAJOR QUESTIONS**\n1. **Response**: We feel sorry again for missing out the expectation symbol. All our bounds are consistent in the sense that they are for in-expectation performance. As for high-probability bounds, it is an easy fix for optimality gap bounds, but we believe for the constraint violations, it is not easy. This is because the constraint violation bound is derived from a sandwich method. Both sides of the sandwich involve Gaussian random vectors. And the lower part of the sandwich appears to be harder for this purpose, because of the term $\\sum_t <n^{(t)}, p^{(t)}>$ around line 481. In general, $p^{(t)}$ is not assumed to be bounded, and thus we may need to bound it first before employing any Gaussian tail bounds. However, as $p^{(t)}$ depends on all past $n$ and $p$, it is therefore hard to characterize, and may need an iteration-by-iteration check. At this moment, we don't have a clear idea of how to do this (by martingale process maybe?). But we will try our best and report any successful attempts. In contrast, our in-expectation bound takes advantage of the zero-mean of $n^{(t)}$ and independence between $n^{(t)}$ and $p^{(t)}$, so this sum term is zero, and proofs can go through.\n\n2. **Response:** Thanks for the question. Yes, for the case without strong duality, the quadratic function works. We also found the current presentation fails to make the choice of potential functions clear (they are scattered among theorems). To make things clear, we decide to add the table in the attached PDF to our main text. The table shall clarify what potential functions and initial points should be chosen, and what the corresponding performance bounds are.\n\n**MINOR QUESTIONS**\n1. **Response:** Yes, we concur. The dual is always convex. We have fixed this.\n2. **Response:** Thanks for this suggestion. We have added discussion on noisy mirror descent and its applications in the Introduction, and found our work a position in the context. In short, noisy mirror descent is usually used for private stochastic convex optimization and saddle point problems, and is applied to a primal problem. In contrast, we apply noisy mirror descent to the dual problem and use it for resource allocation.\n3. **Response:** Yes, you are right, the vector $\\bf{b}$ is public info. We agree with you and added explanations in the Introduction on what information is public/private. Now, it should be clear from the Introduction that only $z_i$ is private data; other info is public. Thank you for this suggestion.\n4. **Response:** Thanks for this suggestion. We have added a discussion to clarify this. As this is related to point 1 you mentioned in Weaknesses, we hope our response there has cleared your concern. Please feel free to let us know if we have made it clear to you. We will be more than happy to provide follow-up explanations.\n5. **Response:** Thank you. We agree with you. The discussion now is brought to the end of Section 3.1, immediately after Theorem 3.6.", "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": "", "extra_scores": {}}, {"review_id": "GguwniwM2q", "reviewer": "Reviewer_8BYy", "summary": "The paper addresses the allocation problem under Joint Differential Privacy within the framework of a convex consumption function, a concave utility function, and a convex 'personal' domain.\n\nThe contributions of this work are threefold. Firstly, it derives results similar to those in previous research, but notably, it does so using only weak duality. Secondly, the paper improves the previously established optimality gap by leveraging strong duality. Lastly, it establishes a lower bound for the Joint Differential Privacy allocation problem, specifically for algorithms whose outputs are feasible allocations, within a certain regime of the epsilon parameter.", "questions": "It caught my attention that the upper bound is for an algorithm that can violate the constraints, but the lower bound is for one that always output feasible allocations. Is it significantly more difficult to analyze a lower bound for the first type of algorithm (fixing a range of constraint violation)?", "limitations": "Yes, the authors have adressed the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The work effectively distinguishes between the capabilities of weak and strong duality. In the case of strong duality, it achieves a significant improvement by reducing the dependency on the quantity of resources $m$ by a square root factor. This improvement, however, comes with the introduction of polylogarithmic dependencies in both the duality gap and the constraint violation.\nThe authors also present a lower bound for the Joint Differential Privacy (JDP) allocation problem under the assumption of strong duality.", "weaknesses": "The text could benefit from increased clarity in certain areas. For example, it is not immediately clear in the abstract that the lower bound is derived using the strong duality assumption. While this is clarified later in the paper, it would be beneficial for the abstract to be more specific on this point.\nAdditionally, it is not clear to me in what sense the lower bound is near matching the upper bound. It seems to me that there is an extra $m$ factor in the lower bound, which makes the difference not merely polylog. Am I missing something?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 8BYy, \n\nWe want to express our gratitude for your time in reviewing our work and the valuable comment you sent to us. Below, we reply to your concerns one by one. Feel free to let us know any follow-up questions. \n\n**Weaknesses**\n\n**Response:** Thank you very much for the suggestions regarding readability. We fully agree with you and have revised our paper accordingly. Now, the abstract clearly indicates the lower bound is derived under strong duality. As for how bounds match, we need to clarify what is the upper bound first. We basically treat the (perhaps weighted) sum of the optimality gap and constraint violations as the overall upper bound. This is reasonable as optimality gap bounds are achieved by solutions that violate constraints.\n\nIntuitively, constraints being violated means more resources are allocated to agents, and it makes sense in this situation, the utility $F(x^\\mathcal{A})$ is closer to the optimal total utility $F(x^*)$ from below. In an extreme case, if $x^{\\mathcal{A}}$ violated constraints too much, the value $F(x^\\mathcal{A})$ might even be greater than the optimal $F(x^*)$ whose $x^*$ is feasible. The example here suggests that when evaluating algorithms that may violate constraints, we must take into account constraint violations. So when reading upper bounds in Table 1, we'd better consider optimality UB and constraint violations together, taking the sum of the two as the ultimate upper bound. If bounds are understood in this way, then our lower bound matches upper bounds up to log factors. Hope this addresses your concern.\n\nNevertheless, we found that our current presentation fails to highlight this interpretation. To make things clear, we decided to clarify this with a new paragraph, **Our interpretation of algorithm performance**; you may find the content of this paragraph in our response to all reviewers.\n\nThank you very much for the comments. And we are very happy to take further questions.\n\n\n**Questions**\n\n**Response:** With our preceding response, we hope the raised concern in your first sentence is well-addressed. Therefore, we move to the second sentence \"is it significantly more difficult to...?\" The short answer is \"No\", it is not significantly more difficult to analyze the lower bound for algorithms given a fixed value of constraint violation. The fixed value of constraint violation can be treated as more resources, then the current proof can still go through after slight modifications. Specifically, the constructed datasets $\\mathcal{D}_0$ and $\\mathcal{D}_1$ in the proof of Theorem 4.3 should now be modified to contain more compulsory requests that consume the additional resources allowed from violations. Remaining proofs then follow. But the valid range of $\\varepsilon$ may need to adjust accordingly, as indicated in step 4 of our proof.\n\nOverall, whether to investigate the lower bounds of an algorithm outputting feasible or infeasible solutions still depends on the way by which we assess algorithms for constrained problems. If constraint violation is allowed, we must take violations into account and give a proper interpretation. For upper bounds, interpreting violations as additional penalties makes sense, in our opinion. But for lower bounds, we cannot come up with a reasonable explanation so we only focused on feasible algorithms.\n\nIn sum, thank you very much for your valuable comments and suggestions. Hope our responses address your concerns, and we are willing to take follow-up questions, if any.", "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": "", "extra_scores": {}}, {"review_id": "GJb7Bh2L6L", "reviewer": "Reviewer_YdYP", "summary": "The paper studies a class of convex resource allocation problems, in which the utilities and constraints are private (and bounded).\nThe paper proposes a simple algorithm that applies mirror descent to the dual problem (while the update of the primal variables is assumed to be exact).\nThe main technical result is an improvement of the utility bound (improves dependency on number of constraints)", "questions": "Please see weaknesses section.", "limitations": "Additional limitations should be discussed:\n- The near optimality claim is not fully justified (given the feasibility assumption in the lower bound).\n- The algorithm and analysis assume primal updates can be done exactly.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written, and the technical results are interesting  (though I did not carefully review proofs)\n- This class of convex problems (with private utilities and constraints) is well motivated and seems relevant in practice.\n- There is a concrete improvement by a factor of m in the utility upper bound for this class, under strong duality assumptions.", "weaknesses": "- Algorithm 1 assumes that the maximization problem (line 3) is solved exactly. This might be realistic for a subclass of problems (for instance when utilty and constraints are linear -- and I suppose this is true in experiments), but the analysis considers a much more general class, for which exact updates are generally not possible (so I find Table 1 to be a bit misleading about this). For the analysis to be complete, this would require allowing inexact updates in line 3. Can the authors work out the details in this case (please explain in the rebuttal)? Otherwise this should be clearly stated as an assumption and reflected in Table 1.\n- Near optimality: The lower bound assumes that the solution is feasible, while the utility upper bound is for infeasible solutions. I don't think you can reasonably conclude that \"noisy mirror descent is near optimal\" (line 258). It should be made clear that optimality is still very much open. The title should be revised too.\n- Dependence on $\\underline{b}$ in Theorem 3.10: it seems one is trading-off a $\\sqrt m$ utility improvement for a $1/\\underline b^2$ term (both in utility and feasibility) which could be arbitrarily bad depending on the problem instance. Is this unavoidable? Can the authors comment?\n\nMinor:\n- I am not sure how meaningful the \"compulsory requests\" relaxation is, as this requires some restriction on $p^*$, and comes at the expense of simplicity/presentation.\n- the introduction mentions personalized recommendation as a motivating example. Can the authors provide more details or references? How is this problem modeled as a constrained resource allocation problem?\n- Theorem 3.5 and 3.6 are written in terms of $p^{(1)}$. Presumably the bounds in Table 1 use a specific choice of $p^{(1)}$. It would be good to comment on that.\n- Using $u$ both for utility functions and \"violation levels\" (line 183) is confusing. Please choose a different notation.\n- In Condition 3.1, I believe you technically want to require differentiability on relint W, and not on W (otherwise your negative entropy examples would not satisfy this -- please comment on whether this is problematic in your proofs).\n- Some quantities are not defined (even if standard, please make sure to define them to make the paper self-contained), for example the $-i$ notation and strong convexity wrt $\\|\\cdot\\|_p$.\n- Assumption 2.4.3 should be rephrased. Maybe \"the constant $\\gamma$ in (4) is assumed to be ...\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer YdYP, \n\nThank you very much for your thorough reading and for providing insightful comments. We will respond to your concerns below one by one. We are more than happy to answer follow-up questions.\n\n**Weaknesses**\n\n- **Response:** Thank you for this sharp observation. Yes, you are right that we have to assume the maximization problem (line 3) is solved exactly. The exact solution is necessary for invoking Danskin's Theorem, which indicates that the vector $\\bf{g}^{(t)}$ defined in line 5 is a gradient of the dual problem at $p^{(t)}$. The experiments only examine linear problems, which has closed-form solutions, i.e., exact solution can be obtained; so no issues for the experiments. For more general problems considered when developing theory, we believe it is not a big issue neither. Because the maximization problem is a concave problem (note that both $F(\\cdot)$ and $-a(\\cdot)$ are concave), it can be solved to $\\epsilon$-optimality, $\\epsilon\\rightarrow 0$. That says, in a limiting sense, the maximization problem can always be solved exactly. Then, we can invoke Danskin's Theorem for gradients, and all proofs remain valid. However, if no exact solutions, then Danskin's Theorem is no longer valid, and the vector $\\bf{g}^{(t)}$ defined in line 5 might not be a (sub)gradient; and all proofs become flawed. We think it needs an overhaul in the proof for this case, and therefore may leave it for future study. Considering that, we will highlight \"solve exactly\" as an assumption in Table 1. Thank you very much for pointing out this.\n\n- **Response:** Thanks. Other reviewers raised similar concerns, so we launched a response to all reviewers on this concern, please refer to that for more details.  Before talking about \"optimality\", we need to clarify the way we evaluate algorithm's performance: we actually treat the sum of utility bounds and constraint violations as the ultimate upper bounds. In other words, when reading Table 1, we should look at the last two columns together. Constraint violation means resources are in shortage; but purchasing more resources from an emergency supplier costs extra money. So practically, the suboptimality in utility + money spent for getting extra resources should be the ultimate performance measure. \n\n    We fully understand your concern, and we also believe an algorithm without violation should be the true optimal algorithm. So we decide to clarify our interpretation of optimality in the abstract, after Table 1 and after Theorem 3.10, 4.3. Thank you again for this valuable comment.\n\n- **Response:** Thank you for another sharp observation. First of all, we found the term $1/\\underline{b}^2$ can be improved to $1/\\underline{b}$. This has been updated to the revised manuscript. Second, there is indeed a trade-off between an improvement of $\\sqrt{m}$ and an additional factor $1/\\underline{b}$. To our best knowledge, the $1/\\underline{b}$ term seems unavoidable. This term has been consistently observed in (non-private) resource allocation literature that involves analysis through primal-dual relationships, see [1-3]. Some papers interpret $\\underline{b}$ as a sign of unbalance within resources, and argue that if $\\underline{b}$ is very small, then no algorithm can achieve good performance [1]. In our specific case, the term $1/\\underline{b}$ appears around line 509 when bounding $p^*$ under strong duality, which is finally carried to utility and feasibility bounds. So it seems inevitable. However, because $\\bf{b}$ appears in the r.h.s of constraints, in practice, $\\underline{b}$ is unlikely to be an arbitrarily small value (though possible in theory). The references [1-3] we provide below consistently observe a satisfying performance in experiments, despite the hidden drawbacks you raised. Ultimately, whether the trade-off matters depends on what assumptions we make on $\\bf{b}$. For us, we treat it as a constant. Hope our response suffices.\n\n**Minors**\n\n- **Response:** In terms of modeling, it gives more flexibility; for example, physically-challenged students **must** be assigned an accessible seat. The condition just ensures normal students do not take away the seat from them. Technically, it facilitates the proof for lower bounds: the constructed datasets contain compulsory requests. Ultimately, this is a 'relaxation', so we think it should be fine.\n\n- **Response:** Thank you. You may find examples and references in [4] helpful. Some network revenue management problems involving personalized recommendations and limited inventory can be modeled as resource allocation problems.\n\n- **Response:** Thanks for alerting us of this. We indeed presume specific $p^{(1)}$ for Table 1. We also notice that the connection between Theorem 3.5, 3.6, 3.10 and Table 1 is somewhat weak and vague. To enhance the connection, we will add the table in the attached PDF file to our main text. The table illustrates what $p^{(1)}$ is used for what bounds. \n\n- **Response:** Thanks. We now use $\\bf{v}$ to denote violation levels.\n\n- **Response:** Thanks. Yes, we want differentiability in the interior of $\\mathcal{W}$. The modification does not cause problems in our proofs. Because proofs are built on results from mirror descent literature. With differentiability in int($\\mathcal{W}$), our assumptions align with those for mirror descent.\n\n- **Response:** Thanks for your thorough reading. These notations are properly introduced now.\n\n- **Response:** Thank you again for your thorough reading. The poor presentation of Assumption 2.4.3 is a result of formatting the paper to meet the 9-page limit requirement. With one more page allowed now, we have rephrased this.\n\n\n[1] A dynamic near-optimal algorithm for online linear programming. OR, 2014\n\n[2] Dual mirror descent for online allocation problems, ICML, 2020\n\n[3] Online linear programming: Dual convergence, new algorithms, and regret bounds, OR, 2022\n\n[4] An improved analysis of LP-based control for revenue management, OR, 2024", "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": "", "extra_scores": {}}]

Author rebuttal:
Dear Reviewers kLe8, 8BYy, YdYP,

We sincerely thank you for your time in reviewing our work and in providing valuable feedback. We would like to initiate a global response to a common concern raised by all of you:

- Given that upper bounds are for an algorithm that can violate constraints, but the lower bound is for one that always outputs feasible solutions, how does the lower bound compare to upper bounds, and why do we claim the proposed algorithm to be "near optimal"?

Before talking about "optimality", we need to clarify the way we evaluate algorithms' performance. **We essentially treat the sum of utility bounds and constraint violations as the ultimate upper bounds** in our mind. Because the algorithm may output infeasible solutions, solely looking at its utility upper bounds is not reasonable. That is to say, when reading performance bounds in Table 1, we should look at the last two columns together. Failing to do so may lead to false conclusions. To see why, please take a look at the table in the attached PDF. As indicated by the first two rows (or third and fourth rows), with different initial point $\bf{p}^{(1)}$, performances vary a lot. When $\bf{p}^{(1)}\rightarrow \bf{0}$, the utility gap bounds are even smaller, but this comes at huge constraint violations (so, we should not conclude that $\bf{p}^{(1)}\rightarrow \bf{0}$ is a better choice)

For this reason, we use the sum of utility bounds and constraint violations as the ultimate performance measure (this idea admits a social welfare interpretation, see text in the block below). In this sense, our proposed algorithm is near optimal.

(On a side note, [HHRW16]'s algorithm is not necessarily near optimal for general convex cases, because their analytic results are only valid for linear problems due to a supporting Lemma they invoked. We will clarify this in the revision.)

We found that the presentation in our initial submission failed to stress the performance measure we used. To this end, we will

- (i) Add the following paragraph to Introduction

> **Our interpretation of algorithm performance** Because algorithms considered may output infeasible solutions, when assessing their performance, we should take into account both suboptimality in utility and constraint violations, i.e., the last two columns in Table 1. We, therefore, treat the sum of them as the ultimate performance. This idea admits a social welfare interpretation: when the central decision maker (e.g., a government) desires to implement an infeasible allocation, she may purchase additional resources from an emergency supplier to make the allocation feasible. Then the total loss in social welfare is the (perhaps, weighted) sum of (i) the loss in utility of agents and (ii) the decision maker's expenditure on extra resources. Besides, Table 2 suggests that initial points affect performance significantly. If we only look at suboptimality, we may mistakenly conclude that the gap could be arbitrarily small. Following our interpretation of performance, our proposed algorithm is near optimal.

- (ii) Add the table in the attached PDF to the main text.

We hope our response addresses your concern. Below, we will reply to each one of you individually. Thank you very much again for all the feedback and comments.

Yours,

Authors of Submission 3277

Meta-review: This paper studies resource allocation problems under joint differential privacy. On the one hand, it goes far beyond existing work, incorporating nonlinear utilities and nonconvex feasible sets. On the other hand, they prove that under suitable conditions --more precisely, strong duality-- a joint-DP instantiation of the mirror-descent algorithm attains utility and feasibility approximation bounds which are only poly-logarithmic on the number of resources. Lower bounds on the aggregate suboptimality + total constraint violation indicate the near optimality of the obtained results.

This work provides an interesting and novel application of mirror-descent methods in the context of private optimization. Moreover, the technical insights related to the role of strong duality seem entirely new and of independent interest. Therefore I recommend this paper to be accepted at the conference.

Some key open questions remain: some of them as the result of discussions in the rebuttal period. Authors are highly encouraged to include these discussions in the final version of the paper. Furthermore, there were some concerns about clarity of the setting and the meaning of the comparison between upper and lower bounds. Please seriously address these concerns in your final version of the paper.
Decision: Accept (poster)