Research map / Bandits and online learning / Online convex optimization and games
Noisy Dual Mirror Descent: A Near Optimal Algorithm for Jointly-DP Convex Resource Allocation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Noisy Dual Mirror Descent, a JDP algorithm for convex resource allocation that runs noisy mirror descent on the dual shadow prices, with Rényi-DP accounting, near-optimal utility/feasibility bounds under strong duality, and a matching minimax lower bound for ε ≥ max{1, 1/(nγ)}.
Problem
Convex resource allocation with m hard coupling constraints across n agents under (ε,δ)-joint differential privacy, where prior methods use loose advanced composition and fail to exploit dual geometry, and minimax limits were unknown.
Approach
Apply noisy mirror descent to the Lagrangian dual to privatize shadow prices (tighter privacy via Rényi DP), then compute primal allocations from averaged prices; under strong duality, use a parameterized negative-entropy mirror map matched to the l1 geometry of a scaled simplex to improve dependence on m and ε.
Key results
- Under strong duality, the utility gap and total ultimate performance are Õ(√ln(1/δ)/ε) for utility and Õ(m√ln(1/δ)/ε) combined, improving over prior Õ(m^{3/2}) constraint violation bounds.
- A minimax lower bound of m/(4ε) is proven for any JDP algorithm outputting feasible allocations when ε ≥ max{1, 1/(nγ)}, matching the upper bound up to log factors.
- Experiments show the proposed MD variants have substantially smaller optimality gaps than Hsu et al. (2016) at slightly higher constraint violations, e.g., at n=800, ε=1 the negative-entropy variant has 2.1% gap vs -1.8% for baseline with 23.9 vs 84.8 total violation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Noisy Dual Mirror Descent instead of HHRW16 | Assignment problem · n=3000, ε=10 | total constraint violation (1/n): 680.1±29.4 -> 18.1±6.0 | Helped |
| use negative entropy potential instead of squared ℓ2 potential (ablation) | Noisy Dual Mirror Descent · Assignment problem, ε=1 across n=800, 1500, 3000 | optimality gap (%): 1.8±3.9 -> 2.1±4.0; 4.3±3.4 -> 6.0±4.1; 4.3±5.1 -> 10.4±5.2 | Hurt |
| use negative entropy potential instead of squared ℓ2 potential (ablation) | Noisy Dual Mirror Descent · Assignment problem, ε=10 across n=800, 1500, 3000 | total constraint violation (1/n): 2.7±1.6 -> 2.6±1.5; 7.2±3.3 -> 4.5±2.5; 22.0±6.3 -> 18.1±6.0 | Helped |
| increase the negative-entropy radius constant K from 1.1 to 2.0 (ablation) | Noisy Dual Mirror Descent workforce scheduling · Workforce scheduling | optimality gap (%) | Hurt |
| increase the negative-entropy radius constant K from 1.1 to 2.0 (ablation) | Noisy Dual Mirror Descent workforce scheduling · Workforce scheduling | constraint violations | Helped |
Surprising findings
- The baseline of Hsu et al. (2016) attains a negative optimality gap (-1.8%) at ε=1 on the n=800 assignment instance, i.e. it reports a utility above the nominal optimum because it violates constraints heavily.
Limitations
- Lower bound only holds for ε ≥ max{1, 1/(nγ)}; general ε left open.
- Feasibility is only guaranteed in expectation and the total performance counts constraint violations, so the output may be infeasible.
- Choice of K (radius) is tuned empirically (K constant 1.1 instead of theoretical 2) and identifying a private way to tune it is open.
Experimental setup
Datasets: workforce scheduling data (public, Opt24) assignment problem raw data (Bea04)
Benchmarks: workforce scheduling instance (7 workers, 14 days) assignment problems (m,n)=(8,800),(15,1500),(30,3000)
Metrics: optimality gap (%) total constraint violation
Baselines: Hsu et al. 2016 dual gradient descent MD_l2 (ours variant) Hsu-Zhang dual multiplicative weights
Builds on: dual gradient descent (HHRW16) dual multiplicative weights (HZ18) Billboard Lemma noisy mirror descent
Closest papers by meaning
- Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates (AAAI 2025 · similarity 0.86)
- Faster Algorithms for User-Level Private Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.86)
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.86)
- Improved Differentially Private and Lazy Online Convex Optimization: Lower Regret without Smoothness Requirements (ICML 2024 · similarity 0.85)
- Convergent Privacy Loss of Noisy-SGD without Convexity and Smoothness (ICLR 2025 · similarity 0.85)
- Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.