Noisy Dual Mirror Descent: A Near Optimal Algorithm for Jointly-DP Convex Resource Allocation

Authors: du  chen
geoffrey a chua
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-09 13:21:50

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.

Main paper: 
 introduction: 
 The resource allocation problem is a 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 as a utility maximization problem, where the central decision maker has to properly allocate m types of limited resources to n agents in order to maximize the total utility of all agents. Each agent's data z i := (u i (•), a i (•), X i ) consists of three elements: (i) a utility function u i : R s + → R + that maps an allocation x i to a utility scalar; (ii) a consumption function a i : R s + → R m + that maps an allocation x i to a consumption vector; and (iii) a feasible set X i ⊆ R s + that may capture the agent's special requirements. With a dataset D := {z i } n i=1 of n agents, the problem is modeled asEQUATIONn i=1 a i (x i ) ≤ nγb;(2)EQUATIONwhere nγb > 0 is the available level of m types of resources. Evidently, the goal in (1) is to find the best allocation x i for each agent subject to resource-coupling constraints (2) and to a personal requirement constraint (3). When u i (•) is concave, and a i (•), X i 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 to one agent would affect the allocation to another agent. When a 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 may misreport the number of its students in poverty, compromising the original intention of the financial support.To overcome privacy concerns in such cases, joint differential privacy (Joint-DP or JDP, for short), which is a 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 a group of collusive agents without i. It guarantees that the allocations received by the collusive agents are insensitive to agent i's data. Considering that the allocation decision x i is usually private to agent i 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 (x 1 , . . . , x n ) satisfy JDP. The Billboard Lemma has wide applications, ranging from convex optimization [HHR + 14, HHRW16, HZ18], to multi-armed bandits [SS18, HLL + 22], to reinforcement learning [VBKW20] . We also use it for privacy analysis. For clarification purposes, we highlight that, in problem (1), dataset {z i } n i=1 := {(u i (•), a i (•), X i )} n i=1 is the private information to protect; resource level nγb 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 [HHRW16, 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 [HHRW16, HZ18, HZ19] all use Advanced Composition, which suggests an 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 a 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, we propose a 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 ℓ 1 geometry of the dual space. Last, we complement previous analysis with a matching minimax lower bound for ε ≥ max{1, 1/(nγ)}, suggesting near optimality of our algorithm. We further conduct numerical experiments to show the effectiveness of our proposed algorithm. Table 1 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 a social welfare interpretation: when the central ) can be derived from [HZ18, Theorem 1.2]. But their original statement is for the minimal supply, not for suboptimality as we considered. † The lower bound is for algorithms outputting feasible allocations, while upper bounds are achieved by algorithms that may output infeasible allocations. So, the lower bound could be higher. The lower bound holds only for ε ≥ max{1, 1/(nγ)} where γ ∈ (0, 1).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 sum of (i) the loss in utility of agents and (ii) the decision maker's 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 a 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 to ours are [HHRW16, HZ18] , both of which designed their algorithms with a dual decomposition idea. [HHRW16] 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 it 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 non-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. 
preliminaries: 
 Definition 2.1 (Differential privacy, [DR14] ). A mechanism M : Z n → P is (ε, δ)-differentially private if, for any pair of neighboring datasets D ∼ D ′ that differ in one data point, and for any subset of output S ⊆ P, we haveP [M(D) ∈ S] ≤ e ε • P [M(D ′ ) ∈ S] + δ.Throughout the work, we use the subscript -i to indicates variables without agent i. For example,X -i := X 1 × • • • X i-1 × X i+1 • • • × X n is a feasible space without i, and M(D) -i := (M(D) 1 , . . . , M(D) i-1 , M(D) i+1 , . . . , M(D) n ) is the view from other agents without i. Definition 2.2 (Joint differential privacy, [KPRU14]). A mechanism M : Z n → X n is (ε, δ)-jointly differentially private if for any pair of neighboring datasets D ∼ D ′ that differ in datapoint i ∈ [n],and for any subset of outputs S ⊆ X -i , we haveP [M(D) -i ∈ S] ≤ e ε • P [M(D ′ ) -i ∈ S] + δ.Lemma 2.3 (Billboard Lemma, [HHR + 14]). Suppose M : Z n → P is (ε, δ)-DP. For any given function f : Z × P → X , denote the output of f on individual i's data asf i := f (z i , M(D)). Then, (f 1 , . . . , f n ) is (ε, δ)-JDP. Definition 2.4 (α-strong convexity). Let α > 0. Function ℓ : R m → R is said to be α-strongly convex w.r.t. ∥•∥ p over set W, if ℓ(x) ≥ ℓ(y) + ⟨∇ℓ(y), x -y⟩ + α 2 ∥x -y∥ 2 p , ∀x, y ∈ W.Primal problem in a condensed form Let x := (x 1 , . . . , x n ) be the collection of allocations. For a given dataset D, let F(x) := n i=1 u i (x i ) be the total utility when allocation is x. Let a(x) := n i=1 a i (x i ) be the total consumed resource, and let X := X 1 × • • • × X n be the feasible region. Then, the resource allocation problem (1), referred to as "primal problem" later, can be written in a condensed form:EQUATIONThe optimal allocation is denoted asx * := arg max x∈X {F(x) : a(x) ≤ nγb}.Dual problem By dualizing the coupling constraint with shadow prices p ≥ 0, we get a Lagrangian function min p≥0 max x∈X {F(x) + ⟨p, nγb -a(x)⟩}. Thus, the Lagrangian dual problem is When there are multiple x * and p * , we can break ties arbitrarily. Let ∥•∥ p denote the p-norm of a vector, and let [n] := {1, . . . , n} be a running set. We impose some assumptions on dataset D to make both primal and dual problems interesting. Assumption 2.5 (Interesting instances). For a datasetEQUATIOND := {(u i (•), a i (•), X i )} n i=1, we assume 1. Convexity: for each i ∈ [n], utility function u i is concave on X i , consumption function a i is convex on X i , and X i is a convex set;2. Boundedness: ∃ u > 0 and bounded b > 0 with ∥b∥ 2 ≤ B such that u i (x i ) ∈ [0, u] anda i (x i ) ∈ [0, b], ∀x i ∈ X i , i ∈ [n]. Specially, if 0 ∈ X i , then u i (0) = 0 and a i (0) = 0;3. Limited resource: the constant γ in (4) is assumed to be in the interval (0, 1) . The primal problem (4) is 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., ∥p * ∥ 1 ̸ = 0;4. Compulsory request allowed: request i can be compulsory in the sense thatX i ̸ ∋ 0, only if max xi∈Xi {u i (x i ) + ⟨p * , -a i (x i )⟩} ≥ 0.These assumptions are very mild. The first assumption restricts our attention to 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-constrained and not ill-posed. The constant γ controls available resource levels, and nγ means the number of agents whose requests can be fully fulfilled. In practice, usually γ ≥ 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 is beneficial. Our assumptions are weaker than those in the literature [HZ18, BLM20, BLM23] by allowing compulsory requests.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 of our work.Guidelines:• The answer NA means that the paper has no 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 (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
the algorithm and analysis: 
 Our algorithm is a private version of Mirror Descent applied to the dual problem (5). Mirror Descent (MD) [NY83] is a 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 → R + . The potential function chosen should meet some conditions below.Condition 3.1 (Potential Functions). The potential function Φ : W → R + chosen should be (i) differentiable on int(W), i.e., the interior of its domain W ⊆ R m ; and (ii) α-strongly convex with respect to ∥•∥ p on W. For a given Φ, let B Φ (x, y) := Φ(x) -Φ(y) -⟨∇Φ(y), x -y⟩ be the Bregman divergence between x ∈ W, y ∈ int(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 1 Noisy Dual Mirror Descent for Resource Allocation Problems, A Parameters: privacy parameters (ε, δ), variance σ 2 ; stepsizes {η (t) } T t=1 ; potential function Φ(•) : W → R + that is α-strongly convex with respect to ℓ p -norm; conjugate index q s.t. 1/q + 1/p = 1, number of iterations T , feasible region of shadow prices P := R m + . 1: Set initial point p (1) ∈ P ∩ int(W) 2: for t = 1 to T do3: Get intermediate allocation decision x (t) ← arg max x∈X F(x) + p (t) , γnb -a(x) 4:Draw a noise vector n (t) ∼ N (0, σ 2 I m×m ) 5:Update private shadow prices according to Noisy Mirror Descent:EQUATIONwhere g (t) := nγb -a(x (t) ) 6: Final allocation decisionx A := (x A 1 , . . . , x A n ) ← 1 T T t=1 x (t) 7: Output x A i to agent i, for all i ∈ [n]algorithm, and in each iteration, we first calculate allocation decisions based on current shadow prices p (t) , i.e. Step 3. Then, we update the shadow prices by Noisy Mirror Descent update rule (6). The gradient g (t) used is exactly the gradient of the dual problem D(p (t) ) 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 a DP manner, then the final allocation decisions will be JDP. Compared to existing works invoking Advanced Composition, we provide a tighter privacy accounting through Rényi DP.Theorem 3.2 (JDP Guarantee). Given ε > 0, δ ∈ (0, 1) andT ≥ 1, if noise variance σ 2 = T • c ε,δ with c ε,δ := ∥b∥ 2 2 • 2 ln (1/δ) ε 2 + 1 ε , then Algorithm 1 A is (ε, δ)-JDP.To better align with expressions in DP literature, we can assume ε ≤ ln (1/δ). Then, the magnitude of c ε,δ becomes ln (1/δ) ε 2, a 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, δ = 10 -3 , and ∥b∥ We now move on to analyze the utility optimality gap F(x * ) -E A F(x A ) . The following weak duality lemma bridges the primal and dual problems.Lemma 3.3 (Weak duality). For any p ≥ 0, the objective value of dual problem (5) is always greater than or equal to that of primal problem (4), i.e., D(p) ≥ max x∈X {F(x) : a(x) ≤ nγb} , ∀p ≥ 0.An immediate result of weak duality is D(p (t) ) ≥ F(x * ), ∀t. Hence, applying weak duality and Jensen's inequality, the optimality gap F(x * ) -F(x A ) can be upper bounded as follows, provided the randomness dice of A is fixed,F(x * ) -F(x A ) ≤ 1 T T t=1 D(p (t) ) -F(x (t) ) = 1 T T t=1 p (t) , nγb -a(x (t) ) = 1 T T t=1 p (t) , g (t) + n (t) - 1 T T t=1 p (t) , n (t) ,where the first equality is by definition of the dual problem, and the second equality is by definition of gradient g (t) . Taking expectation with respect to A removes the subtrahend, since n (t) is independent of p (t) and zero-mean, which givesF(x * ) -E A F(x A ) ≤ E A 1 T T t=1 p (t) , g (t) + n (t). 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 + 23] cases. Not surprisingly, MD can also achieve a small stationarity gap.Lemma 3.4 (Cumulative stationarity gap of MD). Suppose stepsizes η (t) = η in MD update rule (6) are the same for all t ∈ [T ], and let { g (t) } T t=1 be gradients used for update. Then the cumulative stationarity gap T t=1 p (t) -p, g (t) for any anchor point p ∈ P ∩ W is upper bounded asT t=1 p (t) -p, g (t) ≤ η T t=1 g (t) 2 q 2α + B Φ (p, p (1) ) η , ∀p ∈ P ∩ W.With Lemma 3.4 and proper stepsizes, we can control the optimality gap. Denote γ := max{γ, 1-γ}, G := γ 2 n 2 ∥b∥ 2 q , and let z ∼ N (0, I m×m ) be a standard Gaussian random vector. For a given potential function Φ and an initial point p (1) , denote C Φ (p (1) ) := B Φ (0, p (1) )/α. Theorem 3.5 (Utility guarantee). Set stepsizesη (t) = αBΦ(0,p (1) ) T •(G+σ 2 E[∥z∥ 2 q ]) , ∀t ∈ [T ]. Suppose potential function's domain includes 0, i.e., 0 ∈ W. Then running algorithm A with iterationsT ≥ G c ε,δ •E[∥z∥ 2 q ]and σ 2 chosen in Theorem 3.2 yieldsEQUATIONAn instantiation of the utility guarantee is byΦ(•) = 1 2 ∥•∥ 2 2, which is 1-strongly convex w.r.t. ℓ 2 -norm on R m . Then, the upper bound in (7) becomes 2 √ 2m p (1) 2 • √ c ε,δ , which depends on the choice of initial point p (1) . It seems the bound can be arbitrarily small if p (1) is close to 0. But in fact, the theorem itself does not reflect the whole picture, since x A could be infeasible. Therefore, we have to further examine A's feasibility guarantee. Theorem 3.6 (Feasibility guarantee). Given allocation decision x A , denote the violation levels as v A := (a(x A ) -nγb) + , where positive part operator (•) + applies element-wisely. In addition to Condition 3.1, additionally assume the domain W of potential function Φ contains 2 ∥p * ∥ 1 e j , ∀j ∈ [m]. Then, running algorithm A with the same setting as in Theorem 3.5 yieldsEQUATIONwhere C Φ,1 (p (1) ) = BΦ(0,p (1) )+max e∈E 1 BΦ(2∥p * ∥ 1 e,p (1) ) √ BΦ(0,p (1) ), setE 1 := {e ∈ {0, 1} m : ⟨1, e⟩ ≤ 1}.The proof idea is to sandwich the cumulative stationarity gap T t=1 p (t) -p, g (t) at a properly chosen anchor point p := 2 ∥p * ∥ 1 e j A ∈ 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 e j A with a single 1 on j A -th position indicates which constraint j A ∈ [m] is most severely violated. One may notice that the anchor point p := 2 ∥p * ∥ 1 e j A 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 ∥p * ∥ 1 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 * ∥ 1 e j A , ∀j A 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Φ(•) = 1 2 ∥•∥2 2 is the ideal potential function, because its domain W = R m 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 ℓ 2 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 ∥p * ∥ 1 e j A are related to ℓ 1 norm of p * , if we can find a data-independent upper bound for the value of ∥p * ∥ 1 , we might be able to adjust W accordingly without privacy concerns and may further improve performance. We do so in the next subsection. W α w.r.t ∥•∥ p p (1) F(x * ) -E F(x A ) mE v A ∞ squared ℓ2 1 2 ∥p∥ 2 2 R m 1 w.r.t ∥•∥ 2 1 √ m • 1 O √ m ln (1/δ) ε O m 3/2 √ ln (1/δ) ε negative entropy (ne) m j=1 pj ln pj ∆ K w. K = 2u γb 1 K w.r.t. ∥•∥ 1 K m • 1 K O √ ln (1/δ) ε K O m √ ln (1/δ) ε parameterized ne m j=1 bj pj ln (bj pj ) ∆ K (b) w. K = 2u γ b 2 K w.r.t. ∥•∥ 1 K mb j , ∀j K b O √ ln (1/δ) ε K b O m √ ln (1/δ) εNotes. Results for squared ℓ2 (negative entropy) are from Section 3.1 (Section 3.2). Strong duality is necessary for theoretical guarantees by (parameterized) negative entropy. Abbreviations in column titles: cvx.=convexity, init.pt.=initial point, opt.gap = optimality gap, contrs.viol.=constraint violations. The (scaled) simplex set ∆ K (b) with radius K is defined as ∆ K (b) := {p ≥ 0 : ⟨b, p⟩ ≤ K}; the standard simplex is ∆ K := ∆ K (1). † Squared ℓ2 function is strongly convex on whole space R m , while negative entropy functions only on their respective domains.Results in the first and second rows are highlighted as the main contributions in Table 1 .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(x * ) = 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γb is linear in x, 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 feasible 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 [HHRW16, 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 ℓ 1 space. Lemma 3.8 (Strong duality implies bounded p * ). Let p * := arg min p≥0 D(p). Then, under assumptions 2.5 and 3.7, we have ⟨b, p * ⟩ ≤ u γ and ⟨1, p * ⟩ ≤ u γb with b := min j {b j }.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 ℓ 1 geometry. However, negative entropy Φ(w) = m j=1 w j ln w j is widely known to be 1-strongly convex only on the probability simplex ∆ 1 := {w > 0 : ⟨1, w⟩ = 1}. To tailor it for our studied problem, we parameterize the negative entropy Φ(w; θ) := m j=1 (θ j w j ) ln (θ j w j ) with θ > 0, and show that it is also strongly convex in a scaled simplex. Lemma 3.9 (Strong convexity of parameterized negative entropy). Let the parameterized negative entropy Φ(w; θ) := m j=1 (θ j w j ) ln (θ j w j ) be defined on R m + , where we define 0 0 = 0 and 0 ln 0 = 0 by continuity. Then Φ(w; θ) is (minj {θ j }) 2 /K-strongly convex in w w.r.t. ∥•∥ 1 in a scaled simplex ∆ int K (θ) := {w > 0 : ⟨θ, w⟩ ≤ K}.It is immediate to see that if we set θ = 1 and K = 1, 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 Φ(w; b) = m j=1 (b j w j ) ln (b j w j ) for the Mirror Descent update step (6). This does not compromise privacy, since b is a universal upper bound and is not associated with any specific agent. Now, we are ready to improve the algorithm's performance.Theorem 3.10 (Improved utility & feasibility guarantees). Let b := max j {b j }, b := min j {b j }. Under assumptions 2.5 and 3.7, running algorithm 1 A with parameterized negative entropy Φ(w; b) with radius K := 2u/γ, p(1) j = K/(mb j ), ∀j ∈ [m], and same T , σ2 as in Theorem 3.5 yields(utility guarantee) F(x * ) -E A F(x A ) ≤ 8 √ 2u • ln (2m) γb • √ c ε,δ ; (feasibility guarantee) E A v A ∞ ≤ 4u 2 ln (2m) • 2 + b • (ln mb -1) + γb • ∥p * ∥ 1 • √ c ε,δ .Compared to the results in Theorems 3.5 and 3.6 where both dependencies on number of constraints are √ m, the results here have better dependencies of ln m. Moreover, following our interpretation of algorithm performance as discussed in the Introduction, Theorem 3.10 implies that the algorithm's ultimate performance isO √ c ε,δ + m • O √ c ε,δ = O m √ c ε,δ .The additional m factor comes from m constraints, since the feasibility guarantee in Theorem 3.10 is for any single constraint.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
the lower bound: 
 Some post-processing lemmas for JDP are necessary to prove the lower bound. Lemma 4.1 (Self post-processing for JDP). Let M : Z n → X n be an (ε, δ)-JDP mechanism and denote its output by M(D) := (M(D) 1 , . . . , M(D) n ). Let f : X × Z → Y be an arbitrary (randomized) function that can be applied element-wisely to M's output. Then,(f (M(D) 1 , z 1 ), . . . , f (M(D) n , z n )) is (ε, δ)-JDP.Lemma 4.2 (Post-processing for JDP). Let M : Z n → X n be an (ε, δ)-JDP mechanism and denote its output by M(D) := (M(D) 1 , . . . , M(D) n ). Let f : X n-1 → Y be an arbitrary (randomized) function that can be applied to any collection of n -1 elements of M's output. Then, for any k∈ [n], f (M(D) -k ) and f (M(D ′ ) -k ) are (ε, δ)-indistinguishable. 2Lemma 4.1 confirms that processing each JDP output with the agent's own data preserves JDP. Lemma 4.2 says applying any operation to n -1 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 allocationsx A := (x A 1 , . . . , x A n ) outputted by a JDP algorithm A : Z n → X n . By Lemma 4.1, their consumptions (a 1 (x A 1 ), . . . , a n (x A n ))are also JDP. Furthermore, for any collusive group without agent k, their total consumption n i̸ =k a i (x A i ) 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 ε ≥ max{1, 1/(nγ)}, 0 < δ ≤ 1/2, there exists a dataset D satisfying assumptions 2.5 and 3.7 such that any (ε, δ)-JDP algorithm A outputting feasible allocations will lead to a utility loss at least m/(4ε). Therefore, the minimax lower bound isinf A is (ε, δ)-JDP sup D F(x * (D)) -E A F(x A (D)) ≥ m 4ε .The lower bound here nearly matches upper bounds given by Theorem 3.10 up to some logarithmic factors in m and 1/δ. Therefore, Noisy Dual Mirror Descent is near optimal, under our interpretation of algorithm performance. However, the result is limited to ε ≥ max{1, 1/(nγ)}, and it is interesting to 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 
workforce scheduling: 
 Workforce scheduling is about establishing a shift schedule for a given period to maximize workers' total preference while meeting worker availability and shift coverage requirements. Workers' preference and availability are private data to protect. We consider a simple case of scheduling n = 7 workers for m = 14 days with data publicly available [Opt24] . In this case, (i) each worker has preferences c i ∈ Z m + , and utility function isu i (x i ) = ⟨c i , x i ⟩; (ii) shift requirement r j ∈ Z + is imposed on each day j ∈ [m],i.e., the number of workers needed for day j, which couples all workers; and (iii) workers' availability and shift limits described by a polyhedral setX i := {x i ∈ [0, 1] m : l i ≤ ⟨1, x i ⟩ ≤ u i }. The problem is modeled as max { n i=1 ⟨c i , x i ⟩ : i x i = r; x i ∈ X i , ∀i}.While this is a 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, 3, 2, 3, 0, 0, 0] is a sparse vector, one can expect MD equipped with negative entropy to perform better.Figure 1 shows the final decisions under various ε, where the rightmost is the optimal non-private decision where a value of 1 means arranging the person to that day. Private decisions are fractional curves, the lower the better. It is clear that our algorithms have significantly smaller optimality gaps at slightly higher constraint violations.) H P N H 0 D UL V D 0 D WV X P L 3 D X OL Q H 6 LY D 9 LQ F H Q W = LT LD Q J 'D\ 'D\ 'D\ 'D\ 'D\ 'D\ 'D\ 'D\ 'D\ 'D\ 'D\ 'D\ 'D\ 'D\ ε = 1 ) H P N H 0 D UL V D 0 D WV X P L 3 D X OL Q H 6 LY D 9 LQ F H Q W = LT LD Q J ε = 5 ) H P N H 0 D UL V D 0 D WV X P L 3 D X OL Q H 6 LY D 9 LQ F H Q W = LT LD Q J ε = 10 ) H P N H 0 D UL V D 0 D WV X P L 3 D X OL Q H 6 LY D 9 LQ F H Q W = LT LD Q J ε = 20 ) H P N H 0 D UL V D 0 D WV X P L 3 D X OL Q H 6 LY D 9 LQ F H Q W = LT LD Q J ε = ∞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 we show its impact in Figure 2 (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_constant is 2, our algorithms achieve lower optimality gaps at the same level of constraint violations.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{ n i=1 ⟨c i , x i ⟩ : i I m×n x i ≤ nγ1; x i ∈ X i , ∀i} with X i := {x i ∈ [0, 1] n : ⟨1, x i ⟩ ≤ 1}being a unit simplex and I m×n := [I m , . . . , I m ] being a consumption matrix concatenated from n/m identity matrices. Raw data of c i are available at [Bea04] . In this assignment problem, p * > 0 is strictly non-zero. We run experiments and report results in Table 3 . -6.9±1.5 1.8±1.4 13.8±1.3 12.3±0.9 256.7±16.0 156.8±20.8 30.3±10.8 15.7±6.7 MD_l2 (ours) 4.3±3.4 2.8±2.3 1.2±0.8 0.7±0.7 54.6±18.5 35.1±14.8 12.6±4.6 7.2±3.3 MD_ne (ours) 6.0±4.1 3.0±2.1 1.1±0.9 0.6±0.6 47.8±23.0 25.8±12.0 13.4±5.9 4.5±2.5 3000 [HHRW16] -29.4±0.9 -18.9±1.2 6.9 ±1.2 8.2±1.0 > 10 3 > 10 3 743.8±25.7 680.1±29.4 MD_l2 (ours) 4.3±5.1 3.0±2.4 2.0±1.3 1.5±0.7 193.9±54.1 97.2±23.9 39.8±12.6 22.0±6.3 MD_ne (ours) 10.4±5.2 6.1±3.0 3.0±1.1 1.6±0.6 134.5±56.4 65.4±25.1 27.9±8.4 18.1±6.0Notes. Parameters for our algorithms: K = 1.1u/(γb), δ = .01, T = 10 4 . Other settings follow Theorem 3.10. MD_l2 and MD_ne mean that potential function is squared ℓ2 and negative entropy, respectively. For three cases n = 800, 1500, 3000, we set resource level γ = 0.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.From the table, we observe MD_l2 has lower gaps and reasonable constraint violations for small ε; and MD_ne almost dominates others for large ε. Both our algorithms outperform existing methods.Question: Does the paper provide open access to the data and code, with sufficient instructions 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 as part of supplementary material of this submission.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
discussion and conclusion: 
 Limitation of our work. One significant limitation is the restriction of ε ≥ max{1, 1/(nγ)} to make the lower bound hold. However, we identify a 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-standing open question in private online optimization [CDE + 24].In this work, we considered convex resource allocation problems under joint differential privacy. To solve the problem approximately, we proposed an 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.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: In our case, experiment settings/details are mainly about algorithm hyperparameters. 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 a 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. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: In all figures and tables, indications of statistical significance, such as standard deviations and confidence intervals, are properly reported.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence 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). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This is a theory paper. It is 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
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 (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Not applicable, as our work is a theory paper.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a 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 a theory paper. And experiments do not need existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 not available online, the authors are encouraged to reach out to the asset's creators. 
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 of 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 is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
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 not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to 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. 
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 crowdsourcing nor research with human subjects.• 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. 
 
 Appendix: A.1 Proof of Theorem 3.2i depends on all shadow prices (p (1) , . . . , p (T ) ) on the training trajectory and the individual's own data, by Billboard Lemma 2.3, it suffices to verify the whole sequence (p (1) , . . . , p (T ) ) is (ε, δ)-DP. We characterize the DP guarantee through Rényi Differential Privacy [Mir17] . Below are some useful lemmas on Rényi DP.Definition A.1 ((α, ε)-Rényi Differential Privacy, [Mir17] ). Let M : D → P be a randomized mechanism. For any neighboring datasets D ∼ D ′ , let P, P ′ be the distribution of M(D) and M(D ′ ), respectively. Then, M is said to be ε-Rényi differentially private of order α, or (α, ε)-RDP for short, if it holds thatD α (P || P ′ ) ≤ ε, ∀D ∼ D ′ , where D α (P || Q) := 1 α-1 ln E Q P(x) Q(x)α is the Rényi divergence between P and Q.Lemma A.2 (Gaussian Mechanism is RDP, Proposition 7 in [Mir17] ). Let f : D → Z be a vectorvalued function whose global sensitivity is GS:= sup D∼D ′ ∥f (D) -f (D ′ )∥ 2 , then the Gaussian Mechanism M(D) := f (D) + N (0, σ 2 I) is (α, α•GS 2 2σ 2 )-RDP, for any α > 1. Lemma A.3 (Composition for RDP, Proposition 1 in [Mir17]). Let M 1 : D → P 1 be (α, ε 1 )- RDP and M 2 : D × P 1 → P 2 be (α, ε 2 )-RDP. Let X := M 1 (D) be the output of M 1 and Y := M 2 (D, X) be the output of M 2 , then the adaptive composition (X, Y ) satisfies (α, ε 1 + ε 2 )- RDP.Lemma A.4 (From RDP to DP, Proposition 3 in [Mir17] ). If M is an (α, ε)-RDP mechanism, it also satisfies (ε + ln (1/δ) α-1 , δ)-DP, for any δ ∈ (0, 1).For iteration t, we notice that data only plays a role in the gradient g(p (t) ; D) := nγb-a(x(p (t) ; D)) through intermediate allocation decision x(p (t) ; D) := arg max x∈X F(x) -p (t) , a(x) . It is immediate to show that the Global Sensitivity of gradient function isEQUATION)where the last inequality is by our assumption that serving one individual consumes at most b resource (see assumption 2.5). Then, injecting a zero-mean Gaussian noise n (t) ∼ N (0, σ 2 I) into gradients g (t) := g(p (t) ; D) can guarantee (α,α•∥b∥ 2 22σ 2 )-RDP by Lemma A.2. 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 (1) + n (1) , . . . , g (T ) + n (T ) ) satisfies (α,T α•∥b∥ 2 2 2σ 2 )- RDP.As the noisy mirror descent update step in Eq.( 6) is merely post-processing after obtaining (g (1) + n (1) , . . . , g (T ) + n (T ) ), the sequence (p (1) , . . . , p (T ) ) is thus also (α,T α•∥b∥ 2 2 2σ 2 )-RDP. Lastly, by Lemma A.4, (α, T α•∥b∥ 2 2 2σ 2 )-RDP implies ( T α•∥b∥ 2 2 2σ 2 + ln (1/δ)α-1 , δ)-DP ∀δ ∈ (0, 1). Thus, for a given pair of (ε, δ), if we assign privacy budget in the following way:T α∥b∥ 2 2 2σ 2 = ε/2; ln (1/δ) α-1 = ε/2, we can get σ 2 = T ∥b∥ 2 2 • 2 ln (1/δ) ε 2 + 1 ε ,which is the desired variance level.A.2 Proof of Lemma 3.4Proof. For any gradient g (t) used for the mirror descent update step Eq.( 6), shadow prices p (t) , and updated shadow prices p (t+1) , there exists an inequality linking them together (Lemma 9.13, [Bec17] ):g (t) , p (t) -p ≤ η (t) g (t) 2 q 2α + 1 η (t) B Φ (p, p (t) ) -B Φ (p, p (t+1) ) , ∀t, ∀p ∈ P ∩ W.Summing up the above inequality in a telescoping way over t = 1, . . . , T givesT t=1 g (t) , p (t) -p ≤ T t=1 η (t) g (t) 2 q 2α + B Φ (p, p (1) ) η (1) - B Φ (p, p (T +1) ) η (T ) + T -1 t=1 1 η (t+1) - 1 η (t) B Φ (p, p (t+1) ).When stepsizes η (t) = η are the same for all t, the inequality becomesT t=1 g (t) , p (t) -p ≤ η T t=1 g (t) 2 q 2α + B Φ (p, p (1) ) η .A.3 Proof of Theorem 3.5Proof. Let us first fix a sequence of noises {n (t) } T t=1 . Recall that the final allocation decision x A is the average over all decisions along the trajectory and the objective function is concave; therefore, by Jensen's inequality, F(x A ) ≥ 1 T T t=1 F(x (t) ). Moreover, by weak duality, F(x * ) ≤ D(p (t) ), ∀t. With the above results, the optimality gap F(x * ) -F(x A ) can be upper controlled as:F(x * ) -F(x A ) ≤ 1 T T t=1 D(p (t) ) -F(x (t) ) = 1 T T t=1 F(x (t) ) + p (t) , g (t) -F(x (t) ) (by definition of dual problem D) = 1 T T t=1 g (t) , p (t) -0 - 1 T T t=1 n (t) , p (t) .Taking expectation with respect to noises {n (t) } T t=1 on both sides, we can remove the second term on the right hand side in preceding inequality, because n (t) is zero-mean and is independent of p (t) . This leads toF(x * ) -E A F(x A ) ≤ 1 T • E A T t=1 g (t) , p (t) -0 .The inner summation can be upper bounded by applying Lemma 3.4 with p = 0 and η (t) = η > 0, ∀t; we therefore obtainEQUATION)Here are some helpful inequalities:g (t) 2 q = g (t) + n (t) 2 q ≤ 2 g (t) 2 q + 2 n (t) 2 q ; g (t) q = γnb -a(x (t) ) q ≤ γn ∥b∥ q .Denote G := γ 2 n 2 ∥b∥ 2 q , and G A := 1 T T t=1 n (t) 2 q . Using above helpful inequalities, we can upper bound 1EQUATIONPlugging (11) back into (10), we further reach an upper bound:F(x * ) -E A F(x A ) ≤ η • (G + E A [G A ]) α + 1 ηT B Φ (0, p (1)).BecauseG A = 1 T T t=1 n (t) 2 q and n (t) ∼ N (0, σ 2 I m×m ) with σ 2 = T c ε,δ , ∀t, direct calculation gives E A [G A ] = σ 2 E ∥z∥ 2q with z ∼ N (0, I m×m ) being a standard Gaussian random vector. Therefore,F(x * ) -E A F(x A ) ≤ η • G + σ 2 E ∥z∥ 2 q α + 1 ηT B Φ (0, p (1) ).Let C Φ (p (1) ) := B Φ (0, p (1) )/α. Then, plugging in the stepsize η =αBΦ(0,p (1) ) T •(G+σ 2 E[∥z∥ 2 q ]) leads to F(x * ) -E A F(x A ) ≤ 2 G + σ 2 E ∥z∥ 2 q • B Φ (0, p (1) ) αT ≤ 2C Φ (p (1) ) • √ G √ T + √ c ε,δ • E ∥z∥ 2 q . (by σ 2 = T c ε,δ ) (12)Lastly, if we run sufficiently many iterations T ≥G c ε,δ •E[∥z∥ 2 q ], we get the stated result in the theorem.Proof. We first briefly introduce the idea for the proof. We will find a lower bound and an upper bound for the cumulative stationarity gap T t=1 g (t) , p (t) -p in Lemma 3.4. With a properly chosen p ∈ R m + ∩ W as a bridge, comparing these two bounds leads to the desired conclusion. For a given final allocation decision x A , we denote the resource underage level byv A := a(x A ) -nγb + ,where the positive part operator (•) + applies element-wise. It is self-evident that v A ≥ 0 by definition, and v A = 0 implies no constraint violation. Let j A := arg max j∈[m]∪{0} {u A j } be the index of the most-severely violated constraint. Specially, if j A = 0, then we know v A = 0, and we are done. Otherwise, we let e j A be an indicator vector with 1 on its (j A )'s position and 0 on others.Choose p := Ce j A ∈ R m + ∩ W with a constant C to be determined later, we reformulate the cumulative stationarity gapT t=1 g (t) , p (t) -Ce j A into T t=1 g (t) , p (t) -Ce j A = T t=1 g (t) , p (t) ( * ) + T t=1 g (t) , -Ce j A ( * * ) + T t=1 n (t) , p (t) -Ce j A ( * * * ), and control the three terms one by one.(*): First, rewrite ( * ) into a function of dual form:EQUATIONwhere the last inequality is from D(p (t) ) ≥ D(p * ) and applying Jensen's inequality to F(•). Next, we turn to control F(x A ). We observe that if more resource v A becomes available for the original allocation problem, then x A will be a feasible allocation. Hence, we can upper bound the value of F(x A ) with another problem having more resources. Denote the set of feasible allocations when b resource available by X (b) := {x := (x 1 , . . . , x n ) ∈ ⊗ n i=1 X i : a(x) ≤ b}. We haveEQUATIONLet p in (14) be p := p * , and plug (14) back into (13), we obtain( * ) ≥ -T • p * , v A ≥ -T v A ∞ • ∥p * ∥ 1 .(**): The second term ( * * ) helps characterize constraint violations:( * * ) = C T t=1 -g (t) , e j A = CT • 1 T T t=1 a(x (t) ) -nγb, e j A ≥ CT • a(x A ) -nγb, e j A (by assumption a(•) is convex) = CT v A ∞ .(by definitions of v A and e j A ) (***): The third term ( * * * ) involves zero-mean Gaussian noise vectors {n (t) } t that are independent of p (t) . While e j A is dependent on noise vectors, the dependence is not a big issue here, since e j A ∈ E 1 := {e ∈ {0, 1} m : ⟨e, 1⟩ = 1}, and the Gaussian Complexity G(E 1 ) := E z∼N (0,Im×m) sup e∈E1 ⟨e, z⟩ of the set E 1 can be well controlled:G(E 1 ) = E z∼N (0,Im×m) [max{z 1 , . . . , z m }] ≤ √ 2 ln m.Therefore, the term ( * * * ) admits a lower bound in expectation w.r.t. A as shown below:E A [( * * * )] = 0 -C • E A T t=1 n (t) , e j A ≥ -C • E A sup e∈E1 T t=1 n (t) , e = -C √ T σ • G(E 1 ) ≥ -C √ T σ • √ 2 ln m = -CT • c ε,δ • 2 ln m. (by σ = T c ε,δ )Finally, replacing three terms back and taking expectation w.r.t. A, we obtain a lower bound on the cumulative stationarity gap:E A T t=1 g (t) , p (t) -Ce j A ≥ T E A v A ∞ • (C -∥p * ∥ 1 ) -CT • c ε,δ • 2 ln m. (15)Now, we turn to another side and bound the cumulative stationarity gap from above. Suppose we can choose a proper C > 0 such that Ce j A ∈ R m + ∩ W almost surely, the expected cumulative stationarity gap thus can be bounded from above by employing Lemma 3.4:E A T t=1 g (t) , p (t) -Ce j A ≤ E A   η T t=1 g (t) 2 q 2α + 1 η B Φ (Ce j A , p (1) )   .Similarly, denote G := γ 2 n 2 ∥b∥ 2 q and G A :=T t=1 n (t) 2 q /T . Then E A T t=1 g (t) 2 q ≤ 2T • G + σ 2 E ∥z∥ 2 qwith z being a standard Gaussian vector. Plugging these values back, we getE A T t=1 g (t) , p (t) -Ce j A ≤ ηT • G + σ 2 E ∥z∥ 2 q α + 1 η E A B Φ (Ce j A , p (1) ) .Lastly, using stepsize η =EQUATION)Comparing the lower bound (15) with the upper bound (16) and using σ 2 = T c ε,δ , we immediately obtainT E A v A ∞ (C -∥p * ∥ 1 ) -CT c ε,δ • 2 ln m ≤ C Φ,1 (p (1) ) √ α • √ T G + T √ c ε,δ • E ∥z∥ 2 q .Rearranging the above inequality yields (assume C > ∥p * ∥ 1 )EQUATION) When T ≥ G c ε,δ •E[∥z∥ 2 q ], (17) impliesEQUATIONThe 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 * ∥ 1 and (ii)Ce j A ∈ R m + ∩ W for any j A ∈ [m].To this end, we can simply let C = 2 ∥p * ∥ 1 , and replacing C with 2 ∥p * ∥ 1 gives the desired result: A.6 Proof of Lemma 3.9EQUATIONProof. By the definition of strong convexity, it suffices to showEQUATIONAccording to the definition of parameterized negative entropy function, its gradient is ∇Φ(p; θ) j = θ j ln (p j θ j ) + θ j , ∀j ∈ [m]. By the well celebrated Hermite-Hadamard inequality fEQUATIONwhere the case a = 0 or b = 0, or both are obtained by continuity and the conventions that 0 0 = 0 and 0 ln 0 = 0. If we set b = p j θ j and a = q j θ j for (21), we can get (ln (p j θ j ) -ln (q j θ j )) • θ j (p j -q j ) ≥ 2θ j (p j -q j ) 2 p j + q j , ∀j ∈ (ln (p j θ j ) -ln (q j θ j )) • θ j (p j -q j ) ≥ m j=1 2θ j (p j -q j ) 2 p j + q j . (by ( 22))It remains to further lower bound the summation on the r.h.s. We follow the proof idea of Lemma 2 in [BLM23] to complete our proof:m j=1 2θ j (p j -q j ) 2 p j + q j = 2 ⟨θ, p + q⟩ • m j=1 θ j (p j + q j ) ⟨θ, p + q⟩ • |p j -q j | 2 (p j + q j ) 2 ≥ 2 ⟨θ, p + q⟩ •   m j=1 θ j (p j + q j ) ⟨θ, p + q⟩ • |p j -q j | p j + q j   2 (by Jensen's inequality) = 2 ⟨θ, p + q⟩ •   m j=1 θ j |p j -q j |   2 ≥ 1 K •   m j=1 θ j |p j -q j |   2 (since p, q ∈ ∆ int K (θ)) ≥ (min j {θ j }) 2 K • ∥p -q∥ 2 1 .A.7 Proof of Theorem 3.10Proof. The proof follows the general proof of Theorem 3.5 and 3.6 for any potential function Φ. It remains to properly modify results for the Φ chosen. When the potential function is the parameterized negative entropy Φ := Φ(w; b) = m j=1 w j b j ln (w j b j ) defined on ∆ int K (b) := {w > 0 : ⟨b, w⟩ ≤ K} with K = 2u γ , the conjugate index q = ∞, strong convexity parameter α = b 2 /K. Moreover, direct calculation gives the Bregman divergence B Φ (0, p (1) ) = b, p (1) . Because we choose p(1) j = K/(mb j ), ∀j ∈ [m], we thus have B Φ (0, p (1) ) = K.Utility Guarantee: It is evident that C Φ (p (1) ) := B Φ (0, p (1) )/α = K/(b 2 /K) = K/b. Therefore, the utility upper bound (7) becomesF(x * ) -E A F(x A ) = 4C Φ (p (1) ) • E ∥z∥ 2 ∞ • √ c ε,δ ≤ 4 K b • 2 ln (2m) • √ c ε,δ = 8 √ 2u • ln (2m) γb • √ c ε,δ .Feasibility Guarantee: We can work from (19) and first figure out C Φ,1 (p (1) ). Direct calculation gives B Φ (Ce j , p (1) ) = B Φ (0, p (1) ) + Cb j • ln(C/p(1)j ) -1 , ∀j ∈ [m]. Plugging C = 2 ∥p * ∥ 1 , we can upper bound C Φ,1 (p (1) ) as: C Φ,1 (p (1) ) := B Φ (0, p (1) ) + max j B Φ (Ce j , p (1) ) B Φ (0, p (1) ) = 2 √ K + 2 ∥p * ∥ 1 max j b j • ln 2∥p * ∥ 1 mbj K -1 , 0 √ K (since p (1) j = K/(mb j )) ≤ 2 √ K + √ K • max j {b j • (ln (mb j ) -1) , 0} (K ≥ 2 ∥p * ∥ 1 , Lemma 3.8) ≤ 2 √ K + √ Kb • (ln mb -1) + .Substitute C Φ,1 (p (1) ) back into (19) with K = 2u γ , we getE A v A ∞ ≤ 4u 2 ln (2m) • 2 + b • (ln mb -1) + γb • ∥p * ∥ 1 • √ c ε,δ .B Proofs for Section 4B.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 immediately as any randomized mapping can be decomposed into a convex combination of deterministic functions. The proof here largely follows the same idea for the proof of Billboard Lemma. For anyx ∈ X n , let f (x -k , D -k ) := (f (x 1 , z 1 ), . . . , f (x k-1 , z k-1 ), f (x k+1 , z k+1 ), . . . , f (x n , z n )). For any subset S ⊆ Y n-1 , let f -1 (S; D -k ) := x -k ∈ X n-1 : f (x -k , D -k )∈ S be the preimage of S with respect to the mapping f (•, D -k ). Then, we can show thatPr [f (M(D) -k , D -k ) ∈ S] = Pr M(D) -k ∈ f -1 (S; D -k ) ≤ e ε • Pr M(D ′ ) -k ∈ f -1 (S; D -k ) + δ (M(•) is (ε, δ)-JDP) = e ε • Pr [f (M(D ′ ) -k , D -k ) ∈ S] + δ = e ε • Pr f (M(D ′ ) -k , D ′ -k ) ∈ S + δ, (D -k = D ′ -k) which confirms JDP guarantee after self post-processing.Proof. Similarly, the proof is for a deterministic function f . Let f -1 (S) be the preimage of S. For any S ⊆ Y:Pr [f (M(D) -k ) ∈ S] = Pr M(D) -k ∈ f -1 (S) ≤ e ε • Pr M(D ′ ) -k ∈ f -1 (S) + δ (M(•) is (ε, δ)-JDP) = e ε • Pr [f (M(D ′ ) -k ) ∈ S] + δ.The proof consists of several steps: (i) construct a "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 a "hard" distribution of datasets.Let Id(•) be the identity function, and let 1 and 0 be vectors of 1's and 0's whose lengths are m. Define three types of requests:z := (x → ⟨1, x⟩ , Id(•), {1x : x ∈ [0, 1]}); z 1 := (x → ⟨1, x⟩ , Id(•), {1x : x = min{1, nγ}}); z 0 := (x → ⟨1, x⟩ , Id(•), {1x : 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 1 and 2). In what follows, we construct datasets that satisfy Assumption 2.5 (part 3 and 4) and Assumption 3.7 as well.Based on these requests, we construct a pair of neighboring datasets that differ in agent n only: It is easy to verify that part 3 of Assumption 2.5 is also met, i.e., the primal problem is always feasible, and the optimal shadow price is p * = 1, which are non-zeros. The result p * = 1 is by noticing that one unit increase in available resource will increase the objective value of the primal problem by 1.Since p * = 1, it immediate to see that part 4 of Assumption 2.5 also holds, because now the function u i (x i ) + ⟨p * , -a i (x i )⟩ becomes ⟨1, x i ⟩ + ⟨1, -x i ⟩, which is always non-negative for any x i ∈ X i . Moreover, the constraint to be dualized is a linear constraint; thus Assumption 3.7 strong duality holds.Lastly, let dataset D be drawn from Unif{D 0 , D 1 }, i.e. uniformly distributed over these two datasets.Step 2: Identify necessary conditions on JDP algorithm ALet x A (D) := (x A 1 (D), . . . , x A n (D)) be the output of (ε, δ)-JDP algorithm A. The self postprocessing Lemma 4.1 says that if we process each x A i with i's own data, the resulting output is still JDP. That implies (Id(x A 1 ), . . . , Id(x A n )) should also be (ε, δ)-JDP. Moreover, the postprocessing 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   i̸ =n Id(x A i (D)) ∈ S   ≤ e ε Pr   i̸ =n Id(x A i (D ′ )) ∈ S   + δ, ∀S ⊆ [0, nγ1].Instantiating the above inequality with D = D 0 , D ′ = D 1 , and S = (nγ1 -c1, nγ1] with c := min{1, nγ} leads toPr   i̸ =n x A i (D 0 ) ∈ (nγ1 -c1, nγ1]   ≤ e ε Pr   i̸ =n x A i (D 1 ) ∈ (nγ1 -c1, nγ1]   + δ.We can simplify the preceding inequality by changing decision variables from bold format x i to normal format x i , because by construction of requests z, z 1 , z 0 , each decision vector x i := 1x i is fully determined by a single scalar x i . This leads to the following equivalent inequality,Pr   i̸ =n x A i (D 0 ) ∈ (nγ -c, nγ]   ≤ e ε Pr   i̸ =n x A i (D 1 ) ∈ (nγ -c, nγ]   + δ. (23)Moreover, when dataset is D 1 , agent n should always be assigned c unit, forcing resource available for others to be at most nγ -c. Thus, if A is an (ε, δ)-JDP algorithm outputting a feasible allocation with probability 1, then i̸ =n x A i (D 1 ) ≤ nγ -c w.p. 1, and (23) becomes:EQUATION)Therefore, we get a necessary condition (24) for any A being (ε, δ)-JDP: when dataset is D 0 , Algorithm A should not assign many resources to other agents, and only with a small probability δ, other agents can get at least nγ -c resources.Step 3: Reformulate the minimax boundLet ∆ ∈ [0, nγ] be a constant to be determined later, and let S + ∆ := (nγ -∆, nγ], S - ∆ := [0, nγ -∆] be two disjoint regions partitioning the interval [0, nγ]. Let I ∈ {0, 1} m be an indicator so that 1 in j's position implies( n i=1 x A i ) j ∈ S + ∆ ; otherwise, in S - ∆ . Let event E I := {(x 1 , . . . , x n ) : 1 ( n i=1 x i ) j ∈ S + ∆ = I j , ∀j ∈ [m]}.With these notations and the law of total probability, we first rewrite the expression of Algorithm A's utility when dataset is D 0 as:E A F(x A (D 0 )) = I∈{0,1} m E A n i=1 1, x A i (D 0 ) x A (D 0 ) ∈ E I • Pr x A (D 0 ) ∈ E I = I∈{0,1} m E A   n i=1 m j=1 x A i (D 0 ) j x A (D 0 ) ∈ E I   • Pr x A (D 0 ) ∈ E I = I∈{0,1} m E A   m j=1 n i=1 x A i (D 0 ) j x A (D 0 ) ∈ E I   • Pr x A (D 0 ) ∈ E I .We observe that when event E I happens, the resource consumed n i=1 x A i (D 0 ) j is no more than either nγ -∆ or nγ, depending on I j . Hence, we can reach an upper bound expressed by I j :E A F(x A (D 0 )) ≤ I∈{0,1} m E A   m j=1 [(nγ -∆)1 {I j = 0} + nγ1 {I j = 1}] E I   • Pr x A (D 0 ) ∈ E I = I∈{0,1} m E A   mnγ - m j=1 ∆1 {I j = 0} E I   • Pr x A (D 0 ) ∈ E I = mnγ -∆ m j=1 I∈{0,1} m E A 1 {I j = 0} E I Pr x A (D 0 ) ∈ E I = mnγ -∆ m j=1 E A [1 {I j = 0}] = mnγ -∆ m j=1 Pr   n i=1 x A i (D 0 ) j ∈ S - ∆   .Due to the construction of D 0 that x A i := 1x A i , the probability terms in the preceding inequality should be the same among all j = 1, . . . , m; thus, we haveE A F(x A (D 0 )) ≤ mnγ -m∆ • Pr n i=1 x A i (D 0 ) ∈ S - ∆ .Moreover, with D 0 , the allocation to agent n should be x A n (D 0 ) = 0, modifying the preceding inequality intoEQUATIONWe note that with either dataset D 0 or D 1 , the optimal utility obtained in the non-private setting is always mnγ, i.e., F(x * (D 0 )) = F(x * (D 1 )) = mnγ. As a result, the minimax regret is lower bounded as follows:EQUATIONwhere the second inequality is by considering D 0 and plugging in (25).Step 4: Combine all together Suppose ε ≥ max{1, 1/(nγ)}. If we set ∆ = 1 ε , the r.h.s. of (26) becomes m 2ε • inf A Pr i̸ =n x A i (D 0 ) ∈ [0, nγ -1/ε] . Since 1/ε ≤ min{1, nγ} = c, it follows that Pr   i̸ =n x A i (D 0 ) ∈ [0, nγ -1/ε]   ≥ Pr   i̸ =n x A i (D 0 ) ∈ [0, nγ -c]   = 1 -Pr   i̸ =n x A i (D 0 ) ∈ (nγ -c, nγ]   ≥ 1 -δ ≥ 1 2 .(by (24) and δ ∈ (0, 1/2))Plugging the preceding inequality back into (26) immediately leads toinf A is (ε, δ)-JDP sup D F(x * (D)) -E A F(x A (D)) ≥ m 4ε ,which completes the proof.The lower bound in Theorem 4.3 only holds for ε ≥ max{1, 1/(nγ)}. Intuitively, this is because we 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 A sup D is not used. Noticing this oversight, we provide a lower bounding problem that fills this gap.We start with expressing DP in terms of hockey-stick divergence. Suppose µ and µ ′ are two probability measures that are absolutely continuous with respect to each other. Let H e ε (X, Y ) := z∈Z dµ dµ ′ (z) -e ε + dµ ′ (z) be the hockey-stick divergence between two random variables X, Y .Let M be an (ε, δ)-DP mechanism, and let M(D) -k := Π -k M(D) be the random vector of n -1 elements projected to others than agent k. Here are some relationships among indistinguishability, DP, and JDP.• (ε, δ)-indistinguishability: if H e ε (X, Y ) ≤ δ, then X is said to be (ε, δ)-indistinguishable from Y ; • (ε, δ)-DP: for a mechanism M, if sup D∼D ′ H e ε (M(D), M(D ′ )) ≤ δ, we say M is (ε, δ)- DP [BBG18]; • (ε, δ)-JDP: for a mechanism M, if sup D∼D ′ ,k H e ε (M(D) -k , M(D ′ ) -k ) ≤ δ, we say M is (ε, δ)-JDP.It is self-evident from these relationships that DP requires indistinguishability between outputs for any pair of neighboring datasets, while JDP requires indistinguishability 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 1-:= (z 0 , z, . . . , z n-1 requests ), D 1+ := (z 1 , z, . . . , z n-1 requests ), D 1+,2+ := (z 1 , z 1 , z, . . . , z n-2 requests).It is obvious D 1-∼ D 1+ , and D 1+ ∼ D 1+,2+ are pairs of neighboring datasets. Let S -k (x A ) := i̸ =k x A i be the total consumption excluding agent k. By the definition of (ε, δ)-JDP, any JDP algorithm A should satisfy following necessary constraints:EQUATIONEQUATIONEQUATIONEQUATIONThe variable x A (D 1+,2+ ) in both constraints (28) and (29) should be the same, and thus links both constraints. Moreover, the variable x A (D 1-) 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 1-here is essentially the same as D 0 in the proof of Theorem 4.3; thus all analysis for D 0 can be borrowed. Consequently, following the same analysis for (26), we get a lower bound expressed by an inf problem:inf A is (ε, δ)-JDP sup D F(x * (D)) -E A F(x A (D)) ≥ m 2ε • inf A s.t. (27)-(30) Pr S -1 (x A (D 1-)) ∈ [0, nγ - 1 ε ] .We believe analyzing the inf problem with tools in [BBG18] , such as couplings, is promising. After this base case, one can easily extend the set of constraints ( 27)-(30) to take account of more loops.All experiments were run on a 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.minimize method. Source code is available in supplementary materials. Datasets are publicly available as discussed in the main text.When running the algorithm, the only parameter different from Theorem 3.10 is K := 1.1u/(γb), where Theorem 3.10 suggests K := 2u/(γb). The constant factor is modified from 2 to 1.1, as a 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 Notes. We run our algorithm A Noisy Dual MD with two potential functions: negative entropy (abbr. ne) and squared ℓ2-norm function (abbr. ℓ2). Settings are the same as in Figure 1 . bold=better functions, always outperform the existing method. However, the performance of "A w. neg.entr" seems independent of ε and the performance of [HHRW16] 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 in Table 5 below. It should be clear from Table 5 that constraint violations are reduced Table 5 : Constraint violations, mean±sd. Settings are the same as in Figure 1 Total violation Max violation MD_ne MD_l2 [HHRW16] MD_ne MD_l2 [HHRW16] ε = 1 7.9±1.3 6.7±1.7 4.9±0.7 2.7±0.4 2.8±0.6 2.0±0.3 ε = 2 7.0±1.2 6.7±1.8 4.6±0.7 2.4±0.5 2.7±0.7 1.9±0.4 ε = 5 6.4±1.0 5.6±1.5 4.3±0.9 2.1±0.4 2.4±0.6 2.0±0.4 ε = 10 5.1±1.2 4.1±1.5 3.4±0.8 1.8±0.4 1.7±0.5 1.6±0.4 ε = 20 3.5±1.2 2.9±1.0 2.1±0.8 1.4±0.4 1.2±0.4 1.2±0.4 when ε increases, which indicates that our algorithm can maintain a good optimality performance while better reducing constraint violations. While [HHRW16] 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 6 . Impact of "K_constant" From our experiments, we found that the constant factor of 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 in Appendix here, we let their K_constant change as well, in order to gain more understandings of its impact. We find that, when the constant is 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 is evident that when K_constant is small, we get smaller gaps but higher constraint violations. Additionally, when ε takes large values (say, ε = 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 is negative, which means F(x A ) ≥ F(x * ). Considering x A may violate some constraints, this phenomenon is possible. We repeat Table 3 -6.9±1.5 1.8±1.4 13.8±1.3 12.3±0.9 256.7±16.0 156.8±20.8 30.3±10.8 15.7±6.7 MD_l2 (ours) 4.3±3.4 2.8±2.3 1.2±0.8 0.7±0.7 54.6±18.5 35.1±14.8 12.6±4.6 7.2±3.3 MD_ne (ours) 6.0±4.1 3.0±2.1 1.1±0.9 0.6±0.6 47.8±23.0 25.8±12.0 13.4±5.9 4.5±2.5 3000 [HHRW16] -29.4±0.9 -18.9±1.2 6.9 ±1.2 8.2±1.0 > 10 3 > 10 3 743.8±25.7 680.1±29.4 MD_l2 (ours) 4.3±5.1 3.0±2.4 2.0±1.3 1.5±0.7 193.9±54.1 97.2±23.9 39.8±12.6 22.0±6.3 MD_ne (ours) 10.4±5.2 6.1±3.0 3.0±1.1 1.6±0.6 134.5±56.4 65.4±25.1 27.9±8.4 18.1±6.0Notes. Algorithm parameters: K = 1.1u/(γb), δ = .01, T = 10 4 . Other settings follow Theorem 3.10. MD_l2 and MD_ne means potential function is squared ℓ2 and negative entropy, respectively. For three cases n = 800, 1500, 3000, we set resource level γ = 0.1, 0.05, 0.02, respectively. For all values in the table, the lower the better. Bold=better.that optimality gaps should be understood together with constraint violations. Some observations from the table are:1. When ε is small (ε = 1, 2), while [HHRW16] 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 ε gradually grows, our algorithms have a clear pattern of convergence, i.e., smaller optimality gap and fewer constraint violations; but the pattern for [HHRW16] is not clear enough. We conjecture that this is because of high-variance noises injected. 3. If constraint violation matters, MD_ne is most preferred.Runtime Runtimes are reported in Table 8 . Compared to existing methods, our algorithms do not observe a significant increase in runtime. Moreover, as we set T = 10 4 , we can in fact complete training within one hour, even for the largest case with n = 3000.Dual convergence Figure 4 shows the progress of dual variables convergence. The y-axis is the gap between dual variables by our algorithms and the optimal dual variables, while x-axis is the training progress. Shadow areas indicate standard deviations. It is evident that when ε is larger, dual variables converge faster to optimal values, and stay around the optimal values in remaining iterations. When ε 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. 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.p A ||2 ||p * ||2 × 100% Q _YDUHSV Q _YDUHSV Q _YDUHSV Q _YDUHSV ||p * -p A ||2 ||p * ||2 × 100% Q _YDUHSV Q _YDUHSV Q _YDUHSV Q _YDUHSV WUDLQLQJSURJUHVVt/T × 100% ||p * -p A ||2 ||p * ||2 × 100% Q _YDUHSV WUDLQLQJSURJUHVVt/T × 100% Q _YDUHSV WUDLQLQJSURJUHVVt/T × 100% Q _YDUHSV WUDLQLQJSURJUHVVt/T × 100% Q _YDUHSV XSGDWHBUXOH PGBO PGBQHGuidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No 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 as long as it is clear that these goals are not attained by the paper.Two random variables X, Y are (ε, δ)-indistinguishable if both Pr [X ∈ S] ≤ e ε Pr [Y ∈ S] + δ and Pr [Y ∈ S] ≤ e ε Pr [X ∈ S] + δ hold for any subset S. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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).

2. 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).
questions: questions: MAJOR QUESTIONS:
1. About point 1 in weaknesses, it would be more consistent if the authors try to:
a) Provide high-probability results for the constraint violation upper bounds (this should be easy, using the high probability tail bounds of Gaussian noise addition).
b) Provide lower bounds for joint DP resource allocation problems.
2. 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.


MINOR QUESTIONS:
1. 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.
2. 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.
3. 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.
4. The paragraph right after Theorem 3.10 about "purchasing resources" I also found it very confusing. Please make efforts to clarify it.
5. 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: limitations: N/A
paper_summary: paper_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.

The 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.
strength_weakness: strength_weakness: 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.
Additionally, 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?
questions: 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: limitations: Yes, the authors have adressed the limitations of their work.
paper_summary: paper_summary: The paper studies a class of convex resource allocation problems, in which the utilities and constraints are private (and bounded).
The 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).
The main technical result is an improvement of the utility bound (improves dependency on number of constraints)
strength_weakness: strength_weakness: - 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.
- 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.
- 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?

Minor:
- 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.
- 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?
- 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.
- Using $u$ both for utility functions and "violation levels" (line 183) is confusing. Please choose a different notation.
- 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).
- 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$.
- Assumption 2.4.3 should be rephrased. Maybe "the constant $\gamma$ in (4) is assumed to be ..."
questions: questions: Please see weaknesses section.
limitations: limitations: Additional limitations should be discussed:
- The near optimality claim is not fully justified (given the feasibility assumption in the lower bound).
- The algorithm and analysis assume primal updates can be done exactly.

Comments: title: Answer to Rebuttal
Thank you
Answer to Rebuttal
comment: I want to thank the authors for answering my questions. I find them satisfactory and it helped me understand the performance of their algorithm much better.
Thank you very much for raising the score. And we are happy to know our response cleaned your concerns. 
As for the efficiency measure, we agree with you and also believe keeping both results would be more informative. So we will keep both.

Last, thank you again for all your valuable suggestions throughout the review process. Thank you!
First, I would like to thank the authors for their clarifications and thorough work on improving the paper and the results. I generally agree with the authors' answer and proposals, and I am raising my score.

there are still two things I find are worth commenting on:

1. About the efficiency measure. While I understand that there is a welfare interpretation that justifies merging the suboptimality gap and constraint violations, I think there is still value in stating results in a bi-criteria sense (i.e., separately addressing the suboptimality and $\ell_{\infty}$ constraint violation). This for various reasons:
a) Utilities and constraints could be in different scales (money transfers cans equalize scales, but it is still s.t. which may be specific of the application).
b) The polylog upper bounds look far less exciting when they are added (and some information is lost IMO).
All in all, my suggestion is that you keep both results.

2. About the high-probability constraint violations. That's interesting! Thank you for the clarification. If the only issue in this sandwiching is the term $\sum_t <n^{(t)}, p^{(t)}>$, I am possibly wrongt about this, but at this point you are already constraining the dual variables $p$ to lie on the simplex, and since they are predictable (and bounded) it should not be too difficult to upper bound this sum w.h.p. (usiing standard martingale arguments). There are other nontrivial bounds happening in this proof, so I am not sure whether this is enough. BTW, I think it's OK if you don't address this for the submission.