Ball Walk: missing robustness checks for low-dimensional or degenerate polytopes can lead to silent stagnation

[Akash504-ai]

Description

While reviewing the Ball Walk implementation (uniform_ball_walk.hpp), I noticed that several implicit assumptions about the input polytope are not explicitly validated. In certain valid but edge-case scenarios (e.g., low-dimensional or nearly degenerate polytopes), these assumptions can lead to ineffective step sizes, causing the Markov chain to stagnate silently and return misleading samples.

This issue is not about crashes, but about silent correctness failures, which are particularly problematic in sampling algorithms.

Where this was found
File:
include/random_walks/uniform_ball_walk.hpp
In particular, the computation and usage of the Ball Walk step size (delta) inside compute_delta() and apply().

Observed assumptions and potential failure modes

1. Step-size computation depends on polytope dimension without guards

return (NT(4) * (P.InnerBall()).second) / std::sqrt(NT(P.dimension()));

This computation implicitly assumes:

• P.dimension() > 0
• The polytope is not degenerate
• The inner ball radius is meaningful and well-scaled
  However:
• For dimension == 0, this results in division by zero.
• For very low dimensions (e.g., 1D), the resulting delta can be disproportionately large relative to the feasible region, leading to near-total rejection.
• There is no validation of these assumptions.

2. No validation of inner ball existence or radius
The code assumes that (P.InnerBall()).second:

• Exists
• Is strictly positive
• Is numerically stable

For nearly degenerate or badly conditioned polytopes, the inner ball radius can be zero or extremely small, resulting in delta ≈ 0. In this case, all proposed points remain arbitrarily close to the current state, and the walk effectively does not move.
This failure mode is silent: the algorithm completes successfully but returns highly correlated or identical samples.

3. Silent stagnation in the proposal loop

Point y = GetPointInDsphere<Point>::apply(P.dimension(), _delta, rng);
y += p;
if (P.is_in(y) == 1) p = y;

If delta is poorly scaled (too large or too small), proposals are either:

• almost always rejected, or
• accepted but indistinguishable from the current point.

There is currently:

• no acceptance tracking,
• no warning,
• no fallback or adjustment mechanism.

As a result, users may unknowingly receive invalid or misleading samples.

4. Precision mismatch for delta storage
The step size _delta is stored as a double, even though the numeric type NT may have higher precision. This can silently reduce numerical accuracy for certain polytope types.

Impact on users

• Sampling may appear to succeed while producing non-exploratory chains.
• Users may misinterpret results as valid uniform samples.
• Low-dimensional and near-degenerate cases (which volesti otherwise supports) are particularly affected.
• These issues are difficult to detect without deep inspection, making them more harmful than explicit failures.

Possible directions for improvement (suggestions)

• Add explicit validation for low-dimensional or degenerate polytopes when computing the Ball Walk step size.
• Detect and handle cases where the inner ball radius is zero or numerically insignificant.
• Document the assumptions under which Ball Walk is expected to behave correctly.