NeurIPS 2026 论文列表

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.

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.

Recursive training on synthetic data can drive generative models toward collapse, yet most explanations treat collapse as a statistical phenomenon: tail loss, variance shrinkage, or distributional drift. We develop a singular-geometric view of collapse. In a labeled Gaussian mixture abstraction of recursive self-training, we show that mode extinction induces a monotone trajectory in the real log-canonical threshold: as recursive resampling eliminates active modes, the overcomplete mixture moves through increasingly singular strata, with strictly decreasing singular complexity and growing Fisher-information nullity. We further show that this loss of identifiability begins before exact extinction: as a component's weight becomes small, Fisher curvature in its associated parameter directions shrinks proportionally, so exact singularity is the endpoint of a continuous near-nullity trajectory. Thus collapse corresponds not only to reduced distributional diversity, but also to a progressive loss of locally identifiable parameter directions. This theory separates the singular geometry of collapse from the multinomial/Wright--Fisher absorption dynamics. We also prove that, in the mixture abstraction, injecting enough real data prevents component extinction and keeps the singular-complexity trajectory from descending over a fixed horizon with high probability. We then use the theory to motivate loss-landscape diagnostics for neural recursive training, including Hessian spectra, Gauss--Newton effective rank, decoder-block curvature, feature-rank concentration, and local learning coefficient estimates. Across Gaussian mixtures, VaDE, standard VAEs, and a compact DDPM, we find that synthetic-only recursion exhibits the predicted geometric degeneration, that VaDE geometry diagnostics predict future component loss, and that real-data injection stabilizes both distributional and geometric collapse metrics.

Using neural networks to learn optimal transport (OT) maps via minimax optimization has gained increasing interest in generative modeling. However, the widely used semi-dual OT maximin formulation is known to suffer from spurious global solutions that do not correspond to valid transport maps, often addressed by regularizing the objective function. We provide an alternative explanation by showing that these spurious solutions are not stationary points of the associated loss, implying that their appearance in practice stems from the optimizer's failure to converge to stationary points in nonconvex-nonconcave settings. However, when the $c$-concavity constraints are imposed on the potential, commonly to stabilize training, we show that these spurious solutions become stationary. Based on these observations, we propose solving the semi-dual OT problem without $c$-concavity constraints, using optimizers that can reliably converge to stationary points corresponding to OT maps in nonconvex-nonconcave settings, such as a two-timescale extragradient (TTS-EG) method. At the formulation level, we further show that a Lagrangian-based OT minimax formulation provably eliminates spurious global solutions. Our empirical results demonstrate that TTS-EG reliably recovers OT maps under both semi-dual and Lagrangian-based OT formulations without any regularization.

We show that the MinMax algebra provides a form of recurrence that is expressively powerful, efficiently implementable, and most importantly it is not affected by vanishing or exploding gradient. We call MinMax Recurrent Neural Cascades (RNCs) the models obtained by cascading several layers of neurons that employ such recurrence. We show that MinMax RNCs enjoy many favourable theoretical properties. First, their formal expressivity includes all regular languages, arguably the maximal expressivity for a finite-memory system. Second, they can be evaluated in parallel with a runtime that is logarithmic in the input length given enough processors—and they can also be evaluated sequentially. Third, their state and activations are bounded uniformly for all input lengths. Fourth, at almost all points, their loss gradient exists and it is bounded. Fifth, they do not exhibit a vanishing state gradient: the gradient of a state w.r.t. a past state can have constant value one regardless of the time distance between the two states. Finally, we find empirical evidence that the favourable theoretical properties of MinMax RNCs are matched by their practical capabilities: they are able to perfectly solve a number of synthetic tasks, showing superior performance compared to the considered state-of-the-art recurrent neural networks; also, we train a MinMax RNC of 127M parameters on next-token prediction, and the obtained model shows competitive performance for its size, providing evidence of the potential of MinMax RNCs on real-world tasks.

State space models have shown strong potential to outperform Transformers, but their learning mechanisms remain poorly understood, particularly the conditions for successful parameter updates that preserve teacher information. Prior work attributes the difficulty of such updates to the vanishing gradient during backpropagation through time, in which error signals decay exponentially through repeated gradient multiplication. In this work, by expressing error signals explicitly as functions of inputs, we show that the conventional vanishing gradient framework is insufficient to explain the loss of information. Using this representation of error, we reveal that the memory of the input encoded in teacher information does not decay exponentially, and we analytically demonstrate that the loss of supervisory information cannot be alleviated through training. This result theoretically confirms the importance of the initial weights of SSMs and suggests that the recurrent layer does not require training. By performing experiments on both linear SSMs and a representative nonlinear SSM, including language modeling tasks, we confirm that appropriate initialization enables us to fix the recurrence, leading to more stable training of the entire network and higher performance than the conventional training scheme. Our results partially elucidate the learning mechanisms of SSMs and are expected to contribute to the development of improved RNN-based models.

Optimization under heavy-tailed stochastic noise remains a major challenge in modern machine learning, where classical moment assumptions often fail to capture realistic gradient distributions. In this work, we revisit robust estimation techniques and provide a systematic analysis of the Median-of-Means (MoM) estimator under a structured noise model that interpolates between a symmetric heavy-tailed distribution with bounded $\beta$-th moment ($\beta \in (0, 1]$) and a mean-zero distribution with bounded $\alpha$-th moment ($\alpha \in (1, 2]$). We derive new upper bounds on the variance and bias of MoM in this setting, thereby extending the applicability of existing results beyond purely symmetric or bounded-moment settings. Building on these properties, we study clipped stochastic optimization methods with MoM gradient estimation and establish high-probability convergence guarantees that hold for general $\beta \in (0, 1]$ and $\alpha \in (1, 2]$. Our bounds match or improve upon prior complexity guarantees while requiring weaker distributional assumptions, and they reveal that bias only affects the final neighborhood of convergence. Overall, this work advances the theoretical foundations for robust stochastic optimization in the presence of extreme gradient noise.

Optimization proxies amortize parametric constrained optimization by learning fast approximations of solution maps. Because these maps are smooth only within active-set regimes, the parameter space may split into combinatorially many critical regions, making finite-sample generalization and reliable constraint behavior central challenges. To address this challenge, this paper develops sparse stochastic masked Sobolev training for optimization proxies, augmenting value supervision with randomly selected solver-sensitivity targets rather than dense Jacobian matching. The mask acts as an algorithmic control: it exposes the proxy to local derivative information while avoiding overconstraint from conflicting active constraint set signals. We provide approximation bounds showing that, under coverage and regularity, joint value-and-Jacobian matching improves finite-sample generalization. Experiments characterize when and how this benefit appears. In smooth optimal-control distillation, where feasibility is guaranteed by construction, and only a few active-set regimes arise, Sobolev supervision reaches 95\% of teacher performance about $2.5\times$ faster than value-only training. In AC optimal power flow, masked Sobolev training keeps optimality gaps below 0.22\% across three PGLib networks while reducing the median worst-case constraint violation by up to $4\times$. A mean--variance portfolio study identifies the complementary limitation: when sensitivities are highly local or vanish across active-set regimes, derivative supervision can be less useful than value-only training.

Despite the remarkable progress of large Vision-Language Models (VLMs) in Radiology Report Generation (RRG), existing black-box autoregressive generation paradigms lack intermediate clinical logical reasoning. This deficiency renders such models prone to generating linguistically fluent reports with erroneous diagnostic findings, which manifest as plausible hallucinations and thereby undermine clinical reliability. To this end, we propose a novel RRG paradigm termed "Look-Before-You-Leap", aimed at enhancing the clinical logical reasoning capabilities of the model to improve diagnostic accuracy. Specifically, we first construct a self-evolving Radiological Skill (RadSkill) repository to guide the teacher model in distilling high-confidence explicit clinical reasoning, and further internalize this reasoning capability into the implicit diagnostic intuition of the RRG baseline. Building upon this foundation, a novel preference optimization method termed Psychometric Preference Optimization (PSY-PO) is proposed. Grounded in Item Response Theory (IRT) from psychometrics, this method precisely samples clinically misleading dispreferred reports for preference optimization, thereby effectively mitigating plausible hallucinations. Extensive experimental results demonstrate that our proposed method significantly enhances both the generation quality and trustworthiness of radiology reports.

We study bandit convex optimization (BCO) when feedback is adversarially delayed and the comparator sequence is also adversarially non-stationary. This setting arises in online advertising, recommender systems, and adaptive dosing, but existing algorithms either absorb one of the two axes into a black-box global penalty or pay a worst-case cost that ignores the local interaction between delay and drift. We propose Oracle-DARS-DBCO, a delay-aware blocking algorithm whose block length $K$ and one-point smoothing radius $\delta$ satisfy the single identity $K\delta^{2}\asymp n^{2}$. This identity cancels the multiplicative coupling between delay deviation and one-point estimator variance, so the regret of each segment is paid only on that segment. We prove matching upper and lower bounds on the expected dynamic regret: $\widetilde{O}\bigl(\sqrt{n}\,m^{1/4}T^{3/4}+\sqrt{d_{\max}\,mT}\bigr)$ for convex losses and $\widetilde{O}\bigl(n^{2/3}m^{1/3}T^{2/3}+d_{\max}\,m\log(eT/m)\bigr)$ for $\alpha$-strongly convex losses, where $m=S_{T}+1$ is the number of stationary segments and $d_{\max}$ is the worst-case delay. The matching Rademacher-sign lower bounds $\Omega\bigl(\sqrt{d(S_{T}+1)\,T}\bigr)$ and $\Omega\bigl(d(S_{T}+1)\bigr)$ show that the delay price is segment-local. On fourteen scaling experiments, the fitted log--log exponents agree with the predicted ones within $0.04$, and Oracle-DARS-DBCO reduces regret by up to $9.17\times$ relative to the strongest non-restarting baseline on a piecewise-stationary benchmark.

Ensemble sampling is a practically attractive approach to randomized exploration, but existing theoretical guarantees for linear bandits require ensembles much larger than what its practical motivation would suggest. In particular, the sharpest existing analysis achieves the ensemble complexity of $\Theta(d\log T)$, leaving a $\log T$ gap from the intrinsic $\Omega(d)$ ensemble-size barrier. We aim to narrow this gap by proposing an ensemble sampling algorithm that refreshes the ensemble only when the regularized Gram matrix changes substantially. This mechanism localizes the perturbation analysis to epochs with controlled Gram-matrix drift and reduces the sufficient ensemble size to $\Theta(d\log d+d\log\log T)$, while preserving the state-of-the-art $\tilde{\mathcal O}(d^{3/2}\sqrt T)$ regret for ensemble sampling with arbitrary bounded arm sets. We further show that, when the arm set is finite of cardinality $K$, the proposed algorithm achieves the sharper regret bound $\tilde{\mathcal{O}}(d\sqrt{T\log K})$. To the best of our knowledge, this is the first ensemble-sampling guarantee that simultaneously recovers both canonical regret scalings known for randomized linear bandit algorithms: the $\tilde{\mathcal{O}}(d^{3/2}\sqrt{T})$ rate for arbitrary bounded arm sets and the $\tilde{\mathcal{O}}(d\sqrt{T\log K})$ rate for finite arm sets. The algorithm also admits an anytime implementation without resetting past data, and experiments show that it remains competitive with baselines while using substantially smaller ensembles.

Linear contextual bandit algorithms are typically built around pointwise optimism: the exploration bonus is chosen large enough to upper-bound the value of every action with high probability. We study an alternative principle of quasi-optimism, in which the index is deliberately allowed to be smaller than a valid confidence bound. We analyze the algorithmic framework, EQOL, that replaces the usual confidence-radius bonus with the capped quadratic bonus min(c₁,t ‖x‖²_{V_t⁻¹}, c₂,t ‖x‖_{V_t⁻¹}). This index is generally not optimistic, since its quadratic branch can be pointwise smaller than the OFUL bonus. We prove a general regret bound for arbitrary schedules (c₁,t, c₂,t), separating the exploration cost from the quasi-optimistic residual. With a single gap-agnostic tuning, EQOL recovers the high-probability minimax O(d√T) regret bound and, under a positive contextual margin, a uniform gap-dependent O(d²/Δ_min,T) bound. We also provide a geometric interpretation of EQOL through action-dependent ellipsoids, clarifying how quasi-optimism differs from simply shrinking a UCB bonus. Experiments on synthetic and real-data contextual bandit benchmarks show that EQOL substantially outperforms existing algorithms.

We introduce **AutoSpec**, a neural network framework for discovering iterative spectral algorithms for large-scale numerical linear algebra and numerical optimization. Our self-supervised models adapt to input operators using coarse spectral information (e.g., eigenvalue estimates and residual norms), and predict recurrence coefficients for computing or applying a matrix polynomial tailored to a downstream task. The effectiveness of **AutoSpec** relies on three ingredients: an architecture whose inference pass implements short, executable numerical linear algebra recurrences; efficient training on small synthetic problems with transfer to large-scale real-world operators; and task-defined objectives that enforce the desired approximation or preconditioning behavior across the range of spectral profiles represented in the training set. We apply **AutoSpec** to discovering algorithms for representative tasks on spd matrices: accelerating matrix function approximation; accelerating sparse linear solvers; and spectral filtering/preconditioning for eigenvalue computations. On real-world matrices, the learned procedures deliver orders-of-magnitude improvements in accuracy and/or reductions in iteration count, relative to basic baselines. We find clear connections to classical theory: the induced polynomials may exhibit equioscillation behavior characteristic of Chebyshev polynomial approximation.

When auditing machine learning models, human experts sequentially inspect model predictions and explanations, gradually building a mental model of the model’s behavior to uncover errors. This manual process is critical for safe deployment in high-stakes domains but fundamentally limited in scalability. In this work, we propose a novel method to simulate this human auditing behavior for automating the auditing process. We formalize auditing as a sequential decision-making problem, modeled as a Markov decision process. Our state representation summarizes the auditor’s accumulated knowledge of model predictions and feature usage. Building on this formalization, we solve the MDP using reinforcement learning, yielding RLAuditor, which learns to select informative test samples to efficiently uncover model errors. We further connect our formalization to Theory of Mind, showing that our state mirrors how human auditors build mental models: its update rule is equivalent to Bayesian belief revision and it converges to the model’s behavioral pattern at an interpretable rate. We validate our approach on multiple ML models and datasets across different data modalities. In a human subject study, we demonstrate that RLAuditor helps human auditors produce more accurate audit reports in less time.

Stochastic Gradient Descent (SGD) is a workhorse algorithm for continuous optimization. It is a folklore belief among deep learning practitioners that learning rate decay in SGD substantially improves performance. However, it has remained unclear whether learning rate decay offers an asymptotic advantage for \emph{global} nonconvex optimization. We answer this question in the affirmative by demonstrating a natural class of nonconvex functions for which we prove that SGD with learning rate decay requires \emph{exponentially fewer} gradient queries for global optimization than SGD with any fixed learning rate. To the best of our knowledge, this is the first exponential advantage that has been demonstrated for learning rate decay. The class of functions we consider includes many popular benchmark nonconvex functions. Our results provide a robust explanatory theory for the empirically observed benefits of learning rate decay. Our technical results are built upon a new discretization analysis of SGD with decaying step size, that allows us to establish a clean correspondence with continuous-time annealing of Langevin diffusions. We then show that this annealed diffusion performs the non-logconcave sampling task associated to the optimization problem in polynomial time, via a novel application of weak Poincar\'{e} inequalities.

Robust optimization is a widely used framework for decision-making under uncertainty, particularly in high-stakes applications where reliability is critical. A key challenge in this paradigm lies in constructing uncertainty sets that balance robustness and performance: overly conservative sets lead to pessimistic decisions, while insufficient coverage risks failure in practice. Recent approaches based on conformal prediction provide finite-sample, distribution-free guarantees for uncertainty sets, but remain largely task-agnostic and disconnected from downstream decision objectives. In this paper, we propose a decision-aware conformal prediction framework that directly learns the geometry of uncertainty sets to improve robust decision-making. Our approach introduces a polyhedral nonconformity score that induces feature-dependent uncertainty sets, and a three-step procedure that integrates conformal calibration, robust-decision-aware learning, and re-calibration to correct for post-selection bias. We establish finite-sample coverage guarantees for the final, data-dependent uncertainty set, while achieving improved decision performance by reducing unnecessary conservativeness. This work bridges the gap between statistical validity and decision optimality, providing a principled framework for data-driven robust optimization.

Randomization is often used to compromise among fixed policies, classifiers, or interventions, but affected stakeholders may be unable or unwilling to report utilities over all alternatives. We study a weaker feedback model in which, for each proposed lottery, each stakeholder reports only whether it is acceptable. Unlike prior work focused on finding a unanimously acceptable lottery when one exists, we allow unanimity to be impossible and seek lotteries that minimize aggregate acceptability violations. We model each stakeholder's acceptable lotteries by an unknown linear threshold rule over the lottery simplex, and the learner may only ask accept/reject queries. Since binary labels do not reveal utility shortfalls, and such shortfalls are not comparable across stakeholders, we measure violation geometrically: the Euclidean distance, within the affine hull of the simplex, to the stakeholder's normalized acceptance hyperplane. These distances are aggregated using the power mean. Our results characterize exactly which boundary information can be learned from these queries. A deterministic algorithm uses $\mathcal{O}(nm\log(m/\varepsilon))$ queries to recover the normalized boundary whenever violation distances are identifiable from query answers. Otherwise, queries determine the acceptable face but not the rate at which violation grows away from it; this ambiguity is unavoidable. When no ambiguity arises, the aggregate violation objective can be optimized exactly. When it does, we optimize a convex worst-case upper bound objective based on distance to the learned acceptable set and prove an additive loss bound of $\sqrt{2}(|B|/n)^{1/p}$. We also prove structural properties of optimal lotteries, including a support-size bound of $n+1$, and give a limited-budget algorithm with additive-$\alpha$ guarantees. Synthetic experiments illustrate the resulting breadth-depth tradeoff and the effect of the power-mean parameter $p$ on violation distribution.

Optimizing neural networks for quantized objectives is fundamentally challenging because the quantizer is piece-wise constant, yielding zero gradients everywhere except at quantization thresholds where the derivative is undefined. Most existing methods deal with this issue by relaxing gradient computations with techniques like Straight Through Estimators (STE) and do not provide any guarantees of convergence. In this work, taking inspiration from Nesterov smoothing, we approximate the quantized loss surface with a continuous loss surface. In particular, we introduce LOTION, **L**ow-precision **O**ptimization via s**T**ochastic-no**I**se sm**O**othi**N**g, a principled smoothing framework that replaces the raw quantized loss with its expectation under unbiased randomized-rounding noise. In this framework, standard optimizers are guaranteed to converge to a local minimum of the loss surface. Moreover, when using noise derived from stochastic rounding, we show that the global minima of the original quantized loss are preserved. We empirically demonstrate that this method outperforms standard QAT on synthetic testbeds and on 150M-, 300M-, and 600M- parameter language models. On the 150M INT4 benchmark with modern QAT baselines, LOTION further achieves the best quantized validation loss.

Modern Bayesian optimization and adaptive sampling methods increasingly rely on nonlinear parametric models, yet theoretical guarantees for such models under adaptive data collection remain limited. Existing analyses largely focus on Gaussian processes, kernel machines, linear models, or linearized neural approximations, leaving a gap between theory and the nonlinear models used in practice. We develop a kernel-based framework for analyzing regularized nonlinear parametric models trained on adaptively collected data. Our approach uses kernels over the parameter space to induce reproducing-kernel Hilbert space structures over the corresponding model class, yielding confidence bounds for models trained with broad classes of regularized convex losses. We show how these bounds can support convergence guarantees for nonlinear acquisition and surrogate models, including randomized regularized policies that select points by maximizing a trained random model. These results provide a unified route to analyzing nonlinear parametric models in Bayesian optimization and related adaptive optimization settings.