# PEP-Synthesized Minimax Optimizer

- ID: 2125
- Canonical URL: https://synthcore.org/idea/2125/pep-synthesized-minimax-optimizer
- API JSON: https://synthcore.org/api/idea/2125.json
- API Markdown: https://synthcore.org/api/idea/2125.md
- Verification status: mechanism_failed
- Source: [arXiv:2608.11412](https://arxiv.org/abs/2608.11412)
- Category: optimization
- Solves: stability, speedup, accuracy
- ML areas: optimizer, gan, training-dynamics
- Math tags: optimization, convex-analysis, linear-algebra
- Ratings: usefulness 7/10; difficulty 6/10; novelty 7/10

## Idea description

Use the interpolation SDP to synthesize coefficients for a short-memory first-order minimax optimizer with a certified worst-case contraction rate. The resulting recurrence can combine current and previous iterates and gradients, providing an offline-designed alternative to hand-tuned simultaneous descent-ascent, extragradient, or optimistic-gradient updates.

## Mathematical statement

For a saddle objective f(x,y), x is minimized and y is maximized. Let u_i^x=x_i and g_i^x=gradient_x f(x_i,y_i), with analogous definitions u_i^y=y_i and g_i^y=gradient_y f(x_i,y_i). The matrix M(mu,L) encodes the necessary and sufficient interpolation inequality for a mu-strongly convex, L-smooth function: the quadratic form [u_i,u_j,g_i,g_j]^T M(mu,L)[u_i,u_j,g_i,g_j] is nonnegative for every pair. Bilinear coupling is encoded by cross-Hessian sample matrices B_Hx and B_Hy and variable sample matrices B_vx and B_vy. G_x and G_y are Gram matrices of x- and y-side vectors, and L_xy bounds the coupling operator norm. A first-order method with memory N is represented as a linear recurrence on stacked histories. The PEP searches for Lyapunov matrices P_x and P_y and a contraction factor rho satisfying V_{k+1}-rho^2 V_k less than or equal to zero over every feasible Gram matrix.

## Key formulas

- $$M(\mu,L):=\frac{1}{2}\begin{bmatrix}-\mu L&\mu L&\mu&-L\\\mu L&-\mu L&-\mu&L\\\mu&-\mu&-1&1\\-L&L&1&-1\end{bmatrix},\qquad M^x:=M(\mu_x,L_x),\quad M^y:=M(\mu_y,L_y).$$
- $$M^x_{ij}:=\begin{bmatrix}u_i^x\\u_j^x\\g_i^x\\g_j^x\end{bmatrix}^{\!\top}M^x\begin{bmatrix}u_i^x\\u_j^x\\g_i^x\\g_j^x\end{bmatrix}\ge 0,\qquad M^y_{ij}:=\begin{bmatrix}u_i^y\\u_j^y\\g_i^y\\g_j^y\end{bmatrix}^{\!\top}M^y\begin{bmatrix}u_i^y\\u_j^y\\g_i^y\\g_j^y\end{bmatrix}\ge 0.$$
- $$B_{Hx}^{\top}G_xB_{vx}=B_{vy}^{\top}G_yB_{Hy},\qquad B_{Hx}^{\top}G_xB_{Hx}\preceq L_{xy}^{2}B_{vy}^{\top}G_yB_{vy},\qquad B_{Hy}^{\top}G_yB_{Hy}\preceq L_{xy}^{2}B_{vx}^{\top}G_xB_{vx}.$$
- $$\mathcal V_k=\begin{bmatrix}\mathbf x_k\\\mathbf g_k^x\\\mathbf h_k^x\end{bmatrix}^{\!\top}P_x\begin{bmatrix}\mathbf x_k\\\mathbf g_k^x\\\mathbf h_k^x\end{bmatrix}+\begin{bmatrix}\mathbf y_k\\\mathbf g_k^y\\\mathbf h_k^y\end{bmatrix}^{\!\top}P_y\begin{bmatrix}\mathbf y_k\\\mathbf g_k^y\\\mathbf h_k^y\end{bmatrix}+p_x^{\top}\mathbf f_k^x+p_y^{\top}\mathbf f_k^y,\qquad \mathcal V_{k+1}-\rho^2\mathcal V_k\le 0.$$

## Implementation notes

(1) Integration point: replace the update in a two-player training loop, such as a GAN generator-discriminator loop or adversarial fine-tuning loop. Start with memory N=1. Deploy the linear recurrence x_{k+1}=a_0 x_k+a_1 x_{k-1}-b_0 g_k^x-b_1 g_{k-1}^x and y_{k+1}=c_0 y_k+c_1 y_{k-1}+d_0 g_k^y+d_1 g_{k-1}^y. The coefficients are fixed after offline synthesis. (2) Pseudocode: choose mu_x, mu_y, L_x, L_y, and L_xy; enumerate K symbolic oracle states; create a positive-semidefinite Gram matrix G containing all iterate, gradient, and coupling vectors; impose every convex-concave interpolation constraint M^x_ij >= 0 and M^y_ij >= 0; impose the three bilinear coupling matrix constraints; encode the recurrence as linear relations among state columns; solve an SDP for P_x, P_y, p_x, p_y and rho. If coefficient synthesis is not convex jointly with the certificate, grid the four coefficients or alternate between coefficient search and SDP certification. (3) The mathematics computes the feasible interpolation region and certified rho. For neural objectives, estimate L_x and L_y from Hessian-vector power iterations and estimate L_xy from cross-Jacobian-vector products, then inflate all estimates by 10 to 30 percent. (4) First experiment: use the quadratic game f(x,y)=0.5 mu_x ||x||^2+x^T A y-0.5 mu_y ||y||^2 and an MLP GAN on eight-Gaussians. Compare against simultaneous gradient descent-ascent, extragradient, OGDA, and Adam at matched gradient cost. Measure equilibrium error, oscillation amplitude, divergence frequency, and steps to a fixed error. Success is faster convergence or fewer divergences under large coupling norm ||A||.

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built a reproducible short-memory minimax recurrence search and compared it with tuned simultaneous GDA on the scalar quadratic game. The searched recurrence reduced worst-case design spectral radius from 0.9978 to 0.9476, but the supplied interpolation matrix produced negative quadratic forms for 40.2% of valid sampled scalar quadratics, so its stated nonnegativity claim failed. The intended mechanism therefore was not validated; additionally, the synthesized rho was essentially flat rather than increasing with coupling, and both methods remained stable through the tested design range.

### Mechanism check

- Verdict: Built a reproducible short-memory minimax recurrence search and compared it with tuned simultaneous GDA on the scalar quadratic game. The searched recurrence reduced worst-case design spectral radius from 0.9978 to 0.9476, but the supplied interpolation matrix produced negative quadratic forms for 40.2% of valid sampled scalar quadratics, so its stated nonnegativity claim failed. The intended mechanism therefore was not validated; additionally, the synthesized rho was essentially flat rather than increasing with coupling, and both methods remained stable through the tested design range.
- Confidence: 9/10
- Limitations: This is a scalar quadratic spectral-radius MVP, not a full interpolation SDP or neural/GAN experiment. No Lyapunov certificate, multidimensional matrix coupling, Hessian estimation, FLOP-matched training, or statistical multi-seed evaluation was performed. The interpolation formula was tested exactly as supplied; its sign/convention issue was not repaired into a new certified method.

## Artifacts

- [pep_minimax.py](https://synthcore.org/code/855/pep_minimax.py)
- [report.md](https://synthcore.org/code/855/report.md)
- [results.json](https://synthcore.org/code/855/results.json)
- [Download all files as ZIP](https://synthcore.org/download/855)

## Disclaimer

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