- Rating
- 2(+1)
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The authors derive a numerically robust Riemannian Frank--Wolfe algorithm. The acceptance rule is derived by combining a geometric tolerance from strong convexity of the feasible set with a quadratic descent tolerance. Accepted iterates remain feasible and retain the standard sublinear bound for smooth geodesically convex objectives.
Critical strengths
first numerically robust riemannian frank-wolfe algorithm
Critical weaknesses
I have to major issues with this paper:
The first one is that the motivation of the paper is not present. It is not clear at all for me that small numerical variations will induce an substantial error on the feasibility of the algorithm. Actually the main numerical experiment presented in the paper is not good enough in my opinion as it does not show a sufficient advantage of the proposed method. I also suspect that the standard FW method is much faster than the algorithm proposed by the author. Indeed in the numerical experiment the comparaison is never done with time as x axis. One other concern I have is that on a technical side, the paper does not seem to introduce novel ideas for the proofs The theory seems pretty standard.
Questions for authors
Can the authors present more convincing numerical settings that strongly motivate the algorithm they introduce? Can they also compare the methods with time in x axis? Finally can the authors details the points in the proofs that are new and introduced in there analysis?
3 comments
Motivation, running time, novelty, and new settings (2/2)
Novelty of the proofs.
On a technical side, the paper does not seem to introduce novel ideas for the proofs. The theory seems pretty standard. [...] Can the authors details the points in the proofs that are new and introduced in there analysis?
Reply. The convergence proof of Section 4 is the classical Frank–Wolfe argument with one additional error term. The new arguments are the following.
a) Theorem 5.1(i), proof in Section A.2. The definition of strong convexity places metric balls around chord points. The proof turns them into first-order feasible directions at the base point by shrinking the perturbation with a local Lipschitz constant of the exponential map, which tends to one, and obtains an distance to the set. It uses no injectivity, no curvature bound, and no boundary regularity. In a Hilbert space the statement is the classical normal-cone characterization. On a manifold it does not follow from the scaling inequality used in earlier Frank–Wolfe analyses, which degenerates at boundary points (Remark C.3).
b) Theorem 5.1(ii). Optimality of the oracle target makes the pulled-back gradient an inward normal at . The identity then converts the margin at into the gap at . This is why the inequality has a multiplicative factor and no additive residual.
c) Proposition 5.2. After lifting a chord to the spherical cover, its inner product with the centre solves a linear second-order equation. This gives the exact worst-case clearance and the sharpness of the modulus.
d) Theorem A.20 and Proposition A.22. A counterexample shows that the hypotheses of a published sublevel-set theorem are insufficient, and the theorem is restored under an ambient-tube assumption.
e) Theorem D.5. Under an exact feasible oracle and the primitive model of Assumption D.1, a first-exit argument shows that a fixed number of sub-steps and a precision logarithmic in keep the computed chart path in its domain and the total error within the accepted budget.
f) New in the revision. Proposition E.2 reduces the linear oracle on a rotation ball to one dimension by a projection argument. Proposition E.3 transfers the modulus to pose balls by a Hessian comparison and a Sturm argument. Proposition E.1 obtains a gap-relative progress tolerance from convexity at the accepted point.
Numerical settings.
Can the authors present more convincing numerical settings that strongly motivate the algorithm they introduce?
Reply. The revision adds two settings. Experiment L is a synthetic pose-fusion problem on with a pose ball as keep-in set. Unguarded fp16 storage of the pose loses 2.96 orders of magnitude in accuracy, and 2,718 of the 5,996 fp16 proposals near the optimum lie outside the pose ball. The endpoint guard prevents both. Experiment J is a fully validated run, in which the oracle and every update are certified by interval arithmetic.
I thank the authors for the clarifications and the additional experiments I have revised my score but I still think that the paper is slightly below the standard of the conference
Motivation, running time, novelty, and new settings (1/2)
Motivation.
Reply. Numerical error has two measured effects in our experiments, and the second is the larger one.
Feasibility. Near a boundary-active solution the exact update has a clearance that shrinks with the step, while a storage error is fixed. In Experiment G, half-precision (fp16) storage of a feasible float64 endpoint is infeasible in 10 of 216 near-boundary cases, with an error up to 4.3 times the clearance. In Experiment H, 382 of the 12,000 fp16 proposals are infeasible. In the new pose problem of Experiment L, 2,718 of 5,996 are, by up to 1.85 mm.
Accuracy. A feasible perturbation can still erase the progress of a step. Unguarded fp16 storage keeps every iterate feasible and loses 1.74 orders of magnitude in the final gap in Experiment H, 2.02 in Experiment J, and 2.96 in Experiment L, where the final pose is 8.3 mm and 0.20∘ away from the float64 result. A membership guard does not prevent this loss. The new Experiment K shows the mechanism in isolation. An endpoint error that costs a quarter of the step's progress lowers the convergence exponent from 2.00 to 1.55, whereas an error within the accepted budget leaves it at 2.01.
The revision states this motivation in the Introduction with the 1.74 figure.
Advantage and running time.
Reply. We added the comparison with time on the horizontal axis (Table 30, Figure 10). It is run sequentially in one process on the boundary-active instances.
Standard Riemannian Frank–Wolfe is 4 to 5% faster per iteration than the endpoint-guarded methods. At least 95% of the time is spent in the gradient and the linear oracle, which all methods share. With the planar oracle of Proposition E.2 an iteration costs 0.48 ms for standard Riemannian Frank–Wolfe and 0.68 to 0.75 ms for the endpoint-guarded methods.
The endpoint guard provides a guarantee at the cost measured above. Every accepted iterate is feasible, the convergence rates are retained, and a low-precision kernel that would stall is brought back to the accuracy of the reference. The revision strengthens the evidence in three ways. Experiment J certifies the oracle and every update by interval arithmetic and returns a certified bound on the objective gap of each run. Under the gap-relative progress tolerance of Proposition E.1 with the endpoint clearance as geometric term, Experiment I accepts fp32 natively on 63.7% of the boundary-active steps instead of 6.5%. Experiment L applies the endpoint rule to a pose problem.