Improved Differentially Private Riemannian Optimization: Fast Sampling and Variance Reduction
Authors: Saiteja Utpala
Andi Han
Pratik Jawanpuria
Bamdev Mishra
Venue: Accepted by TMLR ()

Abstract: A common step in differentially private ({DP}) Riemannian optimization is sampling from the (tangent) Gaussian distribution as noise needs to be generated in the tangent space to perturb the gradient. In this regard, existing works either use the Markov chain Monte Carlo ({MCMC}) sampling or explicit basis construction based sampling methods on the tangent space. This becomes a computational bottleneck in the practical use of {DP} Riemannian optimization, especially when performing stochastic optimization. In this paper, we discuss different sampling strategies and develop efficient sampling procedures by exploiting linear isometry between tangent spaces and show them to be orders of magnitude faster than both the {MCMC} and sampling using explicit basis construction. Furthermore, we develop the {DP} Riemannian stochastic variance reduced gradient algorithm and compare it with DP Riemannian gradient descent and stochastic gradient descent algorithms on various problems.  

Published in Transactions on Machine Learning Research (02/2023)
Improved Differentially Private Riemannian Optimization: Fast Sampling and Variance Reduction
Saiteja Utpala Independent
auttejantpolo@@maallcoo com
Andi Han University of Sydney
andi.han@@sydneey.eeiee edw..
Pratik Jawanpuria Microsoft India
Bamdev Mishra
bemdeemm@micrrooff..ccmmm
Microsoft India
Reviewed on OpenReview: https: // openreview. net/ forum? id- yaguBNt
Abstract
A common step in diffcrentially private (DP) Riemannian optimization is sampling from the (Langent) Gaussian distribution as noise needs to be generated in the langent space to perturb the gradient. In this regard, existing works either use the Markov chain Monte Carlo (MCMC) sampling or explicit basis construction based sampling methods on the tangent space. This becomes a computational bottleneck in the practical use of DP Riemannian optimization, especially when performing stochastic optimization. In this paper, we discuss different sampling strategies and develop efficient sampling procedures by exploiting linear isometry between langent spaces and show them be orders of magnitude faster than both the MCMC and sampling using explicit basis construction. Furthermore, develop the DP Riemannian stochastic variance reduced gradient algorithm and compare it with DP Riemannian gradient descent and stochastic gradient descent algorithms on various problems.
1 Introduction
Differential privacy (DP) provides rigorous treatment for the notion of data privacy by precisely quantifying the deviation in the model's output distribution under modification of a small number of data points (Dwork al. 2006b Provable guarantees of DP coupled with properties like immunity to arbitrary post-processing, and graceful composability have made it a de- dactacto standard of privacy with steadfast adoption in the real world (Erlingsson et al.] 2014 Apple 2017 Near 2018 Abowd 20018). Furthermore, it has been shown
empirically that DP models resist various kinds of leakage attacks that may cause privacy violations (Rahman
et al. 2018 Carlini al.] 2019 Sablayrolles et al.
2019 Zhu al.) 2019 Balle al., 2022 Carlini et al.
2022
Various approaches have been explored in the literature to ensure differential privacy in machine learning models. These include output perturbation (Chaudhuri et all 2011 Zhang et al. 2017) and objective perturbation (Chaudhuri et al.) 2011 Iyengar et al.) (019)., in which a perturbation torm is added to the oulput of a non-DP algorithm or the optimization objective, respectively. Another approach, gradient perturbation, involves perturbing the gradient information at every iteration of gradient based approaches and has received significant interest in the context doep learning and stochastic optimization (Song et al.
2013 Bassily et al. 2014 Abadi et al. 2016
Wang al.) 2017
Bassily et al. 2019 Wang al. 2019a
Bassily et al. 2021

---

Published in Transactions on Machine Learning Research (02/2023)
Recently, achieving differential privacy over Riemannian manifolds has also been explored in the context of obtaining Fréchet mean (Reimherr et al. 2021 Utpala et al., 2022b Soto et al. 2022 and, more generally, solving empirical risk minimization problems (Han et al. 2022a). Riemannian geometry is a generalization of the Euclidean goometry [Lee 2006) and includes several non-lincar spaces such as the set of positive definite matrices (Bhatia 2009). set of orthogonal matrices (Edelman et al.) 1998), and hyperbolic space (Beltrami
1868 Gromov] 1987), among others. Many machine learning tasks such as principal component analysis
[Absil a 2007), low-rank matrix/ maarrx/tenssor tensor modeling (Boumal & Absil 2011 Kasai et al., [2019] Jawanpuria
& Mishra 2018 Nimishakavi et al.] 2018), metric learning (Bhutani et al. 2018 Han et al. [021]. natural
language processing (Jawanpuria et al.
2018: Jawanpuria et al. 2019b Qi et al. 2021), optimal transport (Mishra et al. 2021
2019a
2020a b). learning embeddings Nickel & Kiela, 2017:
Suzuki et al.,
2019
Jawanpuria et al.
2021
Han et al. 2022b) elc., may be viewed as problem instances on Riemannian
manifolds.
In differentially private Riemannian optimization (Han et al.) 2022a), key step is use tangent Gaussian sampling at every ileration to perturb the gradient direction in the Langent. space. Han al. (202aa) proposed to use the Markov Chain Monte Carlo (MCMC) method (Robert & Casella computationally expensive especially on matrix manifolds with large dimensions. When the underlying Riemannian metric is indueed from the Euclidean metric, such as for sphere, Han et al. (2022a) showed one can avoid MCMC via basis construction for the tangent space. For general manifolds of interest, however, a discussion on basis construction and computationally efficient sampling is missing. The sampling step computationally prohibitive, especially when performing differentially private stochastic optimization over Riemannian manifolds, where the number of sampling calls is relatively high compared to the case of deterministic optimization. It should also be noted that generalizing more sophisticated differentially privale Euclidean stochastic algorithms like differentially private stochastic variance reduced gradient. (Wang) et al. 2017) to Riemannian geometry is non-trivial and is an active area of research. The benefits of (non- private) Riemannian stochastic variance reduction gradient (RSVRG) methods over Riemannian stochastic
1999), ), which is
gradient [Bounabel 2013) has been studied in existing works (Zhang et al. 2016 Zhou et al. 2019: Han &
Gao 2021 Sato et al. 2019).
Our main contributions improving differentially private Riemannian optimization framework are summa- rized below.
Sampling. We propose generic fast sampling methods on the langent space for various matrix manifolds of interest. This makes differentially private Riemannian optimization more practically appealing for real-world applications. The proposed sampling strategy is based on linear isometry between tangent spaces. We show that it is computationally efficient and orders of magnitude faster than other sampling schemes, MCMC, and explicit basis construction, presented in (Han et al. 2022ab.
2. DP-SVRG. We propose a differentially private Ricmannian stochastic variance reduced gradicnt (DP-RSVRG), enriching the suite of differentially private stochastic Riemannian optimization meth- ods.
Our first contribution allows to scale differentially private Riemannian optimization algorithms since sampling is now faster. Our sccond contribution is on developing DP-RSVRG and together with faster sampling, DP- RSVRG scalable to large datasets. In the experiments section, we show the empirical benefit of both of these contributions.
Organization.
The rest of the paper is organized as follows. Section 2 gives background on Riemannian geometry, Riemannian optimization, and differential privacy. We then use various properties of tangent Gaussian distribution and discuss different possible sampling strategies in Section X Section X presents our proposed sampling procodure and gives exact details about how implement in practice for several man- ifolds of interest. In Section 3 we develop a differentially private Riemannian stochastic variance reduction gradient algorithm (DP-RSVRG). Section i discusses the empirical results. Section concludes the paper.
2

---

Published in Transactions on Machine Learning Research (02/2023)
2 Preliminaries and related work
Riemannian Geometry. A Riemannian Manifold M of dimension d is smooth manifold with an inner product structure (:5 (i.e., having a Riemannian metric) on every langent space M. Given a basis & = (B 3d) for TwM at w E M, the Riemannian metric can be represented as a symmetric positive definite matrix G and the inner product can be written as
(2) = G
where vi. 22 are coordinates of the tangent vectors 11, E T in the coordinate system given by B. An induced norm is defined as || = V), for V E M. Let r [0, + M denote any smooth curve and 7(()) E M its derivative, then distance between W1, W2 E M defined as dist(w1, W2) = [0 So (1)()))))))) dt.
A smooth curve y [0, 1] - M called the geodesic if it locally minimizes the distance between 7(0) and (t). For any v Tu,, the exponential map is defined as (x) 7(1) where >(0) = w and 7((0) v. If between any two points w, w' E W M there is unique geodesic connecting them, then the exponential map has inverse map Exp=" -1 W + TwM, which maps a point the manifold to the tangent space T.M. Transporting the vectors on the manifold requires the notion of parallel transport. In particular, the parallel transport from wi E M to W2 E . denoted as PT + M + Tw.- is a linear isometry (i.e., inner product preserving) along a geodesic. In this work, the curvature of manifold refers to the sectional curvature, which provides a local measure of curvature at each point on the manifold.
The Riemannian gradient of a real valued function f M - R, denoted as grad f(w), a tangent vector such that for any V E Tw
(grad f(w), = Df(w](v),
where (v( denotes the directional derivative of ff at w along v. We refer the readers to (Do Carmo &
Flaherty Francis 1992 Lee 2006) for a detailed exposition of Riemannian geometry and (Absil et al.) 2009;
Boumal 2022 for Riemannian optimization.
Function classes on Riemannian Manifolds. We call a neighbourhood W C M totally normal if for any two points, the exponential map is invertible. Let W S be totally normal neighborhood and Dw be its diameter and Kmin be the lower bound on the sectional curvature of W.
A function f W + R is called Lo-geodesically Lipschitz continuous (L-g-lipschitz) for any wi, w2 e M, ((, f(w2)l s Lodist(w, W2). Under the assumption of continuous gradient, function f is Lo geodesically Lipschitz continuous if and only if
I|grad [(w)] $ To,
for all w E MM (Boumal 2022). A differentiable function f : + R is geodesically L-smooth (I-g-smooth) if its gradient L-Lipschitz, i.e., ||grad f(w)) PT grad f(wz))l.n, S Ldist(w), w2). Additionally, it can be shown that if f is geodesically L-smooth, then
L 2
f(wi) S f((2)) + (grad (w22, Exp (w))) (wi)) +
|Exp T (w) )
for all wi, w2 E M. A function is called geodesically p-strongly convex (u-strongly g-convex) (Zhang al. 2016) if for all w1, W2 E W, it satisfies
f(w1) 2 f(w2) + (grad f (122), Exp=y (wn wa - 2 (1E
Let wn be a global minimizer of f. Then f W + R is said to satisfy the Riemannian Polyak Lojakk--ojssiwiizz (PL) condition if there exists > 0, such that,
f(w) f(w") T l|grad f(w)
3

---

Published in Transactions on Machine Learning Research (02/2023)
for any M ZMZnnng et al. 2016). The Riemannian PL condition is a strictly weaker notion than the geodesic strong convexity, L.e, every geodesic u-strongly convex function satisfies the Riemannian PI. con- dition (with т = 1/(2p)) and there exist functions that satisfy the Riemannian PL condition but are not geodesically strongly convex. The trigonometric distance bound from Zhang & Sra (2016) (see Lemma 10 which crucial for deriving convergence analysis of Riemannian optimization algorithms makes use of the curvature constant, defined as
Meniin DW
Kmin
tanh Manin Pw)
Kmin 2 0.
Differential privacy. Let Z be an imput data space and two datasets of size Z, Z' E 2" of size are called adjacent if they differ by most one element. We represent the adjacent datasets Z, by the notation Z ~ Z'. A manifold-valued randomized mechanism R 2 - M is said to be (c, -ppppoxximmy differentially private (ADP) (Dwork et al. 2006a Wasserman & Zhou 2010 if for any two adjacent dalasets
Z ~ Z' and for all measurable sets S C M, we have
TP (R(Z) E 5) S (c)P E S) 6.
Révayi differential privacy (RDP) by Mironov 2017 is a refinement of DP which gives tight privacy bounds under composition of mechanisms. The A-th moment of a mechanism R. is defined as
p(R(Z') = -
(R(A)= = sup log Z~Z'
E (2R(2)
and mechanism R is said to satisfy PD, if K 1) S p. If the mechanism R 2 M is an (adaptive) composition of k mechanisms (R. i.c., R₂ II Mý 2 - - Mi, then
(A) < Σ KR, (A).
Using the moments accountant technique (Abadi et al. 2016), (A, PDPP mechanism can be given (c, ADP certificate. We refer the interested readers to (Dwork et al. 2014 Vadhan
2017) for more details.
Differential privacy on Riemannian manifolds. Reimherr et al. 2021 are the first to consider differen- tial privacy in the Riemannian setting and derived the Riemannian Laplace mechanism based on distribution from (Hajri al.] 2016). [Utpala al. 2022bb derive output perturbation for manifold of symmetric posi-
tive definite matrices (SPD) with the Log- Euclidean metric based distribution from (Schwartzman 2016).
While (Reimherr et al. 2021 Utpala et al. 2022b) focus on output perturbation, Han et al. (2022a) propose unified differentially private Riemannian optimization framework through gradient perturbation.
Han et al. (2022a) consider the following problem 4 where the parameter of interest lies on a Riemannian manifold M and -=),i=1,...,,, represent the set of data samples, i.c.,
F(w) (((m)
1 n Σ (ww)
1 T1
Σ f(:;
min WE
(1)
The aim of differentially private Riemannian optimization is to privatize the solution from a Riemannian optimization solver by injecting noise to the Riemannian gradient similar to the Euclidean case. The Rieman- nian gradient grad F(w) belongs to the tangent space (T,,M, (.)w) and to perturb the Riemannian gradient, Han et al. (022a define an intrinsic Gaussian distribution on the tangent space T.M with density
p(v) sep(-|lv- (00--1///200 /20²), v DE TT.MM
and refer it as the tangent Gaussian distribution. They propose differentially private Riemannian gradient and Riemannian stochastic gradient descent algorithms.
4

---

Published in Transactions on Machine Learning Research (02/2023)
Algorithm 1: Sampling from tangent Gaussian: a general algorithm
Input : Manifold M dimension d, base point w M, Riemannian metric (n-ww: mean M and standard deviation a
Output: Ç such that & ~ (0, d²).
Construct basis 3 of Tw orthonormal wrt to (--)w-
Generate d-dimensional coordinates a a~ ~V, o
3 Generate the sample Ç E M as = E=E:=10: 0;3,
3 Sampling from tangent Gaussian
In this section, we derive various properties of the tangent Gaussian distribution to discuss different sam- pling strategics for different manifolds. The proofs of the claims discussed in this section provided in Appendix B
We begin with the definitions of the Lebesgue measure on the tangent space and the tangent Gaussian distri- bution. We then show that the langent Gaussian reduces to the multivariate Gaussian when an appropriate basis is constructed. This allows sampling to be performed in the intrinsic coordinates of the tangent space and then generate a tangent Gaussian sample by a lincar combination of the basis vectors with the sampled coordinates.
Definition 1 (Lebesgue measure on tangent space). Consider a Riemannian manifold M with the intrinsic dimension d. For M, let H (B,,-.., ,,d] be orthonormal basis of T.M with respect to the Riemannian metric (..-)m. Define chr Bd + T.M as dbr(ci,...,, = Dim c, Let X denote the standard Lebesgue measure on Idd. Then, we define the Lebesgue measure on Tw as the pushforward measure &_ given by
(o. ) x
Remark 1. Let B, be two orthonormal bases of Tw then 6² x= 2 because the Lebesgue measure is invariant under orthogonal transformations (with respect to the Riemannian metric). Hence, in the rest of this draft, we drop the superscript for clarity and denote the pushforward measure as Φ.
We now define the tangent space Gaussian distribution Haan et al. 2022a) under the mcasure in Definition
Definition 2 (Tangent Gaussian (Han et al. 2022a)) ). Let E M, random tangent vector E T follows tangent space Gaussian distribution at w, denoted as & (w, with mean μ E Tw and slandard deviation a > 0 if its densily is given by
||2 1ell
Pro (v) Cu,o exp
2n
under the pushforward measure given in Desinition
Lemma 1. Let w M and Ø be any orthonormal basis of Tw.MM Also, let & Tir denote random tangent vector. Then, the following holds:
1f Nu, for some μ E ToM and for O, then Cw. (2To2)1/22
{ ~ (N, =
where E. Rd denote coordinates in basis H. N(i o²I E~Nii
3. ~ No, then E IEll do where d is the dimension of the manifold.
Remark 2. Statement of Lemma 1 imprroess the bound variance from Han al. 2022a Lemma 4) by removing the dependency the metric tensor G..
Statement of Lemma I implics that random tangent vector follows tangent Gaussian if and only its random coordinates any orthonormal basis follow from the Euclidean Gaussian distribution of the intrinsic dimension. This allows to avoid the computationally expensive MCMC based sampling, which is suggested
5

---

Published in Transactions on Machine Learning Research (02/2023)
Algorithm 2: Sampling from tangent Gaussian using isometric transportation
Input :
Manifold M dimension d, base point w M, Riemannian metric (n-.pp mean μ E standard deviation a > 0, reference point W. Output: { such that Ç ~ (0, d²).
Sample d coordinates
(0, o2 Generate the sample T&M at w.
3 Generate the sample & E T.M by isometric transportation of ç from T&M to TwM g= Ll -m (C).
in (Han et al. 2022a) for manifolds with non- Euclidean Riemannian metrics, and instead apply the basis construction approach for any manifold. We summarize the procedure in A Algorithm [ However, the practical efficiency depends on how Steps 1, 2, and 3 of Algorithm | are implemented for different manifolds.
One natural approach for sampling from tangent Gaussian is to perform an explicit basis construction (Step 1) in which we fully enumcrate the basis elements in B. Steps 2 and 3 can subsequently be performed in straightforward manner. The other approach is to combine Steps 1, 2, and 3 implicitly. We discuss these approaches in the following sections.
3.1 Sampling with explicit basis enumeration
Here, we construct a basis explicitly, i.e., either analytically or by using Gram-Schmidt orthogonalization.
Gram-Schmidt orthogonalizzaton. The tangent space at point on manifold is parameterized by system of linear equations. One approach to perform sampling is to first solve the underlying linear equations to get the basis 2 of TwM that is orthonormal in the sense of the Euclidean metric. Depending the Riemannian metric, we now have two further scenarios.
When the Riemannian metric (,, a scaled Euclidean metrie, then the orthonormal basis with respect to the Riemannian metric (w can be obtained by appropriate scaling of B.
If the Riemannian metric (w is more general metric, we employ the onalization process H to generate new basis that is orthonormal with respect to the Riemannian metric (..-).. This is computationally expensive because if d is the dimension of manifold, then we have to evaluate ((2) inner products (.,-)w-
(GS) orthog-
Analytic basis construction. One way to avoid the computationally prohibitive GS orthogonalizzaton strategy analytically construct bascs for different manifolds. This can be done for various manifolds by exploiting the geometry of the space. We construct the full orthonormal basis with respect to the metric (r--) explicitly by full enumeration. We empirically observe (refer Section 6 that sampling with the explicit basis construction strategy is computationally expensive even if the basis is known analytically.
3.2 Sampling implicitly using isometric transportation
Since our end goal is to efficiently generate tangent Gaussian samples, instead first fully constructing the orthonormal basis and then performing linear combinations, we aim combine Steps 1, 2, and of Algorithm [ Hence, do not fully enumerate the basis but rather create a basis implicitly.
Given manifold with Riemannian metric and depending the basis chosen, there are many ways of implementing the implicit basis strategy. We propose unified way that is both computationally efficient and easy to implement using linear isometric transportation between tangent spaces.
The key observation this strategy the following claim which states that to sample from the tangent Gaussian on T. for w M, one can simply sample from the tangent Gaussian from any other base (reference) point @ and then transport the sample using any linear isometry operator from the reference point to the required base point w.

---

Published in Transactions on Machine Learning Research (02/2023)
Table 1: Reference points for Algorithm I E R denotes the identity matrix. (ei...., e,) denotes the standard basis vectors of R and Rm denotes the zero vector. ()) and (.)2 denote the standard Euclidean inner product on matrices and vectors, respectively. We observe that at specific reference points both the Riemannian metric and tangent space expressions simply.
Manifold
Metric
Reference point i
Tangent space T&M
Metric 6)
Algorithm
Cost
Affine-nvarrant
I E R
SYM(m)
6)F
Alg
3
((m))
SPD
Bures- Wasserseinn
I R=xm
SYM(m)
G)//1
Alg
(
Log- Log-Euclidean
I E Rmxm
SYM(m)
6)r
Alg
O(m²)
Poincaré ball
O E R
R
()2
Alg 6
((m)
Hyperoblic
Lorentz hyperboloid
e1 R
(0) x R=-1
()2
Alg
(
Sphere
Buclidean
e, E Rm
{0} x Rm-1
4/2
Alg
8
((m)
Stiefel
Euclidean
lel..... e₁] Rmxr
SKEW (r) x ((
6)
Alg
(
Grassmann
Euclidean
(e l e, Rmxr
10pmx R(m-r)xr
Alg
O(mr
Claim 2. Let w M and let LI TaM - Twm be any linear isometric transportation. If { oZ) for some E T M and > 0, then
LI th LI" N (LI" mn
(L))))(()))'')) (A),
Remark 3. Linear isometry, as defined above, encompasses the parallel transport and more generally some classes of vector transport on manifolds (Absil et al. 2009; Boumal 2022 Huang et al. 2015 2017 We denote the parallel transport operation as PT and the vector transport operation as VT.
We choose the reference point such that it is relatively easy to sample from the tangent Gaussian at T and then, isometrically transport from @ to the required point w. To be precise, we choose reference point where two things happen: (i) the tangent space T& parametrized freely and (it) the underlying Riemannian metric (w a becomes a scaled Euclidean metric. We term this procedure as isometric trans- portation and summarize it in Algorithm 2 The isometric transportation strategy be seen performing implicit basis construction, i.c., transporting the samples from the w to the required point w is equivalent to transporting the tangent space basis from w to as & = LI -- (E))) Σ a,LI
a.B.)
Efficient implementations of these isometric transportation procedures (parallel transport and vector trans- port) are extensively studied in the literature (Absil et al.) 2009 Xie al.) 2013 Huang et al.] 2015 2017
Thanwerdas & Pennee 2023 Guigui & Pennee
2022 and readily available in many of the existing
Riemannian optimization libraries (Bournal et al. 2014 Townsend et al.) 2016: Miolane et al., 2020 Utpala
ct al. 2022a). Hence, benefit of the isometric transportation strategy (Algorithm 2 is that one only needs to take care of the sampling at @ and the rest follows through. As we see later that implementing tangent Gaussian sampling at a properly chosen reference point t can be made computationally efficient. For all the manifolds, sampling al @ amounts to simply reshaping samples from the standard normal distribution certain size and is readily implementable.
4 Isometric transportation based sampling for different manifolds
In this section, we discuss the proposed sampling strategy and provide details about how to implement it for several interesting manifolds. The rest of the section deals with how to concretely implement Algorithm 2 for several manifolds of interest. For each manifold, we include a summary of the reference points, the metric at the points, and the concrete algorithm for sampling in Table I For the expressions of the parallel transport and vector transport operations on different manifolds, see Appendix A We illustrate through the experiments that Algorithm P is significantly better than other discussed procedures in computational efficiency and renders implementation of differentially private optimization computationally viable, especially for high dimensional matrix manifolds.

---

Published in Transactions on Machine Learning Research (02/2023)
4.1 SPD manifold
Let SPD(m) denote the set of symmetric positive definite malrices of size m x At W E SPD(m), the tangent space at W is (wSPD(m) = SYM(m), where SYM(m) denotes the set of symmetric matrices of We consider three Riemannian metrices: the Afinc-Invariant (AT) metric (Pen- 2006 Bhatia 2009). Bures- Wasserstein (BW) metric (Bhatia et al. 2019), and Log-E log-Euclidean (LE)
size m x m. (Bhatia, 2009
nec
metric (Ariigny et al. 2007) to endow SPD(m) with a Riemannian structure.
Let W, W E (m)(m), U,V E SYM(m) and denote C E SYM(m) such that Ctj = = 1 = and Cij = V2 for i * j and Cty = Cig. W = PDP" is the eigenvalue decomposition of W, where P,D E Rmxm and D is diagonal matrix of eigenvalues [AI,..., .m] and is an orthogonal matrix. We denote the Hadamard between product two square matrices with O.
SPD with Affine-Invarian metric. The AI metric defined (U, V.W Tr (W UW 'v). 'V)'VV) The reference point for Algorithm 2 is W = and the AI metric at I simplifies as (U, VU Tr(UV). As the parallel transport operation is well- well-known for the Al metric, we choose it as the linear isometric trans- The concrete implementation of Algorithm 2 for the SPD manifold with the AT metric is shown in Algorithm Furthermore, the implicit basis that is being used by Algorithm at W is
portation operation in Algorithm 2
3 The computational cost. of implementing Algorithm 3 is O(m²).
H {ar, w22 [eve] - e,ee" w :i I...., m. = . m..
where 1/2 PD Pp denotes the principal square root of W.
Algorithm 3: Sampling SPD with Alfine-Inaariat metric
Input : Base point W.
Output:
Tangent Gaussian sample U WW (0,00.²). Generate normal random vector ~ N(, I m(m+1))
2 Reshape a E I2m(++1)2 into A SYM(m).
U - W (TT== AC.
SPD with Bures- Wasserstein metric. The BW metric is defined (U, V/EW Tr(Lw (U[V), where Cw|U is the solution the matrix equation Lw +JJU+Uww// is W and the BW metric at I simplifies as (U, V) = Tr(UV)/4. We choose the parallel transport as the preferred isometric transportation procedure. The concrete implementation is shown in Algorithm and the cost of implementation is O(m²). The implicit basis at W that is being used by Algorithm 4 is
U. The reference point for Algorithm 2
fcs K o (P" [ere] + ee,e [ p :i= 1,... m,j = i 1,...,m.
where E mmxm such that K,s = A
Algorithm 4: Sampling on SPD with Bures- Wasserstein metric
Input : Base point W.
Output: Tangent Gaussian sample U (w Generate a normal random vector a a~ A(O0, I'I I'Im())))
1
2 Reshape a E Rmmm+11/2 into A SYM(m).
U - PT W (4C A).
SPD with Log-Euclidean metric. The LE metric defined as VU Tr (PLogm[W[(U)DLLLe (L)))))))(((())), where DLogm[W][U) is directional derivative of matrix logarithm of W evaluated at U.
The reference point for Algorithm is W I and the LE metric at I simplifies (U, VI = Tr(UV). With the parallel transport the preferred isometric transportation procedure, the sampling implementation is

---

Published in Transactions on Machine Learning Research (02/2023)
shown in Algorithm The computational cost of this implementation is O(m²). The implicit basis that is being used by Algorithm at W is
T = ( (cp K (P" (ere)) + e P)] pd :i l...,..., m,, = 1, 1....,m.. m,).
where K E R such that Krs = (()r:Aa) where f(z, v)
if x o y else f(a, y) = exp (m)
(xp
when y.
Algorithm 5: Sampling SPD with Nog-Ruclidean metric
Input : Base point W.
Output: Tangent Gaussian sample U Ww(00.2)) Generate normal random vector NN I'mm
2 Reshape E Rm((+1)/2 into A SYM(m).
U = PT A).
4.2 Hyperbolic
We consider the two popular geometric models of the hyperbolic space: the Poincaré ball and the Lorentz hyperboloid model (Nickel & Kiela 2017 2018
Poincaré ball. The Poincaré ball model is defined as PB(m) = {w E RT ||w||2 < 13 with the metric given by (u, v) PB = v/u,v)2/(1
(1- |/(l2) The tangent space at any w E PB(m) is (B() R.. The reference point for Algorithm 2 is o E R"" where denotes the zero vector. The PB metric at is (u, v)BB = (u, v)2. The sampling algorithm is concretely shown in Algorithm 6 whose implementation cost is O(m). The implicit basis that is being used by Algorithm
B
fc,(1 | 12/ :::: m.),
where C; E R ,,...,, denotes the standard basis vector.
Algorithm 6: Sampling on Poincaré ball
Input : Base point w E PB(m).
Output: Tangent Gaussian sample u (0,00²2) Generate a normal random vector ~ NNO PT (TTo=-X((/44 (a/4).
2 u
Lorentz hyperboloid. The Lorentizian inner product for x, w E R" is given by (x, w)c = -1191 + Ek Fili. The Loretnz hyperboloid model is defined as LH(k) = {w E ( w) -1} with the Lorentizian inner product as the Riemannian metric. The langent space at w E LH(k) is given by (k) = {u R² (w, u) =0. 03. The reference point for Algorithm| is w e E R" the LH metric at e simplifics as (u, L) (u, v)2 for u,vé TBB(m) and tangent space simplifics PB(m) {0} = The sampling algorithm is concretely shown in Algorithm The implementation cost (m).. The implicit at is
basis that is being used by Algorithm
I.
Wi+1
(e: ()+)
1+ wi
where e; (0, ) and e; R e p--1 denotes standard basis vectors for i 1...., ..m m
Algorithm 7: Sampling on Lorentz hyperboloid
Input : Base point PB(m).
Output: Tangent Gaussian sample ~ (0, Generate normal random vector ~ Ao0 o oI II,-1).
2 Perforn zero padding a = [0, al E R
3 u a (are--w(aa)) (a).

---

Published in Transactions on Machine Learning Research (02/2023)
4.3 Sphere manifold
The sphere manifold is denoled as the set SP(m) {w E !R" ||w|| 1} and the langent space al is given by (m) = {u E [" u/2 0}. The Riemannian metric is the induced by the Euclidean metric, i.e. (u, v/w = (u, v)2. The reference point for Algorithm 2
is w e₁ E Rm and SP metric at e₁ simplifies as (u, v) = (u, v)2. With parallel transport as the preferred isometric transportation procedure, the sampling with implementation cost O(m). The implicit basis being used by
implementation is shown in A Algorithm g
Algorithm g is
SP w
(c. W++1 W w 1...=,...,... m -0-1
where e; = (0, c,) and 6 R m- denotes the standard basis vector for 1,..., m 1.
Algorithm 8: Sampling sphere
Input : Base point w E (P(m).
Output: Tangent Gaussian sample u u (0, Generate a normal random vector NO0 o I'm Perform zero padding a [0, al e R"
PTT--W()) (a).
4.4 Stiefel manifold
The Stiefel manifold is the set of column orthonormal matrices, i.e. ST ( E Rax W W IH and its tangent space at W TwST(m,r) {U pm W + w U -), where O grxr is the matrix. The Riemannian metric is the induced by the Euclidean metric (U, V)ST Vr(U"V) Edelman et al. 1998). The reference point for Algorithm is W [e1,... e,l E TRxr where the metric is (U, V) = Tr(U" V) and the tangent space is ST(,,) = SKEW(r) x (mm-r)xr where we denote (rEW(r) as the set of new-symmettie matrices of size r. Huang al. (017)) have proposed an efficient isometric vector transport procedure, which choose for implementing Algorithm The concrete sampling procedure is shown in Algorithm with implementation cost O The implicit basis that is being used by Algorithm
Ww
g is
1..):.........---............... - (rt.:j-i.........._............. (W ;i= 1....,, r, ,,....rh
W 2
where e; E RK, E Rm-r denotes the standard basis vectors for i = 1,...,m and W E Rmx(m-r) denotes matrix such that the columns form an orthonormal basis of the orthogonal complement of the columns of W.
Algorithm 9: Sampling Stiefel manifold
Input : Base point W ST(m).
Output: Tangent Gaussian sample, U ~ (w, (0,000 o2).
Generate a normal random vector a ~ N00, 0² Ir((--)) ) and reshape into A1 E SKEW(r).
1
Generate a normal random vector a ~ N'O, 0² ('0 (m-r)xr) and reshape into A₂ E (mm-r)xr
2
A1/V2
W [e
e,] A
gmrr.
A₂
U W-W-W (A).
4.5
Grassmann manifold
The Grassmann manifold GR(m,r) consists of r-dimensional linear subspaces of I (r S m) and is rep- resented as GR(m,r) (W))spanWW)/W E Rmxr w"W V' I,), where colspan denotes the column space.
10

---

Published in Transactions on Machine Learning Research (02/2023)
The tangent space W is Tw (m, IU E RT Rm " O,} where O, R is zero matrix [Edelman et al. 1998) The Riemannian metric is induced by the Fuclidean metric GR = V for U.V E Tw),)m,r). (Edelman et al. 1998). The reference point for Algo- (U, V
rithm is W (e..... e,] Rmxr, the metric W is (U.
Tr(U'v) and tangent space at W simplifies as Tw GR(,,, = {0)rxr x R(m-r)xr, where we denote {0)-xr as the singleton set of zcro ma- trix of size r r. Similar to the Stiefel case, we use the veclor transport may as the preferred isometric transportation procedure (Huang al. (017). The sampling implementation is shown in Algorithm with with computational cost O(mr)). The implicit basis that is being used by Algorithm 10 is
( e i, r,j 1....,...
where e, e Rm-1 denote the standard basis vectors for I,... and WT Rmx(m-r) denotes matrix such that the columns form an orthonormal basis of the orthogonal complement of the column space of W.
Algorithm 10: Sampling on Grassmann manifold
Input : Base point W GR(m).
Output: Tangent Gaussian sample, U ~ ow
Generate normal random vector ~ -N ('m)))((m))))))) and reshape into A R ((m-r)xr,
(m-r)xx)
0
W ee....,, e, A
Rmxr
A
U W- (A).
5 Private Riemannian variance reduced stochastic optimization
Variance reduced stochastic optimization methods (Roux et al. 2012 Johnson & Zhang 2013 Delazio et al.] 2014 Reddi et al.] 2016) employ a hybrid update rule that uses both full gradient and stochastic gradient information simultaneously. By doing so, variance reduced methods improve the gradient complexity compared to the stochastic and the full gradient descent methods by requiring less gradient calls achieve the same convergence rates than the full gradient descent method. Many variance reduction strategies that
work in the Euclidean space have also been generalized to manifolds (Zhang et al. 2016 Sato et al. 2019
Zhou et al. 2019 Han & Gao 2021
In this section, we privatize the Riemannian stochastic variance reduced gradient (RSVRG) algorithm (Zhang et al. 2016) for solving (1) and develop differentially private RSVRG algorithm, henceforth denoted by DP.
RSVRG. Our proposed DP-RSVRG is summarized in Algorithm 11
DP-RSVRG with restart presented
Algorithm 12
DP-RSVRG has two loops. In the inner loop, an unbiased variance reduced stochastic gradient is constructed by correcting the Riemannian stochastic gradient with the full gradient calculated at the outer loop. We add noise from the tangent Gaussian distribution to the variance reduced gradient. The clipping operation clip, M + T.MM is defined as clip, (v) min { [| .1] and it ensures that the norm of v is at most The norm of the full gradient is clipped with parameter Co and the variance reduced gradient with parameter C1, respectively. PT refers to the parallel transport operation.
5.1 Privacy guarantee
In this section, we analyze the privacy guarantees of DP-RSVRG. We begin by noting that the variance reduced stochastic gradient has a deterministic and subsampled component. Hence, Step 7 of Algorithm be equivalently re-written
of
-- clipe, (grad (wf+1, (2))) PT -"t (clipe, (grad f(w"; z1)) - -9 +(h) + E
(2)
11

---

Published in Transactions on Machine Learning Research (02/2023)
Algorithm 11: DP-RSVRG
Input. +uddate frequency m, learning rale 7, number epochs S, clipping parameters Co, C₁N and initial iterate wº.
initialize i w
for = 0, 0,1,...,5 S - do
wi +++1 ."
g-+1
n - clipc. (grad ((00;=))) do Randomly pick & E n1.
for t 0,l,...,
ue+1 = clipe, (grad f(uft) zi,)) PT -wf (clipe, (grad ;(,)) - getl) + tett, where
e+1 (0,
wt+1 ++ Exp (-1jo 1).
Set W. = whtt
10 Output I: wpriv w.
Output II wriiv is choosen uniformly randomly from (fws ((w]+1p 1 1t=0 Js=0
Algorithm 12: DP-RSVRG with restarts
Input : update frequency m, Icarning rate 7) number of epochs S, and initial iterate w.. for k l...,, K do
k+1 D--RSSVRG(m, n, S, w² with output option II.
where E. N (f) and Ei (0, Specifically, the noise variance o² is split into into of for the full gradient query and of for the variance reduced stochastic gradient qucry such that of + o = o².
Claim ensures that pT En + = ~ N (0, Hence, (2) can be viewed composition of full gradient langent Gaussian mechanism
R²(Z) 8+1
clipco (grad f(""; z:)) + En
where Sh ~ ~N= (0) and variance reduced Gaussian mechanism
R²) =clic, (grad ( - PT -ut (clipe, (grad f(""; 20,) - 10-1) c
where G ~ No (0, o)) We now prove the moments bounds on the full gradient mechanism KR and variance reduced mechanism KR in the following claims and the proofs are given in Section B.3.1
Claim 3. The moments bounds satisfy
(A) < 21(A+ 1)C2 and K.R!1 S
8A(A 1)c7
nPoj
of
Now we derive the moments bound on subsampled version of RØ+1 using the results given in Waan et al, c019b|c) and the proof is given in Scction B.3.2
Claim 4. Define subsample: nn + Z the process of sampling single data point from n data points uniformly vandomly. Define the subsampled mechanism for RC+1 as sub,,+1 R,+1 subsample. Suppose 02 2 12C and 2/30 log (n(2 1)(1 + (o2/16C)))), we have
sub
Kanh R.++ (A) 28A(A + 1)C?
n²oz
12

---

Published in Transactions on Machine Learning Research (02/2023)
1 The full mechanism R can be seen adaptive composition of ([Kmbrott) lt=0 Js=0 and {[CR ) Since +o2 o², we can rewrite of ao²; o²2 (1 (1-a)o² for some (0, 1). Using this claim, minimizing over a, and setting C max/Co, C1}, we have
) Is=0
S
8-1
2m52(A + 1)C8
28mSA(A + 1)C
(R(A) $
(1)
+
K (A)
n²o7 +
R2
n²03
1=0 ==0
1=0
s=0
MSA(A + 1)
2
28
= KR) min aE((,1)
(3)
n²0²
1-a
It should be noted that for given X, the minimization over a has a closed-form solution.
The moments bound KR given in 3 can be converted to (e, guarantee using conversion rules, e-g., based X-
on Mironovy 2017 Proposition 3): Given 0 < < 1, <= minx21 (e(A-1)+log 1/6 Recently, however, the optimal conversion rule has been given in (Asoodeh et al. 2020 Theorem 3) for which there exists no closed-
form expression but can be solved numerically get c. The solver available in the autodp library (Wang
et al. 2019c). The above result connecting the moment bound KR with in (3) implies that tighter (c, guarantecs be obtained by optimizing over a, i.c., by exploiting the inter-play between the the noisc added to the full gradient and that to the variance reduced gradient.
It should be emphasized that in the Euclidean setting, Wang et al. 2017) have not considered optimization
of a as in 33 We empirically show that such an optimization of a obtains significant improvement in privacy in Section
We end this section with the following privacy result for Algorithuns 11 and
Claim 5. Algorithms
11 and 12 are (e, 6) differerryyy private with o² 2 c1
mS mS log( /
and o² N
n²
mSK log(1/5)22 02
respectively, for some positive constants C2 and C max C1}.
2²
5.2 Utility guarantee
In this section, we prove the utility guarantees of DP-RSVRG under various function classes manifolds including geodesic strong convex functions, general nonconvex functions, and functions that satisfy the Riemannian
(PL) condition. In particular, the geodesic strong convexity and Riemannian PL conditions generalize the notions of strong convexity and PL condition from the Euclidean space to manifolds, allowing fast convergence (for probloms satisfying these conditions) to global optimality when optimizing on manifolds. The proofs of the results discussed in this section are included Sections B.4.1
B.4.3
Let W M be totally normal ncighborhood and Dw denotes its diameter and Einin is the lower bound curvature of W (discussed in details in Section 2). Following (Zhang & Sra 2016 Han & Gao 2021
Han
et al. 2022a), we make the below standard assumption.
Assumption 1. Each fa in T is L-geodesically smooth and La Lo-geddesically Lipschitz over W.
The gradient complexity of an algorithm is measured in the number of incremental first-order oracle (IFO) calls neoded. An IFO (Agarwal & Bottou 2015) takes an index i E [m], w E W and returns (f((w), grad [()))) E R x T. Also, for readability we hide the log factors through notation Õ in the utility bounds and gradient complexitics. The exact expressions are in [1,, 12 for p-strongly convex func- tions; (16), 17) for non-convex functions; and (18 19h for functions with the Riemannian PL condition in the appendix section.
Theorem 6 (Utility under geodesic strong convexity). Suppose that Assumption 1 holds and F is μ- strongly geodesic conuer over W. If we run the Algorithm 11 with learning rate n = ((())) fre- quency m = ( for S Olog( log
neg (179)czga)) outer loops with output I, then [[F((rrriv) - F (w*)]
T dCLLL (/ (i)) Furthermore, the gradient complexity is given by O(n + 1=²
#
Theorem 7 (Utility under nonconvex functions). Suppose that Assumption 7 holds. If we run the Algo-
rithm 11 with output II, learning rate = O( Inarscrra) frequency m = (n)) and for S= v [log(1/0) Lo
,33
13

---

Published in Transactions on Machine Learning Research (02/2023)
outer loops, then E| grad F( < Lo (oy//d/Log(//0)//P//>))--
The gradient complexitty is given by
ne
(
LC a 6/8
[log(1/3) Lo
We now use Algorithm 12 to achieve utility guarantee under the Riemannian PL condition.
Theorem (Utility under Riemannian PL condition). Suppose that Assumption [ holds and F
1
n +E f((w) satisfies the Riemannian PL condition with parameter т. If we run Algorithm
12 with
learning rule 11 Ol Intiaerz)) frequency
O(n), S =01),, and K = log( aLF log(1/a/L2
n²,²
then
([F(w)tit) - -F(")) s O dLr" log(1/6)1 Purthermore, the gradient complexity is given by (2LT(2
5.3 Discussion: DP-RGD vs DP-RSGD vs DP-RSVRG
In this section, we compare our proposed DP-RSVRG with DP-RGD (Han et al. 2022a) and DP-RSGD Han et al. 2022a)
1. Strongly geodesic convex: DP-RSGD and DP-RGD both assume fa in [1 to be p-strongly g-convex. In contrast, DP-RSVRG in Theorem just assumess that F F= Di= fi to be p-strongly g-convex, which is much weaker assumption. Furthermore, DP-RSVRG assumes fi to be L-g- smooth, while DP-RGD, DP-RSGD do not make any smoothness assumption.
For (-stroongy g-convex functions, DP-RGD and DP-RSGD obtain the utility bound O d5L. log (1/6)B/dist" (wonsst"""","""""" (wn,e")) with gradient complexities n² and n², respectively (Han al. 2022a pn
Theorem 3). On the other hand, DP-RSVRG obtains utility bound Ō ddLLL 16) (we (wg,we)) we win=t""
in Ö(n + CL IFO calls, DP-RSVRG bounds are worse in terms of condition number L/p due #
the weaker assumption as discussed above.
2. Riemannian PL condition: DP-RSGD and DP-RGD both assume f. in to satisfy the Ric- mannian PI. condition with parameter On the other hand, DP-RSVRG in Theorem g assumes that F = Em fi satisfies the same condition, which is weaker.
DP-RGD and DP-RSGD obtain utility bound of T ( 11 in n2,2 IFO calls, respectively. DP-RSVRG obtains utility
n²,2 log an. log(178] and log (1//01) dLr log(1/8)Lā in (LL IFO calls. DP-RSVRG bounds are worse in terms of n²=² PL parameter T because of weaker assumption as mentioned above.
bound O
3. Nonconvex: In the nonconvex setting, only bound on the gradient norm can be obtained instead of a bound on the excess risk. Both DP-RGD and DP-RSGD obtain bound on gradient norm as
VIn't and O VInc O dt. log(1/87 in O Lov Lo
iterations respectively (Han et al. 2022a
La (lo
Theorem 5). From Theorem DP-RSVRG obtains bound on gradient as O Lo dt log(1/)) in O(V (log(1/8) 22/8) iterations. Hence, in this case, DP-RGD, DP-RSGD, and DP-RSVRG have the Lo same matching utility bounds.
ne
6
Experiments
this section, we illustrate the efficacy of the proposed sampling procedures and the proposed DP-RSVRG algorithm. We also show the benefit of a optimization (Section 5.1 in terms of the gain in privacy guarantee.
6.1
Benchmarking different sampling procedures
We benchmark our proposed isometric transportation (Algorithm portation', with the following three baselines.
2 based sampling, denoted as "Trans-
14

---

Published in Transactions on Machine Learning Research (02/2023)
10a
10-
10
Explet Tannsortadto
Dikt Inrepstaiann
Eot Fansparation
task vorqpesdion
10
104
Timee in Secs
10c
Time in Secs
100
Time in Socs
10
10
2.
10
10-4
10
10-2
10
10-3
10-4
10
20
40
20
40
2000
4000
m
m
m
(a) SPD with AI.
(b) SPD with BW.
(c) SPD with LE.
(d) Sphere manifold.
10a
Explet
Spplet::Saare
10
Explrtt
Expleit-Spame
10"
Palit
10
Expliit
Explct--ppee
Trnnporiition
maticnn
Perapprrtal
Tampprtatio
Secs
-
Time Secs
10a
Time Secs
10-1
Time Secs
10'
10
10-3
10-4
10
10-2
10-2
10-3
10-4
10-1
10--
500
1000
750
1000
750
m
m
m
(e) Stiefel r 5.
(I) Stiefel = 20.
Grassmann r 5.
(h) Grassmann r = 20.
10-2
Taplict
10a
Time in Secs
10-2
10-1
10-2
10-1
10-1
10-4
10:
500
1000
1500
2000
500
1000
1500
2000
m
(1) Poincaré ball.
(j) Lorentz hyperboloid.
Figure 1: Benchmarking of different sampling strategies. As can be seen, our proposed method "Transporta- tion' consistently outperforms the other baselines on the manifolds.
1. Sampling using Gram-Schmidt. We perform Gram-Schmidt orthogonalization on the basis Ø that is orthonormal wrt the Euclidean metric. This is a baseline for the SPD and Lorentz hyperboloid manifolds because for other manifolds, the orthonormal basis with respect to the underlying metric (..) can be simply obtained by scaling L. This is denoted as 'Gram-Schmidt".
Sampling using explicit basis. We take the implicit bases generated by the isometric trans- portation strategy (Algorithm) 2 and generate them explicitly, i.e., construct the full basis and then perform linear combinations. This is denoted 'Explicit..
3. Sampling using explicit basis by exploiting sparsity. As additional bascline, implement sampling with explicit basis construction using sparse operations. Sparsity is present in Stiefel, Grassmann, and Poincaré ball bases, and is therefore a baseline only for these three manifolds. This is donoted as "Explicit-pparcc..
In Figure ! we benchmark the sampling time for generating a single sample from the tangent Gaussian distribution on various manifolds discussed in Section 4 For SPD(m), consider (5, 10, 20, 30, 50).
15

---

Published in Transactions on Machine Learning Research (02/2023)
Overhead of privatizations for DP-RSGD (with x 10 epochs) for the SPD Fréchet mean and the principal eigenvector problems. Our proposed isometric transportation based sampling strategy lead to orders of magnitude improvements than those of Han al. (202aa).
Table 2:
Manifold
Size
Han et al.
2022a
This work
SPD
11 x 11
660 his
41 seconds (~ 104 improvement))
Sphere
786
668 seconds
24 sevonds (~ 10 improvement)
For PB(m), LH(m), and (m))), consider {250, 500, 1000, 1500, 2000}. For GR(m,r) and (T r). we consider = {100, 250, 500, 750, 1000} and r {10, 20).
Figure shows the average sampling time over five different base points chosen at random. From the figure, we see that the transportation sampling strategy is faster by two to four orders of magnitude than all the considered baselines. It. also shows the benefit of the transportation strategy as a unified sampling framework.
We study the benefits of the proposed sampling procedures in two problems: private estimation of the SPD Fréchet mean and the principal eigenvector (discussed in Section 6.3 We use DP- OP-RSGD algorithm for both problems and compare our sampling strategy with that developed in (Han et al. 2022a). The results are shown in Table 2 We observe that the proposed sampling strategy offers significant improvements leading to minimal overhead due to privatization.
6.2 Optimizing a in moments bound for better (c.d) guarantees
optto 0.11
We now show that better privacy guarantees can be empirically achieved by op- timizing a in moments bound (Section 5.1. To this end, we use the autodp library (Wang et al. 2019ch and set o Vaa, = ((1 - aaja instead of the standard setting σi 02 o/v2. We fix C 0.1,C2 0.01 and frequency to 10000 and n 100000. The results shown in Figure 2 for epochs S {1, 5, 10, 25, 50, 100} and noise posal to optimize over significantly improves the privacy guarantees than the standard setting. For noise level o = 0.05, we obtain = 0.47, while the standard setting achieves c = 0.64 leading to a 1.6x improvement in privacy guarantee.
0.6
naMea- 0.1)
natto 6.05)
0.4
0.3
0.2
{0.1, 0.05). We observe that pro-
0
20 Epochst5)
40
Figure 2: Improving pri- vacy with a.
6.3 Benchmarking DP-RSVRG
In this section, we compare our proposed DP-SVRG with DP-RGD and DP-RSGD Han ct al. 2022a) for the lask of computing the Fréchet mean and leading eigenvector with privacy configuration e = (0.1, 0.3, 0.5] and 8 = 10-6 The parameter details for all the algorithms are Section
Private Fréchet mean on SPD manifold. We consider the problem of privately estimating the Fréchet mean of SPD matrices under the Affine-Invrrian metric. We select images from PATHMNIST medical imaging dataset (Yang al. 2021 and pass them through the covariance descriptor pipeline to generate images, each represented as a SPD matrix of size 11 x 11. Please refer to Section C.1 for more details on the problem formulation and covariance descriptors. We consider the two sets consisting of 10704 and 10356 images from two different classes. For each set, we compute the optimal Fréchet mean by running the (non-private) RGD for 1000 epochs with learning rate set 0.5. For both the sots, we plot excess risk against the IFFO calls in Figure 3a averaged over five randomized runs. The plots corresponding to the two sets are shown in the two rows of Figure 3a
Private principal cigenvector computation on sphere. We also consider the problem of computing the leading eigenvector a symmetric matrix, details in Section C.2 We take images from two classes of MNIST and generate 784 vectors to form two sets of 6903 and 7877 images. For each set, we compute the covariance matrix and compute its leading eigenvector by using cigen-decomposition of matrix 1/n >n z to find
the optimal solution. We plot the excess risk against the IFO calls in Figure averaged over five randomized runs. The plots corresponding to the two sets shown in the two rows of Figure 3b
16

---

Published in Transactions on Machine Learning Research (02/2023)
10a
10:
10:
101
10a
10
10a
10-1
10-1
10
10-2
calls
0.5
10P
10a
10a
10a
10a
10a
Excoss
10a
10a
107
10-1
10-1
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
K10*
IFO
x22
M2D
(a) Private Fréchet mean of the medical imaging data on the SPD manifold.
c=1.1
2=0.3
<= 0.5
00
3x
0.5
IFO calls
IFO calls
calls
0.5
DF-AGD
DF-AS03
Excess Risk
10a
10a
tot
10a
100
1
2
IFO calls
XLOP
IFO calls
X12
IFO calls
Kis
(b) Private principal eigenvector on MNIST dataset.
== 0.1
c=0,3
== 0.5
De AGD
10a
10a
10a
De 4590
De -SVRS
Excees Risk
1
10
10-1
10-2
10-2
10
IFD calls
IFO calls
IFO calls
(c) Private Fréchet mean of Poincaré embeddings.
Figure 3: Comparison between DP-RGD, DP-RSGD, and DP-RSVRG. Each row in (a), (b), and (c) corre- sponds to consistent dataset. We see the proposed DP-SVRG achieves comparable excess risk compared to the baselines with lower number of IFO calls.
17

---

Published in Transactions on Machine Learning Research (02/2023)
Private Fréchet mean of the Poincaré word embeddings. We generate the hierarchy tree of transitive closure of mammal subtree of the WordNet dataset (Miller 1995), a lexical database, and compute the private Fréchet mean of the Poincaré word embeddings (Nickel & Kiela 2017). WordNet provides relationship between pairs of concepts. For instance, the 'mammal' subtree of WordNet has the concept 'mammal' as the root node and the 'i--a' (hypernymy) velationship defines its edges: 'tiger' is-a 'mammall' 'lion' is-a 'rodent",
etc. The mammal subtree consists of 1180 nodes and 6540 edges. The results are shown Figure 3c
Results. In Figure Sa. observe that the proposed DP-RSVRG obtains an overall better excess risk in computing the private Fréchet mean of the two classes (corresponding to the two rows in Figure Bap medical imaging data. In Figure 3a first row, DP-RSVRG performs consistently better than both the baselines. In Figure 3a second row, DP-RSVRG performs better than DP-RGD and is similar to DP-SRGD. In Figure 3b] the benefit of variance reduction is clearly observed. In both rows of Figure 3b] the proposed DP-SVRG consistently outperforms DP-RGD and DP-RSGD the gradient calls and achieves a good excess risk. On the Fréchet mean computation of the Poincaré embeddings (Figure 3cb, we see that the benefit of variance reduction as well as the proposed DP-RSVRG performs better than DP-RSGD especially in low regime (more stringent private setting). In all cases, DP-RGD performs the best and our proposed DP-RSVRG matches the performance in the initial iterations.
Overall, we observe that the proposed DP-RSVRG obtains better or comparable excess risk against. DP-GD and DP-SGD with generally fewer IFO calls across different levels of noise injection.
7 Conclusion
In this work, have improved the framework of differentially privale Riemannian optimization via efficient sampling and variance reduction. We have proposed linear isometry based sampling strategy to generate tangent Gaussian samples. This largely reduces the cost of privatizing Riemannian optimization. In addition, we have shown how variance reduction improves the gradient complexity in practice. We believe this work allows Riemannian optimization to be privatized efficiently for large-scale applications.
References
Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, Llya Mironov, Kunal Talwar, and Li Zhang, Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference computer and communications security, pp. 308-318, 2016.
John M Abowd. The US census bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2867-2867, 2018.
P-A Absil, Christopher G Baker, and Kyle A Gallivan. Trust-region methods on Riemannian manifolds. Foundations of Computational Mathematics, 7(3):303-332) 2007. 2
P-A Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization algorithms on matrix manifolds. In
Optimization Algorithmss on Matria Manifolds. Princeton University Press, 2009. 3 24
Alekh Agarwal and Leon Bottou. A lower bound for the optimization of finite sums. In International conference on machine learning, pp. 78 86. PMT.R, 2015. 13
D Apple. Learning with privacy at scale. Apple Machine Learning Journal, 1(8), 2017.
Vincent Arsigny, Pierre Fillard, Xavier Pennec, and Nicholas Ayache. Geometric means in a novel vector space structure on symmetric positive-definit matrices. SIAM Journal on Motric Analysis and Applications, 29 (1):328-34) 347, 2007. doi: 10. 10.1137/05063799
Shahab Asoodch, Jiachun Liao, Flavio Calmon, Oliver Kosut, and Lalitha Sankar. A better bound gives a hundred rounds: Enhanced privacy guarantees via f-divergences. In 2020 IEEE International Symposium on Information Theory (TSIT), pp. TEEE, 2020. 13
18

---

Published in Transactions on Machine Learning Research (02/2023)
Borja Balle, Giovanni Cherubin, and Jamie Hayes. Reconstructing training data with informed adversaries. 2022.
arXiv preprint
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algo- rithms and tight error bounds. In 2014 IEEE 55th annual sympostum on foundations of computer science, pp. 464-473. IEEE, 2014. 1
Racf Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems, volune 32, 2019.
Raef Bassily, Cristóbal Guzmán, and Anupama Nandi. Non-Fuclidean differentially private stochastic convex optimization. In Conference on Learning Theory, pp. 474 499.. PMLR, 2021. [
Eugenio Beltrami. Teoria fondamentale degli spazii di curvatura costante: memoria. F. Zanetti, 1868.
Rajendra Bhatia, Positive definite matrices. In Posétive Definite Matrices. Princeton university press, 2009.
24
Rajendra Bhatía, Tanvi Jain, and Yongdo Lim. On the Bures Wasserstein distance between positive definite matrices. Expositiones Mathematicae, 37(2):165 191, 2019. g
Mukul Bhutani, Pratik Jawanpuria, Hiroyuki Kasai, and Bamdev Mishra. Low-rank geometric mean metric learning. ICML workshop on Geometry in Machine Learning (GiMLi), 2018. 2
Silvere Bonnabel. Stochastic gradient descent on Riemannian manifolds. IEEE Transactions on Aulomatic Control, 58(9):2217-222) 2229, 2013.
Nicolas Boumal. An introduction to optimization on smooth manifolds. To appear with Cambridge University Press, Apr 2022.
24
Nicolas Boumal and Pierre-antoine Absil. RTRMC: Riemannian trust-region method for low-rank matrix completion. Advances in neural information processing systems, 24, 2011. 2
Nicolas Boumal, Bamdev Mishra, P-A Absil, and Rodolphe Sepulchre. Manopt, matlab toolbox for optimization manifolds. The Journal of Machine Learning Research, 15(1):1455 1459, 2014. 7
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In Proceedings of the 28th USENIX Conference on Security Symposium, SEC'19, pp. 267-284 USA, 2019. USENIX Association. ISBN 9781939133069. 1
Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Membership inference attacks from first principles. In 2022 IEEE Symposium on Security and Privacy (SP), pp. 1897-1914. IEEE, 2022. !
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk mini- mization. Journal of Machine Learning Research, 12(3). 2011.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: a fast incremental gradient method with support for non-strongly convex composite objectives. Advances in newral information processing systems, 27, 2014. II
Manfredo Perdigao Do Carmo and Flaherty Francis. Riemannian geometry, volume 6, Springer, 1992. B
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, llya Mironov, and Moni Naor. Our data, our- selves: Privacy via distributed noise generation. In Annual international conference on the theory and applications of cryptogrophic techniques, pp. 486-503. Springer, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryplogrophy conference, pp. 265-284 Springer, 2006b. T
19

---

Published in Transactions on Machine Learning Research (02/2023)
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sei. 9(3-4):211-400 2014. 4
Alan Edelman, Tomás A Arias, and Steven T Smith. The geomelry of algorith with orthogonality constraints. SIAM journal on Matric Analysis and Applications, 20(2):303 353, 1998. 2 10
Ülfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy- preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and com- municaaions securily, pp. 1054 1067, 2014.
Mikhael Gromov. Hyperbolic groups. Springer, 1987. 2
Nicolas Guigui and Xavier Pennee. Numerical accuracy of ladder schemes for parallel transport on manifolds.
Foundations of Compulational Mathemalies, 22(3):757-700 7907777779991000 2022. 7
Hatem Hajri, Toana Ilea, Salem Said, Lionel Bombrun, and Yannick Berthoumieu. Riemannian Laplace distribution on the space of symmetric positive definite matrices. Entropy, 18(3):98, 2016. 4
Andi Han and Junbin Gao. Improved variance reduction methods for Riemannian non-convex optimization.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
2
13
Andi Han, Bamdey Mishra, Pratik Kumar Jawanpuria, and Junbin Gao. On riemannian optimization over
positive definite matrices with the wassertwss geometry, Advances in Neural Information Processing Systems, 34:8940 8953, 2021.
Andi Han, Bamdev Mishra, Pratik Jawanpuria, and Junbin Gao. mization. arXiv preprint crXiv:2205.09// 2022a.
Differentially private Riemannian opti-
5
13
16
26
Andi Han, Bamdev Mishra, Pratik Jawanpuria, and Junbin Gao. Riemannian block SPD coupling manifold
and its application to optimal transport. Machine Learning Journal, 2022b. 2
Wen Huang, Kyle A Gallivan, and P-A Absil. Broyden class of quasi-Newton methods for Riemannian optimization. SIAM Journal on Optimization, 25(3):1660 1685, 2015.
24
Wen Huang, P-A Absil, and Kyle A Gallivan. Intrinsic representation of tangent vectors and vector transports matrix manifolds. Numerische Mathematik, 136(2):523 543, 2017.
10
24
Roger Iyengar, Joseph P Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. Towards practical differentially private convex optimization. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 299-316. IEFE, 2019.
Pratik Jawanpuria and Bamdev Mishra. A unified framework for structured low-rank matrix learning. Tn ICML, 2018. 2
Pratik Jawanpuria, Arjun Balgovind, Anoop Kunchukuttan, and Bamdev Mishra. Learning multilingual word embeddings in latent metric space: A geometric approach. Transactions of the Association for Computational Linguistics, 7:107-120, 2019a. 2
Pratik Jawanpuria, Mayank Meghwanshi, and Bamdey Mishra. Low-rank approximations of hyperbolic embeddings. In IEFE Conference on Decision and Control, 2019b. 2
Pratik Jawanpuria, Mayank Meghwanshi, and Bamdev Mishra. Geometry-aware domain adaptation for unsupervised alignment of word embeddings. In Annual Meeting of the Association for Computational Linguistics, 2020a. 2
Pratik Jawanpuria, Mayank Meghwanshi, and Bamdev Mishra. A simple approach to learning unsupervised multilingual embeddings. In Conference on Empirical Methods in Natural Language Processing, 2020b. 2
Pratik Jawanpuria, N. T. V. Satya Dev, and Bamdev Mishra. Efficient robust optimal transport: formulations and algorithms. Tn IEEE Conference on Decision and Control, 2021. 2
20

---

Published in Transactions on Machine Learning Research (02/2023)
Ric Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction.
Aduances in neural informalion processing systems, 26, 2013. 11
Hiroyuki Kasai, Pratik Jawanpuria, and Bamdev Mishra. Riemannian adaptive stochastic gradient algo-
rithms on matrix manifolds. In International Conference on Machine Learning (ICML), 2019. 2
Jakob Nikolas Kather, Johannes Krisam, Pormpimol Charoentong, Tom Luedde, Esther Herpel, Cleo-Aron Weis, Timo Gaiser, Alexander Marx, Nektarios A Valous, Dyke Ferber, et al. Predicting survival from colorectal cancer histology slides using deep learning: A retrospective multicenter study. PLoS medicine,
16(1):e1022330, 2019.
33
John M Lee. Riemannian manifolds: introduction to curvature, volume 176. Springer Science & Business Media, 2006.
2 3
Aaron Lou, Isay Katsman, Qingxuan Jiang, Sorge Belongie, Ser-Nam Lim, and Christopher De Sa. Differ- entiating through the Fréchet mean. In International Conference on Machine Learning, pp- 6393 6403. PMLR, 2020.
24
George A Miller. Wordnet: lexical database for english. Communications of the ACM, 38(1)):39 41, 1995. 18
Nina Miolane, Nicolas Guigui, Alice Le Brigant, Johan Mathe, Benjamin Hou, Yann Thanwerdas, Stefan Heyder, Olivier Peltre, Niklas Koep, Hadi Zaatiti, et al. Geomstats: a Python package for riemannian geometry in machinc learning. Journal of Machine Learning Research, 21(223):1-9 2020.
7 32
Nina Miolane, Matteo Caorsi, Umberto Lupo, Marius Guerard, Nicolas Guigui, Johan Mathe, Yann Cabanes, Wojeiech Reise, Thomas Davies, António Lcitão, et al. Iclr 2021 challenge for computational gcometry &
topology: Design and results. arXiv preprint arXiv:2108 09810, 2021. 32
llya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pp. 263-275. IEEE, 2017. 4
Bamdev Mishra, NTV Satyadev, Hiroyuki Kasai, and Pratik Jawanpuria. Manifold optimization for non- linear optimal transport problems. arXiv:2103.00900 2021. 2
Adele Myers, Saiteja Utpala, Shubham Talbar, Sophia Sanborn, Christian Shewmake, Claire Donnat, Johan Mathe, Rishi Sonthalia, Xinyue Cui, Tom Szwagier, et al. Ichr 2022 challenge for computational geometry & topology: Design and results. In Topological, Algebraic and Geometric Learning Workshops 2022, pp. 269 276. PMLR, 2022. 32
Joe Near. Differential privacy at scale: Uber and Berkeley collaboration. In Enigma 2018 (Enigma 2018), 2018.
Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representations. Ad- vances in newral information processing systems, 30, 2017. 2. g 18
Maximillian Nickel and Douwe Kiela. Learning continuous hierarchies in the Lorentz model of hyperbolic geometry. In International Conference on Machine Learning, pp. 3779 3788. PMLR, 2018. 2 9
Madhav Nimishakavi, Pratik Jawanpuria, and Bamdev Mishra. A dual framework for low-rank tensor completion. In NewrIPS, 2018. 2
Xavier Pennec. Intrinsic statistics on riemannian manifolds: Basic tools for geometric measurements. Journal of Mathematical Imaging and Vision, 25(1):127-154 2006.
Xavicr Pennec, Pierre Fillard, and Nicholas Ayache. A Riemannian framework for tensor computing. Inter- national Journal of computer vision, 66(1):41 66, 2006. 24
Guodong Qi, Huimin Yu, Zhaohui Lu, and Shuzhao Li. Transductive few-shot classification on the oblique manifold. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 1412-8422, 2021. 2
21

---

Published in Transactions on Machine Learning Research (02/2023)
Md Atiqur Rahman, Tanzila Rahman, Robert Laganière, Noman Mohammed, and Yang Wang. Membership inference attack against differentially private deep learning model. Trans. Dala Priu., (111)611779 2018.
Sashank J Reddi, Ahmed Hefny, Suvrit Sra, Barnabás Póczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International conference on machine learning, pp. 314-323. PMLR, 2016.
Matthew Reimherr, Karthik Bharath, and Carlos Soto. Differential privacy over Riemannian manifolds. Advances in Neural Information Processing Systems, 34:12292-1222 123033 2021.
Christian P Robert and George Casella. Monte Carlo stalistical methods, volume 2. Springer, 1999.
2
Nicolas Roux, Mark Schmidt, and Francis Bach. stochastic gradient. method with an exponential conver- gence rate for finite training sets. Advances in neurol information processing systems, 25, 2012.
Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, Yann Ollivier, and Hervé Jégou. White-box, vs black-box: Bayes optimal strategics for membership inference. In International Conference on Machine Learning, pp. 5558 5567. PMLR, 2019.
Hiroyuki Sato, Hiroyuki Kasai, and Bamdev Mishra. Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport. STAM Journal on Oplimizalion, 19(2):1444-1477) 2019.
Armin Schwartzman. Lognormal distributions and geometric averages of symmetric positive definite matrices. International Statistical Review, 84(3):456-488 2016.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descont with differentially private updates. In 2013 IEEE global conference on signal and information processing, pp. 245 248. IEEE 2013.
Carlos J Soto, Karthik Bharath, Matthew Reimherr, and Aleksandra Slavkovic. Shape and structure pre- serving differential privacy. In Advances in Neural Information Processing Systems, 2022. 2
Ryota Suzuki, Ryusuke Takahama, and Shun Onoda. Hyperbolic disk embeddings for directed acyclic graphs.
In International Conference on Machine Learning, pp. 6066-6075. PMLR, 2019. 2
Yann Thanwerdas and Xavier Pennec. ((n) -invariati Riemannian metrics on SPD matrices. Linear Algebra
and its Applications, 661:163 201, 2023. 24
James Townsend, Niklas Koep, and Sebastian Weichwald. Pymanopt: A python toolbox for optimization on manifolds using automatic differentiation. arXiv preprint arXiv:163..0 03236, 2016.
Saiteja Utpala, Andi Han, Pratik Jawanpuria, and Bamdev Mishra. Ricoptax: Riemannian optimization in JAX. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop), 2022a.
Saiteja Utpala, Praneeth Vepakomma, and Nina Miolane. Difierentially private Fréchet mean on the manifold of symmetric positive definite (SPD) matrices. arXiv preprint KKi::2208.04244 2022b.
Salil Vadhan. The complexity of differential privacy. In Tutorials on the Foundations of Cryplogmphy, pp- 347 450. Springer, 2017.
Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. Advances in Neural Information Processing Systems, 30, 2017.
2
Di Wang, Changyou Chen, and Jinhui Xu. Differentially private empirical risk minimization with non-convex loss functions. In International Conference on Machine Learning, pp. 6526-6535, 2019a.
Lingxiao Wang, Bargav Jayaraman, David Evans, and Quanquan Gu. Efficient privacy-preserving stochastic nonconvex optinization. arXiv preprint Xiv: 13659,, 2019b.
12
26
22

---

Published in Transactions on Machine Learning Research (02/2023)
Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled Rényi differential privacy and analytical moments accountant. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1226 1235. PMLR, 2019c.
12
16
Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375-389 2010.
Qian Xie, Sebastian Kurtek, Huiling Le, and Anuj Srivastava. Parallel transport deformations shape space of clastic surfaces. In Proceedings of the IEEE International Conference on Computer Vision, pp. 865 872, 2013.
Jiancheng Yang, Rui Shi, Donglai Wei, Zequan Liu, Lin Zhao, Bilian Ke, Hanspeter Pfister, and Bingbing Ni. Medmnist v2: A large-scale lightweight benchmark for 2d and 3d biomedical image classification. arXiv preprint Xr::::2100. 14795, 2021.
16
Hongyi Zhang and Suvrit Sra. First-order methods for geodesically convex optimization. In Conference on Learning Theory, pp. 1617 1638. PMLR, 2016.
27
Hongyi Zhang, Sashank J Reddi, and Suvrit Sra. Riemannian SVRG:
Fast stochastic optimization Riemannian manifolds. Advances in Newral Information. Processing Systemss 29, 2016.
27 29
33
Jiaqi Zhang, Kai Zheng, Wenlong Mou, and Liwei Wang. Efficient private ERM for smooth objectives. International Joint Conference Artificial Intellignnce, pp- 1922-3928. 2017. 1
Pan Zhou, Xiao-Tong Yuan, and Jiashi Feng. Faster first-order methods for stochastic non-convex opti- mization on Riemannian manifolds. In The 22nd International Conference on Artificial Intelligence and Statisties, pp. 138-147. PMLR, 2019.
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. Advances in neural information processing systems, 32, 2019.
23

---

Published in Transactions on Machine Learning Research (02/2023)
A Details about parallel transport and vector transport
A.1 Parallel transport expressions for SPD, hyperbolic, and sphere manifolds
SPD manifold. For the Affine-Ivvarint and the Log-Euclidean metries, the parallel transport operation of tangent vector U SYM(m) from W to W, W, W.W SPD(m) is available is closed form (Bhatia 2009 Pennee et al. 2006 Thanwerdas & Pennee 2023
For the Bures- Wasserstein metric, there is no closed-form expression for the parallel transport operation for general W. W. However, when W and W commute, there exists closod-form expression Thanwerdas & Pennec 2023). We exploit this for our case W (Algorithm i.e. any base point always commutes with the reference point. Below, we list the parallel transport expressions for all the three metrics, i.c.,
Affine-Invariat Invariant: PT w (U) (WW UU( w))
Bures-Waer Wasserstein: PT w (U) P KB
(P"UP) p"
Log-Euclidean: PT W - w (U) P KL. o (P"UP) p"
where KEw E Raxm such that (KBw)rs A. 5. KLE E |m=x such that (KLE)rs f() 2o). Here, (Ir ex) x + clse (x, (2) when x = and (f1,..., 6m) and (AI,..., Am) E Rm denotes the cigenvalues of W and W, respectively.
z-y
Hyperbolic manifold. The parallel transport expressions can be found in Lou et al. 2020
1 w 1
Poincaré ball: PT PT (u) = 1 gyr - (w). W. w]( =
(w 1 u)),
where w (1 21,,(W, w)2
[1+ w)2
(w, u.c
Lorentz hyperboloid: PT (u)
(w w).
w)c
Sphere manifold. The parallel transport expression can be found in Absil et al. 2009 Boumal 2022
PT = [ (cos ||vl22 - 1) VVT
WVT sin ||vl2
|| u,
|vll2
(I ww )w w
where v = Exp w arcoos (w, w)2
ww )( - w)ll
A.2 Vector transport for Stiefel and Grassmann manifolds
Efficient vector transport on the Stiefel and Grassmann manifolds are provided in (Huang et al. 2017 which proposes a stralegy called transportation by parallelization (Huang et al. 2015). For the exact algorithms, see (Hang et al. 2017 Algorithms 3, 4, and 5).
B Proofs
B.1 Proof of Lemma
Thcorem (Change of variable formula). Let X, Y be measurable space and 6: X Y and f f:Y - R is measurable mapping and let X be measure on X and Φa X denote the pushforward measure of X through on Y then Jy fd((.>) Jx f dd.
24

---

Published in Transactions on Machine Learning Research (02/2023)
Proof.
1. Let ī E I denote the coordinates of and consider the normalixing constant
E i= GB. - -i 1i:3
(-Iv-ull d(o-A)(v) @ Jz exp
/
Cui
exp
dd(c)
JTM
20²
20²
Ei Ej= ((a - pi))3, (cj -15))33)
(*+)
Σ i== (G
11:)
exp
dd(c)
exp
dd(c)
gd
20
3d
20²
(2T02)a/22
(4)
where the change of variable rule (Theorem 9 under transformation & in (+), that (Ba,..., ,a) (a-=B.²² )d is the normalizing constant of
Σ 2x
is orthonormal tangent vectors in (**), and that Jaa exp( Ni,, o( x2 in (t).
2.
Now, let & Nul o²), we show that E~ O( Let C IRd be a measurable set, then consider
= f (os( (4) (2To2)a/2 exp
11v0~ 1
Pr(g A) -Pr(g E (s)())]
d(d.))(v)
20²
Sa (2mo2)a122 exp
Σd Ei=(ce (cs - 17:)2
dD(c).
20
The last equality is obtained similarly as in (4). Since the last expression is exactly probability that a random vector distributed as ((ūīo²La) belongs to set A, we are done. The converse is shown in a similar way.
3. This simply follows Statement 2 of Lemma and the variance bound from the standard Gaussian distribution.
B.2 Proof of Claim 2
Proof. Given that L1 - is a linear isometric mapping, one can show that it is invertible and its inverse is again isometry, which we will denote by LI If Φ. is Lebesuge measure on Tw then - (o.A) is the Lebesgue measure on T.M. This can be seen by observation that, & (BI,...,Ba Pa} orthonormal basis for T&M then (LI 31,... "id....,,""",, L1 - is orthonormal basis for T. Let & ~ Nilu, o²), we will show that LI - Nar (LI -- p. p, consider measurable set S C Tw.M
(_lVv- mll d(oa))(v)
Pr LI 5 = Pr E1 LI (S)+
(1 (2T02)d122 exp
20
LI 1 (v)
10)
(+)
((. (v)
(2mo22)d12 exp
202
L m (w)l
(en)
(LITT (b.)) (v).
(2 exp
20
where we used change of variables formula Theorem (with X = L = S and Φ = L
and that LI is isometry in (x*) Since - (6.)) is the Lebesuge mcasure on T, we have that Liw- (L. 1, 12,
25

---

Published in Transactions on Machine Learning Research (02/2023)
B.3 Proofs of Section 5
B.3.1 Proof of Claim
Let Q*+1 denote the full gradient query given by Q*+1(2) = Ex=1 ; 2;). Let Z, Z' E z" denole adjacent datasets, consider the sensitivily, denoted as A
Proof.
1 III grad f(""; : ala + grad f( ;21
2Cg (5)
++1 sup 11 0* (Z')l Σ n
2~-2
π
Following HHn et al.
2022a Lemma 2), the moments bound of the full gradient mechanism R is given by
KR) (A) 1(A+ 207
5
2A(A + 1)C2
(A+)2
n²oj
Let 2 denote the variance reduced stochastic gradient query given by 22) grad f(uf+t; :2) 22 PT pr"""+""" 11
(grad = getl). Let Z, Z' E Z denote adjacent datasets, consider its sensitivity, denoted
at A4p
A 4+1
2 (2) ( (2')
sup Z~Z
(
||aaad fww +2)==())))))) :2) grad fw, :2')lln ;
+ |PT -w (grad f( - grad f(w"; 2²))
sup Z~Z'
w
|| f(w - (2) - grad (w, + ( :2)) + llgrad ((=";) grad f(""; ;=0""=111) 11
sup Z-Z'
g|ad (w, +1 1 m+ + ||grad f(uf :2)] =')!l + ||grad = 2) + ligrad f("";=')
sup Z~Z'
4C1,
(6)
where we used linearity of parallel transport and triangle's inequality in (x) and that parallel transport is isometric in (f) and triangle incquality and assumption of lipschitz in (t). Now moments bound of R is given by,
+(*+1) 1) (A (A)
8A(A + 1)C
(7)
20
o3
B.3.2 Proof of Claim 4
Proof. By using
Wang et al.
2019b Lemma 3.7) and by choice of parameters o², we have
3.5
28A(A+1)C3
Knuh R, (A) S
K (A)
n²
o2n²
B.3.3 Proof of Claim 5
Proof. For R can be show (e, J)diiffferentlllly private by solving for e and as follows, i.e.,
mSXA + 2)c² 2
28
mSA(A 1)
2
28
de
de
min xE(0.1)
n²o²
a-a
n²o²
+
1
exp
2
6,
(8)
26

---

Published in Transactions on Machine Learning Research (02/2023)
where a* (v14 -1/13 and there exists constant oj > such that o² 2 Ci "=*
mS 1 satisfies Hence,
Algorithm
11
satisfies (e,8)-DP. For Algorithm 12 using similar arguments there exists constant Co 0 such guarantees (c, 6)-DP.
that 0² mSK log(1/8]c* n=
B.4 Proofs of Section 5.2
Lemma 10 (Trigonometric distance bound (Zhang & Sra 2016)). Let wo, W1, W2 E W M lie in totally normal neighborhood of Riemannian manifold with curvature lower bounded by Kimin and Co = dist(wo, w1) and l = dist(w', Wz2 and lg = dist Ww, W2). Denote O as the angle on TuoM such that cos( = Eaci (Exp (ur1); (,))) Expao (wz)) Let Dyy be the diameler of W i.e., Dw == max,,wr dist(w, w'). Define curva- y Vhmin
ture constant Ç =
tanb /Mimnn Kmmin < O and Ç <= =117 if fmiin 2 0. Then, we have that l S 560 + f2 26022 cos
Lemma 11. Bin.eallef + I S E,, grad (ww(t);2,) PT (grad ; - 9 )| 1 + do².
(9)
Proof.
ex grad fww ;24,) PT -w?+ (grad f(0"; 9" 1)+ )- + Ec +
ex ll grad [wftt] z4.))
(grad f (z.)) 9² ")=ي)| Be, llea lle
+ (ll, grad flw, + ; ) - PT - (grad ; - -g²+1), Be, leal)
$ E,, grad fw;," + ; z.,) ; - pT""" +wt (grad (w"; ( | + do²
where we used that E., [e]] = 0 and Ee, || 1 S do in last inequality,
B.4.1
Proof of Theorem 6
Proof.
We bound first term IE, ll grad f fwott1 ;24, pT"""=up" -w (grad f( - 1( as in (Zang
ct al. 2016
Bi, grad [wot ; =5,)
(grad f(w"; zi,) - 1 mntt
< E,, grad (ww/t) (24))= - PT -wt grad f ( 24.) + PT -mut+
(grad F( - "TT"" - grad F(w*)) _
< 2
grad (wwtt :24)) +u,"" grad f(0;;; 2x,) wntt
+
+ 2 |T pT (grad F(w*)
PT - grad F(ww)) 2
-, grad f(u 11 ; -u -wtt grad f(ö"; 2i,) wn
2
+ 2B,
grad F(w") - PT -
grad F(w")
< 4L | Exp uit1 (w" ||( + 2 Exp w0 2
Aist (wi w²) + dist (w* w.).
(10)
Using the trigonometric distance bound in Lemma 10 with wa = x1 2141 wi wtt1 W2 w²
dist? (w w²) I çdist? (w w + dist? (w w²) - 2((Exp-1) po (w Exp wot (w ww
- | = =<|| بب+
with + dist? (wo w²) -2(-mu²* mitt1 Exp Expryt with (w" )) wo
=c/ le dist dist"(w;" (wit), w²) + 2n(v Exp -1 wit (w (w))) Me
27

---

Published in Transactions on Machine Learning Research (02/2023)
Applying expectation we have
dist dist w²)
S (1j Einer 1| 11 lupts + dist _w=) + 20/(Brr. u8t1, Exp ( (w=) Muttt wi
= =nn I? [4dist (wt w²) ,w) + 6dist (w), w" + (g F(us+1 ) Exp -1 w, +1 (w 1) wot + dgn²²²
$ (1)² L22 [4dist? (wf w²) + 6dist (w) w )] + 2n(F(w")) - F(we+1)
H dist (wf _,=,,,,"))) ,,0') + denio²
2
$ (1 + 4(1" 1 mp)dist (w w0) 6(1) 2 L dist ( (w", w=) dcn)=0².
Defining u, dist (wit1: w*), q (1+ 45n mp), p 6(n) L2 dlrj²0² 2 we have following recurrence
U++1 - pdo 5 qu puo) + c from which we have that Um S (p + 9th p)) + m- g'c. Now choosing
|/ = प and m 2 19c2a - we get q= 10ç and = 1/5. Note that I0Ç 1 (L 1) and
- hence 0 < < and which we have that (p + (a p)) = 1/2.
(wd w0 [==']]] S Ejdist (wo w²)] + dc 1²02 m-1
1
2
10
1=202
4²
E dist (w w²) + dc
L
10
1.202
10Ç
10o²
E dist (wmitt w²) + dc
Eldist 2 (w w²)] +
28
n
289
from which we have
El Eldist?(uis w²)] = 2- 2-$EEdist? (w w='] 10g2
Σ
1
S 2-
EE (w w w²)] 2dc-1 10
mS log
289L
2
289
n²e²
200ç
S 1lo((1/8){A
< 2- (oes?((w))) (w w=1] + 289
SSEdiist
n²e²
1 R [Edist w² 2 T. w=)] + lad C S 5log(1/0)
E [[w=))))([')] S
112 n²²²
Now, setting 2-5 d N10 -' dist (w",,)
25
28 (w",w")) d100ç (1/6)
O [log disp''dis' distt("" (w",w="])) )) substituting this we have that, and now for 5 o (log log (1/
neat (w" (w",w") _w=) ))
log (1/8)c1g
E[f(x*) - f(w))) -[f())))((u}) (dCLL log(LL/)) ?wo w²)] log (Lodlo((1/) ))
neju
(11)
n=2
Gradient complexity: xn plus m x IFO calls 2nS + 2mS,
0 (n+
SL22 42
nepEEddist (wilsst??ww,,,, w=)) ))
log
(12)
log (1/5)çLod)
This completes the proof.
B.4.2 Proof of Theorem 7
Before proving Theorem 7 state and prove following lemma that we will be using later.
28

---

Published in Transactions on Machine Learning Research (02/2023)
Lemma 12. Assume that each fo is L-g-smooth, the sectional curvature in X is lower bounded by Kmmin and we run Algorithm 11 with Oplion IT. For Ct, 1,,,, > O and suppose we have e. c++1(1+ 34 1/ 1,3 and ô(t)
Laf² 201+1517 > 0, then the iterute wi+ satisfies the bound
R R +
(tdLaf + cc4 0²
B| grad fww (()²+))1²==
de
where R,t1 = B[F(w[t + ct Expa " for 0 s
Proof. The proof is adapted from Zhang et al. 2016 Lemma 2). Denoting 4,+1 = grad I 22;) +p""" -uill
PT +w?" grad zs, it can be seen that E, ue+ = =- grad Fww PT
grad F F(T=)
Eicer || 1otts
Ei, grad / ; PT -w; (grad If f(ūi;;z)) guti)|?
+ do²
meth
-E, || E, A grad F(wf+>)
11= lutt + do²
2R, || R, A 11 + 2 ||grad F( We.. + do²
(1*) S 21, ||
2 w + 2 |grad F(w;" M( + do²
(1)
2 2L Exp (w ||= + 2||ggrad Fwv (2(_(+))] 1,:11 + do?
where ||a + b1l? < 2 ||a]] + 2 ||611 in (+) and E, || - E. A, E, || EE 112
BA, || in (**) and assumption that Si is L-g-smooth in (t). Taking full expectation we have
E 11 hutH I 21. Exp (w ||
(w;+t)
2 2|grrad F(uG+t) 1mntt + do².
(13)
For bounding the Lyapunov function R+ == E [(utt)) + c++1 (x need to bound on E (w((tt )1 Exp (wf+t)) First consider
E F (
E
F(u + (grad F(uet!), Exp (wit1)
+
L
Exp
Exp
w/-1
2
E F(w[+1) - 17 grad Flw + )|(u +
Inp
1100
1
2
13
E
F( n ||grad F(w
)|=
+
Lap
(2T.²
Exp )112 + 21 grad F(w + o2d)
2
- grad F(we+ + F(u L Exp (w + )|2 2 ddlnpo?
(14)
where we used the assumption that fi is L-g-hhooth implies that F is L-g-smooth in (*) and Exp w of and E. [oo grad F(w in (**). Using the trigonometric distance bound w w we we have,
E (w
Exp + ||= + < [| u. (wttt)/
Exp=? ( (ogg - -(Rxp uo (witt), Exp u (77)) weth
Exp (wi² | || + <ni ||uot1 2 + 2n(grad F(us+1), Exp with (w²)).
29

---

Published in Transactions on Machine Learning Research (02/2023)
Taking the expectation we have
E Exp io
(witt) l1 Exp (w, + y| <n lug 112 + 2n F(uf+)) Exp - ++ -
Exp
|| ビッ² u1 11 112 + 2n 233 Igrad (1 y11
B
Exp +
wpth (w |
2
< E (1 + 3m) Exp (w I|? + en² |2L |Exp (w )|| - grard F(ee (wx+1)) )|² + t
EE !/ grad fw ||
(1 20 2 + n Exp Exp (u + 22772 + 7) l|erad F(w + (dn)²
(15)
Putting
14 and 15 into R we have
R = [ + c++1 [Exp (wa+t) 1/
= c++1 (1 + 2(1) L2 + n3) Exp (wf + c+11 2017 + (/) Ilera c++Ldd1
+ +Ta²² 11) ||grad F F(w ||p + F(wtt() + 1,3 |Ep (w (w ||² +
2 dTnpp02
1
= =[ ) + (ct+1 (1 + 2(12² L² m) + L n²)) Exp (w
+ Ln²² + c++1 (2T + )) |grad F( + () dIn" + c+t(ddd)) 0²
= R R++1_
(LLn²
Lı²² + c+1 2g1 + / )) grad F(w; 2| M11 + ( ddd + cerssd?)) 0².
Rearranging, we get
(1 Lnp² att1 22g 1)) El grad F(w R2t1 ntt (allnf + ari((dr)) o²
from which we have
R RØ+1 R2+1
g I + c+ drp
E| grad F(u <
0².
(1) Lnj² - c (251² + b))
(Ln - c++1 (2Ç1² + 33)
We now give the proof of Theorem
30

---

Published in Transactions on Machine Learning Research (02/2023)
Proof. The proof is adapted from T mS
Zhang et al 2016 Theorems 2, 6 and Corollary 6). Let o, min, and
grad f(u(+1)
M2-1
1 - RRtt
( + cs dnp o²
+
dt
1=0
R
-R+t
( + c++1)) mdn?
0²
pn
Plwott P( + co
Expus (w) (ut+t)1 )1 11 Cm
Expas wy (w 19]
( L + cos) mdn?
+
o²
on + (2L + cos) mdn? 0²,
pn
(++) E F(
8n F(
8n
where 8, 2 8ns Ct I co is used in (+) and that w w wm w++1 and that Cm = 0, co 2 0 in (**).
Now, summing the gradient norm square over all the epochs and using F(w*) F(w²),
get
8-1m-1
E [F - F(w")] + ( + coS) dn² o²
Σ
E
grad f(w
||
<
T
on
==0
Choosing 3= TL21-0 /2 and solving recurrence relation e using m given by theorem as (Zhang et al. 2016 Theorem 2) one can get oo 2017 (e - 1). Substituting that in 8n 2 -,cic=z and finally using this we have
S-1 m-
Igrad f(wf+1)]
Hot E [F(W))) -F(w")] + Ln (2L+
(e - 1)()
Hg
S NoIna gou2
do²
VnS
v
Finally, putting the values of an 2/3, 1/2/10 1/10, v 1/2, and 0² can get that.
C2
mS log( (nSlog(1/8)53
n=
C3
S llgg( 1log1/88/3 18)
ne²
E Igradd )12 s
L2
E. [F(Tt)) - F(w")] + 2/2/311/2
1
+
1
dS dSlog(1/0)L3
nt/3g
nC1/2
ne²
LC1/2
ds Aolog(1 (0g(11))333
E. [F - F(w")]
+
nt/3g
n//222/262
Setting S / [CE[F("") (afaa)-F((aar F(w")] 2/2/, dlog(1/8)
we have
La
Lov dl (og((10))1)
10 F F(ww)
grad 1( s c4
(16)
116
The gradient complexity is given by
[(E(F(W0) - F(w*)] d dlog(1/8)
n2/3
LC ((
F F(w*)
5/3
S(n + 2m)
nn
(17)
Lo
30
dlog(1/0)
Lo
This completes the proof.
31

---

Published in Transactions on Machine Learning Research (02/2023)
B.4.3 Proof of Theorem 8
Proof. With the
values given
in the theorem
statement,
mSk l18)1
a²
Kn[6+ a Lrg (1/(1/
K 14
1/2
logt'
ont73
This implies that
3pann
3ne
El grad [1
_ R [F(W)) F(w"')]
1
dK[6+
n-3
18
LT
1/2
log(1/8));
112/3ç1/2
nç(/2
3nc
24 LT log(1/6)
E [F(W") F(w*))]
3n?e²
Using the Riemannian PL condition, have
24dK 1ooe:logg/////////
E [[( - -(w=)) rB[][grad (1 2 [F(w*) F(w")]
3n
Recursively applying the above for to K we have
E [F(w") F(w*)] + 8dKL log LB K
E [[((w*) fww)]] s 2
ni2²
2
+ SdK log(1 L/)
< 2
E [F(w") F(w²)]
Σ
n²2²
2
1=0
2 2 E [ [F((F F(w")] 16dK LT log(1/8){A
n²²²
("" F(1o')) dL.'" log( (168)2
Putting K log
there is a constant such that
dL log( log(1/5)Lg
n²eZE F(w0) F(ww)]
E [ [(x²)] S
log
n²c²
dLr² (og(2))g1/))))
Ignoring the log factors,
/dL log( (dLr>1og(1/00) (og(1/0)L3
- [ww)]] = E -
(18)
n²c2
Finally, the gradient complexity is given by,
= ((w") - [ww))]
18 (6+
Hg )
KS(n + 2m)= log
n-3 |L
n
dL log L3
1/
34
nT [F(w [
F(w*)]
< LT log
(19)
dL log (1
C Additional experiments and more experimental details for Section 6
Details the parameter configurations of DP-RSVRG, DP-RSGD, and DP-RGD. For DP- RGD, tune the clipping parameters from the set C 0.1, and the number of epochs from {10, 20, 30). For DP-RSGD, clipping parameter is chosen from C = 011, from {n, * 5, * 10, n * 20, n 30). For DP-RSVRG number of epochs is chosen from (5, 10) and set the frequency as m = n1/0 and full gradient clipping parameter C tuned from {1, 0.10.1] and variance reduced gradient clipping parameter C2 from 01, 0.01). For all three algorithms, we tune the learning rate from
and number of epochs
5}. In all our experiments, use geomstats (Miolane n = {5e 5 le 5e lee ......e" 5e le 1,2, ...
et al.
2020
2021
Myers al. 2022
32

---

Published in Transactions on Machine Learning Research (02/2023)
C.1 Details the the Fréchet mean of SPD matrices computation and the covariance descriptors
The Riemannian distance induced by the metric given by dist(Zı, Z2) |logm Z2 1/2,,, Z, Zn 1/2 Ile,
where Logm denotes matrix logarithm. the Fréchet mean is defined minwesrD(m) {F(W) Di= f(W; - |logm (ee dient. of is given in terms inverse Exponential map grad J(W,X;) Riemannian -2w Logmm w 1/11/ W 1/2) w///2 We take first two classes from PATHMNIST KKther et al. 2019 (ADI, adipose tissue; BACK, background).
SPD(m), the solution to following optimization problem:
Given points { 2n
gra-
-2Expw
Covariance descriptors. Let I E Rxxwxx3 denote RGB image with height and width Let d R - R be feature extractor of dimension k i.e. (x) is k-dimensional vector at each spatial coordinate x in the image's domain S. Given small 0, the covariance descriptor R, RRxxxx - SPD(k) associated with ø is defined as
(x()))x)) - ()(()) w/² + InII,
(T)
= S
XES
where μ = -S (x), and n.I ensures (I) SPD(K). Our experiments the private Fréchet
mean computation problem (Section 6.3 use the covariance descriptors with following feature vector:
(I) 2, I
2 + 1To arctan
where (Ir, v), intensities derivatives are denoted by I,, Iy, Isnn Iyn and f 10-6 Let denole convolution operation, then first and second order intensity derivatives computed as below,
+1 0
-1
+1 0 -1
I, =
+2
0
-2
I I+
+2 0
-2
4
46 0
12
++ 0
12
+1 0
-2 0
1
+1
+4
+6
+4 +1
+4
0
8 0
0 0
0
1
Igy = I 1
Is = II
+6 0
12 0 6
-2
8
-
12
-
-2
32
32
+4
8 0
0 0
+1 0 -2 0
+1 +4
+6
+4
+1
For RGB images, (x) is a 11-dimensional vector that makes R2 a 11
x SPD matrix.
C.2 Details on the private leading eigenvector computation problem
The problem of computing the leading eigenvector f(w;z,) = -" satisfics Riemannian PL condition (Zhang et al., 2016) while the problem is nonconvex in the Euclidean setting. Riemannian gradient of f is given by grad f(w; -2([4+1 wwz w.
sample covariance matrix is Σ w (z,z, )w) It has been shown that above problem
minwes- [(ww) Σ
33


Reviews:
[{"review_id": "8a8RLA6HLQ", "reviewer": "Reviewer_35Pm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I am not an expert in differential privacy, so I did not check the details of that section of the paper, but at a glance it seems to be a noteworthy contribution (although it seems not too different from the prior work of Han et al. (2022)).\n\nHowever, there are several weaknesses: (1) I have doubts that the sampling part of this paper is interesting/useful, and many of the claims are overstated; and (2) the paper is very poorly written. Although the DP part of the paper seems to have enough content to merit publication, I cannot recommend acceptance until these issues are fixed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Two main contributions are claimed. First, the authors propose two algorithms for sampling from a Gaussian on the tangent space of a Riemannian manifold: (1) construct an orthonormal basis at the tangent space and construct a random linear combination of this basis where the coefficients are drawn from a Euclidean Gaussian vector; (2) construct the Gaussian at the tangent space of a fixed reference point and isometrically transport this random variable to the desired tangent space. Second, the authors provide a differential privacy analysis of a variance reduced Riemannian optimization algorithm.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In pg. 2, in the paragraph on Riemannian geometry: the description/notation of parallel transport is not precise; parallel transport depends on the choice of curve joining $w_1$ to $w_2$, so this should be specified.\n\nClaims 1-2 are trivial; I do not understand why there is so much discussion devoted to this. Also, in Claim 2, this is not an inequality; this is an equality. I don’t think the authors should claim this is “much stronger” than the results of Han et al. (2022) when there is hardly anything that is proved (it seems that the purpose of this section is to point out a mistake of Han et al. (2022) but that can be a short note in the appendix rather than an entire section of the paper).\n\nIt is an overstatement to say that the sampling scheme introduced in this paper avoids “computationally expensive MCMC” – no one would suggest using MCMC to sample from a simple Gaussian distribution, which is what this paper tries to do. Please weaken the claims.\n\nI have serious doubts that the implicit basis construction is useful. The authors claim that finding an orthonormal basis of the tangent space is expensive, but this is only because they use naive Gram–Schmidt orthonormalization. Note that in order to carry out the implicit basis scheme, one needs an explicit description of parallel transport, which is difficult in general. In the cases when parallel transport is explicit, it is also easy to find an explicit orthonormal basis for the metric; it seems that the authors simply have not tried. For example, for the affine-invariant metric, at the point X one can check that $\\sqrt{\\lambda_i \\lambda_j/2} \\\\, (u_i u_j^\\top + u_j u_i^\\top)$ is an orthonormal basis for the tangent space, where $X = \\sum_{i=1}^d \\lambda_i u_i u_i^\\top$ is the eigendecomposition; note that computing this is no harder than the matrix operations needed to compute the parallel transport. Similarly it seems to me that orthonormal bases can be constructed for the other manifolds listed in this paper, and the authors must do so in order to have a fair comparison of their method.\n\nThe word “hypersphere” should be replaced with the more customary term “sphere”.\n\nThere are many typos, of which I list just a few. In general, this submission would benefit from a thorough proofreading of the grammar. (In particular, I’d like to see typos corrected besides the ones I list below.)\n- Pg. 2, in paragraph about DP-SVRG: “expanding suite…” should say “expanding the suite…”\n- Top of pg. 3: “gradient of real valued” -> “gradient of a real-valued”\n- Pg. 3: The second sentence of the paragraph on function classes is a run-on sentence (and in fact many of the sentences in the preliminaries section are run-on)\n- Pg. 3, definition of geodesic strong convexity: should say “if for all w, w’...”\n- Pg. 3, definition of curvature constant: perhaps you mean to take the absolute value of $\\kappa_{\\min}$?\n- Pg. 3, differential privacy: the definition of the moment of the mechanism is missing an expectation symbol\n- Bottom of pg. 3, “The Riemannian gradient however grad F(w)” is improper English\n- Bottom of pg. 3, the density $p(\\nu)$ is written with $\\mu$ instead of $\\nu$\n- Defn. 1, the pushforward measure should be $\\phi_*^{\\mathscr B} \\lambda$ (the $\\lambda$ is missing)\n- Rmk. 1, “basis” -> “bases”\n- Why does the notation change from $p_w(\\xi)$ to $p_\\xi(\\nu)$ from Defn. 2 to Claim 1?\n- Claim 3 uses $\\sigma_1^2$ which should be $\\sigma^2$\n- Pg. 8, clip operation should be defined with min not max\n- Section B.1, Sampling on hyperbolic spaces: Sentence beginning with “tangent space” is not capitalized\n- Pg. 21, “it’s” -> “its”", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9F05E7iVXr", "reviewer": "Reviewer_3N95", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nI believe the authors had a clever idea - parallel transporting instead of sampling a non-isotropic Gaussian is indeed new. \n\nWeaknesses \n\n1. The paper in its current state is really difficult to read. In particular, I believe much of the mathematics regarding Riemannian geometry needs to be made much more precise and clear, as I had a lot of trouble trying to parse even the basic ideas the authors are proposing. \n2. The authors did not make a careful comparison on the computational cost of sampling a tangent Gaussian vs. their proposed method. In its current state, it is unclear whether or not their method is actually faster. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors introduced a new method for adding noise to a Riemannian optimization procedure, where they avoided directly sampling a non-isotropic Gaussian, but instead using parallel transporting it to a new tangent space to be used instead. ", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "# On the Clarity of Specifying a Coordinate System \n\nI have some confusion regarding section 2-3, and I would like the authors to respond to my detailed concerns below before I can comment on the contributions. \n\nI believe the root of all confusion began in section 2, where the authors did not specify whether they are working with an intrinsic coordinate system on the manifold $\\mathcal{M}$, which induces a **compatible** coordinate (basis) for the tangent space $T_w \\mathcal{M}$. This is not helped by the applications in section 4, where most of the matrix manifolds were described extrinsically using an embedding into a larger Euclidean manifold. \n\n**Question 1** Which coordinate system is the author working with in section 3? \n\nIf the authors are indeed working with the standard approach of using a coordinate system given by the manifold to begin with, then the tangent Gaussian definition can be written exactly using the induced tangent coordinates, where $\\xi \\in \\mathbb{R}^d$ and the density is the same as Euclidean $\\mathcal{N}( \\mu, \\sigma^2 g^{-1} )$ where $g$ is the Riemannian metric in this coordinate. \n\n**Question 2** Then what does it mean in Claim 1 that \"$\\vec{\\xi}$ is in its coordinate in $\\mathscr{B}$\"? \n\nIf the authors meant that a change of coordinate system is suggested for the manifold, then this needs to be clearly specified. \n\n**Question 3** Is what the author proposing sampling a standard Gaussian in a specific tangent space, and parallel transporting it to a new one? \n\n# On the Computational Cost Comparison \n\nI understand that the authors would like avoid computing a matrix vector product form of $g^{-1/2} \\xi$ where $\\xi$ is a standard normal and $g$ is the Riemannian metric. And instead the authors would like sample a standard Gaussian in the tangent space, convert it back to a coordinate system (either intrinsic or extrinsic) where parallel transport can be computed after. \n\nMy questions are multiple fold: \n**Question 4** Is it clear that on the manifolds the authors suggested, that this matrix vector product $g^{-1/2} \\xi$ is difficult to compute? Often the metric $g$ has a lot of structure and computing its inverse or even inverse square root entry-wise can be quite fast, in which case matrix vector product can be computed quite quickly without a memory constraint. This type of computation methods is quite well studied in second order optimization methods such as natural gradient descent and K-FAC. \n\n**Question 5** Suppose the authors can sample a standard Gaussian in the normal coordinates (where $g_{ij}(0) = \\delta_{ij}$), how do the authors intend on converting this back into a coordinate system where parallel transport is known? Or do authors require that the manifold must have at least one point where the Riemannian tangent space has a trivial structure, such as SPD manifold at $I$? \n\n**Question 6** Now that we have a tangent vector, can the authors comment on the actual cost of computing this parallel transport? For example, for the affine-invariant metric, the parallel transport formula is \n$ P^{X,Y} (\\eta) = (YX^{-1})^{1/2} \\eta ((YX^{-1})^{1/2})^* $, \nis this really cheaper given all the matrix inversions and square roots that needs computing? I believe this is at best unclear to me at the moment. \n\nI believe this is a more serious problem whenever parallel transport is not available in closed form, which is the case for at least two of the examples given by the authors, but also generally the case for most manifolds. \n\n# On Alternative Methods \n\nI also have a thought on a high level on whether this method is an overkill. Firstly, is it really necessary to compute exactly a standard normal to have the desired privacy benefits, or is it just easier to analyze? I suspect that the analysis will be harder but normals are often not necessary. \n\nSecondly, is there no other methods to sample a standard Gaussian? A projection for example onto the tangent space of a hypersphere is probably the most direct method to sample a Gaussian, I imagine there are likely other similar approaches that doesn't need parallel transporting from a fixed point to the entire manifold. The current method feels extremely complex for a basic task. \n\n# On Additional Precision and Clarity \n\nWhile less important, I believe the paper can still improve significantly in its mathematical clarity. Here are several suggestions beyond the ones I already described above regarding specifying a coordinate. \n\n - When the parallel transport is introduced, the authors did not specify the curve, which is usually the geodesic between two points. However, this geodesic is not always unique, in which case the authors needs to either rule out or handle the edge case. \n - Is it necessary to define sectional curvature this way? Either the reader do not already know Gauss curvature either or they do and it is not necessary. \n - When the Riemannian gradient is introduced, the authors used the notation $\\langle \\nabla f(w), v \\rangle_2$ for the Euclidean inner product. This is very unclear as I believe the authors are suggesting this inner product is in the embedding Euclidean space, as this cannot be true in coordinates. \n - The exponential map takes two inputs (point and tangent vector), the authors should specify which part is invertible. \n - dist is undefined \n - After \"there exists $\\tau > 0$\" there needs to be a comma or colon separating two expressions \n - $\\kappa_{min}$ is undefined. And in which sense is this a curvature constant? \n - I believe $\\mathcal{R}$ is a map from $\\mathcal{Z}^n$ instead of $\\mathcal{Z}$ \n - What do the notations $\\log_{o \\sim \\mathcal{R}(Z)}$ and $p( \\mathcal{R}(Z) = o )$ mean? \n - The definition of $\\mathcal{R}_i$ is unclear \n - The first introduction of $p(v) \\propto \\exp( -\\| \\xi - \\mu \\|_w^2 / 2\\sigma^2  )$ there is no $v$ on the right hand side \n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "JfFbep9h3X", "reviewer": "Reviewer_1rhr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. Improved sampling procedure is way more faster than existing ones.\n2. Both convergence analyses and experiments are provided for proposed algorithms.\n\nWeakness\n1. I am not familiar with Riemannian optimization, but I feel it would be better to provide a more intuitive explanation on comparison between convergence bounds of the original version and the Riemannian optimization version.\n ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposed a new noise sampling procedure for differentially private Riemannian optimization, the proposed sampling is more efficient than existing sampling procedures. In addition, the paper extends differentially private stochastic variance reduced gradient descent (DP-SVRG) to Riemannian optimization, and provided convergence analyses and experiments. \n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Maybe I missed it but could authors provide some intuition on the difference of convergence rate between Riemannian version of algorithms and the original versions?", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1gZXjdcsVU", "reviewer": "Reviewer_EhVU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I think it is a fairly solid paper. However, it is not quite yet ready at this point: there is a correctness issue or two and things that need to be clarified, plus Section 5 needs a lot of work. \n\n**Strengths:**\n\n-Interesting problem \n\n-*Major speedup benefits of their sampling procedure* vs. the approach of Han et al. (2022) = main strength in my opinion \n\n-DP-RSVRG seems to offer improved practical performance over existing methods in the experiments \n\n-Fairly clear and well-written for the most part \n\n-*Most* results appear to be mostly correct (although I did not check the proofs carefully) \n\n**Weaknesses [and requested changes]**\n\nAt a high level, the main weak spot of the submission in my opinion is Section 5. The algorithm doesn't seem to offer any theoretical benefits over the existing SGD algorithm, which is also simpler. Additionally, there is a seemingly unsupported claim about improved utility bounds: the bounds in Section 5 seem to essentially match the bounds of the prior work (or even be slightly worse due to dependence on the condition number, in the strongly convex/PL case). Third, I am not sure about the correctness of the privacy claim. In more detail, the weaknesses are: \n \n*Abstract:*  \n\n-Would be great to start out with a couple of sentences introducing and *motivating* the problem of DP riemannian optimization (at a high level) to make the paper more accessible \n\n*Intro:* \n\n-\"key step\" -> \"common approach\" seems more apt \n\n-Point to/reference your \"side result\" of improved utility given in the main body..I think it is Claim 2 right? \n\n*Preliminaries*: It would be helpful if you could italicize or underline the key terminology/definitions.\n\n-exponential function definition seems incorrect: there is a $\\xi$ mentioned that does not appear in the definition..should be $v$ I think?\n\n-\"totally normal\" is never defined. Also, \"curvature is $\\mathcal{W}$\" is never defined \n\n-parentheses needed in tahnh \n\n-inconsistency with $\\nu$ and $\\xi$ in definition of Han et al's Gaussian distribution \n\n*Section 3:* \n\n-Is Claim 2 trivial or non-trivial given Han et al.'s Claim 1? I'm confused because if Han et al proved Claim 1, and Claim 2 is a direct consequence of Claim 1, then it is surprising that Han et al did not get as tight a bound on the variance as you. \n\n-Also, why does Claim 2 not allow you to get improved utility bounds in Section 5? \n\n-Claim 3: $\\sigma^2$ is never defined! \n\n*Section 4:* \n\n-Writing: the transition into \"Basis construction\" is not smooth. \n\n-Why can't steps 2 and 3 of Algorithm 1 be performed in stochastic optimization settings?\n\n-analysis of Algorithm 2: Please explain (or even state as a lemma/claim, since it is pretty important) why it is a valid sampling scheme, i.e. why the output has the desired Gaussian distribution. I did not see any discussion of this\n\n-Any conceptual/theoretical justification for why Algorithm 2 leads to speedup vs. Algorithm 1? \n\n-Writing: transition into Subsection 4.1 is not smooth. Complete shift in gears without any warning or explanation of where/why the reader is being led. \n\n-Writing: transition into section 5 is not smooth. For example, you could explain that next, you will use your Gaussian mechanism as a primitive to build a new variance-reduced DP Riemmanian optimization algorithm. \n\n *Section 5.1*\n\n-first paragraph: first sentences don't really capture the essence of variance-reduction (VR). Also, the claim that VR methods require less gradient calls to achieve the same convergence rates as full gradient descent does not seem correct in general (or is not clearly explained): for example, in nonconvex optimization, the optimal stochastic VR methods converge at rate $1/T^{3}$, whereas gradient descent converges at rate $1/T^2$. Please clarify. \n\n-Would help to remind the reader of what the SVRG algorithm looks like before presenting Algorithm 3. Also would help to describe DP-R(S)SGD and compare it (conceptually) vs. Algorithm 3.   \n\n-Alg 3: no noise added in line 4! Not clear if/how you can get DP without noise there. Thus, I am *unsure about the correctness of Claim 6*. \n\n-Equation 2: (Why) can you decompose $\\sigma^2$ in this way in the presence of the PT operator? \n\n-high-level explanation for privacy proof framework is lacking. It seems you essentially rely on privacy of the Gaussian mechanism, privacy amplification by subsampling, and strong composition, right? Please explain why then you use the less transparent moments bounding approach instead. \n\n-Notations with $\\mathcal{K}$ in Claim 4 do not seem to be defined anywhere! \n\n-Claim 6: what choice of $\\sigma^2$ do you need? \n\n-Was there any challenge in analyzing Algorithm 3? Seems to me like it would have been trivial in light of the DP-SVRG and DP-RSGD analyses. \n\n *Section 5.2* \n\n-I don't see convex loss covered; so why the parentheses around (strong)?\n\n-Theorem 8: units/scaling are wrong in utility bound. Should have some dependence on $F(w_0) - F^*$ I think. \n\n-Discussion: why include the strongly convex result at all if the PL bound is better and attained under weaker assumptions? \n\n-Discussion: Is there any theoretical benefit of Alg 3 over DP-RSGD? Gradient complexity is higher you say, which is *very strange/surprising* and should be explained. In the Euclidean case, (DP) SVRG has lower gradient complexity than (DP) SGD. Also utility bound of Alg 3 seems slightly inferior to DP-RSGD bound due to dependence on the condition number (ignoring log factors)? \n\n\n\n\n ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies differentially private (DP) optimization on Riemmanian manifolds. They propose a new faster method of sampling from the tangent Gaussian distribution. They analyze the privacy and utility of a Riemmanian extension of DP-SVRG. Numerical experiments show that their proposed approaches offer benefits over existing methods. ", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above. ", "broader_impact_concerns": "None. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is not an easy case. Two reviewers are leaning towards accept, one reviewer is leaning toward reject.
The main result (sampling from the tangent space) seems to be rather straightforward, but it improves over a previous work, so this is a simple and self-consistent result, and all reviewers like it. However,  a lot of work has been invested into the theoretical study of the DP-RSVG method, which is very technical, and it is not clear if the techniques used are novel, or are just the compilation of the previous results. Moreover, after the revision (stronger baselines for sampling), it looks like two different, unconnected contributions, and the DP part can simply be moved into another application. The title, however, suggest another focus: improving DP Riemannian optimization. 
Thus, the results are good, but the title of the paper has to be fixed, as well as the necessity of the DP RO part completely is unclear. 
At least, sampling has to be mentioned in the title in one way or another.
Another weak point are the numerics for the privacy guarantees. They are given on small toy examples. 
To summarize, in the minor revision the following suggestions can be addressed:
1) The topic/structure of the paper regarding two different, not very well connected contribution. The strongest one is the sampling part, not the very technical DP-RO part
2) Numerical experiments on the DP-RO part look too simple.
3) In the text there are still misprints that need to be fixed.
 
Decision: Accept (poster)