A Unifying Framework for Differentially Private Sums under Continual Observation

• URL: http://arxiv.org/abs/2307.08970v1
• Date: Tue, 18 Jul 2023 05:04:11 GMT
• Title: A Unifying Framework for Differentially Private Sums under Continual Observation
• Authors: Monika Henzinger and Jalaj Upadhyay and Sarvagya Upadhyay
• Abstract summary: 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 emphany sufficiently smoothangular function.
• Score: 20.432568247732206
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 the first differentially private algorithm that does not have a multiplicative error for polynomially-decaying weights. Our algorithm improves on all prior works on differentially private decaying sums under continual observation and recovers exactly the additive error for the special case of continual counting from Henzinger et al. (SODA 2023) as a corollary. Our algorithm is a variant of the factorization mechanism whose error depends on the $\gamma_2$ and $\gamma_F$ norm of the underlying matrix. We give a constructive proof for an almost exact upper bound on the $\gamma_2$ and $\gamma_F$ norm and an almost tight lower bound on the $\gamma_2$ norm for a large class of lower-triangular matrices. This is the first non-trivial lower bound for lower-triangular matrices whose non-zero entries are not all the same. It includes matrices for all continual decaying sums problems, resulting in an upper bound on the additive error of any differentially private decaying sums algorithm under continual observation. We also explore some implications of our result in discrepancy theory and operator algebra. Given the importance of the $\gamma_2$ norm in computer science and the extensive work in mathematics, we believe our result will have further applications.

Related papers

• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  We propose algorithms that utilize the variance of the reward distribution as well as the $B_K$, and show that they can achieve tighter regret upper bounds. We introduce two novel algorithms: Restarted Weighted$textOFUL+$ and Restarted $textSAVE+$. Notably, when the total variance $V_K$ is much smaller than $K$, our algorithms outperform previous state-of-the-art results on non-stationary linear bandits under different settings.
  arXiv  Detail & Related papers  (2024-03-15T23:36:55Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  We study the generalized low-rank matrix bandit problem, proposed in citelu2021low under the Generalized Linear Model (GLM) framework. To overcome the computational infeasibility and theoretical restrain of existing algorithms, we first propose the G-ESTT framework. We show that G-ESTT can achieve the $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret while G-ESTS can achineve the $tildeO
  arXiv  Detail & Related papers  (2024-01-14T14:14:19Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  We propose a natural algorithm that involves imputing the missing values of the matrix $XTX$. We evaluate our algorithm on one-sided recovery of synthetic data and low-coverage genome sequencing.
  arXiv  Detail & Related papers  (2023-06-06T22:35:16Z)
• Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond [8.604882842499212]
  We study the problem of finding elements in the intersection of an arbitrary conic variety in $mathbbFn$ with a given linear subspace. This problem captures a rich family of algorithmic problems under different choices of the variety. We develop an algorithm that solves this problem efficiently for "typical" subspaces.
  arXiv  Detail & Related papers  (2022-12-07T18:45:33Z)
• Almost Tight Error Bounds on Differentially Private Continual Counting [11.549143183739577]
  First large-scale deployment of private federated learning uses differentially private counting in the continual release model as a subroutine. Standard mechanism for continual counting is the binary mechanism. We present a novel mechanism and show that its mean squared error is bothally optimal and a factor 10 smaller than the error of the binary mechanism.
  arXiv  Detail & Related papers  (2022-11-09T16:35:42Z)
• Private Isotonic Regression [54.32252900997422]
  We consider the problem of isotonic regression over a partially ordered set (poset) $mathcalX$ and for any Lipschitz loss function. We obtain a pure-DP algorithm that has an expected excess empirical risk of roughly $mathrmwidth(mathcalX) cdot log|mathcalX| / n$, where $mathrmwidth(mathcalX)$ is the width of the poset. We show that the bounds above are essentially the best that can be
  arXiv  Detail & Related papers  (2022-10-27T05:08:07Z)
• Majorization-minimization for Sparse Nonnegative Matrix Factorization with the $\beta$-divergence [2.3787352248749376]
  It is well known that the norm of the other factor (the dictionary matrix) needs to be controlled in order to avoid an ill-posed formulation. Standard practice consists in constraining the columns of the dictionary to have unit norm, which leads to a nontrivial optimization problem. We derive block-descent majorization-minimization algorithms that result in simple multiplicative updates for either $ell_1$-regularization or the more "aggressive" log-regularization.
  arXiv  Detail & Related papers  (2022-07-13T16:09:29Z)
• Constant matters: Fine-grained Complexity of Differentially Private Continual Observation [10.624505781812385]
  We study fine-grained error bounds for differentially private algorithms for counting continual observation. We are the first to give concrete error bounds for various problems under continual observation.
  arXiv  Detail & Related papers  (2022-02-23T11:50:20Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  We study the problem of learning one-hidden-layer ReLU networks with $k$ hidden units on $mathbbRd$ under Gaussian marginals. For the case of positive coefficients, we give the first-time algorithm for this learning problem for $k$ up to $tildeOOmega(sqrtlog d)$.
  arXiv  Detail & Related papers  (2020-06-22T17:53:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.