Randomized algorithms can find Goldstein stationary points of nonsmooth nonconvex Lipschitz functions with dimension free complexity, but deterministic algorithms cannot. A new result titled The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization closes the gap between what was known and what is true, showing the price is not just linear in dimension but exponential.
The paper studies the standard task of finding a (delta, epsilon) Goldstein stationary point, the accepted relaxation for nonsmooth nonconvex optimization. Prior work by Zhang et al. showed randomized first order methods achieve dimension free oracle complexity, while Jordan et al. and Tian and So proved any deterministic method must scale at least linearly with dimension d. The new analysis pushes that lower bound to exponential, establishing that determinism itself carries an unavoidable and steep cost. For teams training large models where nonsmooth objectives and clipping, normalization and piecewise linearities are routine, the implication is direct: randomness is not a trick for speed, it is required for tractability.
When deterministic choices break deployed models
That theoretical fragility shows up empirically in Robot World Models Are Not Invariant to How the Actions Are Written. The authors train latent dynamics models on one action parameterization, absolute joint targets or deltas relative to current state, and then test on the identical trajectory written the other way. Retrieval degrades by 2.6 to 13.4 times across three robot datasets and two world model architectures. The dynamics are the same, only the notation changed, yet the model collapses. It is a concrete case where a deterministic engineering decision silently becomes part of the learned world.
Harness-Zero: Harness Distillation via Agent-as-Harness tackles the same brittleness at the agent layer. Agent harnesses, the prompts, control flow, tooling and memory that surround a frozen model, can substantially improve performance, but gains stay tied to the harness at deployment and the best harness varies by domain and model. Instead of routing among ever growing specialized harnesses, the authors study distillation that uses a domain or instance optimized harness as training time guidance to internalize its advantage into the model. Together, the three papers point to one lesson for building and shipping models: treat randomness and representation as first class design variables, not afterthoughts, or pay for determinism later.
