- Rating
- 2
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
Please see "questions for authors"
Critical strengths
Please see "questions for authors"
Critical weaknesses
Please see "questions for authors"
Questions for authors
I want to start by saying that I found the abstract very hard to follow. I strongly encourage the authors to re-write the abstract in a way that states upfront : what is the problem at hand and what is the proposed solution and contribution.
..Moreover, the submission stands at 80 pages or so : conference papers are supposed to be short and to the point, and a conference review process is too short for anyone to go over so many pages of appendices.
My second recommendation is please shorten your submission to a readable length. I think it is perfectly fine if the proofs are not included, but only sketched, and if background material is replaced by references to litterature (this is where it came from in the first place).
The introduction does a better job of stating the main problem, which I find quite interesting, and also relevant to applied problems. However, I think the auhots attempt something that is way too difficult : to express the problem and its intended solution in written language (in English).
I recommend the introduction use more mathematics (equations/symbols) to write down the main problem in a clear fashion (roughly, one clearly explained equation is much easier to follow that several dense paragraphs of text).
The "relation to prior work" paragraph is extremely confusing and hard to follow. You should redo completely !! Also, I noticed the use of "We", while the submission is supposed to be anonymous.
In Section 2 "Setting" is quite clear to me, and I like the fact that it is concise, but I also ask myself whether non-experts will be able to make any sense out of it. I do not ask you to change anything here, but just share with you this issue.
I agree that Proposition 2.2. is elementary, and I think there is almost no point in discussing its proof. It would be much better to explain how it is going to be used.
Recommendation : what is a "Sobol’ or Halton sequence" .. I have never heard of that. Please explain or provide a reference.
In the paragraph "Sturm's contraction" :
(a) is Log_x(y) 1-Lipschitz ? Its covariant derivative is the Hessian of squared distance, and that is not bounded !
(b) the remainder of the paragraph does not need the above statement and moreover perhaps does not belong here in the first place (it is supposed to explain Thm E.3).
Section 3 :
The opening sentence is very problematic !! You claim that the norm of G_x is infinite at the cut-locus, but G_x is not defined there. Moreover, its norm remains bounded near the cut locus. You are talking about a problem that does not exist !!
Do Propositions 3.3 and 3.4 even address the main issue of the paper (behavior near singularity..) ? if you impose that g is supported away from the singularity (at a fixed distance), you are not dealing with behavior near the singularity.
Conclusion :
Strengths :
(1) the paper raises an important issue, and attempts to address it in a rigorous mathematical way
Weaknesses :
(2) the paper is incomprehensible to non-experts (..I was able to follow it, but I believe many if not most ICLR attendees will not find it cogent/relevant), and often uses obscure language.
(3) the main results in Section 3 are based on strong hypotheses that do not hold in practice and (mathematically) make everything a bit too easy
4 comments
Response to Reviewer 1Dcm (2/4)
Q10, Q13 (hypotheses of Theorems 3.3 and 3.4).
if you impose that g is supported away from the singularity (at a fixed distance), you are not dealing with behavior near the singularity.
This is not what the theorems assume. In Theorem 3.3(i), are normal coordinates centred at the singular point , and for the Fréchet gradient at the singular point is , the cut point itself, not . The integrand is plus an function, with " supported in ": a ball around the singular point. is allowed and is the case of interest; the lower bound (Theorem D.11) assumes it. The proof of Theorem D.6 removes a ball of radius around and shrinks it with the discrepancy, . Up to constants, the part outside the ball costs , and the part inside is at most times the mass the rule puts in the ball, which positivity of the weights bounds by . No fixed distance enters. Corollary D.7 applies the theorem to , and Table 1 lists the resulting exponents; the revised PDF now states its gradient bound in the main text, in the paragraph "The Fréchet gradient on spheres" after Theorem 3.3. Theorem 3.3(i) now names the ball as the ball around the singular point and lists the dependence of its constant as Theorem D.6 does.
On "strong hypotheses that do not hold in practice": Theorem 3.3(i) has four hypotheses, and the Fréchet mean problem on the sphere with a smooth data density satisfies all of them. (1) The manifold is a round sphere, the space of mean directions and normalized embeddings. (2) The error is measured by the worst-case error in , , for the uniform measure, and the data density enters the loss as a weight (Setting paragraph of Section 2). A known sampling law is the premise of every QMC method, because the points are constructed for it. The theorem asks in addition that its density relative to the uniform measure be smooth, as it is for the von Mises-Fisher laws of Section 5. This covers injected noise and model laws; for data given only as a sample, QMC does not apply at all, with or without a cut locus. (3) The rule has nonnegative weights, as every equal-weight average does. (4) The integrand is bounded with a point singularity of the displayed form and . The Fréchet-mean gradient satisfies (4) with no further assumption: by Eq. (4), has , and , uniformly in and (Corollary D.7). The submission states where the exponent is proved and where it is a prediction (lines 091-093 and 247-249): it is proved for point singularities on spheres and for point and polygonal singularities in the unit square, and it is a prediction for cut loci of codimension one on curved manifolds.
On "too easy": the upper bound has a short proof, and Theorem 3.4 shows that it is nevertheless the right one. Parts (a,b) construct node sets for which no larger exponent holds, so no bound in terms of the discrepancy alone improves the exponents (in the square, the logarithm) of Theorem 3.3; these node sets are built for the purpose and are not sets of optimal order in . Part (c) shows that every equal-weight rule with distinct nodes has worst-case gradient error at least .
Response to Reviewer 1Dcm (3/4)
Q8 (Sturm's contraction).
(a) is Log_x(y) 1-Lipschitz ? Its covariant derivative is the Hessian of squared distance, and that is not bounded !
(a) Yes, in the variable the sentence names. The statement is that is 1-Lipschitz for fixed : the variable is the data point . The Hessian of the squared distance is the derivative in the other variable, . On a Hadamard manifold it is at least the identity, and it is unbounded when the curvature is bounded above by a negative constant (in hyperbolic space its largest eigenvalue is with ). That concerns the derivative in and does not bear on the statement. The derivative in is , of norm at most one, because does not decrease distances in nonpositive curvature. Proposition C.21 gives the proof: in the geodesic triangle the angle at is at most its Euclidean comparison angle, hence
(b) The rest of the paragraph uses this constant. With , the one-point bound (Proposition 2.2(c), in its appendix form C.7(c) for general probability measures) and 1-strong convexity give . Kantorovich-Rubinstein duality bounds the integral of a 1-Lipschitz function against by ; a Lipschitz constant would give . The pointer to Theorem E.3 belongs to the last clause of the paragraph: the same inequality with the Hardy-Krause class in place of the Lipschitz class gives the QMC rate of Karcher means. The revised sentence now has the words "for fixed " and the pointer to Proposition C.21.
Q1, Q3, Q12 (abstract, introduction, vocabulary). The revised PDF now states the problem in standard terminology in the introduction: the text after Eq. (1) and the paragraph that follows define the point set, the rule and the certificate, display the QMC error bound and the gradient error, and name the three bounds of Section 2. The abstract is kept. It states the problem (what a QMC error bound says about a Riemannian minimizer), the main result (the exponent , proved and sharp in the settings it lists) and the scope; one clause now says that the singular integrand is that of squared distances. The paper's own terms ("charge", "potential", "field") are defined in Definition 2.1 and are kept, because on the sphere they are literal: the cap discrepancy is the energy of the charge, and the value and gradient errors are its chordal potential and field at the antipode up to smoother remainders (Proposition 4.1). Each now appears next to its standard name (Section 1; Table 3 in Appendix A). The equations are also in the general response above.
Q4 (prior-work paragraph; "We"). The paragraph is now set out as three labelled lists in the revised PDF: what we use, related work, and what is new. On "We": the first-person plural identifies no one. The PDF lists "Anonymous authors" and contains no names, affiliations or links.
Q6 (Proposition 2.2 is elementary). The submission says the same: "Each part is one line" (line 162) and "The readings of the field are known arguments organized around one object" (lines 118-119). None of it is claimed as new. Its use: part (c) reduces the minimizer error to the integration error of one integrand, , which is the quantity Theorems 3.3 and 3.4 bound when it is singular; parts (a) and (b) give the sample complexities of Corollary 2.3. The revised text now states this use before the proposition.
Q7 (Sobol' and Halton sequences). They are the two standard low-discrepancy sequences in : their first points have star discrepancy , against order for random points (Halton, 1960; Sobol', 1967; Dick, Kuo and Sloan, 2013). The submission cites them and states this bound in Appendix B.2. The revised introduction now describes them at first use, with the references, and Corollary 2.3 cites them.
Response to Reviewer 1Dcm (4/4)
Q2 (length). The main text is 9 pages in the submission and 10 in the revision. The other pages are proofs, experimental protocols and a notation table. ICLR sets no limit on appendices and does not require reviewers to read them. We keep the complete proofs, because the contribution consists of theorems and their soundness can be checked only against proofs. Table 2, at the start of the appendix ("How the appendix is organized"), names for each statement of the main text the appendix result that proves it, so one theorem can be checked without reading the rest.
Q5 (Setting). No change was requested; for readers from the optimization side, the revised introduction now contains a short QMC primer (the text after Eq. (1)).
If the pointers under Q8, Q9 and Q10 resolve the soundness concerns, we would appreciate it if you would reconsider the assessment.
Response to Reviewer 1Dcm (1/4)
Thank you for the paragraph-level reading. Each of the three technical objections (Q9, Q10 with Q13, Q8) is answered by a statement that is in the submission and is proved there. For each we give the statement, its location, and a short derivation. A revised PDF is uploaded, with changes in blue; line numbers below refer to the submitted PDF.
Q9 (Section 3, opening sentence).
The problem exists, and the sentence is about a different norm from the one in the objection. It reads: "The three readings need ∥Gx∥H<∞. For F=21d2 the field integrand is Gx=−Logx, and where the data can reach the cut locus of x this norm is infinite." "This norm" is the function-space norm ∥Gx∥H=sup∥v∥=1∥⟨Gx,v⟩∥H of the map y↦Gx(y) (Definition 2.1), not the pointwise length ∥Gx(y)∥. The submission nowhere says that the pointwise length is unbounded: ∥Logxy∥=d(x,y)≤π on Sd, and Theorem 3.3 assumes that g is bounded. A QMC error bound ∣QNg−Pg∣≤∥g∥HDH(QN) needs the function-space norm, and on the sphere that norm is infinite for the Sobolev classes that carry QMC rates, the classes Hτ(Sd) with τ>d/2: their members are continuous, and Gx has no continuous extension to −x. Section 4 treats the polar chart in which the norm is finite (Proposition 4.2(a)). In normal coordinates z centred at the antipode −x (Eq. (4)),
Logx(Exp−xz)=π∥z∥z−z.
The first term is bounded, homogeneous of degree 0, and discontinuous at z=0. The gradient of its component along v has length π∣sin∠(z,v)∣/∥z∥, whose square is not integrable near z=0 in two dimensions, so ⟨Logx(⋅),v⟩∈/H1(S2); Proposition E.8 proves this. The L2 cap discrepancy bounds integration errors only for functions in H3/2(S2). The introduction states the same fact (lines 080-083).
What is lost is rate, not convergence. On S2, point sets whose cap discrepancy has the optimal order N−3/4 integrate H3/2 functions at that rate. For the Fréchet gradient Theorem 3.3 gives N−3/5 for the same point sets, and Theorem 3.4 shows that this exponent of the discrepancy cannot be improved and that no equal-weight rule with distinct nodes yi does better than πmaxih(yi)/N uniformly in x, which is of order 1/N for a positive density h; for smooth integrands spherical t-designs with N of order t2 reach N−τ/2 for every τ.
On "Gx is not defined there": it is undefined at the single point y=−x only, a set of measure zero. Theorem D.6 allows any bounded value at that point, and the gradient-error statements are for x∈/−suppQN (Theorem 3.4(c), Corollary D.7), so no statement depends on it. So that the two norms cannot be confused, the opening of Section 3 in the revised PDF now names the norm in words: the pointwise length is at most π, and the function-space norm ∥Gx∥H of Definition 2.1 is infinite for every Sobolev class Hτ(Sd) with τ>d/2, the classes that carry QMC rates.