# Curvature-Certified Frank–Wolfe Routing

- ID: 1086
- Canonical URL: https://synthcore.org/idea/1086/curvature-certified-frank-wolfe-routing
- API JSON: https://synthcore.org/api/idea/1086.json
- API Markdown: https://synthcore.org/api/idea/1086.md
- Verification status: unverified
- Source: [arXiv:2607.17684](https://arxiv.org/abs/2607.17684)
- Category: dynamics
- Solves: stability, accuracy, scalability
- ML areas: moe-routing, optimizer, training-dynamics
- Math tags: convex-analysis, optimization, dynamical-systems, geometry
- Ratings: usefulness 5/10; difficulty 5/10; novelty 5/10

## Idea description

Replace an unconstrained simplex router or differentiable mixture layer with a resource-cost-aware router whose learned costs satisfy the paper's monotonicity curvature condition. Use a Euclidean-regularized Frank–Wolfe oracle to update routing probabilities, which should reduce cycling and sensitivity when several examples or agents compete for the same experts.

## Mathematical statement

The paper defines the admissible cost class by \(f'(x)\ge 0\) and \(\Theta_f(x):=2f'(x)+xf''(x)\ge 0\) for every resource load \(x\ge 0\), equivalently requiring the individual resource cost \(g(x)=xf(x)\) to be convex because \(g''(x)=2f'(x)+xf''(x)\). For player \(i\), let \(x_i\in K_i\) be its nonnegative allocation over resources, let \(d_i>0\) be its total mass, and let \(K_i=\{x_i\in\mathbb{R}_+^E:\sum_{e\in E}x_{i,e}=d_i\}\). The product feasible set is \(K=\prod_iK_i\). If total load on resource \(e\) is \(x_e=\sum_i x_{i,e}\), the atomic marginal-cost operator is \(F_{i,e}(x)=f_e(x_e)+x_{i,e}f'_e(x_e)\). The transferred design uses the same curvature condition for each learned resource cost \(f_e\), and applies a regularized linear oracle \(v_i=\arg\min_{y_i\in K_i}\{\langle F_i(x),y_i\rangle+(\lambda/2)\|y_i-x_i\|_2^2\}\), followed by the discrete Frank–Wolfe relaxation \(x_i^{t+1}=(1-\gamma_t)x_i^t+\gamma_t v_i^t\). Here \(\lambda>0\) is Euclidean regularization, \(\gamma_t\in(0,1]\) is the step size, and the simplex tangent space is \(T_i=\{h_i:\sum_eh_{i,e}=0\}\), with orthogonal projection \(P_i\) onto \(T_i\). The simplex result motivates checking positive stability of the tangent-projected Jacobian \(P_TJF(x^*)P_T\) at an interior equilibrium, even when the full operator is not monotone.

## Key formulas

- $$f^{\prime}(x)\geq 0,\qquad \Theta_f(x):=2f^{\prime}(x)+xf^{\prime\prime}(x)\geq 0\quad\forall x\in\mathbb{R}_{+},$$
- $$K_i=\left\{x_i\in\mathbb{R}_{+}^{E}:\sum_{e\in E}x_{i,e}=d_i\right\},\qquad T_i=\left\{h_i\in\mathbb{R}^{E}:\sum_{e\in E}h_{i,e}=0\right\},\qquad P_T=\operatorname{blkdiag}(P_1,\ldots,P_n),$$
- $$x_e=\sum_i x_{i,e},\qquad F_{i,e}(x)=f_e(x_e)+x_{i,e}f_e'(x_e),$$
- $$v_i^t=\arg\min_{y_i\in K_i}\left[\langle F_i(x^t),y_i\rangle+\frac{\lambda}{2}\|y_i-x_i^t\|_2^2\right],\qquad x_i^{t+1}=(1-\gamma_t)x_i^t+\gamma_t v_i^t.$$

## Implementation notes

Integrate this as a replacement for the routing update in a small mixture-of-experts layer, differentiable dispatch layer, or neural mixture model. Let each token or batch member be a player, each expert be a resource, and let \(x_{i,e}\) be its soft assignment with fixed row sum \(d_i=1\). At every routing iteration, compute expert loads \(x_e=\sum_i x_{i,e}\), evaluate a shared or expert-specific cost \(f_e(x_e)\), and form marginal costs \(F_{i,e}=f_e(x_e)+x_{i,e}f'_e(x_e)\). Parameterize costs as positive mixtures of convex monomials, for example \(f_e(z)=a_{e,0}+\sum_{k=1}^K a_{e,k}z^{p_k}\) with \(a_{e,k}\ge0\) and \(p_k\ge1\); this guarantees \(f'_e\ge0\) and \(\Theta_{f_e}\ge0\). Compute the regularized oracle by projecting \(x_i^t-F_i(x^t)/\lambda\) onto the simplex, then update \(x_i^{t+1}=(1-\gamma_t)x_i^t+\gamma_t v_i^t\). Use \(\gamma_t=1/(t+1)\) for a conservative baseline and compare with fixed \(\gamma\). The paper supplies the curvature certificate; estimate empirical local stability by finite differences or automatic differentiation of the tangent-projected Jacobian \(P_TJF(x^*)P_T\). First test on CIFAR-100 with a 4-expert top-1 or soft MoE router and a small ResNet or Transformer, comparing against standard softmax routing plus a load-balancing loss. Measure validation accuracy, expert-load variance, router oscillation between iterations, gradient norm spikes, and loss decrease at equal routing FLOPs. The expected signal is fewer routing oscillations and more stable training, with equal or better accuracy under deliberately imbalanced expert capacities.

## Disclaimer

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