Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.



strength_and_weaknesses: Strength:

This 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.

Weakness:

1. The authors should provide more background and motivation about the problem formulation, i.e., Problem (3). Otherwise, it is difficult for readers to follow.

2. 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.

3. It's confusing about which problem do the updates (17)-(19) aim to solve.




clarity,_quality,_novelty_and_reproducibility: The authors should provide more background and motivation about the problem considered, such that readers could understand it better. The main contributions of this paper should be clarified clearly. The novelty of the paper is good.
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strengths
-----------
* 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.
* The proposed method seems to be technically correct. In particular, each component is justified nicely.
* 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.

Weaknesses
---------------
* The experimental section is rather weak/toy.
* 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.
clarity,_quality,_novelty_and_reproducibility: Clarity
--------
I found the paper to be very clear and concise. In particular, the overall structure of paper (going from problem to solution to implementation) is quite nice and makes the paper quite enjoyable to read.

Quality
--------
I found the paper to overall be of pretty high quality. In particular, the contributions are quite nicely developed, and the overall contributions are generally well-formulated.

Novelty
---------
The paper is reasonably novel. In particular, it approaches and established problem and develops a novel methodology to sharpen the constraints.

Reproducibility
-----------------
There was code to reproduce the experiments.
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
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.
clarity,_quality,_novelty_and_reproducibility: The proposed idea seems to be an extension of the method from the Euclidean space on manifolds. This constitutes a potentially significant contribution, bit I think that the empirical evaluation should be extended. The paper is well written and there are only few spots where it is unclear.
summary_of_the_review: Questions:
1. 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?

2. 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.

3. 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.

4. Minor: 
	- In the sentence after Eq. 6 there is a typo in the integral.
	- In Eq. 9 should it be $P^*$ or $D^*$? 
   
   
I 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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a method to learn a a Lipschitz continuous function on a manifold that utilizes a weighted Laplacian penalty. The proposed method is theoretically justified by giving a bound on primal-dual gap and evaluating the weighted Laplacian penalty empirically computed. The effectiveness of the proposed method is investigated through some numerical experiment.  

The proposed method seems convincing. It is nice that the authors presents a solid theoretical justification on the proposed method. The writing of the paper is clear.   
On the other hand, the reviewers raised some concern on the paper. Indeed, some reviewers (HRYo and 2RoL) pointed out the numerical experiments are weak while they appreciate its theoretical value. Some more extensive experiments with (synthetic/real world) data, different tasks and comparison with more baseline methods would strengthen the paper.  
Most of the theoretical concerns (mainly its clarity) raised by the reviewers were addressed during the rebuttal period. However, I (AC) personally have some additional concerns on the theoretical part. The proofs of Propositions 1 and 2 seem okay, but Proposition 3 requires some revision. Indeed, the authors try to show the bound by evaluating the probability of the event $C_N$ (Eq.(167) in the supplementary). However, there is no explanation about the choice of $z$ and $\theta$ in the definition of $C_N$. The bound should hold uniformly over the choice of $z$ and $\theta$, but there is no description on this point. Actually, the Hoeffding’s inequality in Eq.173 is provided only for a fixed $\theta$ (it should be noticed that the bound should hold uniformly over $\theta$ instead of arbitrary fixed $\theta$). The same argument applied to Eq.(175) with respect to $z$. To obtain a uniform bound, a standard approach requires to utilize techniques such as Rademacher complexity and covering number, but this paper overlooks this point. 

Since this is a rather theoretical paper, the theoretical part is expected to be more solid. Otherwise, the numerical experiments can be much improved. For these reasons, this paper requires revision so that it is accepted in ICLR. 

==   
Here is another minor concern by AC. The duality gap requires Assumption 4, but the bound in Assumption 4 is given for *all* $\theta$, that means that, the bound should hold uniformly on the model *without* the Lipschitz regularization. Due to this point, the theoretical bound can fail to show the benefit of the Lipschitz regularization because $\hat{\zeta}$ (which should be valid on the entire model) becomes a bottleneck. This can be improved by localizing the bound on the subset of the model with a Lipschitz continuity constraint.   

justification_for_why_not_higher_score: Although this paper gives an interesting method, the numerical experiments are quite weak. If we consider this is a theoretical paper, the theoretical analysis can be improved mainly by improving the dependency on $\hat{\zeta}$ defined in Assumption 4. Hence, this paper is a little bit under the bar of acceptance.
Decision: Reject