Tracking Smoothed Gradients Across Iterations to Escape Contact Traps Cheaply

Gradient-based planners and learners get stuck when the loss surface is jagged. A robot pushing a box sees zero gradient until its finger touches the box, and a discontinuous loss has countless tiny pockets. The standard fix is randomized smoothing: average the gradient over many randomly perturbed copies of the current point. This turns the jagged surface into a blurred one whose gradient shows the large-scale downhill direction. The blur is effective but costly. Bundled Gradients through Contact via Randomized Smoothing, which builds these averaged "bundled" gradients for model-predictive control through contact, reports needing about N=100 simulator samples per knot-point. It draws those samples afresh at every iteration, even though consecutive iterates are close and their smoothed gradients nearly coincide.

We propose to carry the smoothed gradient forward from one iteration to the next instead of re-estimating it. The method uses a single-loop variance-reduced estimator, meaning one that updates a running gradient estimate by adding the measured change between consecutive iterates rather than periodically recomputing from scratch. It reuses the same random perturbations at the old and new iterate, so most of the sampling noise cancels in the difference. The conceptual point addresses a tension the literature leaves open. Variance reduction is usually expected to hurt escape from traps because it removes the gradient noise that lets SGD wander. Here, escape comes from the smoothing radius, which redefines the objective. It does not come from estimation noise. The method removes estimation noise and keeps the exploration. The resulting question is concrete: can a smoothed planner match the success rate of 100-sample bundled gradients using a handful of samples per step?

Core Claim

Let $f$ be a piecewise-smooth objective, such as trajectory cost through a contact simulator or a discontinuous surrogate loss. Let $f_\sigma(x) = \mathbb{E}_{w \sim \mathcal{N}(0,I)}[f(x+\sigma w)]$ be its Gaussian smoothing with radius $\sigma$. We track $\nabla f_{\sigma_t}$ with a STORM-style recursion of the kind used by ZeroSARAH and the accelerated zeroth-order momentum methods. The difference term is evaluated with common random perturbations $w_{t,1},\dots,w_{t,k}$ shared between the two iterates:

$$g_t = (1-\alpha)\Big(g_{t-1} + \tfrac{1}{k}\textstyle\sum_{j} \big[\nabla f(x_t + \sigma_t w_{t,j}) - \nabla f(x_{t-1} + \sigma_{t-1} w_{t,j})\big]\Big) + \alpha\, \tfrac{1}{k}\textstyle\sum_j \nabla f(x_t + \sigma_t w'_{t,j}).$$

Here $\alpha \in (0,1]$ is the weight placed on a fresh $k$-sample bundled gradient drawn with independent perturbations $w'$. The same formula handles a radius schedule $\sigma_t$ that shrinks over time, because the perturbation is shared and only the point and the scale change.

Standard variance-reduction theory does not cover this setting, because $f$ is discontinuous. For smooth components, a per-sample gradient difference is bounded by $L\|x_t-x_{t-1}\|$, and the correction's variance falls quadratically with the step length. For a piecewise-smooth $f$ with jump size $J$, a shared perturbation produces a large difference only when it straddles a contact boundary between the two iterates. That event has probability on the order of $\|x_t - x_{t-1}\|/\sigma$, because the boundary must fall inside a slab of that width relative to the Gaussian's scale. This suggests

$$\mathbb{E}\big\|\Delta_t\big\|^2 \lesssim \frac{J^2}{\sigma}\|x_t-x_{t-1}\| + L^2\|x_t-x_{t-1}\|^2,$$

where $\Delta_t$ is the per-sample difference term. The correction's variance therefore decays only linearly in step length near contact boundaries. Our first contribution is to make this mean-square Hölder-type smoothness condition precise and to derive the rate it gives for single-loop tracking of $\nabla f_\sigma$. The analysis should also predict how small $k$ can be as a function of $J$, $\sigma$, and the step size. The second contribution is an empirical test of whether this prediction holds on contact-rich manipulation.

Relation to Prior Work

Two papers motivate the work by documenting entrapment and the value of smoothing. Bundled gradients show that exact gradients fail completely from non-contact initial guesses in planar pushing, box pivoting, and two-fingered hand tasks, while smoothed gradients succeed. That paper uses no recursion across iterations, and recursion is what we add. Noise Injection Irons Out Local Minima and Saddle Points proves that Gaussian noise in SGD acts as a smoothing operator that removes high-frequency traps. Its method, Nomad, reaches zero loss on phase retrieval where Adam and RMSprop do not. The same paper reports that the benefit vanishes on deep networks. That negative result constrains our scope, and we therefore target low-to-moderate-dimensional, physically jagged problems rather than deep-network training.

Three papers supply method pieces but stop short of this combination. Accelerated Zeroth-Order Momentum Methods from Mini to Minimax Optimization, which pairs single-loop STORM with uniform smoothing, is the closest work. It differs from ours in three ways. It uses function-value queries only, it assumes smooth components, and it targets first-order stationarity of black-box attacks. We use first-order simulator gradients at the perturbed points, assume discontinuous components, and target escape from contact traps. Revisiting Randomized Smoothing combines smoothing with SPIDER-style variance reduction under non-global-Lipschitz growth. Its estimator is double-loop, with periodic large batches. It handles steep growth, not jump discontinuities, and its experiments are zeroth-order attacks. PAGE supplies the coin-flip alternative to the momentum form. We test a PAGE-style variant in which a fresh large bundle replaces the recursion with probability $p$.

The saddle-escape line, comprising SNVRG+, A Generic Approach for Escaping Saddle points, and BVR-L-PSGD, pairs variance reduction with negative-curvature steps or injected noise. All three are double-loop. All three also explicitly cannot leave minima whose Hessian is positive semidefinite, which describes the flat zero-gradient non-contact regions we care about. We do not pursue second-order guarantees. Our escape mechanism operates at the level of the objective, not curvature.

Research Program

The theory component states the crossing-probability smoothness condition for piecewise-smooth $f$ under Gaussian perturbations. It then bounds the tracking error $\mathbb{E}\|g_t - \nabla f_{\sigma_t}(x_t)\|^2$ for the recursion above, both with a fixed $\sigma$ and with a slowly decaying $\sigma_t$. Finally, it converts that bound into a stationarity rate for $f_\sigma$. We expect a rate between the smooth STORM rate and the plain Monte Carlo rate, interpolated by $J^2/\sigma$. We will state honestly where the bound becomes vacuous.

The systems component implements the estimator inside the iRS-MPC loop of the bundled-gradient work on its Drake tasks. The same code will also run in a generic optimizer for the Spring Loss on UCI tictactoe from How to Boost Any Loss Function and for phase retrieval. The only memory overhead is storing the previous iterate and the previous estimate, which is trivial at these sizes.

Baselines

The naive reference point is exact-gradient iterative MPC from the bundled-gradient paper, which is reported to fail from non-contact initializations. Alongside it we run Monte Carlo bundled gradients at the published setting of N=100 samples per knot-point. This is the strongest existing method on these tasks. It is the competitor that matters because it already escapes the traps, so we can only win on cost. On Lacuna we found no reported numeric success rate or final cost for iRS-MPC on these tasks. We will therefore reproduce it ourselves under our evaluation protocol rather than quote a figure. Beating it means matching its task success rate and final cost within seed-level confidence intervals while using at most one fifth of its simulator gradient evaluations. We also run iRS-MPC at small N, matching our per-step budget, which gives the "just use fewer samples" reference.

The Cross-Entropy Method is the derivative-free reference. The bundled-gradient paper reports that iRS-MPC converges more tightly and faster than this method. Acc-ZOM represents the closest single-loop smoothed competitor; it is run on function values only, under the same simulator-call budget.

The ablations isolate the key ingredient. The first ablation, plain momentum, keeps an exponential moving average of small bundled gradients with no difference correction. The second uses independent rather than shared perturbations in the difference term. The third is the PAGE-style coin-flip variant. A fourth runs the tracker with $\sigma=0$, which is ordinary single-loop variance reduction; it tests the claim that variance reduction without smoothing stays trapped. For tictactoe Spring Loss we compare against SECBOOST and plain gradient descent. For phase retrieval we compare against Nomad noise injection and PAGE.

Every method gets the same simulator, initializations, and horizon, and every method is scored against total gradient evaluations. Each receives an equal hyperparameter search budget of 30 trials over its own knobs ($\sigma$, step size, $\alpha$ or $p$, $N$ or $k$), selected on a held-out set of initial conditions.

Why not just…?

Why not just keep a momentum average of cheap bundled gradients? This is the most serious threat. A moving average does reduce variance, and it is simpler. Its weakness is bias: as the iterate moves, the average lags behind the current smoothed gradient. Contact planning is exactly the setting where the smoothed gradient rotates sharply once contact is made. The difference correction removes that lag. The momentum-only ablation settles the question directly. If it matches our success rate at equal cost, the recursion adds nothing, and we will report that outcome.

Why not just use more samples, or fewer, in plain bundled gradients? More samples is the N=100 baseline, which is correct but expensive. Fewer samples is the matched-budget baseline. The noise-injection paper's observation that too much noise derails descent while too little fails to clear barriers suggests that a noisy small-N estimate forces a choice between a smaller $\sigma$ and a smaller step size. Each choice costs either escape or speed. The small-N run tests whether that tradeoff actually binds.

Why not just use a derivative-free method such as the Cross-Entropy Method or Acc-ZOM? These methods avoid unreliable contact gradients altogether. The bundled-gradient paper already finds the Cross-Entropy Method slower and looser than gradient bundling. Acc-ZOM's dimension-dependent query complexity of $\mathcal{O}(d^{3/4}\epsilon^{-3})$ suggests it will lag over a planning horizon with many decision variables. Both are run at equal simulator cost, so the comparison is direct.

Why not just use a second-order saddle-escape method? The traps here are flat or positive-semidefinite regions. SNVRG+, the Reddi et al. framework, and BVR-L-PSGD state outright that they cannot escape such regions, so negative-curvature steps do not apply.

Proposed Experiments

The decisive experiment covers the three Drake tasks from non-contact initial guesses. We plot success rate and final trajectory cost against cumulative simulator gradient evaluations, sweeping $k \in \{2,5,10,20\}$ for our method against N=100 bundled gradients, with 20 initializations per task. The central claim holds if some $k \le 20$ matches the N=100 success rate at under a fifth of the evaluations. It fails if the momentum-only ablation does equally well, or if no small $k$ matches.

The second check tests the theory. We log how often shared perturbations straddle a contact mode change between iterates, and we compare the empirical variance of the correction term with the predicted $J^2\|\Delta x\|/\sigma$ scaling across a sweep of $\sigma$. Agreement would show that the crossing argument, not luck, explains the result. The shared-versus-independent ablation should show the largest gap at small $\sigma$.

The third check probes the claim that suppressing estimation noise is harmless when exploration comes from smoothing. On phase retrieval and the Spring Loss, we measure the fraction of runs reaching the global basin for three methods: our tracker, the $\sigma=0$ tracker, and Nomad. The prediction is that the $\sigma=0$ tracker gets trapped while our tracker matches Nomad's reported zero-loss behavior on phase retrieval at lower gradient cost. If our tracker instead behaves like the $\sigma=0$ variant, then the separation between exploration noise and estimation noise does not hold in practice. That would be a useful negative result for the broader worry that variance reduction harms escape.