NeurIPS 2026 论文列表

Backdoor attacks implant a trigger-target association into a model, causing malicious behavior at test time while largely preserving clean performance. Despite extensive empirical study, a unified explanation for why standard training dynamics learn backdoors so effectively remains largely missing. We argue that backdoor learning can be understood as a consequence of simplicity-biased optimization dynamics: trigger features are dynamically simpler than semantic features under stochastic gradient descent (SGD) because they induce more coherent gradient alignment, more stable gating behavior, and stronger early-stage amplification. To formalize this perspective, we introduce a directional data model that separates semantic and trigger features and study a one-hidden-layer ReLU network trained by SGD. Our analysis identifies a frozen-gate signal that governs group-wise early-stage loss decrease up to controlled gate-drift and gate-flip errors, yielding a quantitative explanation for faster poisoned-sample fitting and its dependence on the poisoning ratio. Beyond optimization dynamics, we show that this early-stage bias can induce trigger-dominant neurons with selective activation on poisoned inputs, explaining why vanilla clean fine-tuning can attenuate backdoor behavior without necessarily erasing the underlying trigger-related representation. Empirically, we validate the predicted signatures of early-stage optimization bias, representation-level trigger dominance, and post-training residual behavior using ResNet-18 on standard image classification benchmarks.

Deep Q-Networks (DQNs) approximate value iteration by freezing a target network, forming Bellman-optimality targets, and running an inner regression loop that minimizes a smooth \emph{surrogate loss} (e.g., MSE/Huber loss) on data from a replay buffer. Yet, control is governed by the Bellman optimality operator's $\gamma$-contraction in $\ell_\infty$, whereas common objectives (MSE/Huber loss) measure progress in an averaged $\ell_2/\ell_1$ geometry; thus, improving the surrogate need not reduce the worst-case Bellman error that drives performance. To bridge this gap we connect the progress in the inner loop for each surrogate to the Bellman residual under the $\ell_\infty$ norm. Our analysis provides explicit thresholds denoted by $\alpha$ under which sufficient progress guarantees a $\ell_\infty$ contraction up to a standard approximation floor. This yields new convergence guarantees for DQN with fixed targets trained using MSE or Huber-type losses, and motivates a novel soft-$\ell_\infty$ surrogate that smoothly approximates the sup-norm and better matches the $\ell_\infty$ geometry resulting in the least stringent inner loop accuracy requirements. Across Atari benchmarks, soft-$\ell_\infty$ consistently reduces the worst-case Bellman residual and matches or improves returns relative to standard objectives, providing a practical, geometry-aligned recipe for stable DQN training.

Variational quantum algorithms (VQAs) rely on gradient-based optimization over parameterized circuits whose loss landscape lives on a manifold of quantum states. Quantum natural gradient (QNG) accounts for this geometry through the quantum Fisher information matrix (QFIM). However, estimating the full QFIM is prohibitively expensive within practical quantum circuit shot budgets. Existing tractable approximations either discard inter-block couplings, as in block-diagonal QNG, or replace the QFIM with a measurement-induced classical Fisher surrogate, as in random natural gradient (RNG). We propose a locality-aware surrogate that targets the QFIM through its covariance representation in terms of propagated generators, retaining a structured subset of informative cross-parameter couplings while remaining practical to estimate under finite-shot budgets. Our construction combines three ingredients: weight-$k$ Pauli truncation to control estimation variance, support-overlap masking to exploit sparsity, and single-dataset classical-shadow estimation that reuses the same shadow dataset across all retained metric entries. Truncation level $k$ provides a bias--variance tradeoff: larger $k$ captures more of the propagated-generator structure but increases estimation cost, making it a budget-constrained design choice. Circuit parameters whose truncated generators remain nonzero form an active set receiving surrogate-QNG updates, while the rest follow standard gradient descent. We provide finite-shot concentration bounds for the shadow-estimated surrogate and convergence guarantees to a stationary neighborhood under standard smoothness assumptions. Experiments on variational quantum eigensolver (VQE) instances with local ans\"atze for Heisenberg and Ising spin chains show improved convergence per cumulative shot relative to SGD, Adam, block-diagonal QNG, and RNG baselines under finite-shot budgets, including on systems up to 16 qubits.

While the maximal coding rate reduction (MCR$^2$) objective has become a useful principle for learning compact and discriminative representations, a theoretical understanding of its optimization geometry remains limited, especially on why first-order methods often exhibit fast convergence near its local maximizers. In this work, we show that the MCR$^2$ objective satisfies an error-bound property in a neighborhood of its local maximizers. This property guarantees that the distance to the local maximizer set can be bounded above by the gradient norm at any point in the neighborhood, directly implying regularity conditions such as the Polyak-Lojasiewicz inequality and quadratic growth. Leveraging this property, we prove that first-order methods converge linearly to a local maximizer of the MCR$^2$ objective under mild conditions. Numerical experiments validate the predicted local convergence behavior and provide empirical evidence that optimizing the MCR$^2$ objective improves representation geometry while maintaining competitive downstream accuracy.

A common approach for contextual optimization first trains a model to predict the unknown state from the context, and then takes the action that is optimal for the predicted state. We show that this follow-the-prediction policy can be brittle: for several standard problems, even a minimum-variance predictor with arbitrarily small RMSE can incur constant excess loss. We propose a simple policy that robustifies any black-box predictor by optimizing against the worst case in an $\varepsilon$-neighborhood of the prediction. We identify a problem-specific quantity, the \emph{robust optimization gap}, that captures the price of this hedging, and prove a general bound on the loss. We instantiate the framework for contextual posted pricing, ski rental, and house flipping, deriving closed-form robust policies and $O(\eta^{2/3})$ loss bounds in all three settings, where $\eta$ is the RMSE of the predictor. For posted pricing, this improves upon a result of Medina and Vassilvitskii (2017), and with a substantially simpler argument.

We propose the Grid Efficient Transport Optimization Linear Programming (GETO-LP) model, a novel formulation of the Fixed-Support Wasserstein barycenter problem for $M$ probability distributions supported on $d$-dimensional grids. While standard LP models require $O(MN^2)$ variables, the GETO-LP model requires only $O(dMN^{1+\frac{1}{d}})$, with $N$ being the total number of points in the grid support. Despite the reduced number of variables, our formulation is \emph{exact}, meaning that its solution fully characterizes both the barycenter $\nu$ and the optimal transport plans between $\nu$ and each of the $M$ input distributions without additional optimization steps. We validate the GETO-LP model via extensive comparisons with classical and entropic regularization solvers, demonstrating its effectiveness on both synthetic data and real-world applications such as color palette manipulation and medical data averaging. Overall, our approach provides an effective formulation for the Wasserstein barycenter problem, offering a memory-efficient alternative that naturally integrates with other existing computational frameworks.

Decentralized stochastic minimax optimization has recently attracted significant attention due to its applications in machine learning. However, existing state-of-the-art methods use learning rates of different scales for the primal and dual variables, making them difficult to tune in practice. To address this problem, this paper proposes a novel doubly smoothed decentralized stochastic minimax algorithm. Specifically, in terms of algorithm design, we update both the primal and dual variables using smoothed gradients and introduce novel approaches to handle the computation and communication of the auxiliary variables introduced by the smoothing technique. On the theoretical side, for nonconvex-PL problems, our convergence analysis reveals that the learning rates for the primal and dual variables are of the same scale. Moreover, the order of the condition number in our convergence rate is improved to $O(\kappa^{3/2})$. To the best of our knowledge, this is the first time it has been improved to such a favorable order. Finally, extensive experimental results validate the effectiveness of our algorithm.

This paper studies the problem of jointly learning a reward function, a cost function, and a policy from an expert's preferences. We formulate the problem as a constrained bi-level optimization problem, where the upper level infers the reward and cost functions from preferences, while the lower level optimizes a policy to best align with those preferences. To solve this problem, we propose a double-loop algorithm, Constrained Bi-level Optimization for Preference-Based Reinforcement Learning (CB-PbRL), which solves the lower-level optimization problem in the inner loop and the upper-level optimization problem in the outer loop. We establish a theoretical guarantee that CB-PbRL converges at a rate of $\mathcal{O}(1/\sqrt{K})$, and we demonstrate its effectiveness across multiple simulation environments.

Optimizing non-convex functions is a fundamental challenge across machine learning and combinatorial optimization. We introduce and study $\gamma$-weakly $\theta$-up-concavity, a novel first-order condition that characterizes a broad class of such functions. This condition provides a powerful unifying framework, strictly generalizing both DR-submodular and One-Sided Smooth (OSS) functions while capturing broader forms of scale-dependent curvature, including accumulating-then-diminishing returns and flat-start behavior. Our central theoretical contribution demonstrates that $\gamma$-weakly $\theta$-up-concave functions are upper-linearizable: for any feasible point, we can construct a linear surrogate whose gains provably approximate the original non-linear objective. A key technical contribution is a nonuniform upper-linearization argument yielding approximation coefficients that depend explicitly on the curvature parameters and the geometry of the feasible region. This linearizability yields immediate and unified approximation guarantees for a wide range of problems. Specifically, we obtain unified approximation guarantees for offline optimization as well as static and dynamic regret bounds in online settings via standard reductions to linear optimization. Moreover, our framework recovers the optimal approximation coefficient for DR-submodular maximization and improves existing approximation coefficients for OSS optimization, particularly over matroid constraints.