Solving Positive Linear Programs with Differential Privacy

Adrian Vladu; Alina Ene; Huy Le Nguyen; Ta Duy Nguyen

arxiv: 2604.26838 · v2 · pith:KISQ3XV4new · submitted 2026-04-29 · 💻 cs.DS

Solving Positive Linear Programs with Differential Privacy

Alina Ene , Huy Le Nguyen , Ta Duy Nguyen , Adrian Vladu This is my paper

Pith reviewed 2026-05-07 12:02 UTC · model grok-4.3

classification 💻 cs.DS

keywords positivealgorithmsconstraintlinearonlyprivacyprivateprograms

0 comments

The pith

Differentially private solvers for positive LPs that approximate solutions with bounded constraint violations and improve on prior instance-dependent and new data-independent guarantees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Positive linear programs are optimization tasks with all nonnegative numbers, used for allocating resources or covering demands. The setting here is high-sensitivity privacy where one constraint can change arbitrarily, so the algorithm cannot protect every constraint perfectly. The authors adapt a dense multiplicative-weights method, analyzed from a regularized dual perspective, to output approximate solutions that violate only a limited number of constraints. They improve earlier guarantees that depended on the specific instance and add new bounds that depend only on the number of variables or constraints. The approach exploits the nonnegative structure of the programs to control the privacy-accuracy trade-off.

Core claim

We give private solvers that return approximate solutions while violating only a controlled number of constraints. Our algorithms improve the prior instance-dependent guarantees, and also yield new data-independent bounds that depend only on the dimension.

Load-bearing premise

The focus on positive linear programs (nonnegative coefficients and variables) in the high-sensitivity constraint-private regime of Hsu et al., where full constraint satisfaction under privacy is impossible.

read the original abstract

We study differentially private approximation algorithms for positive linear programs (LPs with nonnegative coefficients and variables), focusing on the fundamental families of packing, covering, and mixed packing-covering formulations. We focus on the high-sensitivity, constraint-private regime of Hsu-Roth-Roughgarden-Ullman (ICALP 2014), where neighboring instances may differ by an arbitrary single constraint, so one cannot hope to approximately satisfy every constraint under privacy. We give private solvers that return approximate solutions while violating only a controlled number of constraints. Our algorithms improve the prior instance-dependent guarantees, and also yield new data-independent bounds that depend only on the dimension. Our techniques involve a dense multiplicative weights update method developed from a regularized dual viewpoint, which we analyze in a way that exploits structure specific to positive LPs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives private solvers for positive LPs with improved instance-dependent results plus new dimension-only bounds via dense MWU on the regularized dual.

read the letter

The main thing to know is that the authors improve differentially private approximation for positive linear programs by returning solutions that violate only a controlled number of constraints, with both better instance-dependent guarantees and new bounds that depend only on dimension rather than the specific instance data. This sits in the high-sensitivity constraint-private model from Hsu et al., where full constraint satisfaction is impossible under privacy, so the controlled-violation relaxation is the right target. Their approach develops a dense multiplicative-weights update from a regularized dual and uses the nonnegativity of coefficients and variables to control the analysis. That structure-specific step is what lets them escape purely instance-dependent bounds. The work covers packing, covering, and mixed formulations, which keeps the results relevant to resource-allocation style problems. The high-level technique looks like a natural and honest extension of existing MWU and duality tools rather than a forced fit. A soft spot is that the abstract gives no proof details or explicit error terms, so it is hard to judge how clean the analysis is or whether extra logarithmic factors appear in the final bounds. If the full paper delivers tight, reproducible derivations without hidden assumptions, the improvement holds; otherwise the dimension-dependent claim could be weaker than advertised. This is for people working on private optimization or approximation algorithms for LPs. A reader who knows MWU and LP duality will get concrete technical value from the new bounds. The paper deserves peer review because the problem is central, the claims are specific, and the technique is grounded enough to merit checking the details.

Referee Report

0 major / 2 minor

Summary. The paper develops differentially private approximation algorithms for positive linear programs (packing, covering, and mixed packing-covering) in the high-sensitivity constraint-private model. In this regime, neighboring instances differ by a single arbitrary constraint, making it impossible to approximately satisfy all constraints under privacy. The algorithms return approximate solutions while violating only a controlled number of constraints, improving prior instance-dependent guarantees and providing new data-independent bounds that depend only on the dimension. The central technique is a dense multiplicative-weights update method derived from a regularized dual formulation that exploits the nonnegativity structure of positive LPs.

Significance. If the results hold, the paper makes a solid contribution to differentially private optimization. It advances the state of the art by tightening instance-dependent violation bounds and adding clean dimension-only bounds that are independent of the specific data. The regularized-dual derivation of the dense MWU method is a technically interesting approach that leverages positive-LP structure in a natural way and may generalize. The work is well-motivated by the known impossibility results in the constraint-private model and builds directly on standard LP duality and privacy definitions without circularity or hidden parameters.

minor comments (2)

[Abstract] The abstract and introduction would benefit from a brief, self-contained definition or example of what 'dense' MWU means in this context and why the regularization is required to obtain the stated bounds.
Notation for the positive LP families (packing, covering, mixed) and the precise privacy model (neighboring relation on constraints) should be introduced with a single displayed equation block early in the paper for reference.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and constructive review. We are pleased that the referee recognizes the paper's contributions to differentially private solvers for positive LPs in the constraint-private model, the improvements to instance-dependent violation bounds, the new dimension-dependent data-independent bounds, and the technical value of the regularized dual derivation of the dense MWU method. The referee's assessment aligns with our view that the work is well-motivated by known impossibilities and builds directly on standard LP duality without circularity.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper derives private solvers for positive LPs via a dense MWU method from a regularized dual viewpoint, exploiting nonnegativity and standard LP duality plus privacy definitions. No load-bearing step reduces by construction to a fitted parameter, self-definition, or self-citation chain. The cited Hsu et al. (2014) regime is external prior work defining the model, not an internal reduction. The instance-dependent and dimension-only bounds follow from the analysis without renaming known results or smuggling ansatzes. The central claim remains independently verifiable against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Relies on standard assumptions of linear programming theory and differential privacy definitions; no new entities or fitted parameters introduced in the abstract.

axioms (2)

domain assumption Linear programs have nonnegative coefficients and variables (positive LPs)
Explicit focus stated in the abstract for packing, covering, and mixed formulations.
domain assumption Neighboring instances differ by an arbitrary single constraint in the high-sensitivity regime
References the Hsu-Roth-Roughgarden-Ullman (ICALP 2014) setting where full privacy without violations is impossible.

pith-pipeline@v0.9.0 · 5429 in / 1231 out tokens · 83946 ms · 2026-05-07T12:02:13.379083+00:00 · methodology

Solving Positive Linear Programs with Differential Privacy

Core claim

Load-bearing premise

discussion (0)