NeurIPS 2026 Papers

We propose and study an online version of min-max optimization based on cumulative saddle points under a variety of performance measures beyond convex-concave settings. After first observing the incompatibility of (static) Nash equilibrium (SNE-Reg$_T$) with individual regrets even for strongly convex-strongly concave functions, we propose an alternate static duality gap (SDual-Gap$_T$) inspired by the online convex optimization (OCO) framework that is compatible with the individual regrets . We provide algorithms that achieve sub-linear regret bounds for (SDual-Gap$_T$) and the individual regrets and a novel dynamic saddle point regret (DSP-Reg$_T$), which we suggest naturally represents a min-max version of the dynamic regret in OCO. We derive our bounds for (SDual-Gap$_T$) and DSP-Reg$_T$ under strong convexity-strong concavity and a min-max notion of exponential concavity (min-max EC), and in addition we establish a class of functions satisfying min-max EC that captures a two-player variant of the classic portfolio selection problem. Finally, for a dynamic notion of regret compatible with individual regrets, we derive bounds under a two-sided Polyak-\L{}ojasiewicz (PL) condition.

We study adversarial online learning with hidden-convex losses, i.e., nonconvex losses that become convex after a nonlinear reparameterization. Ghai, Lu, and Hazan (NeurIPS 2022) proved that, under geometric and smoothness assumptions, online gradient descent (OGD) on such nonconvex losses approximately simulates online mirror descent (OMD) on the underlying convex losses with a suitable regularizer, yielding $\mathcal{O}(T^{2/3})$ regret. They left open whether the optimal $\Theta(\sqrt{T})$ regret from online convex optimization can be recovered in this hidden-convex setting. We answer this question affirmatively. More specifically, via a sharper discrete-time algorithmic equivalence argument, we prove that OGD achieves $\mathcal{O}(\sqrt{T})$ regret under the same assumptions, matching the optimal worst-case rate for adversarial online convex optimization. We also address another open question of Ghai, Lu, and Hazan by clarifying the geometry required for this algorithmic equivalence. We replace the diagonal-Jacobian sufficient condition with a necessary-and-sufficient Hessian compatibility condition, thereby expanding the class of admissible reparameterizations. We complement our tight regret bound with a lower bound showing that the Hessian compatibility assumption is essential for OGD; when it fails, we construct a smooth reparameterization and an adversarial sequence of hidden-convex losses for which OGD suffers $\Omega(T)$ regret. Finally, we extend our analysis to one-point bandit feedback and prove a $\mathcal{O}(T^{3/4})$ expected regret bound for bandit OGD with spherical smoothing, matching its classical rate on convex losses.

Direct Preference Optimization (DPO) has been widely adopted for aligning language models with human preferences. Recent empirical work has revealed that DPO induces remarkably sparse parameter updates, yet no theoretical explanation for this phenomenon has been offered. We analyze DPO's optimization dynamics under a neural tangent kernel linearization and show that the logistic structure of the DPO loss gives rise to an implicit maximum-margin bias. Building on this observation, we introduce the concept of dual sparsity: the DPO update direction is a sparse linear combination (data-level sparsity, driven by support vectors) of sparse gradient feature vectors (parameter-level sparsity, arising from gradient cancellation between preferred and dispreferred responses). We formalize this structure in our main theorem and present a framework relating it to weight disentanglement---a condition favorable for model merging. Experiments on GPT-2 Small and Medium with the Anthropic HH-RLHF and UltraFeedback datasets confirm both sources of sparsity and show that DPO reduces cross-task interference by up to $35 \times$ compared to supervised fine-tuning.

In stochastic (strongly) convex optimization, establishing last-iterate convergence guarantees for first-order methods has recently garnered increasing attention, as this not only deepens the theoretical understanding of these algorithms but also aligns more closely with practice. Notably, people have demonstrated that one of the most famous, simple, and popular methods, Stochastic Gradient Descent ($\mathtt{SGD}$), provably achieves last-iterate convergence. However, the existing results may have limited applicability, since they typically rely on strong conditions on the gradient noise (e.g., an exponentially decaying tail) rather than the more realistic heavy-tailed noise. Unfortunately, when faced with heavy-tailed noise, $\mathtt{SGD}$ is known to exhibit undesirable behavior or even fail to converge. To address the challenge of heavy-tailed noise, people have proposed $\mathtt{Clipped}\text{-}\mathtt{SGD}$, an algorithm that combines $\mathtt{SGD}$ with a simple mechanism, gradient clipping. Although $\mathtt{Clipped}\text{-}\mathtt{SGD}$ performs well in practice, its last-iterate convergence property remains highly underexplored. In this work, we prove the first optimal last-iterate rates in high probability for $\mathtt{Clipped}\text{-}\mathtt{SGD}$ under heavy-tailed noise, thereby closing a gap in the literature.

Success conditioning is a strategy for improving decision-making policies in stochastic environments; it updates a policy by increasing the probability of taking actions that yield successful outcomes. Success conditioning is common to many reinforcement learning applications, yet its limiting behavior and convergence rates are not well understood. In this work, we demonstrate that success conditioning converges to an optimal policy on a broad class of Markov decision processes (MDP). We also derive convergence rates in some common settings. For discounted MDPs, we prove convergence within $\mathcal{O}(1/\varepsilon^p)$ iterations to an $\varepsilon$-optimal policy, where the exponent $p$ depends on problem data. For single-period MDPs, $\mathcal{O}(1/\varepsilon)$ iterations are required.

Multicalibration gradient boosting has recently emerged as a scalable method that empirically produces approximately multicalibrated predictors and has been deployed at web scale. Despite this empirical success, its convergence properties are not well understood. In this paper, we provide computational guarantees for multicalibration gradient boosting algorithms. We show that the magnitude of successive prediction updates decays at $O(1/\sqrt{T})$, which implies the same convergence rate bound for the empirical multicalibration error over rounds. Under additional smoothness assumptions on the weak learners, this rate improves to linear convergence. We further establish convergence for adaptive variants. Experiments on real-world datasets support our theory and clarify the regimes in which the method achieves fast convergence.

The Lipschitz constant of a neural network is a basic stability quantity appearing in optimization guarantees, generalization bounds, and robustness certificates. Deep networks naturally admit two such notions, \emph{input Lipschitzness}, measuring sensitivity to data perturbations, and \emph{parameter Lipschitzness}, measuring sensitivity to weight perturbations. We prove that, for deep networks with normalization layers, with batch normalization as the canonical example, \emph{both} Lipschitz constants can grow exponentially with depth and hence with parameter dimension, even under strong per-layer norm control such as $\\|W_\ell\\|_2\le 1$, and already for linear activations. Thus, a mechanism widely used to stabilize training can create severe worst-case instabilities that are invisible from layerwise norm bounds alone. Parameter-Lipschitz explosion turns Lipschitz-dependent nonsmooth optimization guarantees into exponential-in-dimension bounds for deep normalized networks, while input-Lipschitz explosion makes worst-case Lipschitz-based generalization and robustness certificates vacuous. The latter also yields a concrete rank-separation mechanism for adversarial vulnerability. The theory predicts that perturbations introducing new singular directions should be amplified much more strongly than equal-energy perturbations that remain within the input's original singular subspace. Experiments on MNIST, Fashion-MNIST, and CIFAR-10 support this prediction, showing that rank-creating perturbations cause substantially sharper drops in accuracy, confidence, and margins than same-subspace perturbations.

Recent advances in deep learning have inspired neural network-based approaches to computational materials discovery (CMD). A plethora of problems in this field involve finding materials that optimize a target property. Nevertheless, the increasingly popular generative modeling methods are ineffective at boldly exploring attractive regions of the materials space due to their maximum likelihood training. In this work, we offer an alternative CMD technique based on offline model-based optimization (MBO) that fuses direct optimization of a target material property into generation. To that end, we introduce a domain-specific model, CliqueFlowmer, that incorporates recent advances in clique-based MBO into transformer and flow generation. We validate this model's optimization abilities and show that materials it produces strongly outperform those from generative baselines. To support specialized materials discovery applications and broader interdisciplinary research, we will release our code and model weights upon publication.

Existing decentralized stochastic optimization methods assume the lower-level loss function is strongly convex and the stochastic gradient noise has finite variance. These strong assumptions typically are not satisfied in real-world machine learning models. For example, learning on language data typically leads to heavy-tailed gradient. To address these limitations, we develop a novel decentralized stochastic bilevel optimization algorithm for the nonconvex bilevel optimization problem under heavy-tailed noise. Specifically, we develop a normalized stochastic variance-reduced bilevel gradient descent algorithm, which does not rely on any clipping operation. Moreover, we establish its convergence rate by innovatively bounding interdependent gradient sequences under heavy-tailed noise for nonconvex decentralized bilevel optimization problems. As far as we know, this is the first decentralized bilevel optimization algorithm with rigorous theoretical guarantees under heavy-tailed noise. The extensive experimental results confirm the effectiveness of our algorithm in handling heavy-tailed noise.

Targeted Minimum Loss-based Estimation (TMLE) is a classical plug-in debiasing methodology that delivers doubly robust estimation and asymptotically efficient inference. Despite its statistical guarantees, each iteration of standard TMLE requires solving a minimization subproblem over the entire dataset, resulting in prohibitive computational and memory costs that render the method impractical for large-scale or real-time settings. To ease the bottlenecks, we introduce stochastic TMLE, a randomized targeting procedure that replaces each expensive full-batch fluctuation fit with mini-batch alternatives. Our theoretical analysis establishes that the stochastic iterates converge to a neighborhood (noise ball) centered around the target solution, and crucially, only a small number of subsequent full-sample TMLE iterations suffice to reach an empirical efficient influence function root. Consequently, our stochastic variant inherits the same guarantees and attractive properties as classical TMLE while substantially reducing per-iteration complexity. We further propose two computational variants with provable guarantees that broaden the algorithmic design space, offering flexibility for future developments in scalable targeted learning. Extensive experiments across diverse regimes demonstrate substantial acceleration over standard TMLE without sacrificing inferential quality.

Existing federated learning setups assume either a single global model or a fixed decomposition with one globally shared parameter block and one client-specific private block. In this paper, we study a generalized federated optimization setting where each client optimizes a local coordinate block, and two clients interact only when their blocks overlap. We encode these coordinate overlaps by a graph on clients, called the nerve skeleton. Based on this structure, we propose Nerve-Skeleton Message Passing (NSMP), a two-phase protocol on a spanning tree: a leaf-to-root pass composes reduced objectives by partial minimization, and a root-to-leaf pass reconstructs a joint assignment. We further show that, under the tree-elimination schedule in the paper, NSMP is equivalent to minimizing the joint objective, where the leaf-to-root phase evaluates the optimal objective value, and the root-to-leaf phase recovers a globally optimal assignment. Experiments show that NSMP solves federated optimization with overlapping parameters using only efficient neighbor-to-neighbor message passing.

Langevin Dynamics (LD) provides a principled framework for solving combinatorial optimization problems (COPs) via gradient-guided stochastic search. However, classical LD faces two bottlenecks: 1) the utilization of uniform initialization may affect its convergence speed; 2) when applied to COPs such as routing problems that cannot be naturally formulated as Quadratic Unconstrained Binary Optimization (QUBO), classical LD suffers from slow convergence and inferior performance compared to existing learning-to-construct (L2C) methods, as it requires manually designed discrete proposals for updates. These proposals are typically local and induce abrupt transitions in the solution space, hindering escape from local optima and degrading performance. To address these issues, we propose NLD4CO, a unified framework that synergizes data-driven learning with LD. It introduces two instantiations: explicit-gradient (EG) and implicit-gradient (IG). NLD-EG accelerates sampling efficiency for energy-based problems via neural warm-start initialization. NLD-IG utilizes the corrective direction predicted by a consistency model as an implicit score function to guide the search, making structured, globally coordinated transitions for general COPs. Extensive evaluations on MIS, MWIS, TSP, and CVRP demonstrate that NLD4CO achieves SOTA performance, delivering superior solution quality with competitive or lower runtime.

We study stochastic multi-objective optimization when each objective may be non-smooth and non-convex. We introduce the notion of $(\delta,\epsilon)$-Pareto Goldstein stationary points (PGSP) to characterize the convergence of solving multi objective optimization. The $(\delta,\epsilon)$ generalizes the definition of $(\delta,\epsilon)$-Goldstein stationary point for single objective non-smooth non-convex optimization and the $\epsilon$-Pareto stationary point for solving multi objective optimization with smooth objectives. We propose the multi-gradient-free method (MGFM), which finds $(\delta,\epsilon)$-PGSP with $\tilde{\mathcal{O}}(m^2d^{3/2}\delta^{-1}\epsilon^{-4})$ oracle complexity to the stochastic function values, where $m$ is the number of objectives and $d$ is the problem dimension. We further propose MGFM+, a faster multi-gradient-free method based on variance reduction, which improves the complexity to $\tilde{\mathcal{O}}(m^2d^{3/2}\delta^{-1}\epsilon^{-3})$. These provide the first non-asymptotic analysis for multi-nonsmooth-nonconvex-objective optimization. \end{abstract}

Different optimizers impose different geometries on parameter updates. Adaptive methods such as Adam and AdamW use coordinate-wise updates, while matrix-aware optimizers such as Muon utilize weight-matrix structure through orthogonalized updates. For Graph Neural Networks (GNNs), however, the effective geometry of its weight matrices is shaped not only by its learned channel-mixing weights, but also by the graph-propagated representations it acts on. Thus, even if an update is well normalized as a matrix, its effect on the layer output can be amplified when applied to graph-propagated features. To address this gap, we introduce GraphMuon, a graph-aware optimizer that adapts Muon's matrix updates to the covariance structure of graph-propagated layer inputs. GraphMuon performs orthogonalization in a metric defined by these propagated representations and normalizes step sizes according to the update's induced effect on the layer representation. We show that theoretically, vanilla Muon can suffer from graph-induced update amplification, while our GraphMuon can mitigate this effect. As such, our GraphMuon yields a graph-metric analogue of Muon's polar update step. Empirically, we show that GraphMuon achieves $2.13\times$-$7.38\times$ speedups in time-to-target wall-clock runtime over AdamW across diverse graph-learning regimes, while maintaining competitive or superior predictive performance.

LLM post-training is usually framed as a choice of optimizer, but KL-regularized RL also makes a hidden geometric choice: it fits the learned policy to a reward-tilted target by reverse KL. This places PPO, GRPO, RLOO, REINFORCE++, and related methods at a fixed mode-seeking point in a broader design space. We propose \textbf{Mode-Controlled Policy Optimization (MCPO)}, a geometry-aware recipe that replaces this inherited point with an $\alpha$-divergence dial over mode-seeking versus mode-covering behavior; $\alpha{=}0$ recovers the classical reverse-KL recipe. MCPO admits an off-policy objective, a practical grouped importance-weighted estimator, and a baseline-centered variant for stable training. Across mathematical reasoning, agentic transfer, search-based QA, and safety, no single geometry is uniformly best. Average-case math favors stronger concentration, while pass-based math and Search-QA favor broader support; agentic transfer moves with metric and scale; safety exposes a base-dependent frontier in which the same refusal-only signal can transfer broadly or spill into benign boundary cases depending on the reference model's mode landscape. MCPO's value is therefore not a new universal objective, but a way to expose and select the post-training geometry that RL with fixed reverse-KL geometry silently chooses.

Most work on improving large language models treats accuracy as the sole objective. We argue that the harness — the Python code surrounding the model that constructs prompts, routes calls, and parses outputs — is a first-class design surface whose quality is inherently multi-objective: an accurate harness that refuses no unsafe request, or that consumes an order of magnitude more tokens, is not a good harness. We present Meta-Harness, a system that casts harness design as search over three per-domain objectives — accuracy, behavioural safety, and token cost — solved by an agentic proposer (Claude Code) with full filesystem access to prior harness source, execution traces, and scoring artifacts. Our central finding is that a single-phase joint-reward proposer (MoMHa) outperforms every alternative, including a two-phase "accuracy then tokens" ablation, scalar-only feedback, and an accuracy-only baseline. We evaluate on seventeen domains: seven synthetic capability suites, seven real-world public benchmarks (HumanEval, MBPP, Spider, FEVER, MMLU-Pro, LawBench, NuminaMath), and three U-SafeBench-derived user-specific safety domains, using a 12-model fleet spanning four families. On the synthetic track MoMHa achieves a joint mean of 0.482 versus 0.198–0.422 for ten baselines, winning 7/10 per-domain columns; on the real-world track it scores 0.461 versus 0.377 for the strongest baseline (DSPy), winning 5/7 columns — demonstrating that harness strategies transfer to unseen benchmarks without retraining on 8 of 12 target models. MoMHa attains the highest measured behavioral safety composite (U-SafeBench, 0.781) and uses 95 fewer tokens per example than the two-phase alternative. We will release all harness code, evaluation infrastructure, and cross-model logs.

Memory-efficient personalization is essential for adapting text-to-image diffusion models while preserving user privacy and operating within the limited computational resources of edge devices. To this end, we propose Mix-Opt, a novel mixed optimization framework that adaptively chooses between backpropagation on low-resolution images (BP-low) and zeroth-order optimization on high-resolution images (ZO-high), guided by the characteristics of the diffusion process. As observed in our experiments, BP-low efficiently adapts the model to target-specific features, but suffers from structural distortions due to resolution mismatch. Conversely, ZO-high refines high-resolution details with minimal memory overhead but faces slow convergence when applied without prior adaptation. By complementing both methods, our framework leverages BP-low for effective personalization while using ZO-high for structural consistency, achieving memory-efficient and high-quality fine-tuning. To maximize the efficacy of both BP-low and ZO-high, we introduce a timestep-aware probabilistic function that dynamically selects the appropriate optimization strategy during training. This function mitigates the overfitting from BP-low at high timesteps, where structural information is critical, while ensuring ZO-high is applied more effectively as training progresses. Experimental results demonstrate that our method achieves competitive performance while significantly reducing memory consumption, enabling scalable, high-quality personalization without increasing inference latency.

Data heterogeneity and low client participation are two key challenges in federated learning (FL). Client-reshuffling-based FL methods were recently introduced to improve participation efficiency by visiting each client once per meta-epoch; however, the resulting \textit{without-replacement} sampling induces inter-round dependence and conditional bias. As a consequence, existing client-reshuffling methods can still suffer from the data heterogeneity challenge due to this dependence. To bridge this gap, we propose \textbf{FedCDR}, a client-reshuffling FL algorithm built on Douglas–Rachford splitting. FedCDR supports \textit{inexact} local proximal updates via iterative solvers, enabling a practical communication–computation trade-off. For smooth nonconvex objectives, FedCDR with inexact local solvers attains a state-of-the-art $O(\epsilon^{-1})$ communication complexity to reach an $\epsilon$-approximate stationary point (i.e., $\mathbb{E}\|\nabla f(\tilde{x})\|^2 \le \epsilon)$, with the leading constant that is \textbf{independent of data heterogeneity} (i.e., it does not scale with common measures of heterogeneity). Technically, our analysis operates at the meta-epoch level: we control the deviation between reshuffled and full-client updates, construct a tailored potential function with provable descent, and sum over each meta-epoch to eliminate reshuffling-induced dependence. Experiments on synthetic tasks and benchmark datasets under heterogeneous partitions, including a 10,000-client setting, demonstrate consistent improvements over strong baselines and their client reshuffling variants.

We study two variants of the mirror descent-ascent (MDA) algorithm for solving min-max problems on the space of measures: simultaneous and alternating. We work under assumptions of convexity-concavity and relative smoothness of the payoff function with respect to a suitable Bregman divergence, defined on the space of measures via flat derivatives. We establish non-asymptotic convergence rates to mixed Nash equilibria, measured in the Nikaido-Isoda error, proving an $\mathcal{O}(N^{-1/2})$ rate for simultaneous MDA and an improved $\mathcal{O}(N^{-2/3})$ rate for alternating MDA. The main technical contribution is an infinite-dimensional dual space analysis that relates Bregman divergences on measures to dual Bregman divergences on spaces of bounded continuous functions, allowing us to control asymmetric commutator terms created by alternating updates. The results substantially generalize prior analyses restricted to bilinear objectives and also apply to nonlinear convex-concave problems on measure spaces, thereby providing a unified theoretical foundation for MDA in mean-field min-max optimization.