Sampling in Constrained Domains with Orthogonal-Space Variational Gradient Descent
Authors: Ruqi Zhang
qiang liu
Xin T. Tong
Venue: NeurIPS 2022 Accept (2022)

Abstract: Sampling methods, as important inference and learning techniques, are typically designed for unconstrained domains. However, constraints are ubiquitous in machine learning problems, such as those on safety, fairness, robustness, and many other properties that must be satisfied to apply sampling results in real-life applications. Enforcing these constraints often leads to implicitly-defined manifolds, making efficient sampling with constraints very challenging. In this paper, we propose a new variational framework with a designed orthogonal-space gradient flow (O-Gradient) for sampling on a manifold $\mathcal{G}_0$ defined by general equality constraints. O-Gradient decomposes the gradient into two parts: one decreases the distance to $\mathcal{G}_0$ and the other decreases the KL divergence in the orthogonal space. While most existing manifold sampling methods require initialization on $\mathcal{G}_0$, O-Gradient does not require such prior knowledge. We prove that O-Gradient converges to the target constrained distribution with rate $\widetilde{O}(1/\text{the number of iterations})$ under mild conditions. Our proof relies on a new Stein characterization of conditional measure which could be of independent interest. We implement O-Gradient through both Langevin dynamics and Stein variational gradient descent and demonstrate its effectiveness in various experiments, including Bayesian deep neural networks.

Sampling in Constrained Domains with Orthogonal-Space Variational Gradient Descent
Rugi Zhang
Qiang Liu Department of Computer Science University of Texas at Austin lqianggcs. texas. edu
Department of Computer Science
Purdue University rugizopurdue edu
Xin T. Tong
Department of Mathematics National University of Singapore mattxin@nus edu. sg
Abstract
Sampling methods, as important inference and learning techniques, are typically de- signed for unconstrained domains. However, constraints are ubiquitous in machine learning problems, such as those on safety, fairness, robustness, and many other properties that must be satisfied to apply sampling results in real-life applications. Enforcing these constraints often leads implicitly-defined manifolds, making efficient sampling with constraints very challenging. In this paper, propose a new variational framework with designed orthogonal Gradient) for sampling manifold Go defined by general equality constraints. O-Gradient decomposes the gradient into two parts: one decreases the distance Go and the other decreases the KL divergence in the orthogonal space. While most existing manifold sampling methods require initialization on Go, O-Gradient does not require such prior knowledge. We prove that O-Gradient converges to the target constrained distribution with rate ((1 /te number of iterations) under mild conditions. Our proof relies on new Stein characterization of conditional measure which could be of independent interest. We implement O- D-Grrdieet through both Langevin dynamics and Stein variational gradient descent and demonstrate its effectiveness various experiments, including Bayesian deep neural networks.
gradient flow (O-
1 Introduction
Sampling methods, such as Markov chain Monte Carlo (MCMC) [[] and Stein variational gradi- ent descent (SVGD)
have been widely used for getting samples from approximating intractable distributions in machine learning (ML) problems, such as estimating Bayesian neural network posteriors 38), generating new images B3J and training energy energy-based based models [5)] While being powerful, most sampling methods usually can only be used in unconstrained domains or some special geometric spaces. This greatly limits the application of sampling to many real-life tasks.
P3 p
We consider sampling from a distribution π with an equality constraint g(x) 0 where g : Rdd - TR. general differentiable function. The domain this case the level set Go {a Rd g(x) = 0} which is submanifold in Rdd We do not require additional information about Gu, such explicit parameterization or known in-domain points, which is in contrast, often demanded by previous The problem defined above includes many MI applications, such as disease
methods 35 2 19
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

n(x)
m(x)
n(x)
g(x) 0
g(x)
g(x)
(a) O-Gradient
(b) O Langevin
(c) O-SVGD
Figure I: Visualization of our methods. (a) O-Gradient v is formed by by which follows Vg. and which is perpendicular to Vg. (b)-(c Applying O-Gradient Langevin dynamics and SVGD. Both methods can approach the manifold and sample on it.
diagnosis with logic rules constraint, policymaking with fairness constraint for different demographic subgroups, and autonomous driving with robustness constraint to unseen scenarios.
In this paper, we propose new variational framework which transforms the above constrained sampling problem into constrained functional minimization problem. A special gradient flow, denoted orthogonal-space gradient flow (O-Gradient), is developed to minimize the objective. As illustrated in Figure Ta, the direction of O-Gradient v can be decomposed into two parts: the first part o4 drives the sampler towards the manifold Go following Vg and keeps on Go once arrived; the second part makes the sampler explore Go following the density π (z)) We prove the convergence of O- O-Gradient in the continuous-time mean-field limit. O-Gradient can be applied both Langevin dynamics and SVGD, resulting in O-Langevin and O-SVGD respectively. As shown in Figure | D&c. both methods can converge to the target distribution on the manifold. In particular, O-Langevin converges following noisy trajectory while O-SVGD converges smoothly. similar to their standard unconstrained counterparts. We empirically demonstrate the sampling performance of O-Langevin and O-S D-DVGD across different constrained ML problems. We summarize our contributions follows:
We reformulate the hard-constrained sampling problem into a functional optimization problem and derive special gradient flow, O-Gradient, to obtain the solution.
We prove that O-Gradient converges the target constrained distribution with rate ( /the number of iterations) under mild conditions. Our proof technique includes Stein characterization of conditional measure which could be of independent interest.
We implement O-Gradient through both Langevin dynamics and SVGD and demonstrate its effectiveness in various experiments, including constrained synthetic distribution, income classification with fairness constraint, loan classification with logic rules and image classification with robust Bayesian deep neural networks.
Related Work
Sampling Explicitly Defined Manifolds Manifolds with special shapes, such as geometric or physics structures, can sometimes be explicitly parameterized in lower dimension spaces. For example, torus embedded in R can be explicitly defined in two dimensions using polar coordinates. Variants of classical methods have been developed to sample on such manifolds, including rejection sampling (6), Langevin dynamics [35)] Hamiltonian Monte Carlo (HMC) B and Riemannian
manifold HMC [16. 28]. However, explicit parameterization is only applicable to a few special cases and cannot used for general machine learning problems. contrast to this line of work, our method is able to work with more general manifolds defined in the original domain Rdd.
Sampling on Implicitly Defined Manifolds Many common applications are not endowed with
simple manifolds, such molecular dynamics [17. matrix factorization [27] and free energy calculations K4 Motivated by these applications, sampling methods on implicitly defined manifolds have been developed. Brubaker et al. 2 has proposed a family of constrained MCMC methods by applying Lagrangian mechanics to Hamiltonian dynamics. Zappa et al. [37 has introduced
constrained Metropolis-Hastinng (MH) with reverse projection check to ensure the reversibility.

---

Later, this method has been extended to HMC [9 and multiple projections 120] However, the implementation and analysis of these methods often assume the algorithm starts on the manifold and never leaves it, requiring prior known points on the manifold and expensive projection subroutines, such as Newton's s method 37 18 20 or a long time ordinary differential equation (ODE) [39 31 14]. In contrast, our method works with distributions supported on the ambient space and thus gets rid of the above strong assumptions, leading to a much faster update per iteration. This makes our method especially suitable for complex ML models such deep neural networks.
Sampling with Moment Constraint Recently, sampling with general moment constraint, such as [g] S O where q is the approximated distribution, has been studied (25]. However, this type of constraint can not guarantee every sample to satisfy g(x) From technical view, the target distribution with a moment constraint is usually not singular w.r.t π, so the problem is conceptually less challenging compared the problem considered in this work.
3 Preliminaries
Variational Framework We review the derivation of Langevin dynamics and SVGD from unified variational framework. The variational approach frames the problem of sampling into KI. divergence minimization problem: minger (T.(q T) where P is the space of probability measures. We start from an initial distribution go and an initial point zo ~ qo. and update z; following dr, = vi ( dt,, where uy: I2d + Rd is a velocity field at time Then the density q: of x3 follows Fokker- Planckk equation: dq:/ /t = V (vig)), and the KL divergence decreases with the following rate [2
d (g. σ) E. [Aru] E.g [(5T 8q.) [e),
dt
where (Z)( = Sn (x)TT()))))))))))))))))))) v(x) + V v(z) is the Stein operator, and 8p V log is the score function of the distribution p. The optimal o is obtained by solving an optimization in Hilbert space H.
max R. [(+ - 8qe Tm) vEH
||
The above objective makes sure that 82 decreases the KL divergence as fast as possible.
Langevin Dynamics and SVGD Algorithms Both Langevin dynamics and SVGD can be derived from this variational framework by taking to different spaces. Taking H to be Lgg the velocity field becomes vx(-) (+, (- which can be simulated by Langevin dynamics dz, sa (It)dt + dW, with We being a standard Browninan motion. After discretization with step size n > the update step of Langevin dynamics is I++1 = Iz Langevin(x:).. where
Langevin(2:) = V log T (xx) + 22 ~NN(0,
(3)
Taking H. to be the reproducing kernel Hilbert space (RKHS) of continuously differentiable kemell k: Rdd x Rdd + R. the velocity field becomes (-) = Enagg (((.,))8=(()) + (.k,(. After discretization, the update step of SVGD for particles {xx J.2 is 21,41 Fiet + n ( for = 1,...,,, n, where 1j is step size and
SVGD
(a.a.TH)) log (1g)(1))) V,,,, 2(1
(4)
4 Main Method
In this section, we formulate the constrained sampling problem into a constrained optimization through the variational lens in Section 4.1 and introduce a new gradient flow to solve the problem in Section 4.2 We apply this general framework to Langevin dynamics and SVGD, leading to two
practical algorithms in Section 4
4.1 Constrained Variational Optimization
Recall that our goal is to draw samples according to the probability of m, but restricted to a low dimensional manifold specified by an equality: Go == {x Rd: g(x) = 0}. Similar to the standard
3

---

variational framework in Section 5 the space probability measures:
we can formulate the problem into a constrained optimization in
min K T), s.t. <(g(x)= - =. gEp
However, this problem is in general ill- ill-posed. To see that, when q satisfies the constraint, g will be singular w.r.t π, so both de and (L(g) x) are not defined. Although the problem ill-posed, we are actually still able to derive a KI-gradient flow to solve the problem by considering q supported on Rd. The intuition the derivation that, in addition to minimizing the objective as in Eq. ( the velocity filed i2 should also push g towards Go to satisfy the constraint. Surprisingly, the distribution q: following such a gradient flow indeed converges to the target distribution on the manifold. We will focus on the derivation of the gradient flow here and leave its rigorous justification in Section
de
4.2 Orthogonal-Space Gradient Flow (O-Gradient)
As mentioned above, besides maximizing the decay of KL( || r), the velocity field et also needs to drive towards the manifold satisfying g(x) O. particular, we add 2 a requirement that the value of g(x) is driven towards 0 with a given rate:
= arg max Eg [(sx - Sqz To] NEW
2 |1 s.t. Vg(x) -g(z)==((((a))
(5)
where (2r) is an increasing odd function. To see the effect of the constraint term, we consider three cases:
When ((x) > 0, then (V)c)))V)))))))) = -+(((=)) > 0 which ensures that will make decrease strictly.
When g(x) < 0, then (x) Vg(<>) = - ((((()) < 0 which ensures that o will make increase strictly.
When g(x) then (x) Vg(x)= (x)(()) which ensures x stay on the manifold Go.
We choose (xx) = osiin(())>= with a > 0 and 3 E (0, 1] in this paper because it one of the simplest functions that satisfy the requirements and we found it works well in theory and practice.
In summary, the objective function in Eq. (5) is the same as Eq. framework while the constraint ensures that Us pushes di towards the manifold and keeps it stay. It is
the standard variational
easy to see that the solution of the above problem can be decomposed as ee = 02 + i, where
(x) = - VV(()))
(6)
V/((2)12
We use fig to denote (pointwise) orthogonality: f(x) gxx) = 0, Vo E Rdd. Note that by is parallel to Vg and the remaining is to determine eu. Note that Ta can be represented as a projection of an arbitrary function u to the orthogonal space of Vg:
U1 D(x)u(x), where D(x) = I Vg(z)
The projection operator D makes sure that e L holds for any u, of which the optimal value can get by maximizing the unconstrained objective in Eq. 2
max Feg, (s== sg.) T (oy + =1)) 1| = max Fyg [(D(s sq.)) )) | T1
(8)
a
The optimal solution of depends on the choice of space H. which we discuss in Section
Overall, we obtain the velocity field v by first formulating constrained optimization and then trans- forming it into an unconstrained optimization via orthogonal decomposition. We call i. Orthogonal- Space Gradient Flow (O-Gradient) and it drives qe to the target distribution only with the knowledge of Vg. requiring no explicit representation of the manifold Go.

---

4.3 Practical Algorithms
After deriving O-Gradient for general Hilbert spaces H. we explain how implement using SVGD and Langevin dynamics. The resulting O-SVGD and O-Langevin are outlined in Algorithm [ At high level, our algorithms keep the original SVGD or Langevin dynamics movement in the directions perpendicular to Vg, while pushing the density towards 9o along the Vg direction.
O-SVGD We apply O-Gradient to SVGD first since it is fairly straightforward. Recall that by can be obtained using Eq. 16. We solve Eq. & to get U1 through the following lemma.
Lemma 4.1. When H is an RKHS with kernel k: R& x R R. solution to Eq.
8 is
Du(x) = Ey (K1 (z, 8) (1) + Vy ki (x. with the orthogonal-sper space kernel k (1( = k(x, (()) Here ky: R x R + Raxd is matrix valued, and Vy ki = E, 0g, k (z.
Then the combined velocity is obtained using the original SVGD with the kernel kj.
Uy (x)) (x))) + / Ti (z. u)s (v) +
/ V. (KI ())
Numerically, we iteratively update set of n particles { C RA, such that its empirical
distribution > 08,,./n /n. is an approximation of qi in proper sense when step size - 0 and particle size n + +00. Similar to the update of standard SVGD Eq. 4 the update O-SVGD T1,++1 Fi, 7 (uv(3ss,) SVGDR, (2H,z)) where
a
SVGD (I))))
Σ k (3,0, aga log ( + ki
It is worth noting that SVGD&, identical Eq. but with kernel hn rather than k.
O-Langevin The Langevin implementation requires some additional derivation, First of all, with
H D2 we can show that the optimal velocity field is vt(x) Φ(x) - D(x)s (z) where Φ(z)
(x) + (z)) This leads to a density flow
d
di (x)=) V (z()))(((() + V (D())V
(10)
Next, we try to design stochastic differential equation (SDE) of which the Fokker-Plank equation (FPE) is identical to Eq. (00. The result is given by the following:
Theorem 4.2, Consider a vector field r(x) = V Dxx), or its component-wise formulation r;(x) = Ej Ony (i) where Ij denotes the jth dimension of x. Consider the SDE
dx, = (b(xx) + r(xx))dtt + (2:(x:)dW
(11)
with = D(<)s) then its FPE is identical to Eq. TOp. Moreover i) the value g(x)) has deterministic decay (z,) = - (xx,;; ii) for any f with V VfLVg = 0, the generator of at
satisfies the Langevin equation: de [E(((x)) = =x]| == Lf(x)= f (z)s=(x) + (z)
It is worth pointing out that if g(zn) O, then g(xx) O. that is, always stays on Go- In this case, Eq. ( degenerates to manifold Langevin dynamics studied in previous work 9 B5J. However, our SDE does not have this requirement since it is still well well-defined off Go. This is especially useful for numerical implementations, leading to fast algorithm without expensive projection steps.
Similar to the standard Langevin dynamics update in Eq.
B
the update rule of O-Langevin is
It-1 = It + + my (xx) + Langevin (24) where
Langevin [ini_____a_ (ar,) = 1y (a)))) mr(x)) + Do, & ~(,00
(12)
Theoretical Analysis
We theoretically justify the convergence of O-Gradient in this section. To do so, we first describe the target measure as a conditioned measure Πl. then derive its associated orthogonal-space Fisher divergence, and finally prove that O-Gradient converges to lIg.
5

---

Algorithm 1 O-SVGD and O-Langevin.
given: Initialization { for O-SVGD and To for O-Langevin, step size 17. loop
compute (y(x)) = (((()) Vg(ar and the projection operator D(x) = I Va(=)Vo(a) 1 ()(=))|
[[Va(z)]*
if O update f K by Eq. (9)
if O-Langevin, update 24 by Eq. 2
end doop
5.1 Conditioned measure and its Stein characterization
First of all, conditioning on a zero-mett wew.mmmaauut set is a challenging concept. Assume we have distribution
Il with density и. Let A be set with (A) + O, then (A) = I[AA
A) = 0, this definition is ill-posed Instead, a standard way to define a conditioned measure on a zero measure
((BAA) However, if (T(A)
set is using disintegration theorem [5. Let [ = II( (g(2)) 2) be the measure such that
Enlf(=)] E5 (f Vf.
(13)
where II is the pushforward measure of II under g. It is worth noting that HI not the measure with Hausdorff density x on Go- Instead, under regularity conditions, Ho can also be defined through Hausdorff density (<z)/|Vg(x)) on 9o, see Lemma 6.4. of [32].
One can also avoid this rather abstract definition, and consider an alternative definition which is more intuitive and Bayesian. Suppose we observe = g(x)) + of, where & ~ (0, 1). Under prior x: n, the posterior 22 (z) x (2x) exp(-Ie g(x) 2/2o²) Then we can show that 11, is the (weak) limit of - as σ + O, moreover, satisfies a Stein characterization of conditional measure. We need some regularity assumptions to state our results.
Definition 5.1. A density q is g-regular if there is a constant such that for small enough 1) > 0,
[Bg=Arto.))l (== (5)/==+++))))))) - Lmp
Vz.
(14)
Note that Eq. (14 holds if q is Lipschitz function. Moreover, while Definition 5. requires Eq. (44 to hold for all z, in practice we only concern Ho. thus only need the equation to hold for near 0.
1 Proposition 5.2. Suppose x is g-regular. Then the weak limit of = x T (x) exp( 27 (g(x)) =))² as 7 + concentrates on G2 and satisfies Eq. 13p. Moreover, for each z,
EnI [A+ = 0, VøLVg.
(15)
The first part of Proposition 5.2 also provides us with way to sample 11,, we can sample sequence of distribution π Tyk.= with Th + 0. However, this method involves double loops and is usually much more expensive than single-loop algorithms.
The second part of Proposition 5.2 can be used to formulate an orthogonal -spcce Stein equation. Specificallyy, given a q concentrated on G., consider checking whether [A, is zero for @ E H = {Φ= Φ Vg). which is a necessary condition for = IT.. Notably, this equation is well defined in d without using any parameterizatton of G..
Compared with the standard Stein equation, we add an additional restriction that & E Hi. We argue such restriction is actually very natural. To see that, we note II, is concentrated on 9z, so we should check the Stein equation with vector field that "live" only on Gz. namely the tangent bundle TG.. Notably, if d(x) E TG., then ((x) Vg(x), therefore is natural to consider H.,
5.2 Orthogonal-Space SSpace Fisher divergence
divergeidnee
Next we consider how generalize Fisher divergence for constrained sampling. Since the orthogonal- space Stein equation can only discern discrepancy in M.1 it is natural to consider an aiooognal--se -space Fisher divergence
Fi (g(gxx) == ||D(s, s. 11.
(16)
6

---

where D is the H. -Poojejcction operator defined pointwisely using Eq. 7 Its easy to see F1 is well defined for a density q on R.. But it remains unclear whether it can be used measure the distance between q and !!
To answer this question, we need some form of strong convexity conditions. Recall that in the unconstrained case, such conditions can be characterized by Poincaré inequalities (PI) when H. is L. so we will focus on this setting. PI counterparts of SVGD remain an open question [C 7. which we hope to be addressed by future works. When constrained on Gg. PI's formulation involves gradients so it depends on the Riemannian metric used in Gz. One natural choice of Riemannian metric the metric inherited from R which equals [ f (z)]l, since ((r) is also the projection onto the tangent bundle of Gz. This leads to the following definition.
Definition 5.3. II follows k-PI, for any smooth f on R varn, [f] I KEn,
PI on Riemannian manifold has been studied in previous work 12 21 In particular, Theorem 2.10 of [12] shows that PI holds for the Riemannian measure if the manifold G3 compact, and hence also holds for any equivalent distributions. But it is often hard to find the exact PI constant x for II,, especially if we are interested in family of II, with possibly discontinuous dependence on 2.
Proposition 5.4. Suppose that II satisfies for |a| S 8, and q is supported { 19(x)) S 6). Suppose also that 11,, q8, 7 admit C density functions. Then for any function f such that [fl s 1. the following holds
[Eglf] - En,f)-En,(fe [f]l= sy 1I - -s + max 1
En,
[f]l.
In particular, Proposition 5.4 shows that we have a y such that is 1) supported close to Go and 2) Fi (g, π is small, then q close to II in total variation. We can also interpret the bound alternatively as a decomposition of the difference between and II: the first part measures the difference along H.1 directions and it is controlled by F1; the second part measures the difference along Vg direction, and it is controlled by the distance between q y's support to Go-
As final remark, the orthogonal-space Stein equation (5) and orthogonal-space Fisher divergence (16) can be applied to densities supported on Rd and their formulations do not require information of Go such as parameterization and geodesic. Therefore, they can be used very computationally friendly statistical divergence practice.
Proposition 5.5. Suppose we apply vi o + Du with 5 and ( to the density field q-
1. Let M, = max{ (g(]))((),) E supp(g)))- Let S₁ be the solution of an ordinary differential equation S. (S.). Suppose So = Mo < co, then M, < St a.s.
2. Assume v is differentiable with derivative é. Suppose g is also smooth enough so that
2Vg Vg
VgT S Ag
I VollV
(17)
1
Then the KL-divergence follows dt (L( S (q. T) + E. (1)( + C.E, (MC
The first result shows that the support of q: will shrink towards Go. But in order avoid possible stagnation case, e.g. |ل is too small, it is necessary to impose [7p. The second result provides us some hint on the choice of v. Note that under qe for large enough t, g(x) will take values close to 0, so we need (0) (0) = Since (xx) should have the same sign with æ, one natural choice would be (yy) asign (y) y 1++
Theorem 5.6. Suppose we choose ((y) asign(y))8) 1+8 for an a 0,8 [0, and the conditions of Proposition 5.5 hold. Suppose also that KL(g0. T) < 8o and [V((z)] S Do if [w(x) < Ma. then Mr O(T minesT Fi(q, x) OlogTT/T) The orthogonal- space Stein equality holds approximately, in the sense that for any minsT An S /Fi(g,, T) O( /Mog T/T).
and | =
7

---

0.014
Oclangenn
2.01
1.122
SUCD
swon
0.01
CHIMC
2,000
Dang
1.000
1.000
1000
0.602
9-5VCD
1000
2023
6000
5922
1000
2220
2033
6000
5400
2032
C000
6000
9933
2000
0030
6982
80C0
(b)
(c)
(d)
Figure 2: Energy distance and MAE w.r.t. iterations when starting: (a)&(b) on the manifold and (c)&(d) outside the manifold.
Theorem 5.6 that we can obtain qr that is supported on 9 = fx 19(x)1 S 6). while it has close zero orthogonal-space Fisher divergence and the Stein identity holds approximately on H1. Combining it with Proposition 5.4 we have
Corollary 5.7. Under the conditions of Theorem 5.6 for a bounded f with H I suppose (2)2) (x =] = [n, is Lipschitz with near 2 O, then minggT [. [f] En, [f]l = (og/)//T)
6 Experiments
We demonstrate the effectiveness of our methods on various tasks, including a constrained synthetic distribution, an income classification with a fairness constraint, a loan application with a logic constraint and Bayesian deep neural networks with a robustness constraint. For all MCMC methods, we run n parallel chains and collect the final samples. For all SVGD, we use n particles with an RBF kernel. We released the code https: /tts::///hhu......m.. cww www..o/ggwang//////a// 0 gradient
Synthetic Distribution We first demonstrate our methods on a two-dimensional synthetic dis- tribution where the ground truth samples are available. Let y .N(0, 7), and we transform y to [2] by
o (y) where (zx) = [x1 + x2] T_ We aim to sample from π(z) with constraint g(x) = I1 + .. O. We are able to generate ground truth samples by first generating Yo ~ (O, 1) and then setting Zgg. [- yo]- We report the energy distance between the col- lected samples and the ground truth samples (measuring how well samples approximate the target distribution) and the mean absolute error (MAE) [g(z)] (measuring how well the samples satisfy the constraint). We set n 50 for this task.
In order to compare with previous manifold sampling methods, which all require initializations on the manifold, we first consider the case when the sampler starts on the manifold. We compare with constrained Langevin dynamics (CLangevin) and constrained Hamiltonian Monte Carlo (CHMC), which are two advanced manifold samplers [9]. From Figure 2b. we observe that O-SVGD and O-Langevin converge after 2000 and 4000 steps respectively whereas CLangevin and CHMC have not fully converged even after 5000 steps. These results indicate that projection- based methods could be inefficient due to finding sub-optimal solutions in the projection subroutines. In terms of runtime, observe that O-Langevin converges the fastest (see Appendix for comparisons). Figure P shows that previous methods have almost MAE all the time since they required to stay the manifold. Our methods have reasonably small MAE (but not zero due to operating in the ambient space) even without expensive projection steps. O-Langevin has more wiggly trajectories than O-SVGD due to injecting the Gaussian noise.
Next, we test our methods starting outside the manifold, where previous manifold sampling methods terms of iterations and both methods converge very quickly to the manifold and are able to stay close to it.
are not applicable. From Figure &ice we observe again that O-SVGD converges the fastest in
Income Classification with Fairness Constraint ML Fairness has gained increasing attention in recent years, which aims to guarantee unbiased treatments for individuals w.r.t. gender, race, disabilities, etc. Following previous work [26 244 we predict whether an individual's annual income is greater than 50, 000 unfavorably in terms of the gender. We use Adult Income dataset [[3] and train a Bayesian neural network with two-layer multilayer perceptron (MLP). During testing, we use CV score, standard faimess measure of disparate impact, the evaluation metric 4 On this task,
8

---

0200
-2.06
-1.50
-1.00
5..000
0.2022
Langran
0:00
00000
2.325
0.000
LoLnngett
-2.6
0.0006
5VG3
Langeot
SviDD
-2.99
0.0004
3.000
-3.4
0.0002
0.76
0.445
-0.70
Hies
Rus
Ris
(a) Training Curve
(b) Testing Curve
Figure 3: Income Classification: O-Langevin and O-SVGD have almost zero fairness loss and disparate impact while maintaining great prediction performance. Standard Langevin and SVGD fail to make fair predictions.
0.25
O-Langpeh
0-9VGD
0.20
Lengesth
8:52
Laaggennn B-SVG3
O Langesit O-SVCD Langeshi
-1.4
0:00
0.05
Largoen
Oslangeute
SVGD
SVGD
0-5W5D
-1.4
Largede
-3.7
5V0D
0.0
0
532
1003
1530
2000
0-
500
1003
3500
2033
0
200
3000
1552
2000
500
3000
1500
2033
(a) Training Curve
(b) Testing Curve
Figure 4: Loan Classification: O-Langevin and O-SVGD satisfy the constraint well whereas standard Langevin and SVGD violate the constraint severely.
CV score is defined as piincome 50, 000 female) p(income 50, 0000 male]] Training and testing performance of our methods and standard algorithms are shown in Figure 3 We find that during training and testing, both O-Langevin and O-SVGD satisfy the constraint very well while maintaining high training LL and test accuracy. In contrast, standard Langevin and SVGD violate the constraint significantly, indicating that they fail to make fair predictions. These results demonstrate the power of O-Gradient which keeps the sampler on the manifold while still correctly sampling from (Tx).
Loan Classification with Logic Rules Following previous work P5 we predict whether to lend loans to applicants and encode two logic rules: (1) an applicant must be rejected not employed and having the lowest credit rank; (2) an applicant must be approved if employed over 15 years and having the highest credit rank. We use a Bayesian logistic regression model and set g(Ø) = hugic (2) B(y, [Loss v, 811 z))] where Diogic is a uniform distribution over all datapoints (u, that satisfy the constraint, Loss refers to the classification loss and is the prediction made by the model. During testing, we compute the violation which is the percentage of predictions that do not follow the logic rules. In Figure 4 see that both of our methods satisfy the logic rules well whereas standard algorithms violate the constraint severely. A drop in the accuracy of our methods might be caused by conflicts between the data and the logic rules, that is, the solution with high accuracy does not satisfy the constraint. A similar phenomenon has also been observed in Liu et al. 251 which implies that this negative impact the accuracy is most likely due to the task rather than the algorithm. Nevertheless, our methods can obtain models satisfying the constraint, thus guarantee their safety and interpretability.
Prior-Agnostic Bayesian Neural Networks Bayesian neural network (BNN) has been widely used in deep learning (DL) for quantifying uncertainty. The posterior of BNNs is determined by the prior which reflects our prior knowledge, and the likelihood which quantifies the data fitness. Due to complex NN architectures, specifying an appropriate prior for BNNs has been shown be difficult [8] A poor prior often leads to a bad posterior and thus bad inference results. To automatically control the influence of the prior, one approach is to sample from the posterior with the constraint of reasonably high data fitness. We apply our methods to image classification on CIFAR 10 with ResNet-18 18. Since the training loss is typically very small in DL, we set the constraint to be g(x) Loss(x:.. Similar to stochastic Langevin dynamics (SGLD) 36 and SVGD, our methods are easy to be combined with stochastic gradients which are used on this task. We also ignore the second-order derivative terms in our methods for speedup. Besides standard algorithms, also compare with tempered

---

Table 1: Results on Image Classification (%). O-Langevin and O-SVGD significantly outperform
unconstrained methods in terms of both generalization accuracy and calibration.
Test Error ())
ECE (4)
AUROC (f)
SGLD
15.00
2.21
89.41
Tempered SGLD
4.73
0.83
97.63
O-Langevin
4.46
0.87
98.68
SVGD
6.1I
0.93
93.55
O-SVGD
4.92
0.77
94.69
SGLD which has been used in the literature for good performance 33 We report test error, expected calibration error (ECE) and AUROC on the SVHN dataset (measuring out-of-distribution detection).
From Table ! we see that O-Langevin and O-SVGD improve significantly over their unconstrained counterparts all three metrics. O-Langevin has the lowest test error and the highest AUROC while O-SVGD has the lowest ECE. These results indicate that the constraint can automatically limit the effect of the prior, leading to better posterior and thus better generalization and calibration.
7 Conclusion and Limitations
We propose new variational framework with designed gradient flow (O-Gradient) for sampling in implicitly defined constrained domains. O-Gradient is formed by two orthogonal directions where one drives the sampler towards the domain and the other explores the domain by decreasing KL divergence. We prove the convergence of O- Gradient and apply the framework to both Langevin dynamics and SVGD. We empirically demonstrate the power of our methods on variety of ML tasks.
While ML achieves impressive performance, we must take realistic constraints into consideration when deploying it in daily life. This work provides a principled framework for solving constrained sampling problem with theoretical guarantees and practical algorithms.
One possible limitation of methods is that the obtained samples not exactly the manifold due to working in an ambient space, though can be made arbitrarily close to the manifold by tuning hyperapameters. This might be solved by including projection step. Another limitation is that only consider an equality constraint. It will be interesting to incorporating inequality constraints into the framework. Besides, our theory only considers the convergence in the continuous-time limit. Future work could provide convergence analysis in discrete time, which may characterize the properties of practical algorithms more accurately.
Acknowledgements
QL supported by (AREER-184642) SenSE2033267, EAGER-2041327, Office of Navy Research, and NSF AI Institute for Foundations of Machine Learning (IFML). XT is supported by the Singapore Ministry of Education (MOE) grant R- 1-14-000-292-1144
References
[1] Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Li Meng. Handbook of markov chain monte carlo. CRC press, 2011.
[2] Marcus Brubaker, Mathieu Salzmann, and Raquel Urtasun. A family of meme methods on implicitly defined manifolds. In Artificial intelligence and statistics, pages 161-172. PMLR, 2012.
[3] Simon Byme and Mark Girolami. Geodesic monte carlo embedded manifolds. Scandinavian Journal of Statistics, 40(4):825-845, 2013.
[4] Toon Calders and Sicco Verwer. Three naive bayes approaches for discrimination-free classifi- cation. Data Mining and Knowledge Discovery, 21(2):277-292, 2010.
10

---

[5] Joseph T Chang and David Pollard. Conditioning as disintegration. Statistica Neerlandica, 51 (3):287-317, 1997.
[6] Persi Diaconis, Susan Holmes, and Mehrdad Shahshahani. Sampling from a manifold. In Advances in modern statistical theory and upplications: a Festschrift in honor of Morris L. Eaton, pages 102-125. Institute Mathematical Statistics, 2013.
[7] Andrew Duncan, Nikolas Nüsken, and Lukasz Szpruch. On the geometry of stein variational gradient descent. arXiv preprint arXiv: 2019.
[8] Vincent Fortuin, Adrià Garriga-Alonso Florian Wenzel, Gunnar Rätsch, Richard Turner, Mark van der Wilk, and Laurence Aitchison. Bayesian neural network priors revisited. arXiv preprint arXiv:2102.06571, 2021.
[9] Mark Girolami and Ben Calderhead. Riemann manifold langevin and hamiltonian monte carlo methods. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 73(2): 123-214, 2011.
[10] Jackson Gorham and Lester Mackey. Measuring sample quality with kernels. In International Conference on Machine Learning, pages 1292-1301. PMLR, 2017.
[11] Alexey Gritsenko, Tim Salimans, Rianne van den Berg, Jasper Snoek, and Nal Kalchbrenner. spectral energy distance for parallel speech synthesis. Advances in Neural Information Processing Systems, 33:13063 33:13062-13072, 2020.
[12] Emmanuel Hebey. Nonlinear Analysis on Manifolds: Sobolev Spaces and Inequalities: Sobolev Spaces and Inequalities, volume 5. American Mathematical Soc., 2000.
[13] Ron Kohavi. Scaling up the accuracy of naive-bayes classifiers: A decision tree hybrid. Kdd, volume 96, pages 202-207, 1996.
[14] Yunbum Kook, Yin Tat Lee, Ruoqi Shen, and Santosh S Vempala. Sampling with riemannian hamiltonian monte carlo in a constrained space. arXiv preprint arXiv:2202.01908, 2022.
[15] Yann LeCun, Sumit Chopra, Raia Hadsell, M Ranzato, and F Huang. A tutorial on energy-based learning, Predicting structured data, 1, 2006.
[16] Yin Tat Lee and Santosh S Vempala. Convergence rate of riemannian hamiltonian monte carlo and faster polytope volume computation. Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pages 1115-1121, 1121, 2018
[17] Tony Lelievre and Gabriel Stoltz. Partial differential equations and stochastic methods in molccular dynamics. Acta Numerica, 28:681-880, 2016.
[18] Tony Lelievre, Mathias Rousset, and Gabriel Stoltz. Langevin dynamics with constraints and computation of free energy differences. Mathematics of computation, 81(220):2071-2125, 2012.
[19] Tony Lelièvre, Mathias Rousset, and Gabriel Stoltz. Hybrid monte carlo methods for sampling probability measures on submanifolds. Numerische Mathematik, 143(2):379-421, 2019.
[20] Tony Lelièvre, Gabriel Stoltz, and Wei Zhang. Multiple projection markov chain monte carlo algorithms on submanifolds. IMA Journal of Numerical Analysis, 2022.
[21] Peter Li and Jiaping Wang. Weighted poincaré inequality and rigidity of complete manifolds. In Annales scientifiques de l'Ecole normale supérieure, volume 39, pages 921-982, 2006.
[22] Qiang Liu. Stein variational gradient descent as gradient flow. Advances Neural Information Processing Systems (NeurIPS), 2017.
[23] Qiang Liu and Dilin Wang. Stein variational gradient descent: A general purpose Bayesian inference algorithm. In Advances Neural Information Processing Systems (NeurIPS), 2016.
[24] Suyun Liu and I Luis Nunes Vicente. Accuracy and faimess trade-offs machine learning: stochastic multi-objective approach. arXiv preprint arXiv:2008.011333 2020.
11

---

[25] Xingchao Liu, Xin Tong, and Qiang Liu. Sampling with trusthworthy constraints: A variational gradient framework. Advances in Neural Information Processing Systems. 34, 2021.
[26] Natalia Martinez, Martin Bertran, and Guillermo Sapiro. Minimax pareto fairness: A multi objective perspective. In International Conference Machine Learning, pages 6755-6764. PMLR, 2020.
[27] Gilles Meyer, Silvere Bonnabel, and Rodolphe Sepulchre. Linear regression under fixed-rank constraints: riemannian approach. In Proceedings of the 28th international conference on machine learning, 2011.
[28) Sam Patterson and Yee Whye Teh. Stochastic gradient riemannian langevin dynamics on the probability simplex. In Advances Neural Information Processing Systems (NeurlPS), 2013.
[29] Dino Sejdinovic, Arthur Gretton, Bharath Sriperumbudur, and Kenji Fukumizu. Hypothesis testing using pairwise distances and associated kernels (with appendix). International conference on machine learning. 2012.
[30] Dino Sejdinovic, Bharath Sriperumbudur, Arthur Gretton, and Kenji Fukumizu, Equivalence of bissence-bbasd and rkhs-based statistics in hypothesis testing. The annals of statistics, pages 2263-2291, 2013.
[31] Upanshu Sharma and Wei Zhang. Nonreversible sampling schemes on submanifolds. SIAM Journal on Numerical Analysís, 596)):2999-3331, 2021.
[32] Leon Simon. Introduction to geometric measure theory. Tsinghua Lectures, 2014.
[33] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. In Advances in Neural Information Processing Systems, pages 11895-11907, 2019.
[34] Gabriel Stoltz, Mathias Rousset, et Free energy computations: mathematical perspective. World Scientific, 2010.
[35] Xiao Wang, Qi Lei, and Toannis Panageas. Fast convergence of langevin dynamics on manifold: Geodesics meet log-sobolev. Advances in Neural Information Processing Systems, 18904, 2020.
[36] Max Welling and Yee W Teh. Bayesian learning via stochastic gradient Langevin dynamics. In International Conference on Machine Learning, 2011.
[37] Emilio Zappa, Miranda Holmes-Cerfon, and Jonathan Goodman. Monte carlo on manifolds: sampling densities and integrating functions. Communications Pure and Applied Mathemat- ics, 71(12):26992267, 2018.
[38] Ruqi Zhang. Chunyuan Li, Jianyi Zhang, Changyou Chen, and Andrew Gordon Wilson. Cyclical stochastic gradient meme for bayesian deep learning. International Conference on Learning Representations, 2020.
[39] Wei Zhang, Ergodic sdes submanifolds and related numerical sampling schemes. ESAIM: Mathematical Modelling and Numerical Analysis, (4()):391-430 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
12

---

(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof's of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URI.)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report enror bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) curating/releusing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals. if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "nkB2f92wDU", "reviewer": "Reviewer_nfnT", "summary": "This paper introduced a sampling method, namely O-Gradient, that enables defining equality constraints which is achieved by two-component strategy: decrease the distance to the manifold by decreasing the KL divergence as fast as possible (using a velocity field. The paper presents two formulations using Langevin dynamics (O-Langevin) and SVGD (O-SVGD). The paper presents both theoretical analysis of the convergence of O-Gradient based on Proposition 5.2 that defines a limit that is used to formulate an orthogonal-space Stein equation. This in turn is used to generalize the Fisher divergence. The experimental evaluation considered both synthetic and real scenarios. In the former, the paper presents analysis of convergence comparing O-Gradient with  constrained Langevin dynamics and constrained Hamiltonian Monte Carlo, as baselines, where O-Gradient methods show better convergence when sampling from inside or outside the manifold. The baseline methods have a MAE is almost zero for when sampling is done from inside and are not applicable for sampling from outside the manifold. The real-world experiments are done for income classification, loan classification, and image classification where O-Gradient methods seem to perform better than the alternatives.", "questions": "Could you clarify why the FPE of the definition of $dx_t$ in line 150 does not follow Eq (10).\nWhat function is used to compute the CV score in the Income Classification with Fairness Constraint ?\nWhat is the function used to compute the error in Loan Classification with Logic Rules?\nWhat is the function that was used to compute the test error in the experiment “Prior-Agnostic Bayesian Neural Networks”?", "limitations": "The paper describes the limitations in terms of the nature of the model (i.e., it is an approximation and samples are not exactly on the manifold, the type of constraint is equality only, and continuous time).\nNo limitations are provided outside this technical realm. ", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In summary, the paper is somewhat clear but more could be added to make it self-contained. The organization is not bad. The originality is mostly about the specific equality constrain considered during sampling. The quality of the work is theoretically good and experimentally reasonable. Some specific details include:\n\nStrengths:\nVariational gradient descent applied to sampling with equality constraints is relatively novel problem. It is related to, but not the same than, variational inference subject to inequality constraints for which there are works that propose a solution. \nIt is an interesting approach to try to define sampling in terms of closeness and orthogonality to the related manifold defined by the domain of the distribution and the equality constraint. \n\nWeaknesses:\nThe paper, as written, is only accessible to the ML sub-community working on Sten variational inference and sampling and related topics as it does not present the intuition of the work but rather in general terms. For instance, the paper states that Fokker–Plank equation of the SDE $dx_t$ (dubbed by the paper as natural guess) does not follow the density flow expected in Eq 10. Further details could clarify this.\n\nThere are other sections of the paper where the explanations provided are insufficient such as the lack of a data description in the experiment for Loan Classification with Logic Rules. The function used to measure the test error in the experiment “Prior-Agnostic Bayesian Neural Networks” is not detailed.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "i3MZV_wxNNL", "reviewer": "Reviewer_aCms", "summary": "This paper proposed a new variational framework for sampling from constrained domains. By designing an orthogonal-space gradient flow, i.e. the O-Gradient, the proposed methods can sample from manifolds defined by general equality constraints. The O-Gradient can be realized by both the Langevin dynamics and the Stein variational gradient descent, namely the O-Langevin and the O-SVGD. In contrast to previous methods, the O-Langevin and the O-SVGD do not require initializing the samples on the manifolds defined by the constraints. Besides, the paper has proved that the O-Gradient converges to the target distributions with rate $\\tilde{\\mathcal{O}}(1/T)$, where T is the number of iterations. In the experiment section, the O-SVGD and the O-Langevin have shown their effectiveness in various setups, showing that they can generate samples that approximate the target distribution well while also staying on the manifold defined by the constraints.", "questions": "1. In Section 4.1, \"$\\frac{dq}{d\\pi}$ and $KL(q||\\pi)$ are ill-posed\", what is the definition of \"ill-posed\"?\n2. What's the interpretation of Eq. (5)? Why do you choose the function $\\psi(x)=\\alpha\\text{sign}(x)|x|^{1+\\beta}$?\n3. In line 149, what is the \"projection intuition\"?\n4. Line 252, what is the \"energy distance\"?", "limitations": "Yes, the author has adequately addressed the limitations and potential negative societal impact of their work. The limitations of the approach were presented above.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The paper has addressed an interesting topic of variational samplers.\n2. The proposed methods have made remarkable progress upon previous methods, alleviating the requirement of initializing samples on the targeted manifold.\n\nWeakness:\n1. It seems that the proposed method has some negative impact on the original task, e.g. in the income classification experiment, a decrease in the test accuracy can be observed.\n2. It is unclear what the computational cost of this method is compared to the compared baselines.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NprasKLXOyS", "reviewer": "Reviewer_p8UL", "summary": "The paper explores an orthogonal space gradient descent. This is achieved by constructing the perpendicular space from the gradient direction using $\\mathbb{I} -\\frac {\\nabla g \\nabla g^T}{\\norm{g}^2} $", "questions": "I do not have sufficient context on the paper, therefore I do not have any questions at this point.", "limitations": "Yes, the authors have addressed the impact of their work sufficiently.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The reviewers expertise is limited in this field, hence the comments will be very brief and editorial.\nStrengths:\n1. The paper is well written. Both the language and the math seem to be consistent.\n\n\nWeaknesses:\n1. The applications might not exactly be suitable for a conference like Neurips\n2. The complexity is of the algorithm is not mentioned.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1vFEYrqpefz", "reviewer": "Reviewer_K6fK", "summary": "The paper introduces a class of algorithms for sampling from a target density conditionally on a set of constraints expressed as an equation $g(x)=0$. The paper relies on a variational formulation of the vector fields defining Langevin dynamics and SVGD to derive an Orthogonal- version of such vector field with two components: an orthogonal component that drives samples toward the set of constraints and a tangential component that diffuses the particles to that they are distributed according to the target. The algorithm is simple to compute and requires only evaluating the score of the target, the constraint g(x), and its gradient. \nConvergence rates for the algorithm are provided and rely on a new stein characterization of conditional measures which appears to generalize stein characterization.", "questions": "Proof of prop 5.4:\n        - It appears the authors apply the k-PI inequality of Definition 5.3 to the function f(y) = \\sqrt{q_z(y)/Pi_z(y)}. When computing the variance of f under $\\Pi_z$, I get the expression: $1- a^2$ with a = E_{Pi_z}[f], so that k-Pi would be given by $(1-a^2)\\leq E[||D\\nabla ||^2]$. However, in the proof, the authors use the inequality $2(1-a)\\leq E[||D\\nabla ||^2]$. I do not see why this would hold, since $1-a^2 \\leq 2(1-a) $. \n       - The equation after line 493 suggests that the score difference between $q_z$ and $\\Pi_z$ is the limit of the scores $\\pi_{\\eta,z}$, but I do not see why this is true. It seems this claim follows from Proposition5.2. However, the latter only shows that the densities $\\pi_{\\eta,z}$ converge towards Pi_z in the 'weak limit'. This result does not necessarily imply that scores of $\\pi_{\\eta,z}$ converge to the score of $PI_z$ in a pointwise sense. Please clarify this.  \n \n- Statement of thm 5.5: I think the statement should be modified as follows:\n\nSet $M_t= sup(|g(x)|, x\\in supp (q_0)  )$ and define S_t by dS_t = -psi(S_t) and $S_0=M_0$. If M_0<+infty, then M_t\\leq S_t for all times.  Currently, the paper makes the stronger claim that dM_t=-\\psi(M_t), but this is not proven and is not really needed for the rest of the paper.\n            \nIn eq 17, there is a factor 2 missing to the 3 terms otherwise the proof in the appendix doesn’t hold.\n\nFollowing the proof of thm 5.6, it seems that the conclusion of thm 5.6 on the upper bound of the O-stein discrepancy is wrong. Instead, the upper bound should hold only for the min_t over [0,T] and not for any t in [0,T]. \n\t\t\nEq $17$ does not seem to be an appropriate smoothness assumption: when g is smoother the l.h.s in 17 blows up to infinity, so that the constant C_0 must be larger and larger. In the limit case when g is constant, the inequality never holds. This can be fixed by scaling the l.h.s by the norm of $||g||$ and replacing the last term in L 228 by the ratio (\\psi(g(x))/\\Vert g(x)\\Vert). \n\n\n", "limitations": "The authors should discuss how restrictive are the assumptions required for the results + fix the proofs. I am willing to raise my score to a (weak) acceptance it these issues are addressed in an acceptable manner.", "rating": 7, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The idea appears to be novel and might have a significant impact in the context of conditional sampling under generic equation constraints. The algorithms are simple to use and appear to be effective on the considered examples. \nThe presentation is also clear and the problem well motivated.\n\n \nMy main concern is about the soundness of the theory as it appears there are some errors or unclear steps in the proofs (see questions section for more details). I hope the authors can fix these issues and clarify these points. More generally, the write-up of the proofs should be improved to better explain the intermediate steps in the calculations and add explicit logical links between different components of the proofs. \n\nIt seems that the main result relies on at least two strong assumptions: the Poincaré inequality for conditional densities and the inequality in eq (17) on the constraint $g$. Can the authors provide examples where such assumptions hold? Classical PI holds in many situations, but for the conditional case, it is still unclear to me how restrictive this is.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept