Learning Globally Smooth Functions on Manifolds
Authors: Juan Cervino
Luiz F. O. Chamon
Benjamin David Haeffele
Rene Vidal
Alejandro Ribeiro
Venue: Submitted to ICLR 2023 (2023)
Keywords: Lipschitz functions
Manifolds
Machine Learning

Abstract: Smoothness and low dimensional structures play central roles in improving generalization and stability in learning and statistics. The combination of these properties has led to many advances in semi-supervised learning, generative modeling, and control of dynamical systems. However, learning smooth functions is generally challenging, except in simple cases such as learning linear or kernel models. Typical methods are either too conservative, relying on crude upper bounds such as spectral normalization, too lax, penalizing smoothness on average, or too computationally intensive, requiring the solution of large-scale semi-definite programs. These issues are only exacerbated when trying to simultaneously exploit low dimensionality using, e.g., manifolds. This work proposes to overcome these obstacles by combining techniques from semi-infinite constrained learning and manifold regularization. To do so, it shows that, under typical conditions, the problem of learning a Lipschitz continuous function on a manifold is equivalent to a dynamically weighted manifold regularization problem. This observation leads to a practical algorithm based on a weighted Laplacian penalty whose weights are adapted using stochastic gradient techniques. We prove that, under mild conditions, this method estimates the Lipschitz constant of the solution, learning a globally smooth solution as a byproduct. Numerical examples illustrate the advantages of using this method to impose global smoothness on manifolds as opposed to imposing smoothness on average.

LEARNING GLOBALLY SMOOTH FUNCTIONS ON MANIFOLDS
A Anonymous authors Paper under double-blind review
A ABSTRACT
Smoothness and low dimensional structures play central roles in improving generalization and stability in lcarning and statistics. The combination these properties has led to many advances in semi-supervised learning, generative modeling, and control of dynamical systems. However, learning smooth functions is generally challenging, except in simple cases such as learning linear kernel models. Typical methods either too conser- vative, relying on crude upper bounds such as spectral normalization, too lax, penalizing smoothness requiring the solution of large-scale semi-definite programs. These issues are only exacerbated when trying to simultaneously exploit low dimensionality using, e.g,, manifolds. This work proposes to overcome these obstacles by combining techniques from semi-infinite constrained learning and manifold regularization. To do so, it shows that, under typical conditions, the problem of learning a Lipschitz continuous function on a manifold is equivalent to a dynamically weighted manifold regularization problem. This observation leads a practical algorithm based on a weighted Laplacian penalty whose weights are adapted using stochastic gradient techniques. We prove that, under mild conditions, this method estimates the Lipschitz constant of the solution, learning a globally smooth solution as byproduct. Numerical examples illustrate the advantages of using this method to impose global smoothness manifolds opposed to imposing smoothness on average.
average, too computationally intensive,
INTRODUCTION
Learning smooth functions has been shown to be advantagcous in general and is of particular interest in physical systems. This is because of the gencral observation that close input features tend to be associated with close outputs and of the particular fact that in physical systems Lipschitz coutinuity of input-oulput maps translates lo stability and safety (Oberman
and Calder 2018 Finlay et al. 2018a Couellan 2021 F Finlay et al. 2018b Pauli et al. 2021
Krishnan et al. 2020 Shi et al. 2019 Lindemann et al. 2021 Arghal et al. 2021
can require the parameterization to be smooth. Such is the idca, c.g., of spectral normalization of weights in noural networks (Miyato et al. 2018 Zhao and Liu 2020). Smooth parameterizations have the advantage of being globally smooth, but they may be restrictive because they impose smoothness for inputs that are not necessarily realized in the data. This drawback motivales the use of Lipschitz penallies in risk minimization (Oberman and Calder 2018 Finlay et al., 2018a Couellan 2021 Pauli et al. 2021 [ungert et al.] 2021), which offers the opposite tradeoff. Since penalties encourage but do not enforce small Lipschitz constants, we may learn functions that are smooth on average, but with no global guarantees of smoothness at every point in the support of the data. Formulations that guarantee global smoothness can be obtained if the risk minimization problem is modified by the addition of a Lipschitz constant constraint (Krishnan et al.) 2020 Shi et al. 2019 Lindemann et al. 2021 Arghal et al. 2021 This yields formulations that guarantee Lipschitz smoothness in all possible inputs without the drawback of enforcing smoothness outside of the input data distribution. Several empirical studies (Krishnan et al., 2020 Shi et al. 2019 Lindemaan et al.) 2021 Arghal et al. 2021) have demonstrated the ad advantage of imposing global smoot hness constraints only observed inputs.
To learn smooth functions

---

(a) Datasot set.
(b) Manifold Lipachitx (ours) (c) Manifold Regularisation
(d) Ambient Regularization
Figure 1: Two moons dataset. The setting consists of a two dimensional classification
problem of two classes with labeled, and 200 unlabeled samples per class. The objective is to correctly classify the 200 unlabeled samples. We consider two cases (top) the esated manifold has two connected components, and (bottom) the manifold is weakly connected (cf. Figure D. We plot the output of one layer neural network trained using Manifold Regularization, Manifold/ Ambient Lipschitz. Ambient Regularization fails to classify the unlabeled samples, given that ignores the distribution of samples given by the Manifold. The case which the manifold has two connected component (cf. Figure Ia), our method works good Manifold Regularization, due the fact that the Lipschitz constant will be made small in both components separately. However, when the manifold is weakly connected, Manifold Regularization fails recognize the transition between the components, penalize large gradients across the manifold, converging to plane that comnects the two samples. Our Manifold Lipschitz method, as requires the Lipschitz constant be small, forces sharp transition along the point with maximal scparation.
it will
In this paper we exploit the fact that data can be often modeled as points in a low-dimensional manifold. We therefore consider manifold Lipschitz constants in which function smoothness is assessed with respect to distances measured over the data manifold (Definition D. Although this looks like minor difference, controlling Lipschitz constants over data manilolss is quite different from controlling Lipschitz constants in the ambient space. In Figure we look at classification problem with classes arranged in two separate half moons. Constraining Lipschitz constants in the ambient space effectively assumes the underlying data is uniformly distributed in space (ef. Figure 1 (d)] Constraining Lipschitz constants in the data manifold, however, properly accounts for the data distribution [ef. Figure (a)).
This example also illustrates how constraining manifold Lipschitz constants is related to manifold regularization (Belkin et al. 2005 Niyogi 2013 Li et al. (022).. The difference that manifold regularization penalizes the average norm of the manifold gradient. This distinction is significant because regularizing is more brittle than imposing constraints. In the example in Figure [I] manifold regularization fails separate the dataset when the moons are close (ef. Figure (c), bottom]. Classificatiinn with manifold Lipschitz constant constraint more robust. this change in the data distribution [ef. Figure 1 (a), bottom].
Global constrains in the manifold gradient yield statistical constrained learning problem with an infinite and dense number of constraints. This a challenging problem to approximate and solve. Here, approach the solution of this problem in the Lagrangian dual domain and establish connections with manifold regularization that allow for the use of point cloud Laplacians. Our specific contributions are the following:
(C1) We introduce constrained statistical risk minimization problem in which we learn function that: (i) attains a target loss and (ii) attains the smallest possible manifold Lipschitz constant. among these functions that satisfy the target loss (Section 2
2

---

(C2) We introduce the Lagrangian dual problem and show that its empirical version is statistically consistent approximation of the primal. This results does not require the learning parametrization to be convex (Section 3.1
(C3) We generalize results from the manifold regularization literature to show that under regularity conditions, the evaluation of manifold Lipschitz constants can be recast in more amenable form utilizing weighted point cloud Laplacian (Proposition in Section 3.2
(C4) We present a dual ascent algorithm to find optimal multiplicrs. The function that attains the target loss and minimizes the manifold Lipschitz constant follows as byproduct (Section 3.3
(C5) We illustrate the merits of learning with global manifold smoothness guarantees with respect to ambient space and standard manifold regularization through two examples: (i) learning robot navigation policies in a space with obstacles and (ii) learning model mismatches in differential drive steering over non-ideal surfaces (Section
RELATED WORK
This paper is at the intersection learning with Lipschitz constant constraints (Oberman
and Calder 2018 Finlay et al. 2018a; Couellan, 2021 Pauli et al. 2021 Bungert et al.) 2021
Miyato et al. 2018 Zhao and Liu 2020 Krishnan et al. 2020 Shi et al.) 2019 Lind emann
ct al. 2021 Arghal et al.) 2021 and manifold regularization
Belkin et al. 2005 Niyogi
2013
Li et al. 2022 Hein et al. 2005 Belkin and Niyogi 2005). Relative lo the literalure on
learning with Lipschitz constraints we ofler the ability to leverage data manifolds. Since data manifolds are often characterized with unlabeled data (Kejani et al. 2020 Belkin and Niyogi
2004 Jiang et al. 2019
Kipf and Welling 2016 Yang al. 2016 Zhu 2005 Lecouat al.
Cabannes et al. 2021,, similar to these works, we utilize the point cloud Laplacian technique to compute the integral of the norm of the gradient. Relative to the literature on manifold regularization we offer global smoothness assurances instcad of an average penalty of large manifold gradients. discretized maintaining convexity, and at the expense of deriving a sensitive solution, their approach leads to a large optimization problem. Similar to us, KKrshhaa et al. 2020 poses the problem of minimizing a Lipschtiz constant, however, they utilize softer surrogate (i.e. p-norm loss) which is a smoother version of the Lipschitz constant. Their approach therefore, tradeoffs numerical stability (small p) with accurate Lipschitz constant estimation (p = 20). We do not work with surrogates, and we seek to minimize the maximum norm of the gradient, utilizing an epigraph technique.
2018 Ouali et al.
2020
(Krishnan et al. 2020), the space is
GLOBAL CONSTRAINING OF MANIFOLD LIPSCHITZ CONSTANTS
We consider data pairs (z, v) in which the input features x E M C DDD lie in compact oriented Riemannian manifold M and the output features are real valued y E R. We study the regression problem of finding function ʃa M R, parameterized by 0 E θ C R that minimizes the expectation of a nonnegative loss é IR x R + R,, where ((fe y) represents the loss of predicting output fa( when the world realizes the pair (I, y). Data pairs (x, y) are drawn according to an unknown probability distribution p(z, y) on M x R which we can factor as p(x, y) p(z))(
We are interested in lcarning smooth functions, i.c. functions with controlled variability over the manifold M. We therefore let ( represent the manifold gradient of so and introduce the following definition.
Definition 1 (Manifold Lipschitz Constant). Given a Riemonnian manifold M, the function fo : M + IR is said to be I.-Tipschttz continuous if there exists a strictly positime constant M,
I L>0 0 such that for all pairs of points x1,
1fo(0z) fo(x2)) (d1,
(1)
3

---

where ( 222 denotes the distance between 21 and 22 in the manifold M. If the function fo is differentiable, [ is equivalent to requiring the gradient norm to be bounded by L,
f S L, for all x E M.
[VMf(()) = lim sup
dm(x,x²)
d'EM t'tx dx(r,)))
With definition I in place and restricting attention to differentiable functions fo our stated goal of learning lunctions So with controlled variability over the manifold M can then be written as p=
min P. 0E0,p20
subject to (e se
[/V S P, p(z)-a.e., = ZEM.
In this formulation the statistical loss Bp(z,)) [e (fo(z)))) is required to be below a target level e, Of all functions fe that can satisfy this loss requirement, Problem 3 defines as optimal the one whose Lipschitz constant L vp is the smallest.
The goal of this paper is to develop methodologies to solve 3 when the data distribution and the manifold are unknown. To characterize the distribution we are given sample pairs (x,, y1) drawn from the joint distribution p(x, y). To characterize the manifold we are given samples z drawn from the marginal distribution p(a:). This includes the samples x; from the (labeled) data pairs (Iz, Ms) and may also include (unlabeled) samples 2;-
It. is interesting to observe that [3] shows that the problems of manifold regularization [Belkin et al.] 2005; Niyogi 2013
: Kejani et al., 2020 Li et al. 2022) and Lipschitz constant
control (Oberman and Calder 2018 Finlay et al. 2018a Couellan 2021 Finlay al. 2018b
Pauli et al. 2021 Krishnan el all 20200 Shi et al.
2019 Lindemann et al. [222 Argha et al.
2021) are related. This connection is important to understand the merit of (3 To explain
this better observe that there are three motivations for the problem formulation in 13 (i) is often the case that samples 21 and 22 are close, then the conditional distributions ply x1) and p(u x22) are close as well. A function so with small Lipschitz constant leverages this property. (ii) The Lipschitz constant of fe is guaranteed to be smaller than L = vp. This provides advantages in, e.g. physical systems where Lipschitz constant guarantees translates to stability and safety assurances. (iii) It leverages the intrinsic low-dimensional structure of the manifold M embedded in the ambient space. In particular, this permits taking advantage of unlabeled data.
Motivations (i) and (ii) are tropes of the Lipschitz regularization literature; e.g.. Oberman
and Calder (2018); Finlay et al. (2018a]); Couellan (2021] 05 Finlay et al. (2018b); Pauli et al.
(2021 Krishnan al. (020); Shi et al. 2019 Lindemann et al. [2027] Arghal et al. (2021 Indeed, the problem formulation in [3] is inspired in similar problem formulations in which
the Lipschitz constant is regularized the ambient space, minimize L, 660,p20
subject to
Ep (Jo(z), Se,
[J(()) - fo(=)] < 1111y=20 =|l. (v,))~p(a)
difference between (3) and 4 is that in the latter we use a Lipschitz condition that does not require differentiability. A more important difference is that in (4) the Lipschitz constant regularized in the ambient space. The distance between features y and z in (4) the Euclidean distance |yy - z|I. This is disparate from the manifold metric d dy(yy, 2) that is implicit in the manifold gradient constraint in (3). Thus, the formulation in (3) improves upon because of it leverages the structure of the manifold M [ef. Motivation (iii).
Motivations (i) and (iii) are themes of the manifold regularization literature (Belkin et al. 2005 Niyogi 2013 Kejani al. 2020 Li et al.] 2022). And, indeod, it is ready to conclude
by invoking Green's s first identity (see Section 3.2 that the formulation in ( is also inspired in the manifold regularization problem,
minimize Ep(rg)) (fo())ff))))))))))) +7 [V 0E0
(5)
4

---

The difference between 3 and 5 is that in the latter the manifold Lipschitz constant added as a regularization penalty. This is disparate from the imposition of a manifold
Lipschitz constraint in (3.. The regularization in ( favors solutions with small Lipschitz constant. by penalizing large Lipschitz constants, while the constraint in (3) guaranlees that the Lipschitz constant is bounded by p. This is the distinction between regularizing Lipschitz constant versus construining Lipschitz constant. The constraint in 5 is also imposed at all points in the manifold, whereas the regularization in (5) is an average over the manifold. Taking an average allows for large Lipschitz constants at some specific points this is canceled out by small Lipschitz constants in other points of the manifold. Both of these observations imply that (3) improves upon (5) because it offers global smnss guarantees that are important in, e.g., physical systems [cf. Motivation (iii)-
Remark 1 (Alternative Manifold Lipschitz Control Formulations). There are three arbitrary choices in (a) We choose to constrain the average statistical loss Rp(a,y) ( S e; (b) choose constrain the pointwise Lipschitz constant [[)]f((2)]] I and (c) choose as our objective to require a target loss and minimize the Lipschitz constant == vp. We can alternatively choose to constrain the pointwise loss (z) S to constrain the average Lipschitz constant JM [V (=Mff())lpp(zddV(
I |cf (, or to require a target smoothness I, vp and minimize the loss All of the possible eight. combinations of choices are of interest. We formulate (3) because it is the most. natural intersection between the regularization of Lipschitz constants ambient spaces |cf. (4) and manifold regularization lef. [. The techniques we develop in this paper can be adapted to any of the other seven alternative formulations.
LEARNING WITH GLOBAL LIPSCHITZ CONSTRAINTS
Problem 3 is a constrained learning problem that we will solve in the dual domain |Chamon and Ribeiro, 2020). To that end, observe that (3) has statistical and pointwise constraints. The loss constraint Ep(a.y) (fo(z), y)] S e is said to be statistical because it restricts the expected loss over the data distribution. The Lipschitz constant constraints (/ < said to be pointwise because they are imposed for all individual points in the manifold except for a set of zero measure, Consider then a Lagrange multiplier μ associated with the statistical constraint Ep( (Jo(z), v)] S and Lagrange multiplier distribution A(z) associated with the of pointwise constraints [[Vmfo(=)]] S p. The dual problem associated with 3 can then be written
D = max min L(0, = (BI((f((z)) -c) M
n.220
/ X())p())dV(=)=
subject to
We point out that in 6 we remove p from the Lagrangian by incorporating the dual variable see Appendix A for details.
constraint SM (d
We henceforth use the dual problem (6) in lieu of Since we are interested in situations in which we do not have access to the data distribution p(x,8) y) we further consider empirical versions of (6) Consider then N i.i.d. samples (In, Vo) drawn from p(x, y) and define the empirical dual problem as,
D' = max min ((O, = Σ ((f(a.))) -c() 1 Σ ( 2AA0
n=1
subject to N
1
Σ ((zn)= =1
(7)
where, to simplify notation, we assume no unlabcled samples available. If unlabeled samples are given the modification is straight-forward; see Appendix B
The remainder of this section provides three technical contributions:
5

---

(C2)
To justify solutions of primal problem ( This is challenging because of two reasons: (i) Since we did not assume the use of a convex parameterization, (3) is not convex problem Thus, the primal and dual problems are not necessarily equivalent. (ii) Since we are maximizing over the dual variables μ and (2)), we do not know if the empirical dual formulation in (7) is close to the statistical dual formulation in (6. We will overcome these two challenges and show that the empirical dual problem 7 is a consistent
must show statistical consistency with respect to the
O.
approximation of the statistical primal problem (Proposition 1 in Section 3.1.
(C3) Solving 7 requires evaluating the gradient norm sum (1/N) Ex
(o(an)))
We will generalize results from the manifold regularization literature to show that under regularity conditions on À the gradient norm integral can be computed a more amenable form utilizing a weighted point cloud Laplacian (Proposition in Section 3.2)
(C4) We introduce a primal-dual algorithm to solve (Section 3.3
3.1 STATISTICAL CONSISTENCY OF THE EMPIRICAL DUAL PROBLEM
We show in this section that 7 is close to (3. Doinn so requires the following assumptions: Assumption 1. The loss l is M-Lipschilz continuous, B B-bounded, and conver.
Assumption 2. Let 7 {fe 0 E C R with compact @ be the hypothesis class, and let (H) be the closure of its convEr hull. For each v > 0 and tp E H there exists E θ such that simultaneously supzeM lęp(z) fa(z)] S and sup.eM [IV))((2) ( v. Assumption 3. The hypothesis class H is G-Lipschitz in ils gradients, i.e. V (z) V VMJa, S G]Je,(2) Jag(=)],
Assumption 4. There crists C(N,6) 2 O, and Č(N,8) 8) 2 0 monotonically decreasing with N, such that
1 N
BIe (((x))))
1 N Σ ((fo(sa)) S CCN,,),, [[Jo(a)] ((((())
Σ n=1
solon) S ((N,O), (8)
N
for all 0 E O, with probubility 1 - 8 over independent draws (Ii, Mn) p. Assumption 5. There exists a fensible solution E such that TE(((o(>)) v)) <e- Mv.
Assumption 1 holds for most losses utilized in practice. Assumption 2 is a requirement the richness of the parametrization In the particular case of neural networks the covering constant is upper bounded by the universal approximation bound of the neural network. Assumption 3 also holds for neural networks if we use smooth nonlinearities e.g. hyperbolic tangents. The uniform convergence property (8) is customary in learning theory to prove PAC lcarnability and is implicd by bounds on complexity measures such as VC dimension or Rademacher complexity (Mohri al.] [2018 Vapnik 1999. Shallv-Shwartz and Ben- Ben-David 2014h. The following theorem provides the desired bound.
Let fi X* be solutions of the empirical dual problem Under assump- tions there erists E argmingg L(A, fa" ,²²)²)) such that, with probability 1 - 55,
Proposition 1.
1 1p- 1 (vv) + (1 A)C(N, + O(((N,)))
(9)
where A max(A" ,²) and respectively.
C for constant C co, where μº, f0 solutions of (6)
Proposition I shows that the empirical dual problem 7 statistically consistent. That is to say. for any realization of N according to p. the difference between the empirical dual problem (7) and the statistical smooth learning problem 4 decreases as N increases. This difference is bounded in terms of the richness of the parametrization (v), the difficulty of the fit requirement (as expressed by the optimal dual variables μ²' ,²,fa"), and the number of samples (N). The guarantee has form typical for constrained learning problems (Chamon and Ribeiro 2020). Proposition states that we are able to predict what is the minimum norm of the gradient. that a function class can have while satisfying expected loss. This

---

is important, because we do not require access to the distribution of the samples p, only set of N samples sampled according to this distribution. On the other hand, Proposition [ does not state that by solving the dual problem 7 we will obtain solution of the primal problem 3 The following proposition provides a bound on the near feasibility of the solution
of 7 with respect to the solution of 3
Proposition 2.
Let fit X be solutions of the empirical dual problem 7 Under assump-
lions there erists 0+ E argming İ(0, f,,,;,,))) such that, with probability 56,
N
max #EM /VVaaa (=)11 P + P
1
Σ (ffa-(z)) (2n). - + 0(v) (())) and (10)
N
Ele(fg((z).)) S s ((v,6).
(11)
Proposition 2 provides near optimality, and near feasibility conditions for solutions Ò obtained through the empirical dual problem (7). The difference between the maximum gradient of the obtained solution & and the optimal value P is bounded by the number of samples N, as well as the empirical constraint. violation. Notice that even though the optimal dual variable js is not known, the constraint violation can be evaluated in practice, as only requires to evaluate the obtained function over the N given samples.
Remark 2 (Interpolators). In practice, the number of porameters in a parametric function (e.g. Neural Nelwork) lends to exceed the dimension of the impul, which allows functions to interpolate the data, i.e. to allain zero loss on the dataset. Proposition D. presents a connection to interpolating functions. By setting 6 = 0, if the function achienes zero error over the empirical distribution i.e. E(fg- (Ix), Un) 0, for all n E [NV, then the dependency on μ² disappears. This implies that over interpolating classifiers, the one with the mónimum Lipschitz constant over the samples, is probobly the one that attains the minimum Lipschitz constant over the whole manifold.
3.2 FROM MANIFOLD GRADIENT TO DISCRETE LAPLACIAN
We derive an alternative way of computing the integral of the norm of the gradient utilizing samples. To do so, we define the normalized point cloud Laplacian according a probability distribution X.
Definition 2 (Point-cloud Laplacian). Consider a set of points Iı, Iı,..., EN E M, sampled according to probability X ::M + R. The normalized graph Laplacian of So at E M is defined as
N Σ N ((), fo(xx))
1
fo(e)
(12)
for
W(2 1 Ge(z, with G.(z,
11
(13)
(4mt)a/2
(02) N G,(2,an), and W(x))
1 N
Σ GelEms mnn
(14)
N-1
As long as the function considered is smooth enough, the following convergence result holds: Proposition 3 (Point Cloud Estimate). Let A be the set of probability distributions defined compact d-dimensional differentiable manifold M isometrically embedded in RD such that 12
A (>: :
< X22) < b < 30, 20.12 00,1221 s oo and 1 S d < oc for all 2 E M), and let fe, with 0 E 9, be family of functions with uniformly bounded derivatives up to order 3 wanishing at the boundary AM. For any 6 > 0,8 > 0, for all N > No.
/f [IVIfo(())) AEA,8CO
sup
> 2 S6
26
(15)
where the point cloud laplacian D So is as defined in with t N 24244 for any a > 0.

---

The proof of Proposition [ relies two steps. First, relate the integral of the norm of the gradient over the manifold with the integral of the continuous Laplace- -elatram operator by virtue of Green's identity. Second, we approximate the value of the Laplace-Beltrenne Beltrami operator by the point-eloud Laplacian. Proposition connects the integral of the norm of the gradient of function fo with point cloud Laplacian operator, this result connects the dual problem 7 with the primal while allowing for more amenable way of computing the integral.
Remark 3 (Laplacian Regularization and Manifold Lipschitz). The dual problem (6) is closely related to the manifold regularization problem ( In particular, the two become equivalent by substituting p 4 -= and utilizing uniform distribution for X. The key difference between the problems is given by the dual variable X, which can be though as probabilily distribution over the manisoold that penalizes regions of the manifold where the norm of the gradient of fe is larger. The standard procedure in Laplacian regularization is to calculate the graph- Laplacian of the set of points L utilizing the heat kernel, and compute the integral by f Lf, where f = (fo(())...... fo(x)) In the case of Manifold Lipschitz, the same product con be computed, but utilizing the re-weighted point cloud laplacian.
3.3 DUAL ASCENT ALGORITHM
We outline an iterative and empirical primal-dual algorithm to solve the dual problem. Upon the initialization of for and Ao Poo we set to minimize the dual function as follows,
ak+1
02 no VoL(Ok. pk: At);
(16)
where no is a positive step-size. Note that to solve problem 16 we can either utilize the gradient version the the lagrangian (ef. equation (7),, or the point-cloud Laplacian (cf. equation 15 Consequent to updating 0, we update the dual variables follows,
luk + 7u (M
Σ
pk++1
Und
(17)
==1
Me+1(2n) = >x(xx)) + mIll V.l for all data points In
(18)
N
Ab+1 = argmin | | A such that Σ A = N.
(19)
n=1
where T/ 7/x positive step-sizes. Note that require convex projection over i to satisfy the normalizing constraint. In step (18) we require to estimate the norm of the gradient at data point In: which we estimate for the neighboring data points. Intuitively, the primal dual procedure increases the value of A(rx) at points in which the norm of the gradient is larger. The role of y is to enforce the loss E to be smaller than c, a larger value of would increase the relative importance over the norm of the integral. See Appendix F
4 NUMERICAL RESULTS
4.1 NAVIGATION CONTROLS PROBLEM
In this section, we consider the problem of continuous navigation of an agent. The agent's 's objective is to reach a goal while avoiding obstacles. The state space of the agent is given by its position, and navigates by taking actions on the velocity. We construct a square grid of points in the free space i.c. outside of the obstacles, and find the shortest path between two starting positions and the goal along the grid. For those two grid trajectories, we compute the optimal actions to be taken at each point in order to follow the trajectory. The learner equipped with both labeled trajectories, as well as the unlabeled point grid. To leverage the manifold
Method
Trajectories
ERM
85
Ambient Reg.
66
Manifold Reg.
77
Manifold Lipschitz
94
Table 1: Number of successful tra- jectories from 100 random starting points.
8

---

255 DS AT
B6 D5
25 15 0S RT
(a) Dataset
(b) Manifold Lipschitz.
(c) Dual variables A.
(d) ERM.
(e) Ambient Regularization.
(f) Manifold Regularization.
Figure 2: Figure 2a shows the training dataset, blue stars depict unlabeled point, and blue arrow the optimal action at the red star. Figure 2b shows the learned function using Manifold Learning, and 20 its associated dual variables associated. Figures 2d
2c 2
show the functions
learned using ERMM, ambient regularization, and Manifold regularization respectively.
structure of the data, we consider the grid of points,
and we construct the point cloud Laplacian considering adjacent points the grid. As mcasure of merit, we take 100 random points and we compute the trajectories. A trajectory successful it achieves the goal without colliding. The results are shown Table [ and the learned functions in Figure 2
4.2 GROUND ROBOT ERROR PREDICTION
In this real world experiment, we seek learn the error that model would make in predicting the dynamics of a ground robot Koppel et al. (2016). We posses trajectories, in the form of time series of the control signals of an iRobot Packbot mak- ing turns both pavement, and grass. For cach trajectory, the mismatch between the real and the model-predicted states quantified. Given dataset of trajectories and errors made by the model, the objective is to learn the error that model will make. Details of the experiment can
Method
Grass
Pavernet
ERM
0.42
0.0120
Ambient Reg.
0.31
0.0065
Manifold Reg.
0.38
0.0045
Manifold Lipschitz
0.25
0.0032
Table 2: Error Prediction accuracy for the Ground Robot Experiment.
be found in G.3
CONCLUSION
In this work, we presented a constrain learning method to obtain smooth functions over manifold data. We have shown that under mild conditions, the problem of finding smooth functions over a manifold can be reformulated as a weighted point cloud Laplacian penalty over varying probability distributions whose dynamics govern by the constraint violations. Three numerical examples validate the empirical advantages of obtaining functions that vary smoothly over the data.

---

REFERENCES
Adam M Oberman and Jeff Calder. Lipschitz regularized deep neural networks converge and generalize. arXiv preprint X88: 09540, 2018.
Chris Finlay, Adam M. Oberman, and Bilal Abbasi. Improved robustness to adversarial examples using lipschitz regularization of the loss. CoRR, bbs/1180.00053, 2018a. URL htttp://rxiv.orrt matps//11000000
Nicolas Coucllan. The coupling effect of lipschitz regularization in ncural networks. SN Compuler Science, 2(2):1 9, 2021.
Chris Finlay, Jeff Calder, Bilal Abbasi, and Adam Oberman. Lipschitz regularized deep neural networks generalize and are adversarially robust. arXiv preprint arXiv: 0908009400 2018b.
Patricia Pauli, Anne Koch, Julian Berberich, Paul Kohler, and Frank Allgöwer. Training robust neural networks using lipschitz bounds. IEEE Control Systems Letters, 6:121 126, 2021.
Vishaal Krishman, Al Makdah, Abed AlRahman, and Fabio Pasqualetti. Lipschitz bounds and provably robust training by laplacian smoothing. Advances in Neural Information Processing Systems, 33: 08:10024-10985, 2020.
Guanya Shi, Xichen Shi, Michael O'Connell, Rose Yu, Kamyar Azizzadenesheli, Animashrce Anandkumar, Yisong Yue, and Soon-Jo Chung. Neural lander: Stable drone landing control using learned dynamics. In 2019 International Conference on Robotics and Automation (ICRA), pages 1184-9790. TEEE, 2019.
Lars Lindemann, Haimin Hu, Alexander Robey, Hanwen Zhang, Dimos Dimarogonas, Stephen Tu, and Nikolai Matni. Learning bybrid control barrier functions from data. In Conference on Robot Learning, pages 1351 1370. PMLR, 2021.
Raghu Arghal, Eric Lei, and Shirin Sacedi Bidokhti. Robust graph neural networks via
probabilistic lipschitz constraints. arXiv preprint arXiv:2112.07575 2021.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normal- ization for generative adversarial networks. arXiv preprint
2018.
Liquan Zhao and Yan Liu. Spectral normalization for domain adaptation. Information, 11 (2):68, 2020.
Leon Bungert, René Raab, Tim Roith, Leo Schwinn, and Daniel Tenbrinck. Clip: Cheap lipschitz training of neural networks. International Conference on Scale Space and Variational Methods in Computer Vision, pages 307-319. Springer, 2021.
Misha Belkin, Partha Niyogi, and Vikas Sindhwani. On manifold regularization. In Interna- tional Workshop on Artificial Intelligence and Statistics, pages 17 24. PMLR, 2005.
Partha Niyogi. Manifold regularization and semi-supervised learning: Some theoretical analyses. Journal of Machine Learning Research, 14(5), 2013.
Zengyi Li, Yubei Chen, Yann LeCun, and Friedrich T Sommer. Neural manifold clustering and embedding. arXiv preprint arXiv:2201.1000, 2022.
Matthias Hein, Jean- Yves Audibert, and Ulrike von Luxburg. From graphs to manifolds weak and strong pointwise consistency of graph laplacians. In International Conference Computational Learning Theory, pages 470-485. Springer, 2005.
Mikhail Belkin and Partha Niyogi. Towards a theoretical foundation for laplacian- based manifold methods. In International Conference on Computational Learning Theory, pages 486-500. Springer, 2005.
M Tavassoli Kejani, Fadi Dornaika, and H Talebi. Graph convolution networks with manifold regularization for semi-supervised learning. Neural Networks, 127:160-160 167, 2020.
10

---

Mikhail Belkin and Partha Niyogi. Semi-supervised learning riemannian manifolds. Machine learning, 56(1):209 239, 2004.
Bo Jiang, Ziyan Zhang, Doudou Lin, Jin Tang, and Bin Luo. Semi-supervised learning with graph searting-convolutionn networks. In Proceedings of the IEEE/CV /CVP conference on compuler vision and pallern recognition, pages 11313 11320, 2019.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXi preprint arXiv:1609 NX0:16609.0207,,, 2016.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pages 40 48. PMLR, 2016.
Xiaojin Jerry Zhu. Semi-supervised learning litcrature survey. University of Wisconsin- Madison Deporbment of Compuler Sciences, 2005.
Bruno Lecouat, Chuan-Sheng Foo, Houssam Zenati, and Vijay R Chandrasekhar. Semi- supervised learning with gans: Revisiting manifold regularization. arXi preprint 1rX5::880..088 08957, 2018.
Yassine Ouali, Céline Hudelot, and Myriam Tami. An overview of deep semi-supervised learning. Xiv preprint (al::2006002270 2020.
Vivien Cabannes, Loucas Pillaud- Vivien, Francis Bach, and Alessandro Rudi. Overcoming the curse of dimensionality with laplacian regularization in semi-supervised lcarning. Advances in Neural Information Processing Systems, 34, 2021.
Luiz Chamon and Alejandro Ribeiro. Probably approximately correct constrained learning. Advances in Neural Information Processing Systems, 33:16722 16735, 2020.
Mchryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 1999.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Alec Koppel, Jonathan Fink, Garrett Warnell, Ethan Stump, and Alejandro Ribeiro. Online learning for characterizing unknown environments in ground robotic vehicle models. In 2016 SREE/RS, International Conference on Intelligent Robots and Systems (IROS), pages 626-633, 2016. doi: 10.1109/ F000/RRO.000 211.779111..
Luiz FO Chamon, Santiago Paternain, Miguel Calvo-Fullana, and Alejandro Ribeiro. Con- strained learning with non-convex losses. arXiv preprint arXiv:2103. 05134, 2021.
Andrzej Ruszczynski. Nonlinear optimization. Princeton university press, 2011.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Conver oplimization. Cambridge university press, 2004.
Manfredo Perdigao Do Carmo and J Flaherty Francis. Riemannian geometry, volume 6. Springer, 1992.
Steven Rosenberg. The Laplacian on Riemanmian Manifold: An Introduction to Analysis on Manifolds. London Mathematical Society Student. Texts. Cambridge University Press, 1997. doi: 10.1017/CB097800:
Weiran Wang and Miguel A Carreira-Perpinén. Perpinán. Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application. aix preprint arXiv: 1et.1309..54 2013.
11

---

Richard Zhang, Phillip Isola, Alexei A Efros, Eli Shechtman, and Oliver Wang. The unreasonable effectiveness of deep features as a perceptual metric. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 586-595, 2018.
Valentin Khrulkov, Leyla Mirvakhabova, Evgeniya Ustinova, Ivan Oscledets, and Victor Lempitsky. Hyperbolic image embeddings. In Proceedings of the IEEE/CT /CFF Conference on Compuler Vision and Pallern Recognition (CVPR), June 2020.
Tianbao Yang. Advancing non-convex and constrained learning: Challenges and opportunities. Al Mallers, 5(3):29 39, 2019.
Alexander Robey, Luiz Chamon, George J Pappas, Hamed Hassani, and Alejandro Ribeiro. Adversarial robustness with semi-infinite constrained learning. Advances in Neural Infor- mation Processing Systems, 34:6198- -6215, 2021.
Juan Cervino, Luana Ruiz, and Alejandro Ribeiro. Training stable graph neural networks through constrained learning. In ICASSP 2022-2023 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4223-4222 IEEE, 2022.
Zebang Shen, Juan Cervino, Hamed Hassani, and Alejandro Ribciro. An agnostic approach to federated learning with class imbalance. In International Conference on Learning Represenlations, 2021.
Juan Elenter, Navid NaderiAlizadeh, and Alejandro Ribeiro. A lagrangian duality approach to active learning. arXiv preprint 0rXiv2222.04100. 2022.
Santiago Paternain, Luiz Chamon, Miguel Calvo- and Alejandro Ribeiro. Constrained reinforcement learning has zero duality gap. Advances in Neural Information Processing Systems, 32, 2019.
Santiago Paternain, Miguel Calvo-Fullana, Luiz FO Chamon, and Alejandro Ribeiro. Safe policies for reinforcement learning via primal-dual methods. IEEE Transactions on Automatic Control, 2022.
Agustin Castellano, Hancheng Min, Juan Bazerque, and Enrique Mallada. Reinforcement learning with almost sure constraints. arxi preprint arXiv:2112.00 12.05198. 2021.
Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achieving zero constraint violation for constrained reinforcement. learning via primal-dual approach. arXiv preprint #rXiv:2109.06332 2021.
Mohammadhosein Hasanbeig, Alessandro Abate, and Daniel Kroening. Logically-constrainee reinforcement learning. or preprint arXiv:1501.00099 2018
Mark Eisen, Clark Zhang, Luiz FO Chamon, Daniel D Lee, and Alejandro Ribeiro. Learning optimal resource allocations in wireless systems. IEEE Transactions on Signal Processing, 67(10))2775-21 2790, 2019.
Shufei Zhang, Kaizhu Huang, Jianke Zhu, and Yang Liu. Manifold adversarial train- ing for supervised and semi-supervised learning. Neural Networks, 140:282-201 2233, 2021. ISSN 0893-6080.
doi: https: //oss:////oor/////// 10..oorr//0001011. 10.11100.11... wt0.1066j...euet..200 2021 03.0031. URL https
Mare Khoury and Dylan Hadfield-Menell. On the geometry of adversarial examples. arXiv preprint arvi 00525, 2018
Xingjun Ma, Bo Li, Yisen Wang, Sarah M Erfani, Sudanthi Wijewickrema, Grant Schoenebeck, Dawn Song, Michael Houle, and James Bailey. Characterizing adversarial subspaces using local intrinsic dimensionality. arXiv preprint arXiv:1801. 026113, 2018.
Seyed-Mohsen Mezsavi-Dezfooli, Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Robustness via curvature regularization, and vice versa. In Proceedings of the SEEE/CE Conference on Computer Vision and Pattern Recognition, pages 9078-9088800 2019.
12

---

Charles Jin and Martin Rinard. Manifold regularization for locally stable deep neural networks. arXw preprint 2iv: 042000004.6,... 2020.
Carlos Lassance, Vincent Gripon, and Antonio Ortega. Laplacian networks: Bounding indicator function smoothness for neural networks robustness. APSIPA Transactions on Signal and Information Processing, 10, 2021.
David Stutz, Matthias Hein, and Bernt Schicle. Discntangling adversarial robustness and gencralization. In Proceedings of the IEEE/CT /CF Conference on Computer Vision and Paltern Recognition, pages 6976 6987, 2019.
Mihaela Rosca, Theophane Weber, Arthur Gretton, and Shakir Mohamod. A case for neural network smoothness constraints. In Jessica Zosa Forde, Francisco Ruiz, Mclanic F. Pradier, and Aaron Schein, editors, Proceedings "I Can't Believe It's Not Better!" at NeurIPS Workshops, volume 137 of Proceedliggs of Machine Learning Research, pages 21 32. html Sébastien Bubeck and Mark Sellke. universal law of robustness via isoperimetry. Advances in Neural Information Processing Systems, 34, 2021.
PMLR, 12 Dec 2020. URL httpps://proceeddings mlr
Matthias Hein, Jean-Yves Audibert, and Ulrike von Luxburg. Graph laplacians and their convergence on random neighborhood graphs. Journal of Machine Learning Research, (6), 2007.
David B Dunson, Hau-Tieng Wu, and Nan Wu. Spectral convergence of graph laplacian and heat kernel reconstruction in Lo from random samples. Applied and Computational Harmonic Analysis, 55:282 336, 2021.
Hau-Time TinnTiing Wu and Nan Wu. Think globally, fit locally under the manifold setup: Asymptotic analysis of locally linear embedding. The Anmals of Statistics, 96(6B):3805-381) 2018.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in Neural Informalion Processing Systems, 32, 2019.
Tom Z Jiahao, Kong Yao Chee, and M Ani Hsieh. Online dynamics learning for predietive control with an application to acrial robots. arXiv preprint arXic:2207.093/ 2022.
Kong Yao Chee, Tom Z Jiahao, and M Ani Hsich. Knode-mpe: A knowledge-based data- driven predictive control framework for aerial robots. IEEE Robotics and Automation Letters, 7(2):2819 2826, 2022.
Tom Z Jiahao, M Ani Hsich, and Eric Forgoston. Knowledgo-based learning of nonlinear dynamics and chaos. Chaos: An Interdisciplinary Journal of Nonlinear Science, 31(11): 111101, 2021.
13


Reviews:
[{"review_id": "pDGQQOo8vMe", "reviewer": "Reviewer_2RoL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The authors propose a technique to learn a globally Lipschitz function when the data lie near a manifold. They derive a suitable constrained optimization problem together with the associated optimization scheme. Theoretical results are provided which show that under some conditions it is sensible to solve the empirical optimization problem as it approximates the true problem. The effectiveness of the approach is demonstrated in the experiments. ", "summary_of_the_review": "Questions:\n1. In Euclidean spaces it is known that if the norm of the gradient is bounded then the function is Lipschitz. Does the same result hold when $f$ is defined on Riemannian manifolds?\n\n2. I think that the efficiency of your method highly depends on the construction of the graph Laplacian, and for this reason some discussion and demonstrations should be included.\n\n3. Similarly, I think that the experimental setting is a little bit short compared to the rest of the paper. In my opinion some additional (synthetic) experiments as the one in Fig. 1 can help, as well as classic semi-supervised learning problems with real data.\n\n4. Minor: \n\t- In the sentence after Eq. 6 there is a typo in the integral.\n\t- In Eq. 9 should it be $P^*$ or $D^*$? \n   \n   \nI think that the paper has a lot of merits and the technical content seems solid. Of course, this is theoretical contribution, but I since it focuses on a particular problem that has potential benefits in applications, I would like to see some additional (synthetic/real-world) experiments.", "strength_and_weaknesses": "There are many parts of the paper that I like e.g. explaining some steps in good detail, but there are few parts which are a bit unclear to me. The introduction of the problem is ok, relying on the example in Fig. 1 and on the difference between favour vs guarantee that a function is globally Lipschitz. Maybe you could elaborate a bit more why using the manifold information is better. The technical content seems reasonable, but I have not checked all the derivations in details. I think that additional experiments should be conducted.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "k1plm_lkaU", "reviewer": "Reviewer_HRYo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper learns smooth functions (as measured by the Lipschitz constant) on Riemannian manifolds embedded in Euclidean space. Notably, these methods assume the manifold is unknown, presenting a significant technical challenge. The paper then develops several optimization problems and shows to make these tractable through various analyses and perspectives. Empirical results are presented for two tasks.", "summary_of_the_review": "I lean to accept the paper, mostly due to the technical novelty and very clear exposition. However, I do think that the experimental setup is quite weak, and the applications may be rather limited. However, since this a general trend with manifold learning papers in general, I am willing to somewhat overlook them given the technical novelty.", "strength_and_weaknesses": "Strengths\n-----------\n* The method is quite nicely developed. In particular, I found the construction to be well-reasoned and nicely created, from the initial optimization problem formulation to the final algorithmic implementation.\n* The proposed method seems to be technically correct. In particular, each component is justified nicely.\n* The method is quite a novel departure from previous methods, as it handles what feels like a significantly more complex problem formulation. In particular, it merges both lipschitz and manifold constraints.\n\nWeaknesses\n---------------\n* The experimental section is rather weak/toy.\n* The method may not be very applicable. In particular, outside of the standard manifold learning justifications, I question how well this will scale to high dimensional data/large number of data points.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Q4MdvzsQahT", "reviewer": "Reviewer_FBLh", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studied the problem of learning a Lipschitz continuous function on a manifold. The authors used the Lagrangian dual problem and showed that its empirical version can be an approximation of the primal with statistical consistency. The authors further showed that, by using a weighted point cloud Laplacian, the evaluation of manifold Lipschitz constants can be recast in a more amenable form. The numerical results show the effectiveness of the proposed method.\n\n\n", "summary_of_the_review": "It is not easy for the reviewer to follow this paper, because of the insufficient background and motivation for the problem formulation considered. The authors should make clearer the main contributions of this paper compared to the previous work.", "strength_and_weaknesses": "Strength:\n\nThis paper presents a computationally efficient method to learn a Lipschitz continuous function on a manifold, which is a combination of techniques from semi-infinite constrained learning and manifold regularization. Theoretical analysis is also provided.\n\nWeakness:\n\n1. The authors should provide more background and motivation about the problem formulation, i.e., Problem (3). Otherwise, it is difficult for readers to follow.\n\n2. The authors should provide some insights for Proposition 3 about why the integral of the manifold gradient term can be approximated by the point cloud Laplacian term.\n\n3. It's confusing about which problem do the updates (17)-(19) aim to solve.\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject