# Tikhonov-Extragradient Bilevel Optimizer

- ID: 2814
- Canonical URL: https://synthcore.org/idea/2814/tikhonov-extragradient-bilevel-optimizer
- API JSON: https://synthcore.org/api/idea/2814.json
- API Markdown: https://synthcore.org/api/idea/2814.md
- Verification status: unverified
- Source: [arXiv:2608.29181](https://arxiv.org/abs/2608.29181)
- Category: optimization
- Solves: stability, accuracy, sample-efficiency
- ML areas: optimizer, fine-tuning, training-dynamics
- Math tags: optimization, convex-analysis, dynamical-systems
- Ratings: usefulness 6/10; difficulty 5/10; novelty 6/10

## Idea description

Use a decaying Tikhonov term to make inner training dynamics select a stable outer-preferred solution, and evaluate the regularized operator at a look-ahead point before updating parameters. This is intended for convex heads, adapters, equilibrium layers, or locally monotone inner objectives rather than unrestricted nonconvex end-to-end training.

## Mathematical statement

The paper studies the structured bilevel problem $\min_x H(x)=h(x)+\hat h(x)$ subject to $0\in V(x)+\partial\hat f(x)$, where $h$ is convex and differentiable, $V$ is continuous and monotone, and $\hat f,\hat h$ are proper lower-semicontinuous convex functions. The smooth adaptation sets $F(x)=V(x)$ and uses the dynamically regularized operator $F_{\lambda_k}(x)=F(x)+\lambda_k\nabla H(x)$, where $x$ is the trainable parameter vector, $F$ is the inner residual or inner gradient, $H$ is the outer validation loss, and $\lambda_k>0$ is a decaying outer-selection coefficient. The extragradient update first predicts $y_k=x_k-\eta F_{\lambda_k}(x_k)$ and then corrects with $x_{k+1}=x_k-\eta F_{\lambda_k}(y_k)$, where $\eta$ is the step size. A practical schedule is $\lambda_k=\lambda_0(k+1)^{-p}$ with $0<p\leq1$; positive regularization early selects among nearly equivalent inner solutions, while decay eventually emphasizes the inner problem.

## Key formulas

- $$\min_x H(x):=h(x)+\hat{h}(x)\quad\text{subject to}\quad 0\in V(x)+\partial\hat{f}(x).$$
- $$F_{\lambda_k}(x)=F(x)+\lambda_k\nabla H(x),\qquad \lambda_k=\lambda_0(k+1)^{-p},\quad 0<p\leq1.$$
- $$y_k=x_k-\eta F_{\lambda_k}(x_k),\qquad x_{k+1}=x_k-\eta F_{\lambda_k}(y_k).$$
- $$F_{\lambda_k}(y_k)=F(y_k)+\lambda_k\nabla H(y_k).$$

## Implementation notes

Integrate this at the inner optimizer for a bilevel task. Use a small pretrained encoder with a trainable linear classifier or LoRA adapter as $x$; define $F(x)=\nabla_xL_{\mathrm{train}}(x)$ and $H(x)=L_{\mathrm{val}}(x)$, preferably with the trainable block isolated so the inner objective is close to convex or locally monotone. At iteration $k$, compute a training gradient $g=\nabla_xL_{\mathrm{train}}(x)$ and validation gradient $v=\nabla_xL_{\mathrm{val}}(x)$, form $r=g+\lambda_kv$, and create look-ahead parameters $y=x-\eta r$. Recompute both gradients at $y$: $g_y=\nabla_yL_{\mathrm{train}}(y)$ and $v_y=\nabla_yL_{\mathrm{val}}(y)$, then update $x\leftarrow x-\eta(g_y+\lambda_kv_y)$. Use $\lambda_k=\lambda_0(k+1)^{-p}$, gradient clipping, and stop-gradient through $y$ for the first implementation. The mathematical quantities supplied by the method are the regularized operator and extragradient recursion; estimate approximate monotonicity empirically using random pairs, via $\langle F(x)-F(z),x-z\rangle/\|x-z\|^2$. Compare against SGD, AdamW, and ordinary extragradient at equal gradient evaluations on a frozen-feature classifier or LoRA model on AG News. Track validation loss, iterate displacement, gradient-angle oscillation, and final last-iterate accuracy. Success means reduced oscillation and better final validation accuracy at equal compute, with a target of 20% lower validation-loss variance or faster last-iterate convergence than SGD.

## Disclaimer

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