Many equilibrium problems in learning and economics have the same shape. Each agent has a private, curved cost that only it knows: a smooth loss, an entropy term, a utility function. The agents interact only through a bilinear term, such as a price times a quantity or a strategy times a payoff matrix. Convex minimization written as a Fenchel game has exactly this form. In that rewriting, a "gradient player" and a "point player" compete over the payoff $\langle x, y\rangle - f^*(y)$, where $f^*$ is the convex conjugate of the objective. Linearly constrained resource allocation with a price-setting agent and regularized zero-sum games share the shape. In decentralized deployments the strategy actually played each round is what matters, because it is the allocation implemented or the policy executed, so we want the played strategies themselves to converge quickly. Each agent also sees only its own feedback. This is the standard notion of uncoupled learning: no agent knows the others' payoffs or algorithms.
The best tool for turning fast averaged convergence into fast convergence of the played strategy is the Average-to-Last reduction of Cai et al.. In that reduction, players publicly play their running average and recover per-round feedback by differencing averaged feedback. Its authors restrict it to linear utilities because the differencing trick fails once payoffs are nonlinear. Our observation is that the trick only needs linearity in the cross-player term. A player's own nonlinearity is something it can evaluate itself at its own point. This proposal builds a composite, weighted version of the reduction. The aim is to show that played strategies inherit accelerated averaged rates, up to $O(1/T^2)$ in the gap, on games with bilinear coupling and one-sided curvature. It also tests where the approach breaks, namely under noisy feedback.
Core Claim
Take a game in which player $i$ chooses $x_i$ in a convex set. Its loss is $h_i(x_i) + \sum_j \langle x_i, B_{ij} x_j\rangle$, where $h_i$ is a private convex function known only to player $i$ and the matrices $B_{ij}$ define the bilinear coupling. Any uncoupled no-regret algorithm run on this game can be wrapped so that the played profile at round $T$ equals the inner algorithm's weighted average, with weights $\alpha_t$. Every player sees exactly the feedback the original game would give its inner iterate. The wrapper works as follows. Player $i$ plays $\bar x_i^t = \sum_{k\le t}\alpha_k x_i^k / A_t$, where $A_t=\sum_{k\le t}\alpha_k$. It observes the coupling feedback $c_i^t = \sum_j B_{ij}\bar x_j^t$; if it only sees its full gradient at the played point, it subtracts its own $\nabla h_i(\bar x_i^t)$ first. It then extracts what its inner iterate would have faced:
$$ \sum_j B_{ij} x_j^t \;=\; \frac{A_t\, c_i^t - A_{t-1}\, c_i^{t-1}}{\alpha_t}. $$
The extracted feedback is exact because the coupling is linear in opponents' actions. The private curvature never passes through the differencing step, since the inner algorithm evaluates $h_i$ at its own iterate. The formula with $\alpha_t \equiv 1$ is the original reduction of Cai et al.. The weighted form with $\alpha_t = t$ is what lets us transfer the accelerated rates that optimistic learners obtain under linear weighting in Fenchel games, as shown in Abernethy et al. and Wang et al.. The expected payoff is a duality gap at the played profile of order $O(1/T^2)$ when one side is curved and smooth. That is a quadratic improvement over the $\Omega(1/\sqrt{T})$ floor that Golowich et al. prove for stationary first-order methods such as extragradient and optimistic gradient. There is no contradiction with their bound, because the wrapper is non-stationary: its effective step changes with $t$ through the weights.
Relation to Prior Work
The Fenchel-game line supplies the inner dynamics. Abernethy et al. and Wang et al. recast convex minimization as a zero-sum game and recover Nesterov acceleration from optimistic no-regret players. Abernethy et al. prove $O(1/T^2)$ and linear rates under weighted regret. All of these guarantees concern averaged iterates computed by a single designer who controls both players. We reuse their weighted optimistic learners unchanged and change only what is played and what is observed.
The uncoupled last-iterate line motivates the problem and also constrains it. Cai et al. give $O(\log d/T)$ last-iterate rates in polymatrix games but explicitly assume linear utilities; we relax exactly that assumption, and only in the cross-player term. Ito et al. obtain anytime last-iterate rates for stochastic monotone variational inequalities with a single-call regularized optimistic gradient, but in Euclidean geometry and with tuning that depends on the Lipschitz constant and noise level. Chen and Mazumdar show that generalized Frank-Wolfe and smoothed fictitious play reach $O(T^{-1/2})$ last-iterate in deterministic monotone variational inequalities. Both are natural competitors, not ingredients. Fiegel et al. constrain the design: under bandit feedback the uncoupled last-iterate rate cannot beat $T^{-1/4}$. We therefore restrict our claims to gradient feedback, exact or noisy, and do not pursue bandit feedback.
Research Program
The first component is analysis. We will state the composite weighted wrapper and prove that the duality gap at the played profile equals the inner weighted-average gap. We will check the conditions on the private term under which the inner algorithm still receives a valid loss sequence. We will then instantiate the wrapper with three inner learners. The first is the optimistic Fenchel dynamics of Abernethy et al., targeting $O(1/T^2)$ when one player's private term is smooth and strongly convex and the other's is linear. The second is optimistic multiplicative weights with an entropy private term, targeting the regularized-game regime. The third is optimistic follow-the-regularized-leader with dilated entropy on treeplexes, following Farina, Kroer, and Sandholm, to cover regularized extensive-form games. We will also bound each player's dynamic regret on played actions, mirroring the $O(\log d \log T)$ result of Cai et al.
The second component is the known weak point: noise. The extraction step multiplies observation error by roughly $A_t/\alpha_t$, which is of order $t$ under both uniform and linear weighting. Noisy gradients therefore produce extracted feedback whose noise grows with time. We will characterize this amplification and test one remedy: batch sizes that grow with the round, giving a matched cost in samples. We will report honestly the noise level beyond which the wrapper loses to regularized optimistic gradient. If no remedy works, the contribution is scoped to the deterministic setting, and we will say so.
Baselines
The naive reference point is uncoupled optimistic gradient descent-ascent, or optimistic multiplicative weights on simplices, run on the original game with its last iterate reported. This is what a practitioner would deploy without any reduction. We will also report its ergodic average, which isolates the value of making the played point converge.
The strongest existing competitor is regularized optimistic gradient from Ito et al.. It is single-call, uncoupled, and has anytime last-iterate guarantees in exactly our noisy regime. On their linear-operator benchmark it is reported to reach a gap "below $10^{-25}$" in the noiseless case over 500,000 iterations, with plain regularized gradient plateauing near $10^{-23}$. Because that benchmark's operator is linear, our wrapper reduces there to the original reduction. Beating it on that benchmark therefore means reaching a fixed precision such as $10^{-10}$ in fewer gradient calls, not reaching a lower floor. On composite games, beating it means a steeper fitted log-log slope of the gap at the played point: near $-2$ versus its roughly $-1$ noiseless rate. The second competitor is smoothed fictitious play / generalized Frank-Wolfe from Chen and Mazumdar, whose reported last-iterate rate is $O(T^{-1/2})$ deterministic and $O(T^{-1/6})$ stochastic. The third is the original linear-utility reduction of Cai et al. applied naively to composite games, treating the full gradient at the average as if it were linear. This should be biased, and it shows why the composite split matters. For extensive-form instances we add CFR+ and Discounted CFR as in Brown and Sandholm, using their last iterates.
All methods receive the same gradient-call budget. They get the same hyperparameter grid size, with step sizes tuned per instance on a held-out seed. Results are reported over 20 seeds. Two ablations isolate the key ingredients. The first sets $\alpha_t\equiv 1$, which tests whether weighting, rather than the reduction itself, carries the acceleration. The second replaces exact extraction with direct use of the feedback observed at the played point, which tests whether the extraction is necessary.
Why not just…?
Why not just output the running average, as no-regret theory already allows? For offline convex optimization this alternative is correct and costs nothing. Our wrapper's played point is that average, so we claim no gain there. The averaged strategy is not what the agents actually play, though. When allocations, prices, or policies are implemented every round, the oscillating per-round play of plain optimistic learners is what agents experience, as Cai et al. and Ito et al. both stress. The naive-baseline comparison of played versus averaged gaps will measure how large that difference is on each benchmark.
Why not just run optimistic gradient or extragradient and read off the last iterate? On smooth convex-concave problems, Golowich et al. prove these stationary methods cannot beat $\Omega(1/\sqrt{T})$ in last-iterate gap, and extragradient's second call requires querying opponents at hypothetical points. The real threat is strongly monotone instances, where every player has curvature, because simple optimistic methods already converge linearly there. We expect parity in that regime and gains only under one-sided curvature, the Fenchel and price-setting structure. The experiments separate the two regimes deliberately.
Why not just regularize the game and run optimistic multiplicative weights to a fast last iterate? Adding entropy to an unregularized game makes it strongly monotone. It also moves the equilibrium, so the result is biased unless the regularization is annealed, and annealing is exactly the schedule-tuning burden documented by Ito et al.. When the regularization is part of the true problem, as with quantal-response equilibria, this alternative is a strong baseline and is included as such.
Proposed Experiments
We will use four benchmark families from the file. The first is Fenchel games for smooth convex minimization over the simplex and the $\ell_2$ ball, the setting of Wang et al.. The y-player's private term is $f^*$ and the x-player is linear; we use quadratic and logistic objectives in dimensions 10 to 250. The second is the 10-dimensional hypercube linear variational inequality from Ito et al. at noise levels $\sigma\in\{0, 0.01, 0.1\}$, used as a linear-case sanity check and for the noise study. The third is Rock-Paper-Scissors, Burglar-Policeman, and $100\times100$ random zero-sum matrix games from Chen and Mazumdar, with and without a one-sided entropy term. The fourth is entropy-regularized Kuhn and Leduc poker. For the composite regularized variants, no reported result was found on Lacuna, so all baselines will be run fresh. We also add a synthetic linearly constrained resource-allocation game: $n$ agents with private strongly convex costs and a linear price player. No reported result was found on Lacuna for this game. Metrics are the duality gap or exploitability at the played profile, the fitted log-log slope over the second half of the run, gradient calls to reach $10^{-6}$ and $10^{-10}$, and per-player dynamic regret.
Three checks decide the outcome. First, on one-sided-curvature Fenchel games, the played-profile gap under the weighted wrapper should have slope near $-2$. Optimistic gradient and regularized optimistic gradient should sit near $-1$ or shallower, and the $\alpha_t\equiv 1$ ablation should sit near $-1$. If the weighted wrapper does not separate from its own ablation, the acceleration-transfer claim fails. Second, the naive linear reduction applied to composite games should stall at a nonzero gap while the composite wrapper does not. This confirms that the cross-player split is the operative ingredient. Third, we will sweep $\sigma$ to locate the crossover point at which regularized optimistic gradient overtakes the wrapper, with and without growing batches, under equal sample budgets. That crossover point defines the practical scope of the method, and it is a result we will report whichever way it falls.
References
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications
- Faster Rates for Convex-Concave Games
- No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization
- Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
- On Frank-Wolfe and Equilibrium Computation
- Acceleration through Optimistic No-Regret Dynamics
- Last-Iterate Convergence of Regularized Gradient Methods for Stochastic Monotone Variational Inequalities
- Last-Iterate Convergence for Generalized Frank-Wolfe in Monotone Variational Inequalities
- The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
- Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions
- Solving Imperfect-Information Games via Discounted Regret Minimization