An official website of the United States government
Noise perturbation is one of the most fundamental approaches for achieving (ε,δ)-differential privacy (DP) guarantees when releasing the result of a query or function ƒ(•)∈RMevaluated on a sensitive datasetx. In this approach, calibrated noisen∈ RMis used to obscure the difference vectorf(x) 0 f(x'), wherex' is known as a neighboring dataset. A DP guarantee is obtained by studying the tail probability bound of a privacy loss random variable (PLRV), defined as the Radon-Nikodym derivative between two distributions. Whennfollows a multivariate Gaussian distribution, the PLRV is characterized as a specific univariate Gaussian. In this paper, we propose a novel scheme to generatenby leveraging the fact that the perturbation noise is typically spherically symmetric (i.e., the distribution is rotationally invariant around the origin). The new noise generation scheme allows us to investigate the privacy loss from a geometric perspective and express the resulting PLRV using a product measure, W x U; measureWis related to a radius random variable controlling the magnitude ofn, while measureUinvolves a directional random variable governing the angle betweennand the difference ƒ(x)-ƒ(x'). We derive a closed-form moment bound on the product measure to prove (ε,δ)-DP. Under the same (ε,δ)-DP guarantee, our mechanism yields a smaller expected noise magnitude than the classic Gaussian noise in high dimensions, thereby significantly improving the utility of the noisy result ƒ(x)+n. To validate this, we consider privacy-preserving convex and non-convex empirical risk minimization (ERM) problems in high dimensional space. We propose leveraging our developed noise in output perturbation, objective perturbation, and gradient perturbation to establish DP guarantees when solving ERMs. Experiments on multiple datasets show that our method achieves significant utility improvements for convex ERM models (e.g., regression and SVM) under the same privacy guarantees. For non-convex models (e.g., neural networks), it provides substantially stronger privacy guarantees under comparable utility. Code Repository: https://github.com/issleepgroup/Product-Noise-ERM
more »
« less
Practical and Accurate Local Edge Differentially Private Graph Algorithms
The rise of massive networks across diverse domains necessitates sophisticated graph analytics, often involving sensitive data and raising privacy concerns. This paper addresses these challenges usinglocal differential privacy (LDP), which enforces privacy at the individual level, whereno third-party entity is trusted, unlike centralized models that assume a trusted curator. We introduce novel LDP algorithms for two fundamental graph statistics:k-core decomposition and triangle counting. Our approach leverages input-dependent private graph properties—specifically degeneracy and maximum degree—to improve theoretical utility. Unlike prior methods, our error bounds depend on the maximum degree rather than the total edge count, yielding significantly tighter guarantees. For triangle counting, we improve on the work of Imola, Murakami, and Chaudhury [USENIX Security '21, '22], which bounds error in terms of edge count. Our algorithm instead achieves bounds based on degeneracy by leveraging a private out-degree orientation, a refined variant of Eden et al.'s randomized response technique [ICALP '23], and a novel analysis, yielding stronger guarantees than prior work. Beyond theoretical gains, we are the first to evaluate local DP algorithms in a distributed simulation, unlike prior work tested on a single processor. Experiments on real-world graphs show substantial accuracy gains: ourk-core decomposition achieves errors within 3xof exact values, far outperforming the 131x error in the baseline of Dhulipala et al. [FOCS '22]. Our triangle counting algorithm reduces multiplicative approximation errors by up tosix orders of magnitude, while maintaining competitive runtime.
more »
« less
- PAR ID:
- 10690217
- Publisher / Repository:
- Proceedings of the VLDB Endowment
- Date Published:
- Journal Name:
- Proceedings of the VLDB Endowment
- Volume:
- 18
- Issue:
- 11
- ISSN:
- 2150-8097
- Page Range / eLocation ID:
- 4199 to 4213
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In thetrace reconstruction problem, an unknown source stringx∈ {0,1}nis sent through a probabilisticdeletion channelthat independently deletes each bit with probability δ and concatenates the surviving bits, yielding atraceofx. The problem is to reconstructxgiven independent traces. This problem has received much attention in recent years both in the worst-case setting wherexmay be an arbitrary string in {0,1}n[7,8,10,11,12,23] and in the average-case setting wherexis drawn uniformly at random from {0,1}n[7,8,12,13,25]. This article studies trace reconstruction in thesmoothed analysissetting, in which a “worst-case” stringxworstis chosen arbitrarily from {0,1}n, and then a perturbed versionxofxworstis formed by independently replacing each coordinate by a uniform random bit with probability σ. The problem is to reconstructxgiven independent traces from it. Our main result is an algorithm that, for any constant perturbation rate 0< σ < 1 and any constant deletion rate 0 < δ < 1, uses poly(n) running time and traces and succeeds with high probability in reconstructing the stringx. This stands in contrast with the worst-case version of the problem, for which\(\text{exp}(\tilde{O}(n^{1/5}))\)is the best known time and sample complexity [8]. Our approach is based on reconstructingxfrom the multiset of its short subwords and is quite different from previous algorithms for either the worst-case or average-case versions of the problem. The heart of our work is a new poly(n)-time procedure for reconstructing the multiset of allO(logn)-length subwords of any source stringx∈ {0,1}ngiven access to traces ofx.more » « less
-
The densest subgraph discovery (DSD) problem is a fundamental task in graph mining with applications in social networks, bioinformatics, graph databases, and systems engineering. Given a graphG= (V, E) and an integerk? 2, the goal is to find a vertex subsetD?Vwhose induced subgraphG(D) maximizes thek-clique density, defined as the number ofk-cliques per vertex. Larger values ofkcapture higher-order connectivity patterns beyond edges, enabling the discovery of more cohesive structures. We present a GPU-accelerated framework that integrates a warp-levelk-clique enumeration algorithm along with clique-core–based pruning and edge pruning techniques to reduce the search space, followed by parallel connected component decomposition to split the pruned graph into independent smaller subproblems. The exact solution is then obtained by formulating DSD on each connected component as a maximum flow problem and solving it using a highly parallel vertex-centric push–relabel algorithm, enhanced with tight upper and lower density bounds and compact, GPU-friendly data structures. Experiments on a diverse set of real-world and synthetic graphs show substantial speedups over the state-of-the-art CPU implementation, while producing identical solutions.more » « less
-
Microservice architectures have become the de facto paradigm for building scalable, service-oriented systems. Although their decentralized design promotes resilience and rapid development, the inherent complexity leads to subtle performance challenges. In particular,non-fatalerrors - internal failures of remote procedure calls that do not cause top-level request failures - can accumulate along the critical path, inflating latency and wasting resources. In this work, we analyze over 11 billion RPCs across more than 6,000 microservices at Uber. Our study shows that nearly 29% of successful requests experience non-fatal errors that remain hidden in traditional monitoring. We propose a novellatency-reduction estimator(LR estimator) to quantify the potential benefit of eliminating these errors. Our contributions include a systematic study of RPC error patterns, a methodology to estimate latency reductions, and case studies demonstrating up to a 30% reduction in tail latency.more » « less
-
PriML, a language developed in recent work onresponsive parallelism, extends traditional fine-grained parallel languages such as Cilk by allowing programmers to annotate threads withpriorities. Programmers thus get the substantial throughput benefits of lightweight threads scheduled by a user-level runtime, while retaining the ability to use threads for responsive applications typically programmed with lower-level threading systems. PriML’s type system guarantees the absence ofpriority inversions, costly performance errors in which high-priority threads are delayed by low-priority threads, enabling formal bounds on throughput and responsiveness, but at the cost of expressiveness: threads may not change priority once spawned and the priority of a thread is specified as a priority literal in the code (i.e., priorities are notfirst-class). This work relaxes the two assumptions above by trackingsets of prioritiesusing techniques drawn from the literature on refinement types. We extend the graph-based cost models of responsive parallelism to incorporate first-class and changing priorities, and prove bounds on the throughput and responsiveness of well-typed programs in our extended language. We implement our type system extensions in the PriML compiler, and demonstrate the benefits of the extension using a concurrent web server as a case study.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.14778/3749646.3749687
