acceptodds
Under review as a conference paper at ICLR 2027

Certified Feasibility for Inexact Riemannian Frank–Wolfe on Strongly Convex Sets

Abstract

We study constrained optimization on Riemannian manifolds where every iterate must remain feasible despite numerical approximation of the updates. Riemannian Frank–Wolfe preserves feasibility by moving along geodesics within a geodesically convex constraint set. Numerical approximation and finite-precision storage, however, can destroy this guarantee even when the output remains a valid manifold point. For numerical maps, we derive an acceptance rule combining a geometric tolerance from strong convexity of the feasible set with a quadratic descent tolerance; given feasible oracle targets, valid error bounds, and the stated oracle-accuracy and step-schedule conditions, accepted iterates remain feasible and retain the standard sublinear bound for smooth geodesically convex objectives. We then derive an intrinsic tangent-cone margin and, under smooth logarithms, an exact-oracle scaling inequality with a multiplicative conditioning factor. We use this inequality to transfer known faster rates when the gradient norm is bounded away from zero. We derive sharp rotation-ball formulas that make the geometric tolerances explicit. Finally, for a fixed-sub-step Euler integrator in a rotation chart, we prove that mantissa precision logarithmic in the inverse target accuracy suffices, given an exact feasible oracle, the stated primitive-error model, and sufficient available precision. Rotation experiments show that the acceptance rule maintains feasibility and recovers reference accuracy under low-precision storage through accurate fallback.

Primary area:
optimization
Keywords:
Riemannian optimization, Frank-Wolfe methods, geodesically strongly convex sets, inexact optimization, finite-precision analysis

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 2 reviews, above 27% of the others.
Reviewer_X8TGOpenReview ↗
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
AuthorsOpenReview ↗

Motivation, running time, novelty, and new settings (1/2)

Motivation.

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.

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∘0.20^\circ 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.

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. [...] Can they also compare the methods with time in x axis?

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.

methodms per iterationtime to gap 10−510^{-5}
standard Riemannian Frank–Wolfe, float645.080.75 s
fp16 storage, no guard5.22not reached
fp16 storage, membership guard5.19not reached
fp16 storage, endpoint guard5.340.80 s
fp32 storage, endpoint guard5.290.77 s

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.

AuthorsOpenReview ↗

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 Λt\Lambda_t of the exponential map, which tends to one, and obtains an o(t)o(t) 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 qq makes the pulled-back gradient (DqLog⁡x)∗grad⁡F(x)(D_q\operatorname{Log}_x)^{*}\operatorname{grad} F(x) an inward normal at qq. The identity DqLog⁡x[Log⁡qx]=−Log⁡xqD_q\operatorname{Log}_x[\operatorname{Log}_qx]=-\operatorname{Log}_xq then converts the margin at qq into the gap at xx. 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 1/ε1/\varepsilon 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 SO(3)×R3\mathrm{SO}(3)\times\mathbb{R}^3 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

Reviewer_fLcMOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper derives endpoint-error conditions for feasibility and for preserving convergence guarantees of inexact Riemannian Frank–Wolfe optimization on geodesically strongly convex sets.

Critical strengths
  • The theoretical analysis is solid; the proofs that I checked are correct.
  • The introduction of an inexact variant could make Riemannian Frank–Wolfe more broadly applicable.
Critical weaknesses
  • The mathematical analysis is quite classical and mostly leverages tools from Euclidean and Riemannian Frank–Wolfe analysis.
  • There is no general certified numerical oracle that could enable broad applicability. Adding at least one complete implementation example with validated primitive bounds and certified oracle feasibility/accuracy could strengthen the paper.
  • The experiments do not showcase a real-world use case. Another experiment that could strengthen the paper is testing the faster-rate prediction under controlled endpoint errors, which would relate the geometric scaling result to numerical behavior.
  • It would have been nice if the code were made available for review for reproducibility, not just after the conclusion of the review process.
Questions for authors

See weaknesses

4 comments
AuthorsOpenReview ↗

Novelty, a certified oracle, new experiments, and code (1/2)

W1.

The mathematical analysis is quite classical and mostly leverages tools from Euclidean and Riemannian Frank–Wolfe analysis.

Reply. We agree for Section 4. The descent argument there is the classical Frank–Wolfe argument with one additional error term, and it shows that certification changes only a coefficient of the recurrence. The new results are geometric and numerical.

a) Theorem 5.1(i) proves a margin for every feasible anchor at every boundary point directly from the metric definition of strong convexity, without a curvature bound, boundary regularity, or convexity of the logarithmic images. In a Hilbert space this margin is the normal-cone characterization of strong convexity, and it coincides with the scaling inequality at linear maximizers. On a manifold the Riemannian scaling inequality is imposed at oracle maximizers only, and at a boundary point with an outward normal it reduces to 0≥00\ge0 (Remark C.3). The margin therefore has to be proved separately.

b) Theorem 5.1(ii) carries this margin from the oracle target back to the iterate through the differential of the logarithm. The resulting exact-oracle scaling inequality has a multiplicative factor mlog⁡m_{\log}, equal to 1 on rotation balls, and no additive residual, in contrast to the general intrinsic route of Scieur et al. (2026, Proposition 3.3).

c) Proposition 5.2 gives the sharp modulus 14cot⁡(ρ/2)\tfrac14\cot(\rho/2) and the exact worst-case clearance of rotation balls, and Proposition A.19 shows that the Euclidean value 1/(2ρ)1/(2\rho) is not a valid modulus.

d) Proposition A.22 shows that the restricted-domain hypotheses of a published sublevel-set theorem are insufficient, and Theorem A.20 restores the conclusion under an explicit ambient-tube assumption.

e) Theorem D.5 proves that mantissa precision logarithmic in 1/ε1/\varepsilon suffices for a concrete integrator under an exact feasible oracle and the primitive model of Assumption D.1, through a first-exit argument that controls the chart domain and the rounding error together.

The revision adds three results of the same kind, namely the gap-relative progress tolerance of Proposition E.1, the reduction of the oracle on a rotation ball to one dimension in Proposition E.2, and the strong convexity of pose balls in Proposition E.3. The new paragraph “What the manifold changes” in Section 5 makes the contrast between item (a) and the Euclidean case explicit.

W2.

There is no general certified numerical oracle that could enable broad applicability. Adding at least one complete implementation example with validated primitive bounds and certified oracle feasibility/accuracy could strengthen the paper.

Reply. The revision adds this example as Experiment J (Sections E.2 and E.5).

Certified oracle. Proposition E.2 shows that the linear oracle over a rotation ball attains its minimum on an explicit circle of the boundary sphere, so the oracle is the global minimization of a smooth periodic function of one angle. We certify it by interval branch and bound. The certificate consists of the feasibility of the stored target, a bound δk\delta_k on its suboptimality, and an upper bound on the Frank–Wolfe gap, hence on F(xk)−F⋆F(x_k)-F^\star.

Validated update. The exact endpoint is enclosed by interval arithmetic from the stored data, and the distance from each stored proposal to this enclosure is bounded from above. The acceptance test compares this bound with an interval lower bound of the accepted budget. No constant of Assumption D.1 enters.

Outcome. On the nonradial family of Experiment H we ran 14 treatments on 40 trajectories of 300 iterations. All 168,000 iterations carry a complete certificate with δk≤5⋅10−4ηk\delta_k\le5\cdot10^{-4} \eta_k, every stored point has a validated nonnegative clearance, and no run returns a status. A certificate takes a median of 72 and at most 104 interval evaluations. Each run also carries a certified bound on its own objective gap. At k=300k=300 its median is 3.7⋅10−63.7\cdot10^{-6} in the boundary-active regime, where the gap to the numerical reference is also 3.7⋅10−63.7\cdot10^{-6}. The hypotheses of Theorem 4.1 that concern a run are thus established by computation, up to the correctness of the interval library.

Cost and scope. The certificates dominate the cost. An iteration spends about 19 ms on the enclosures and 38 ms on the oracle certificate in a pure Python interval implementation, against 0.6 ms for the float64 planar oracle.

AuthorsOpenReview ↗

Novelty, a certified oracle, new experiments, and code (2/2)

W3.

The experiments do not showcase a real-world use case. Another experiment that could strengthen the paper is testing the faster-rate prediction under controlled endpoint errors, which would relate the geometric scaling result to numerical behavior.

Reply. We added both experiments.

Faster rates under controlled endpoint errors (Experiment K, Table 33, Figure 12). On the boundary-active instances, with the schedules ηk=a/(k+a)\eta_k=a/(k+a), we inject at every step an error of prescribed size along the ascent direction of the objective, which is the worst first-order direction. The fitted decay exponents for a=2a=2 and a=4a=4 are 2.00 and 3.93 without error and 2.01 and 3.93 when the error equals the accepted budget βk\beta_k, so the largest error that the accepted budget admits leaves the rate of Corollary 4.2 unchanged. When the error is instead scaled so that it costs the fraction λ\lambda of the step's progress, the exponents fall to 1.55 and 2.93 for λ=14\lambda=\tfrac14 and to 1.21 and 2.20 for λ=12\lambda=\tfrac12, against the guaranteed values 1.5, 3, 1, and 2 of Proposition E.1. The value 2.93 shows the same finite-range deficit as the error-free fit of 3.93 against 4. The same runs relate the geometric result to the numerics directly. The ratio gk/(α∣grad⁡F(xk)∣dk2)g_k/(\alpha\\|\operatorname{grad} F(x_k)\\|d_k^2), which Theorem 5.1(ii) bounds below by mlog⁡=1m_{\log}=1, has minimum 1.000001 and median about 2⋅1042\cdot10^{4} over 12,000 steps, so the constant of the theorem is attained to six digits and is far from typical.

A problem beyond rotation averaging (Experiment L, Table 34, Figure 13). Proposition E.3 shows that pose balls, the balls of SO(3)×R3\mathrm{SO}(3)\times\mathbb{R}^3 in the product metric, are strongly convex with the modulus of rotation balls. We use it for a synthetic pose-fusion problem, in which a pose must stay in a pose ball that trades 20∘20^\circ of attitude deviation against 0.35 m of position deviation. With iterates stored in fp16 in world coordinates and no guard, the run stays feasible and stalls. Its final gap is 2.96 orders of magnitude above that of the float64 run, and its final pose lies a median of 0.20∘0.20^\circ and 8.3 mm from the float64 result. A float64 membership guard never intervenes and leaves this loss unchanged. The endpoint-guarded runs match the float64 accuracy on the 19 trajectories that complete the horizon, with no violation, and one run returns cannot certify at k=295k=295. Of the 5,996 fp16 proposals that the endpoint guard examines, 2,718 lie outside the pose ball, by up to 1.85 mm. Animations of the unguarded and the endpoint-guarded run accompany the code.

W4.

It would have been nice if the code were made available for review for reproducibility, not just after the conclusion of the review process.

Reply. We agree. An anonymized package is uploaded with the revision as supplementary material. It contains the code, the pinned dependencies, the raw records of every reported run, the generated tables and figures, the unit tests, and the scripts of the new Experiments I to M, with a table that maps each table and figure of the paper to its script and records. The reproducibility statement has been updated.

Thanks to the authors for the detailed revisions, which have improved the paper. However, I still feel that the novelty of the mathematical analysis and the significance of the empirical results is slightly below the bar for acceptance. I will therefore retain my score.

Thank you for reading the revision and for your assessment of it. We add two remarks on the points you name.

Novelty of the analysis. We agree that the descent argument of Section 4 is classical. The new mathematics is Theorem 5.1. The scaling inequality of earlier Riemannian Frank–Wolfe analyses is imposed at oracle maximizers, and at a boundary point with an outward normal it reduces to 0 ≥ 0 (Remark C.3). The margin behind the faster rates therefore does not follow from it. Theorem 5.1(i) proves this margin from the metric definition of strong convexity alone, and Theorem 5.1(ii) carries it to the iterate with a multiplicative factor and no additive residual.

Significance of the experiments. The experiments measure a loss that a feasibility check does not detect. 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. A membership guard does not prevent this loss. With the endpoint guard the runs of Experiment H reach the reference accuracy at 4 to 5% more time per iteration, and Experiment J certifies all 168,000 iterations by interval arithmetic, with no primitive model and no uncertified oracle.

We would be grateful if you would take these two points into account in your final assessment.

Comments on the paper

5 comments
AuthorsOpenReview ↗

General response and summary of the revision

We thank the three reviewers for their careful reading. The reviews share four requests, items 1 to 4 below, and the revision answers each of them with new analysis and experiments. These are collected in a new Appendix E and summarized in one paragraph of Section 6, which takes the main text onto the tenth page allowed in the discussion phase. All other changes to the submitted text are marked in color in the revised PDF. Items 5 and 6 concern Lemma A.4 and the code.

  1. A certified oracle and a fully validated run (Reviewer fLcM, W2; Reviewer dauH, W2, W3, Q2, Q3). Proposition E.2 reduces linear minimization over a rotation ball to the global minimization of a smooth function of one angle. An interval branch and bound over that angle certifies the feasibility of the returned target, a bound δk\delta_k on its suboptimality, and an upper bound on F(xk)−F⋆F(x_k)-F^\star. Experiment JJ combines this certified oracle with interval enclosures of the exact endpoint, so that neither a primitive model nor an uncertified oracle remains. On the nonradial family of Experiment H, all 168,000168{,}000 iterations of 1414 treatments are certified with δk≤5⋅10−4 ηk\delta_k\le5\cdot10^{-4}\,\eta_k, at a median of 7272 interval evaluations per oracle call.

  2. A less conservative accepted budget that keeps the sublinear and the faster rates (Reviewer dauH, W4, Q4; Reviewer X8TG). Proposition E.1 also accepts an endpoint error measured against the decrease ηkgk\eta_k g_k of the step, in addition to the tolerance of order ηk2dk2\eta_k^2d_k^2. It keeps the sublinear rate and the faster rates, with the decrease term ηkhk\eta_k h_k of each recurrence multiplied by 1−λ1-\lambda (λ<12\lambda < \frac{1}{2}). In Experiment II, on the proposals of Experiment HH, the fp32 fallbacks in the boundary-active regime fall from 5,6135{,}613 to 2,1782{,}178 of 6,0006{,}000 steps under this gap-relative progress tolerance, with the gradient bound taken at the candidate and the endpoint clearance of Remark C.2 as geometric term. They fall to zero under the absolute allowance of Remark A.16 with the same geometric term, which keeps the sublinear rate. The accuracy is unchanged, and no trajectory violates in either case. The fp16 proposal is accepted natively on fewer than 33\\% of these steps under every accepted budget that keeps the faster rates. When the absolute allowance accepts 16.116.1\\% of the fp16 proposals, the final gap is 0.190.19 orders of magnitude above the reference, and unguarded fp16 loses 1.741.74 orders.

  3. Evidence in wall-clock time, under controlled errors, and on a second problem (Reviewer fLcM, W3; Reviewer dauH, W5, Q5; Reviewer X8TG). Table 30 and Figure 10 compare the methods with time on the horizontal axis. The endpoint-guarded methods cost 44 to 55\\% more per iteration than standard Riemannian Frank--Wolfe and reach a gap of 10−510^{-5} in 0.770.77 to 0.800.80 s against 0.750.75 s. Experiment K injects endpoint errors of controlled size. The fitted exponents for a=2a=2 and a=4a=4 are 2.012.01 and 3.933.93 at the accepted budget, against the value aa of Corollary 4.2, and 1.551.55 and 2.932.93 when the error costs a quarter of the step's progress, against the guaranteed values 1.51.5 and 33 of Proposition E.1. The value 2.932.93 shows the same finite-range deficit as the error-free fit of 3.933.93 against 44. Proposition E.3 shows that balls of SO×RnSO\times\mathbb R^n, called pose balls, are strongly convex with the modulus of rotation balls, and Experiment L uses it for a synthetic pose-fusion problem. Experiment M runs the fixed-NN policy of Theorem D.5 on nonradial trajectories with nonzero truncation.

  4. What is new in the analysis (Reviewer fLcM, W1; Reviewer X8TG). The descent argument of Section 4 is the classical Frank--Wolfe argument with one additional error term, and the new difficulty is geometric. On a manifold the scaling inequality is imposed at oracle maximizers and reduces to 0≥00\ge0 at a boundary point with an outward normal, so Theorem 5.1(i) proves the margin separately and Theorem 5.1(ii) carries it back to the iterate. A new paragraph in Section 5, ``What the manifold changes'', gives this comparison.

  5. Lemma A.4 (Reviewer dauH, W1, Q1). Lemma A.4 identifies the contingent cone with the closure of the conic hull, written cone⁡Ap‾\overline{\operatorname{cone}A_p} on line 738 of the submission. The revision writes the closure in words and lists the conclusions of the lemma that later results use.

  6. Code (Reviewer fLcM, W4). An anonymized package with all code, raw results, and the scripts of the new experiments is uploaded with the revision as supplementary material.

AuthorsOpenReview ↗

Lemma A.4, validated certification, conservatism, and scope (1/4)

W1 and Q1.

Lemma A.4 is false as stated. The contingent cone of a closed star-shaped set is generally the closure of its conic hull, not necessarily the conic hull itself. [...] Can the authors correct Lemma A.4 [...] and provide a precise audit of every result that uses the original equality? In particular, which later claims require actual attainment of a tangent direction by a finite chord rather than approximation by chord directions?

Reply. Lemma A.4 is stated with the closure of the conic hull, which is the correct object. In the submitted PDF, line 738 reads TC(p)=cone⁡Ap‾T_{\mathcal C}({p})=\overline{\operatorname{cone}A_p}. The proof states on line 746 that the contingent cone at the origin is cone⁡S‾\overline{\operatorname{cone}S} and takes v∈cone⁡S‾v\in\overline{\operatorname{cone}S} on line 748. The closure appears there only as an overline, directly before a definition of cone⁡Ap\operatorname{cone}A_p that has none. The revision writes the closure in words.

  • The statement now reads “TC(p)T_{\mathcal C}({p}) is the closure of the conic hull cone⁡Ap:=λa:λ≥0,a∈Ap\operatorname{cone}A_p:=\\{\lambda a:\lambda\ge0, a\in A_p\\} of ApA_p, that is, TC(p)=cone⁡Ap‾T_{\mathcal C}({p})=\overline{\operatorname{cone}A_p}”, and the proof says “the closure of the conic hull” in words.
  • A paragraph after the proof explains why the closure cannot be omitted. For a closed disc whose boundary passes through the origin, the conic hull is an open half-plane together with the origin, and the contingent cone is the closed half-plane.
  • The same paragraph gives the requested audit. In every result of the paper, approximation of a tangent direction by scaled chord directions suffices, and no claim requires attainment by a finite chord. Lemma A.4 enters through three conclusions, all of which hold for the closure. Corollary A.5, the discussion after Proposition A.6, and Corollary B.1 use that TC(p)T_{\mathcal C}({p}) is a closed convex cone, hence equal to its bipolar. Remark B.2 uses derivability and the product formula. Theorem 5.1 and Lemma A.18 are independent of Lemma A.4. They work with the limit definition (9) and with the sequential description of Lemma A.3(ii), in which tangent directions are limits of scaled chord directions.

W2 and Q2.

The implementation-level certification remains conditional on unproved primitive bounds. [...] Can the primitive bounds in Assumption D.1 be proved using outward-rounded interval arithmetic or another verified numerical framework, including the complete reference-endpoint routine? Would the released code reproduce a genuinely unconditional certificate rather than a certificate conditional on calibrated constants?

Reply. The revision adds an end-to-end run with no primitive model, Experiment J (Section E.5). It follows an a posteriori route. Instead of proving a bound for each float64 primitive, the routine encloses the exact endpoint zk+1z_{k+1} by outward-rounded interval arithmetic from the stored binary data, bounds the distance from the stored proposal to that enclosure from above, and compares the bound with an interval lower bound of the accepted budget. The membership of every iterate, the objective, the gradient, and the oracle certificate are enclosed in the same way. The accuracy of the reference-endpoint routine is therefore not a hypothesis. Its output is one more proposal whose error is bounded.

For this experiment the answer to the second question is yes. The released code reproduces certificates that depend on no calibrated constant. They rest on the correctness of the interval library, of which the routine uses the four arithmetic operations, the square root, the sine, and the cosine. Every angle is enclosed by a candidate interval that is verified with the interval sine and cosine, because the interval arctangent of the library is not outward rounded and no inverse trigonometric function is taken from it. On all 168,000 iterations the certificates are complete, and every stored point has a validated nonnegative clearance. With validated enclosures the float64 proposal is accepted on every step of the 300-iteration horizon.

Experiments C to H keep the a priori model of Assumption D.1 and remain conditional. Theorem D.5 predicts acceptance before the computation, so it needs a priori bounds, and a proof of the constants of Assumption D.1 for the kernels of that theorem is still open. The validated run is about two orders of magnitude slower than an uncertified float64 run in our pure Python implementation.

AuthorsOpenReview ↗

Lemma A.4, validated certification, conservatism, and scope (2/4)

W3 and Q3.

A difficult part of the problem is delegated to the oracle contract. [...] Can the authors give a nontrivial, end-to-end certified linear minimization oracle on the ball, including represented feasibility and a computable bound, and report total complexity including oracle work?

Reply. Yes. Proposition E.2 shows that for xx in the ball and a nonzero gradient, the minimum of the linear oracle is attained on an explicit circle Γ\Gamma of the boundary sphere, the intersection of that sphere with a three-dimensional subspace that contains the lifts of xx, of the gradient, and of the centre. The oracle is thus the global minimization of a smooth periodic function Φ\Phi of one angle. The certified oracle of Section E.2 runs an interval branch and bound on Φ\Phi with a centred form, and returns three certificates for the stored target qkq_k, namely its represented feasibility, the bound δk=φ‾k−Φ‾\delta_k=\overline\varphi_k-\underline\Phi on its suboptimality, and the bound hk≤−Φ‾h_k\le-\underline\Phi on the objective gap.

Complexity, including oracle work (Table 31). An oracle call takes a median of 72 and at most 104 interval evaluations of (Φ,Φ′)(\Phi,\Phi^{\prime}) for the requirement δk≤10−3ηk\delta_k\le10^{-3}\eta_k. Per iteration, measured sequentially in one process, the float64 planar oracle that proposes the target takes 0.6 ms, its certificate 38 ms, the interval enclosures of membership, objective, and gradient 19 ms, and the endpoint enclosure, kernel, and decision together about 1 ms. A fully validated run of 300 iterations therefore costs about 18 s per trajectory in pure Python.

Where the certified oracle enters the theory. The sublinear guarantee of Theorem 4.1 holds with the certified δk\delta_k. Corollary 4.2 is stated for exact oracles. In the proof of Theorem D.5 the exactness enters only through the chord bound dk>ε/Gd_k > \varepsilon/G. With a certified δk≤min⁡δTk,ε/2\delta_k\le\min\\{\delta T_k,\varepsilon/2\\} the rate bound of Lemma A.12 still holds and the same step gives dk>ε/(2G)d_k > \varepsilon/(2G), which changes the threshold bεb_\varepsilon by a constant number of bits. The statement of Theorem D.5 keeps the exact-oracle hypothesis in this revision. The planar reduction is also useful without certification. In float64 the planar oracle is about ten times faster than the numerical reference oracle (Table 30).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.