Nonexistence of dimension-free algorithms for Goldstein approximate SOSPs

Let $f$ be an $L$-smooth function. A Goldstein approximate second-order stationary point (SOSP) is an approximate second-order stationary point in the Goldstein sense, as defined in the paper. Nonexistence conjecture. No randomized algorithm computes Goldstein approximate SOSPs of $L$-smooth functions with complexity independent of the dimension. The question concerns whether the dimension-free computability known for Goldstein approximate first-order stationary points extends to the second-order setting; the authors state that they are inclined to believe the answer is negative, but the conjecture remains open.