Jalaj Upadhyay
YOU?
Author Swipe
View article: Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting
Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting Open
The factorization norms of the lower-triangular all-ones $n \times n$ matrix, $γ_2(M_{count})$ and $γ_{F}(M_{count})$, play a central role in differential privacy as they are used to give theoretical justification of the accuracy of the on…
View article: Correlated Noise Mechanisms for Differentially Private Learning
Correlated Noise Mechanisms for Differentially Private Learning Open
This monograph explores the design and analysis of correlated noise mechanisms for differential privacy (DP), focusing on their application to private training of AI and machine learning models via the core primitive of estimation of weigh…
View article: Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD
Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD Open
Matrix factorization mechanisms for differentially private training have emerged as a promising approach to improve model utility under privacy constraints. In practical settings, models are typically trained over multiple epochs, requirin…
View article: On the Price of Differential Privacy for Hierarchical Clustering
On the Price of Differential Privacy for Hierarchical Clustering Open
Hierarchical clustering is a fundamental unsupervised machine learning task with the aim of organizing data into a hierarchy of clusters. Many applications of hierarchical clustering involve sensitive user information, therefore motivating…
View article: A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances
A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances Open
We study the problem of approximating all-pair distances in a weighted undirected graph with differential privacy, introduced by Sealfon [Sea16]. Given a publicly known undirected graph, we treat the weights of edges as sensitive informati…
View article: Continual Release Moment Estimation with Differential Privacy
Continual Release Moment Estimation with Differential Privacy Open
We propose Joint Moment Estimation (JME), a method for continually and privately estimating both the first and second moments of data with reduced noise compared to naive approaches. JME uses the matrix mechanism and a joint sensitivity an…
View article: Improved Differentially Private Continual Observation Using Group Algebra
Improved Differentially Private Continual Observation Using Group Algebra Open
Differentially private weighted prefix sum under continual observation is a crucial component in the production-level deployment of private next-word prediction for Gboard, which, according to Google, has over a billion users. More specifi…
View article: Optimality of Matrix Mechanism on $\ell_p^p$-metric
Optimality of Matrix Mechanism on $\ell_p^p$-metric Open
In this paper, we introduce the $\ell_p^p$-error metric (for $p \geq 2$) when answering linear queries under the constraint of differential privacy. We characterize such an error under $(ε,δ)$-differential privacy. Before this paper, tight…
View article: Differentially Private Decentralized Learning with Random Walks
Differentially Private Decentralized Learning with Random Walks Open
The popularity of federated learning comes from the possibility of better scalability and the ability for participants to keep control of their data, improving data security and sovereignty. Unfortunately, sharing model updates also create…
View article: Continual Counting with Gradual Privacy Expiration
Continual Counting with Gradual Privacy Expiration Open
Differential privacy with gradual expiration models the setting where data items arrive in a stream and at a given time $t$ the privacy loss guaranteed for a data item seen at time $(t-d)$ is $εg(d)$, where $g$ is a monotonically non-decre…
View article: The Discrepancy of Shortest Paths
The Discrepancy of Shortest Paths Open
The hereditary discrepancy of a set system is a quantitative measure of the pseudorandom properties of the system. Roughly speaking, hereditary discrepancy measures how well one can 2-color the elements of the system so that each set conta…
View article: Optimal Bounds on Private Graph Approximation
Optimal Bounds on Private Graph Approximation Open
We propose an efficient $ε$-differentially private algorithm, that given a simple {\em weighted} $n$-vertex, $m$-edge graph $G$ with a \emph{maximum unweighted} degree $Δ(G) \leq n-1$, outputs a synthetic graph which approximates the spect…
View article: A Unifying Framework for Differentially Private Sums under Continual Observation
A Unifying Framework for Differentially Private Sums under Continual Observation Open
We study the problem of maintaining a differentially private decaying sum under continual observation. We give a unifying framework and an efficient algorithm for this problem for \emph{any sufficiently smooth} function. Our algorithm is t…
View article: Separation of the Factorization Norm and Randomized Communication Complexity
Separation of the Factorization Norm and Randomized Communication Complexity Open
In an influential paper, Linial and Shraibman (STOC '07) introduced the factorization norm as a powerful tool for proving lower bounds against randomized and quantum communication complexities. They showed that the logarithm of the approxi…
View article: Differentially Private Range Query on Shortest Paths
Differentially Private Range Query on Shortest Paths Open
We consider differentially private range queries on a graph where query ranges are defined as the set of edges on a shortest path of the graph. Edges in the graph carry sensitive attributes and the goal is to report the sum of these attrib…
View article: Almost Tight Error Bounds on Differentially Private Continual Counting
Almost Tight Error Bounds on Differentially Private Continual Counting Open
The first large-scale deployment of private federated learning uses differentially private counting in the continual release model as a subroutine (Google AI blog titled "Federated Learning with Formal Differential Privacy Guarantees"). In…
View article: Differentially Private Sampling from Rashomon Sets, and the Universality of Langevin Diffusion for Convex Optimization
Differentially Private Sampling from Rashomon Sets, and the Universality of Langevin Diffusion for Convex Optimization Open
In this paper we provide an algorithmic framework based on Langevin diffusion (LD) and its corresponding discretizations that allow us to simultaneously obtain: i) An algorithm for sampling from the exponential mechanism, whose privacy ana…
View article: Near Optimal Linear Algebra in the Online and Sliding Window Models
Near Optimal Linear Algebra in the Online and Sliding Window Models Open
We initiate the study of numerical linear algebra in the sliding window model, where only the most recent W updates in a stream form the underlying data set. Although many existing algorithms in the sliding window model use or borrow eleme…
View article: A Framework for Private Matrix Analysis
A Framework for Private Matrix Analysis Open
We study private matrix analysis in the sliding window model where only the last $W$ updates to matrices are considered useful for analysis. We give first efficient $o(W)$ space differentially private algorithms for spectral approximation,…
View article: Multi-prover proof of retrievability
Multi-prover proof of retrievability Open
There has been considerable recent interest in “cloud storage” wherein a user asks a server to store a large file. One issue is whether the user can verify that the server is actually storing the file, and typically a challenge-response pr…
View article: Multi-prover proof of retrievability
Multi-prover proof of retrievability Open
There has been considerable recent interest in “cloud storage” wherein a user asks a server to store a large file. One issue is whether the user can verify that the server is actually storing the file, and typically a challenge-response pr…
View article: Numerical Linear Algebra in the Sliding Window Model
Numerical Linear Algebra in the Sliding Window Model Open
We initiate the study of numerical linear algebra in the sliding window model, where only the most recent $W$ updates in the data stream form the underlying set. Although most existing work in the sliding window model uses the smooth histo…
View article: Near Optimal Linear Algebra in the Online and Sliding Window Models
Near Optimal Linear Algebra in the Online and Sliding Window Models Open
We initiate the study of numerical linear algebra in the sliding window model, where only the most recent $W$ updates in a stream form the underlying data set. We first introduce a unified row-sampling based framework that gives randomized…
View article: On Low-Space Differentially Private Low-rank Factorization in the Spectral Norm
On Low-Space Differentially Private Low-rank Factorization in the Spectral Norm Open
Low-rank factorization is used in many areas of computer science where one performs spectral analysis on large sensitive data stored in the form of matrices. In this paper, we study differentially private low-rank factorization of a matrix…
View article: The Price of Differential Privacy for Low-Rank Factorization
The Price of Differential Privacy for Low-Rank Factorization Open
In this paper, we study what price one has to pay to release {\em differentially private low-rank factorization} of a matrix. We consider various settings that are close to the real world applications of low-rank factorization: (i) the man…
View article: Fast and Space-optimal Low-rank Factorization in the Streaming Model With Application in Differential Privacy.
Fast and Space-optimal Low-rank Factorization in the Streaming Model With Application in Differential Privacy. Open
In this paper, we consider the problem of computing a low-rank factorization of an $m \times n$ matrix in the general turnstile update model. We consider both the private and non-private setting. In the non-private setting, we give a space…
View article: Block-Wise Non-Malleable Codes
Block-Wise Non-Malleable Codes Open
Non-malleable codes, introduced by Dziembowski, Pietrzak, and Wichs (ICS'10) provide the guarantee that if a codeword c of a message m, is modified by a tampering function f to c', then c' either decodes to m or to "something unrelated" to…