NeurIPS 2026 Papers

Pass@$k$ is a widely used performance metric for verifiable large language model tasks, including mathematical reasoning, code generation, and short-answer reasoning. It defines success if any of $k$ independently sampled solutions passes a verifier. This multi-sample inference metric has motivated inference-aware fine-tuning methods that directly optimize pass@$k$. However, prior work reports a recurring trade-off: pass@$k$ improves while pass@1 degrades under such methods. This trade-off is practically important because pass@1 often remains a hard operational constraint due to latency and cost budgets, imperfect verifier coverage, and the need for a reliable single-shot fallback. We study the origin of this trade-off and provide a theoretical characterization of when pass@$k$ policy optimization can reduce pass@1 through gradient conflict induced by prompt interference. We show that pass@$k$ policy gradients can conflict with pass@1 gradients because pass@$k$ optimization implicitly reweights prompts toward low-success prompts; when these prompts are what we term \emph{negatively interfering}, their upweighting can rotate the pass@k update direction away from the pass@1 direction. We illustrate our theoretical findings with large language model experiments on verifiable mathematical reasoning and coding tasks.

$(1+1)$-evolution strategy (ES) is a classic variant of evolution strategy for black-box optimization via direct and random search while keeping only a single solution per generation in $\mathbb{R}^n$. Despite convergence with different step-size adaptations, it often remains impractical due to dependence on the unfavorable high dimension of the search space $\mathbb{R}^n$. In fact, many modern optimization problems are naturally constrained to low-dimensional manifolds embedded in very high-dimensional ambient spaces. To see the potential of intrinsic dimensionality reduction for improving practicality, we consider the truncated Riemannian $(1+1)$-ES on a compact Riemannian submanifold $\mathcal{M}\subset\mathbb{R}^n$ and establish its non-asymptotic stationarity guarantee at the standard nonconvex zeroth-order rate of $\widetilde{\mathcal{O}}(\varepsilon^{-4})$ function evaluations. The explicit Gaussian second-moment term in the bound scales with the intrinsic tangent dimension $d=\dim\mathcal{M}$ rather than the ambient dimension $n$, while the remaining truncation dependence is captured by an explicit small-ball drift constant $\alpha_d(R/\sigma_0)$. To the best of our knowledge, this gives the first non-asymptotic stationarity analysis for a comparison-based ES-type method on compact nonconvex Riemannian submanifolds under localized pullback smoothness. Numerical illustrations on sparse PCA over spheres and smooth-surrogate stationarity diagnostics illustrate behavior consistent with the theory and its limitations, while additional experimental studies on truncation radius diagnostics, black-box tuning, and classical evolutionary computation benchmarks support the practical relevance of geometry-aware comparison-based search under limited function-evaluation budgets.

In this paper, we provide improved bounds on the complexity of solving $\ell_p$-Lipchitz convex optimization problem in parallel. We lower bound the depth of highly-parallel algorithms, i.e., the number of rounds required by a parallel algorithm making $O(\mathrm{poly}(d))$ queries per round to compute an $\epsilon$-approximate minimizer of a $\ell_p$-Lipschitz, $d$-dimensional convex function over the unit $\ell_p$ ball. We provide a framework for proving lower bounds for parallel $\ell_p$-Lipschitz convex optimization that generalizes prior lower bound proofs and for all $p \in (1,\infty)$ (other than 2) improves the depth for which it can be shown that no super-polylogarithmic improvement over sequential algorithms is possible. We also prove a variety of new lower bounds for $p>2$. Notably, for $p=\infty$, we establish the near optimal parallel complexity of the class of ball-acceleration methods up to depth $\tilde{O}(\sqrt{d})$, which is the first near-optimality result in the parallel convex optimization setting for an algorithm other than mirror descent. Additionally, by providing new algorithms we characterize the optimal depth needed to solve to accuracy $\epsilon = d^{-1/4}$ for all $p \geq 2$ (up to polylogarithmic factors). We also provide extensions of our lower bounds to parallel quantum $\ell_p$-Lipschitz convex optimization.

Scaling laws and hyperparameter tuning remain central challenges in training large-scale models, particularly under differential privacy (DP), where optimization is further complicated by noise injection and per-sample gradient clipping. While Maximal Update Parametrization ($\mu$P) allows for zero-shot hyperparameter transfer in standard training, we show that it fails under DP constraints due to the distinct spectral properties of high-dimensional noise versus low-rank gradients. In this work, we introduce DP-$\mu$P, a theoretically grounded framework that extends $\mu$P to the privacy-preserving setting. By analyzing the interaction between gradient clipping, noise injection, and feature learning, we derive a Signal-to-Noise Ratio (SNR) condition that governs layer-wise learning rate scaling. Combining this with our proposed spectral scaling formulation, we provide specific scaling rules for DP-SGD, DP-Adam, and DP-Muon. Empirically, we demonstrate that DP-$\mu$P enables effective zero-shot transfer of learning rates across model widths on diverse architectures (MLP, ViT, GPT-2), matching or exceeding the performance of individually tuned baselines while significantly reducing computational costs.

Initialization determines the optimization ``fate'' of a model, going far beyond just setting the scale of its weights. It establishes a fundamental initial geometry over the data, permanently dictating which examples are considered close, which directions are easy to change, and which representations gradient descent will naturally refine first. Because this starting point dictates the model's future trajectory, we ask: can this initial geometry be explicitly chosen by referencing a completely different architecture? To achieve this, we introduce representational similarity as an optimization prior. This is an initialization-only procedure that aligns a target network to the representational geometry of a randomly initialized guide network before any downstream training occurs. Crucially, the guide network transfers no learned knowledge: it is frozen, never sees labels. We demonstrate that this cross-architecture transfer of fate works in two key domains: instilling the optimization benefits of depth into shallow targets by aligning them to deeper, randomly initialized guides, and transferring representational granularity by using fine-resolution guides to shape the initialization geometry of networks built with coarser representations. Ultimately, this establishes that a model's architectural destiny can be decoupled from its physical structure and explicitly programmed at initialization.

Zeroth-order optimization (ZOO) has emerged as a promising approach for fine-tuning Large Language Models (LLMs) when gradient access is unavailable or memory-prohibitive. However, ZOO relies on estimating gradients via finite differences between two function evaluations at perturbation scale $\mu$, making it inherently noisier than its first-order counterpart. This raises a fundamental question: \textit{under what conditions does ZOO yield reliable gradient estimates?} In this work, we provide a rigorous variance-theoretic answer through a generic noise-amplification framework and demonstrate that the reliability of ZOO gradient estimations is structurally determined by whether the two finite-difference evaluations are performed on \textit{matched data}. Mismatched evaluations, as induced by on-policy Reinforcement Learning (RL), produce a $1/\mu^2$ oracle-noise amplification that sets an irreducible noise floor, whereas matched evaluations, as realized by offline optimization methods such as Boltzmann Targeted SFT (BOLT), eliminate this amplification entirely via noise cancellation. We further derive convergence guarantees with explicit constants that cleanly separate the two regimes. Controlled experiments on math reasoning tasks validate these findings, using ZooBOLT and ZooGRPO --- zeroth-order adaptations of BOLT and GRPO --- as representatives of the matched- and mismatched-data regimes respectively. On GSM8K with Qwen2.5-1.5B, ZooBOLT recovers $96.1\%$ of first-order BOLT's performance gains, while ZooGRPO exhibits near-zero learning despite its first-order counterpart achieving strong results. This qualitative separation persists across harder benchmarks (MATH), larger model scales (Qwen2.5-7B), and different model variants (DeepSeek-R1-Distill-Qwen-1.5B). Additionally, ZOO methods reduce peak memory to near-inference levels, validating its practicality as a memory-efficient fine-tuning paradigm.

Predictive models on structured tabular data often face imbalanced targets: training emphasizes common values while rare outcomes stay underrepresented. Distributionally robust optimization hedges against shift, but standard ambiguity sets use a single radius over the entire distribution, so adversarial mass concentrates on dense regions and rare target ranges remain weakly protected; worst-case statements then track bulk behavior rather than tails. We introduce target-conditional distributionally robust optimization (TC-DRO), which defines ambiguity per target region with radii that grow where data are scarce. We establish coverage, per-region excess risk that tightens with local sample size when standard DRO yields vacuous tail guarantees, and a dual as weighted empirical risk with theory-derived density-adaptive weights. Experiments on seven tabular benchmarks show that Wasserstein DRO collapses to empirical risk minimization under uniform weights, while global $\chi^2$-DRO can remain close to ERM in practice; TC-DRO improves tail MSE and SERA relative to both standard training and recent imbalanced-regression methods.

Large language models (LLMs) deployed as agents remain vulnerable to prompt-based instruction injection, where user inputs induce the model to violate higher-priority system directives. Existing methods often treat violations as a coherent class or rely on surface text patterns, which can limit robustness as attack strategies evolve. In this paper, we investigate LLM hidden-state dynamics under attack and uncover a phenomenon we term Asymmetric Logic: the model's response generations concentrate in a relatively low-variability region of latent representation space when it's compliant to the system prompt, while compromised behaviors exhibit diverse deviations. Based on this observation, we propose Asymmetric Entropic Optimization (AEO), a novel framework that monitors the internal shifts in latent representations to detect and proactively rectify anomalous behaviors. Our method effectively identifies logic deviations by quantifying the entropic divergence between the compliant manifold and the chaotic violation space. Across a range of state-of-the-art LLM backbones, AEO demonstrates strong robustness to diverse instruction injection attacks. For instance, on Qwen2.5-14B-Instruct, AEO attains a detection AUC of 97.28% with FPR95 of only 10.38%. The same chaos score also gates a lightweight post-hoc correction module that lifts overall instruction-following accuracy from 63.94% to 76.00% on IHEval, without any model fine-tuning. The code is available at https://anonymous.4open.science/r/AEO-code-56D2/.

We study stochastic zeroth-order (ZO) optimization of smooth nonconvex objectives under heavy-tailed sample-gradient noise, a regime motivated by empirical evidence that gradient noise in modern machine learning can violate the bounded-variance assumption underlying classical ZO theory. While the first-order literature has established optimal rates under bounded $p$-th moment noise for $p \in (1,2]$, analogous high-probability guarantees for nonconvex ZO optimization remain largely unexplored. The ZO setting is not a direct corollary of first-order theory: first-order methods update using $\nabla F(x;\xi)$, the same object on which the noise assumption is imposed, whereas derivative-free methods only observe noisy function values and construct directional finite-difference estimates. Thus, weak-$L_p$ control of $\nabla F(x;\xi)-\nabla f(x)$ must first be transferred to scalar two-point directional estimates, a concentration step absent from standard first-order analyses. We propose the Robust Scalar-Clipped Zeroth-Order method (\textbf{RSC-ZO}), a two-point method that clips each scalar directional derivative before aggregation. Under sample-wise smoothness and a weak-$L_p$ tail bound on the sample-gradient noise, RSC-ZO finds an $\varepsilon$-stationary point with high probability using $ \widetilde{O}\\left( \frac{d^{\frac{p}{2(p-1)}}} {\varepsilon^{\frac{3p-2}{p-1}}} \right) $ noisy function evaluations, matching the optimal first-order $\varepsilon$-dependence. At $p=2$, our bound becomes $\widetilde{O}(d\varepsilon^{-4})$, matching the classical dimension-accuracy dependence for stochastic ZO methods under bounded-variance noise, which is typically established only in expectation. In contrast, our guarantee holds with high probability and under the strictly weaker weak-$L_2$ tail condition, which can allow infinite gradient-noise variance. We further extend the analysis to a momentum variant and quantify the resulting batch-size/stepsize tradeoff.

Stochastic reconfiguration (SR) is the standard optimizer for neural quantum states (NQS), but modern NQS often have far more parameters than Monte Carlo samples. We show that in this regime the diagonal shift is more than a numerical stabilizer. It acts as a statistical filter for finite-sample generalization. At a fixed wave function, SR is ridge regression from tangent features to the centered local energy. Its residual is the expressivity gap, the part of imaginary-time evolution outside the current tangent space. This gap is orthogonal to the tangent space in population, but finite batches make it act as noise that SR can overfit. The shift therefore balances shrinkage of useful update directions against variance from fitting sampled residuals. Exact $4\times4$ $J_1$-$J_2$ experiments separate two effects of overparameterization. Larger tangent spaces help when they reduce the expressivity gap, but they can hurt when they overfit a fixed gap. In a $100$-site transverse-field Ising family trained with a foundation NQS, validation risk is U-shaped in the shift while variance decreases, matching the noisy-ridge model. This view leads to multi-shift SR (MS-SR), which averages independent ridge solves at data-adaptive shifts to form a richer, lower-variance spectral filter. MS-SR lowers validation risk and stays closer to the ideal tangent-space imaginary-time update compared to other competitive NQS optimizers.

We study stochastic simple bilevel optimization with smooth, possibly nonconvex upper- and lower-level objectives accessed only through stochastic gradient oracles. A key challenge is that the dual multiplier induced by the lower-level constraint may become unbounded near lower-level stationary points, invalidating bounded-dual analyses and destabilizing stochastic gradient estimates. To address this, we propose \emph{Stochastic Dynamic Barrier Perturbed Gradient} (SDBPG), a single-loop method that adaptively perturbs the dual formulation to regularize this degeneracy. The perturbation stabilizes the multiplier and yields controlled bias and variance even near the lower-level stationarity region. Under a mild rare-visit assumption, SDBPG finds an $(\epsilon_f,\epsilon_g)$-stationary point in $\mathcal{O}(\max\{\epsilon_f^{-2},\epsilon_g^{-2}\})$ iterations, with sample gradient complexities $\mathcal{O}(\epsilon^{-4})$ and $\mathcal{O}(\epsilon^{-6})$ for the upper- and lower-level objectives where $\epsilon=\max(\epsilon_f,\epsilon_g)$. We further develop PR-SDBPG, a penalty-regularized variant that eliminates the rare-visit assumption, and VR-PR-SDBPG, which improves the resulting sample complexities entirely through variance reduction. To our knowledge, these are the first explicit $(\epsilon_f,\epsilon_g)$-stationarity guarantees for stochastic nonconvex-nonconvex simple bilevel optimization.

This paper initiates the study of a stochastic approximation approach with the Fully Stochastic Primal Dual Algorithm (FSPDA) framework for decentralized optimization on random and time varying topologies. Our framework relies on a novel observation that randomnesses in time varying topology can be incorporated into a stochastic equality constrained optimization formulation. We derived two new algorithms supporting sparsified communication on time varying topologies --- FSPDA-SA allows agents to execute multiple local gradient steps to accelerate convergence, and FSPDA-STORM further incorporates variance reduction to improve sample complexity. For problems with smooth (possibly non-convex) objective function, within $T$ iterations, FSPDA-SA (resp. FSPDA-STORM) finds an $\mathcal{O}( 1/\sqrt{T} )$-stationary (resp. $\mathcal{O}( 1/T^{2/3} )$) solution. The latter shows the first near-optimal convergence rate over time varying topology.

Large-scale Ising optimization underlies critical optimization and learning applications, including correlation clustering, MAP inference, and energy-based models. Spectral relaxation methods run in polynomial time but yield solutions with significant optimality gaps while metaheuristics close those gaps but scale poorly to large instances. In particular, spectral methods are inherently single-shot as they solve exactly one eigenvalue problem. We introduce $\textit{Spectral Annealing}$ (SpecAnn), a new spectral optimization approach that transforms traditional spectral methods from single-shot approximations into exploration-based optimization, by sweeping a parametrized normalization path from the raw adjacency to the signed normalized Laplacian, with an $O(n)$ diagonal predictor that warm-starts successive eigensolves and GPU-batched local search refining candidates in parallel. Experiments on general Ising problems demonstrate that SpecAnn achieves competitive to near-optimal solutions depending on instance structure, with runtimes less than 7 minutes for instances of 8.4M variables. SpecAnn delivers up to 83$\times$ speedup over recent GPU-accelerated methods while maintaining superior solution quality, and scales successfully beyond 524K variables where traditional metaheuristics fail.

Exact solution of hard combinatorial optimization problems often relies on strong convex relaxations, but solving these relaxations repeatedly inside a branch-and-bound algorithm can be prohibitively expensive. Hence, we consider this challenge for \new{Max-Cut problem} (Max-Cut), where branch and bound commonly uses semidefinite programming (SDP) relaxations to bound subproblems. We propose a Max-Cut-specific \new{graph neural network} that serves as a principled, lightweight neural proxy for these SDP solvers and can be plugged directly into an exact branch-and-bound framework. The proposed architecture has update steps of complexity $\mathcal{O}(n^2 + ne)$, and predicts both primal- and dual-feasible SDP solutions. The primal SDP solutions yield feasible Max-Cut solutions via the Goemans--Williamson algorithm. In addition, it is trained in a self-supervised fashion without requiring solved SDP relaxations as labels. Empirically, we show that our architecture can substantially reduce the cost of bounding in exact Max-Cut solving by up to $10.6 \times$ compared with using the state-of-the-art SDP solver Mosek. Our work highlights the potential of learned, validity-preserving surrogates for accelerating exact optimization over structured convex relaxations.

Second-order methods are provably faster than first-order methods, and their efficient implementations for large-scale optimization problems have attracted significant attention. Yet, optimization problems in ML often have nonsmooth derivatives, which makes the existing convergence rate theory of second-order methods inapplicable. In this paper, we propose a new semismooth Newton method (SSN) that enjoys both global convergence rates and asymptotic superlinear convergence without requiring second-order differentiability. Crucially, our method does not require (generalized) Hessians to be evaluated at each iteration but only periodically, and it reuses stale Hessians otherwise (i.e., it performs lazy Hessian updates), saving compute cost and often leading to significant speedups in time, whilst still maintaining strong global and local convergence rate guarantees. We develop our theory in an infinite-dimensional setting and illustrate it with numerical experiments on matrix factorization and neural networks with Lipschitz constraints.

While adaptive gradient methods are the workhorse of modern machine learning, sign-based optimization algorithms such as Lion and Muon have recently demonstrated superior empirical performance over AdamW in training large language models (LLM). However, a theoretical understanding of why sign-based updates outperform variance-adapted methods remains elusive. In this paper, we aim to bridge the gap between theory and practice through the lens of heavy-tailed gradient noise, a phenomenon frequently observed in language modeling tasks. Theoretically, we introduce a novel generalized heavy-tailed noise condition that captures the behavior of LLMs more accurately than standard finite variance assumptions. Under this noise model, we establish sharp convergence rates of SignSGD and Lion for generalized smooth function classes, matching or surpassing previous best-known bounds. Furthermore, we extend our analysis to Muon and Muonlight, providing what is, to our knowledge, the first rigorous analysis of matrix optimization under heavy-tailed stochasticity. These results offer a strong theoretical justification for the empirical superiority of sign-based optimizers, showcasing that they are naturally suited to handle the noisy gradients associated with heavy tails. Empirically, LLM pretraining experiments validate our theoretical insights and confirm that our proposed noise models are well-aligned with practice.

Existing guarantees for misspecified kernelized bandit optimization pay for misspecification through kernel complexity: in generic offline bounds, the misspecification level $\varepsilon$ is multiplied by $\sqrt{d_\mathrm{eff}}$, where $d_\mathrm{eff}$ is the kernel effective dimension, while in online regret bounds, the corresponding penalty is $\sqrt{\gamma_n}\,n\varepsilon$, where $\gamma_n$ is the maximum information gain after $n$ rounds of interaction. In this work, we show that, for a large class of kernels, the misspecification amplification can be reduced to logarithmic or polylogarithmic growth. In the offline setting, we first prove high-probability simple-regret bounds whose misspecification term is governed by a spectral Lebesgue constant. This yields logarithmic amplification for one-dimensional monotone spectra and polylogarithmic amplification for multivariate Fourier-diagonal product kernels. In the online setting, we modify a domain-splitting algorithm and prove a cumulative regret bound of $\widetilde{\mathcal O}(\sqrt{\gamma_n n}+n\varepsilon)$ under mild localized eigendecay assumptions, removing the extra $\sqrt{\gamma_n}$ factor from the misspecification term. The common principle is localization: spectral localization controls the Lebesgue constant of the offline approximation operator, while domain splitting implements the spatial analogue of this mechanism in the online setting, preventing local misspecification errors from being amplified globally.

We study optimistic bilevel optimization when the lower-level problem has a non-isolated manifold of minimizers. In this setting, the hyper-objective may be non-differentiable because the upper-level criterion must choose among multiple lower-level solutions. Under a local Polyak--{\L}ojasiewicz (P{\L}) condition, we show that differentiability does not require the lower-level solution set to be a singleton: uniqueness of the optimistic selection is sufficient. This yields an explicit pseudoinverse-based hyper-gradient formula extending the classical singleton-minimizer result. We further characterize the regularity of the hyper-objective: non-degeneracy of the selected minimizer along the solution manifold yields local smoothness, while failure of uniqueness can create many non-differentiable points and failure of non-degeneracy can destroy all positive H\"older regularity of the hyper-gradient. Motivated by this theory, we propose HG-MS, a select-then-differentiate method combining explicit optimistic selection with efficient pseudoinverse-based hyper-gradient computation. Despite the nonconvex nature of optimistic selection over the lower-level solution manifold, we show that HG-MS converges to a stationary point of the optimistic objective with complexity governed by the intrinsic dimension of the solution manifold rather than its ambient dimension. Empirically, we test a practical variant of HG-MS for matched-budget LLM source reweighting. This variant preserves the select-then-differentiate principle and obtains the best GSM8K/MATH scores across the tested backbones, along with competitive or best MT-Bench instruction-following results.

We establish sample complexity results for stochastic optimization over the integers, especially with a view to understand the complexity with respect to the corresponding continuous optimization problem. We show that integer optimization can sometimes require strictly more samples and sometimes strictly smaller number of samples, depending on the structure of the objective and constraints. 1. For Lipschitz objectives over subsets of the $\ell_\infty$ ball, the statistical complexity of general stochastic mixed-integer, nonlinear, nonconvex optimization is exactly the same as stochastic linear optimization with just bound constraints. 2. For Lipschitz objectives over subsets of the $\ell_2$ ball, we show that integer optimization can require strictly *smaller* sample size compared to the continuous setting in a certain regime. To get to this result, we also establish tight sample complexity results for nonconvex continuous stochastic optimization which, to the best of our knowledge, do not appear in prior work. 3. For strongly convex, smooth objectives, integer optimization has high statistical complexity compared to the continuous setting. In particular, we show that integer optimization requires $\Omega(1/\epsilon^2)$ samples to report an $\epsilon$-approximate solution, compared to the well-known $O(1/\epsilon)$ sample complexity from the continuous optimization literature.