# Bregman-Projection Polyak Optimizer

- ID: 2447
- Canonical URL: https://synthcore.org/idea/2447/bregman-projection-polyak-optimizer
- API JSON: https://synthcore.org/api/idea/2447.json
- API Markdown: https://synthcore.org/api/idea/2447.md
- Verification status: failed_benchmark
- Source: [arXiv:2608.17252](https://arxiv.org/abs/2608.17252)
- Category: optimization
- Solves: speedup, stability, accuracy
- ML areas: optimizer, moe-routing, mlp, training-dynamics
- Math tags: optimization, convex-analysis, geometry
- Ratings: usefulness 7/10; difficulty 5/10; novelty 7/10

## Idea description

Replace the Euclidean Polyak step in an optimizer with a mirror-descent step whose length is chosen by projecting onto the current affine lower-bound halfspace in Bregman geometry. This permits entropy geometry for simplex-valued router probabilities, log geometry for positive parameters, and other mirror maps without reducing the method to a norm-based learning-rate rule.

## Mathematical statement

The paper's baseline Polyak update is $$x_{t+1}=x_t-\alpha_t g(x_t),\qquad \alpha_t=\frac{f(x_t)-f_\star}{\|g(x_t)\|_2^2},$$ where $f$ is a convex objective, $g(x_t)\in\partial f(x_t)$ is a subgradient, and $f_\star=\min_x f(x)$. For a differentiable strictly convex mirror map $h$, define the Bregman divergence $$D_h(y,x)=h(y)-h(x)-\langle\nabla h(x),y-x\rangle.$$ At iterate $x_t$, let $\delta_t=f(x_t)-\widehat f_\star$ and let $g_t=
abla f(x_t)$. The affine first-order lower-bound halfspace is $H_t=\{y:f(x_t)+\langle g_t,y-x_t\rangle\leq\widehat f_\star\}$. Mirror Polyak chooses the next point as the Bregman projection $$x_{t+1}=\arg\min_{y\in H_t}D_h(y,x_t).$$ The KKT conditions reduce this to $$x_{t+1}=\nabla h^{-1}(\nabla h(x_t)-\lambda_tg_t),$$ where $\lambda_t\geq0$ satisfies $$\langle g_t,x_t-x_{t+1}\rangle=\delta_t.$$ In Euclidean geometry, $h(x)=\frac{1}{2}\|x\|_2^2$, so $x_{t+1}=x_t-\lambda_tg_t$ and $\lambda_t=\delta_t/\|g_t\|_2^2$, recovering the Polyak rule. The neural-network adaptation uses the safe stochastic gap $\delta_t=[f_t-\widehat f_\star]_+$ and optionally clips $\lambda_t$.

## Key formulas

- $$x_{t+1}=x_t-\alpha_tg(x_t),\qquad \alpha_t=\frac{f(x_t)-f_\star}{\|g(x_t)\|_2^2}.$$
- $$D_h(y,x)=h(y)-h(x)-\langle\nabla h(x),y-x\rangle.$$
- $$x_{t+1}=\arg\min_{y:\,f(x_t)+\langle g_t,y-x_t\rangle\leq\widehat f_\star}D_h(y,x_t).$$
- $$x_{t+1}=\nabla h^{-1}\!\left(\nabla h(x_t)-\lambda_tg_t\right),\qquad \left\langle g_t,x_t-x_{t+1}\right\rangle=\delta_t,\quad \delta_t=[f(x_t)-\widehat f_\star]_+.$$

## Implementation notes

Integrate this optimizer at the parameter-update stage for a selected tensor, initially a simplex-valued MoE router, positive gate vector, or nonnegative factor in a low-rank layer. Keep the remaining network on AdamW so the first experiment isolates the geometry. For simplex probabilities use negative entropy $h(p)=\sum_i p_i\log p_i$, whose gradient is $\nabla h(p)=\log p+1$ and whose inverse produces $p_i(\lambda)\propto p_{t,i}\exp(-\lambda g_{t,i})$. For positive parameters use $h(w)=\sum_i(w_i\log w_i-w_i)$, giving $w_i(\lambda)=w_{t,i}\exp(-\lambda g_{t,i})$. Pseudocode: compute minibatch loss $f_t$ and gradient $g_t$; set $\delta=[f_t-\widehat f_\star]_+$; if $\delta=0$, skip the update; otherwise define $x(\lambda)=\nabla h^{-1}(\nabla h(x_t)-\lambda g_t)$; solve $\phi(\lambda)=\langle g_t,x_t-x(\lambda)\rangle-\delta=0$ by expanding an upper bracket and then performing 8--12 bisection iterations; update $x_{t+1}=x(\lambda)$ and renormalize simplex tensors. Stop gradients through the root solve. Use a known loss lower bound when available; otherwise maintain an exponential minimum of recent losses and subtract a margin, $\widehat f_\star=\min_{s\leq t}f_s-m$, with $m\in\{0.01,0.05,0.1\}$. The inverse mirror map is analytic, so the only numerical operation is a scalar root solve. First test on CIFAR-10 with a two-layer MLP containing a softmax router or positive gate. Compare against SGD, AdamW, and Euclidean Polyak with matched gradient evaluations. Record training loss versus steps and FLOPs, validation accuracy, gradient spikes, root-failure frequency, clipping frequency, and router entropy. A successful result is faster loss descent or lower final loss at equal updates without exploding entropy or requiring a learning-rate sweep.

## Verification

- Status: failed_benchmark
- Mechanism evidence: yes
- Mechanism confirmed: no
- Practical verdict: inconclusive
- Verdict: Built an entropy-geometry Bregman-Projection Polyak optimizer for simplex variables with stable analytic mirror mapping and scalar bisection root solving. The mechanism manifested: small-gap lambda/delta matched 1/Var_p(g)=2.782415 within 4e-8 relative error, simultaneous gradient/gap scaling matched the predicted lambda->lambda/a law exactly, fixed-gap local scaling matched 1/a^2 within 1.5e-7, and root feasibility switched at the predicted reachable gap 0.86. In the toy optimization both methods converged to essentially zero loss; Euclidean Polyak was slightly better at step 10, so no practical optimization win was observed.

### Mechanism check

- Verdict: Built an entropy-geometry Bregman-Projection Polyak optimizer for simplex variables with stable analytic mirror mapping and scalar bisection root solving. The mechanism manifested: small-gap lambda/delta matched 1/Var_p(g)=2.782415 within 4e-8 relative error, simultaneous gradient/gap scaling matched the predicted lambda->lambda/a law exactly, fixed-gap local scaling matched 1/a^2 within 1.5e-7, and root feasibility switched at the predicted reachable gap 0.86. In the toy optimization both methods converged to essentially zero loss; Euclidean Polyak was slightly better at step 10, so no practical optimization win was observed.
- Confidence: 9/10
- Limitations: Only deterministic NumPy simplex optimization was tested, not a neural network, stochastic gradients, AdamW integration, CIFAR-10, wall-clock speed, clipping frequency, router entropy over training, or GPU behavior. The optimization comparison used the exact known optimum and a tiny 8-dimensional quadratic, so it establishes the mechanism rather than a general training advantage.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.4921
- Paired wins: 4/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_experiment.py](https://synthcore.org/code/948/bench_experiment.py)
- [bench_report.json](https://synthcore.org/code/948/bench_report.json)
- [experiment.py](https://synthcore.org/code/948/experiment.py)
- [report.md](https://synthcore.org/code/948/report.md)
- [report_bench_2026-09-01T163446.md](https://synthcore.org/code/948/report_bench_2026-09-01T163446.md)
- [results.json](https://synthcore.org/code/948/results.json)
- [Download all files as ZIP](https://synthcore.org/download/948)

## Disclaimer

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