# Sampled Goldstein optimizer

- ID: 2628
- Canonical URL: https://synthcore.org/idea/2628/sampled-goldstein-optimizer
- API JSON: https://synthcore.org/api/idea/2628.json
- API Markdown: https://synthcore.org/api/idea/2628.md
- Verification status: unverified
- Source: [arXiv:2608.20642](https://arxiv.org/abs/2608.20642)
- Category: optimization
- Solves: stability, accuracy, speedup
- ML areas: optimizer, training-dynamics, mlp, cnn
- Math tags: optimization, convex-analysis, geometry, dynamical-systems
- Ratings: usefulness 6/10; difficulty 6/10; novelty 6/10

## Idea description

Replace the single backpropagated subgradient of a piecewise-smooth network loss by a minimum-norm convex combination of gradients evaluated at nearby parameter perturbations. Shrink the perturbation radius geometrically and restart the schedule when the sampled Goldstein direction becomes small, following the paper's INGD motivation.

## Mathematical statement

For a locally Lipschitz objective f: R^d -> R and radius delta > 0, the Goldstein subdifferential is the convex hull of nearby Clarke subgradients, G_delta f(x) = conv{partial_C f(y): ||y-x||_2 <= delta}; in a piecewise-C^1 network, sampled elements can be ordinary gradients g_i = grad f(x + u_i), with ||u_i||_2 <= delta. The usable direction is the minimum-norm convex combination g_star = sum_i alpha_i g_i, where alpha_i >= 0 and sum_i alpha_i = 1, minimizing ||sum_i alpha_i g_i||_2. The paper describes Interpolated Normalized Gradient Descent using constant step size delta and termination when a Goldstein subgradient has norm below epsilon, with restarts and geometrically decaying delta = epsilon = 10^{-r}, r = 1,2,... . The proposed neural optimizer uses this explicit sampled convex-hull approximation and does not require differentiability at the current point.

## Key formulas

- $$G_{\delta}f(x)=\operatorname{conv}\left\{\partial_C f(y):\|y-x\|_2\leq\delta\right\}.$$
- $$g_{\star}=\sum_{i=1}^{m}\alpha_i g_i,\qquad \alpha_i\geq0,\quad\sum_{i=1}^{m}\alpha_i=1,\qquad g_{\star}=\arg\min_{g\in\operatorname{conv}\{g_1,\ldots,g_m\}}\|g\|_2.$$
- $$x_{k+1}=x_k-\eta\,\frac{g_{\star}}{\max(\|g_{\star}\|_2,\tau)},\qquad \delta=\epsilon=10^{-r},\quad r=1,2,\ldots.$$
- $$f(x)=x_1^2+2\left|x_1^2-x_2\right|.$$

## Implementation notes

Integrate this as an optimizer replacement at the parameter-update level, first for a small ReLU MLP or CNN. At each update, save the current parameter vector theta and draw m perturbations u_i uniformly from the sphere or normalized Gaussian directions with ||u_i||_2 = delta; evaluate the same minibatch loss at theta + u_i and backpropagate each loss to obtain g_i. Solve the simplex quadratic program min_alpha ||G alpha||_2^2 subject to alpha_i >= 0 and sum_i alpha_i = 1, where G has columns g_i. For a cheap MVP, use projected gradient descent on alpha or Frank-Wolfe: initialize alpha uniformly, repeatedly choose j = argmin_j <G alpha, g_j>, move alpha toward e_j, and stop after 10-20 iterations. Form g_star = G alpha, then apply the normalized update theta <- theta - eta*g_star/max(||g_star||_2,tau), with tau=1e-8. The paper's mathematical object is the sampled convex hull and its minimum-norm element; empirical choices are m, perturbation distribution, eta, and QP tolerance. Start with m=4 or 8, delta=epsilon, and reduce both by 10x after a fixed patience interval or when ||g_star|| falls below epsilon; reset momentum or optimizer state at each restart. Compare against AdamW and SGD on a 2-layer ReLU MLP trained on MNIST or a small CNN on CIFAR-10, using matched total gradient evaluations rather than matched optimizer steps. Measure loss versus gradient evaluations, gradient-direction variance across minibatches, final accuracy, and sensitivity to initialization. Success means lower loss or fewer activation-boundary instabilities at equal gradient evaluations; a meaningful negative result is no improvement after accounting for the m-fold gradient cost.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.