Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD

• URL: http://arxiv.org/abs/2505.12128v1
• Date: Sat, 17 May 2025 19:41:44 GMT
• Title: Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD
• Authors: Nikita P. Kalinin, Ryan McKenna, Jalaj Upadhyay, Christoph H. Lampert,
• Abstract summary: We introduce a new explicit factorization method, Banded Inverse Square Root (BISR), which imposes a banded structure on the inverse correlation matrix.<n>BISR achieves anally optimal error by matching the upper and lower bounds.
• Score: 21.92418810749819
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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, requiring matrix factorizations that account for repeated participation. Existing theoretical upper and lower bounds on multi-epoch factorization error leave a significant gap. In this work, we introduce a new explicit factorization method, Banded Inverse Square Root (BISR), which imposes a banded structure on the inverse correlation matrix. This factorization enables us to derive an explicit and tight characterization of the multi-epoch error. We further prove that BISR achieves asymptotically optimal error by matching the upper and lower bounds. Empirically, BISR performs on par with state-of-the-art factorization methods, while being simpler to implement, computationally efficient, and easier to analyze.

Related papers

• Induced Covariance for Causal Discovery in Linear Sparse Structures [55.2480439325792]
  Causal models seek to unravel the cause-effect relationships among variables from observed data. This paper introduces a novel causal discovery algorithm designed for settings in which variables exhibit linearly sparse relationships.
  arXiv  Detail & Related papers  (2024-10-02T04:01:38Z)
• Fitting Multilevel Factor Models [41.38783926370621]
  We develop a novel, fast implementation of the expectation-maximization algorithm, tailored for multilevel factor models. We show that the inverse of an invertible PSD MLR matrix is also an MLR matrix with the same sparsity in factors. We present an algorithm that computes the Cholesky factorization of an expanded matrix with linear time and space complexities.
  arXiv  Detail & Related papers  (2024-09-18T15:39:12Z)
• Banded Square Root Matrix Factorization for Differentially Private Model Training [3.6371628922281305]
  We present a new matrix factorization approach, BSR, which overcomes this computational bottleneck. By exploiting properties of the standard matrix square root, BSR allows to efficiently handle also large-scale problems. Our numerical experiments demonstrate that models trained using BSR perform on par with the best existing methods, while completely avoiding their computational overhead.
  arXiv  Detail & Related papers  (2024-05-22T15:47:35Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Multiple Augmented Reduced Rank Regression for Pan-Cancer Analysis [0.0]
  We propose multiple augmented reduced rank regression (maRRR), a flexible matrix regression and factorization method. We consider a structured nuclear norm objective that is motivated by random matrix theory. We apply maRRR to gene expression data from multiple cancer types (i.e., pan-cancer) from TCGA.
  arXiv  Detail & Related papers  (2023-08-30T21:40:58Z)
• An inexact LPA for DC composite optimization and application to matrix completions with outliers [5.746154410100363]
  This paper concerns a class of composite optimization problems. By leveraging the composite structure, we provide a condition for the potential function to have the KL property of $1/2$ at the iterate sequence.
  arXiv  Detail & Related papers  (2023-03-29T16:15:34Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• Partial Least Square Regression via Three-factor SVD-type Manifold Optimization for EEG Decoding [4.0204191666595595]
  We propose a new method to solve the partial least square regression, named PLSR via optimization on bi-Grassmann manifold (PLSRbiGr) qlPLSRbiGr is validated with a variety of experiments for decoding EEG signals at motor imagery (MI) and steady-state visual evoked potential (SSVEP) task.
  arXiv  Detail & Related papers  (2022-08-09T11:57:02Z)
• Unitary Approximate Message Passing for Matrix Factorization [90.84906091118084]
  We consider matrix factorization (MF) with certain constraints, which finds wide applications in various areas. We develop a Bayesian approach to MF with an efficient message passing implementation, called UAMPMF. We show that UAMPMF significantly outperforms state-of-the-art algorithms in terms of recovery accuracy, robustness and computational complexity.
  arXiv  Detail & Related papers  (2022-07-31T12:09:32Z)
• Matrix Completion via Non-Convex Relaxation and Adaptive Correlation Learning [90.8576971748142]
  We develop a novel surrogate that can be optimized by closed-form solutions. We exploit upperwise correlation for completion, and thus an adaptive correlation learning model.
  arXiv  Detail & Related papers  (2022-03-04T08:50:50Z)
• Learning with Multiclass AUC: Theory and Algorithms [141.63211412386283]
  Area under the ROC curve (AUC) is a well-known ranking metric for problems such as imbalanced learning and recommender systems. In this paper, we start an early trial to consider the problem of learning multiclass scoring functions via optimizing multiclass AUC metrics.
  arXiv  Detail & Related papers  (2021-07-28T05:18:10Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)

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.