论文检索

Optimization · Non-Convex

Kaiyi Ji

Although upper bound guarantees for bilevel optimization have been widely studied, progress on lower bounds has been limited due to the complexity of the bilevel structure. In this work, we focus on the smooth nonconvex-strongly-convex setting and develop new hard instances that yield nontrivial lower bounds under deterministic and stochastic first-order oracle models. In the deterministic case, we prove that any first-order zero-respecting algorithm requires at least $\Omega(\kappa^{3/2}\epsilon^{-2})$ oracle calls to find an $\epsilon$-accurate stationary point, improving the optimal lower bounds known for single-level nonconvex optimization and for nonconvex-strongly-convex min-max problems. In the stochastic case, we show that at least $\Omega(\kappa^{5/2}\epsilon^{-4})$ stochastic oracle calls are necessary, again strengthening the best known bounds in related settings. Our results expose substantial gaps between current upper and lower bounds for bilevel optimization and suggest that even simplified regimes, such as those with quadratic lower-level objectives, warrant further investigation toward understanding the optimal complexity of bilevel optimization under standard first-order oracles.

Deep Learning · Other Representation Learning

Jianqiao Zeng, Ruocheng Wang, Yanzhi Liu, Hao Xiong, Junchi Yan

Despite the fast progress in neural operator learning, long-sequence modeling still is a standing challenge whereby latent states have been introduced with techniques well derived. Diverging from existing methods that treat latent states as transient variables or decoupled representations, CoEvol-NO introduces a {persistent state} to establish a {co-evolutionary framework}, where the latent state and mesh sequence are updated jointly and bidirectionally. Inspired by classical numerical methods, we model the layer-wise state evolution as a {Predictor-Corrector (PC)} process. Specifically, a ``Predictor'' generates a tentative target, followed by a ``Corrector'' that refines the persistent state via an {error-driven update mechanism}. Furthermore, our theoretical analysis reveals that the widely used \textit{direct substitution} and \textit{residual update} paradigms are essentially {first-order approximations} of this error-driven correction under different loss assumptions. We theoretically prove that CoEvol-NO achieves strict {linear time complexity}. Extensive experiments on five standard benchmarks and two large-scale industrial design tasks demonstrate that CoEvol-NO consistently achieves {state-of-the-art (SOTA)} performance.

Deep Learning · Large Language Models

Ali Abbasi, Chayne Thrash, Haoran Qin, Shansita Sharma, Sepehr Seifi, Soheil Kolouri

Advances in large language models have driven strong performance across many tasks, but their memory and compute costs still hinder deployment. SVD-based compression reduces storage and can speed up inference via low-rank factors, yet performance depends on how rank is allocated under a global compression ratio. Prior methods often use homogeneous ranks for similarly sized matrices, despite large differences in loss sensitivity, or rely on expensive iterative pre-truncation optimization to determine per matrix ranks. We propose **Zero Sum SVD** (**ZS-SVD**), a post-training method that performs *global* singular component selection using activation whitening and first-order calibration loss estimates in whitened coordinates. **ZS-SVD** prunes components across the whole model with a **zero sum** rule that keeps the cumulative predicted loss change near zero, automatically yielding heterogeneous ranks without solving a rank allocation optimization. Motivated by evidence that gradients near pretrained solutions exhibit low rank structure, we also introduce an optional lightweight correction that applies a **single** projected gradient update after truncation, followed by re-truncation. Extensive experiments across multiple LLM architectures show consistent gains across diverse benchmarks and compression ratios.

General Machine Learning · Everything Else

CHEN WANG, Yongli Hu, Huajie Jiang, Kan Guo, Tengfei Liu, Junbin Gao, Yanfeng Sun, Baocai Yin

We reconceptualize Personalized Multimodal Federated Learning (PMFL) by treating missing modalities as intrinsic structural identities that constrain each client to a distinct Riemannian submanifold, rather than deficiencies to be compensated. To resolve the tension between identity preservation and cross-client collaboration, we cast PMFL as an identity-aware potential game and seek a geometry-consistent equilibrium instead of a single full-modality global optimum. We propose GeoEvo, which realizes this equilibrium via Fisher--Riemannian evolutionary dynamics: Natural Evolution Strategies for curvature-adaptive local exploration and subspace-constrained particle swarm updates for symbiotic knowledge transfer. GeoEvo admits a Lyapunov potential and, with a monotone acceptance rule, guarantees potential dissipation; in non-convex regimes it achieves an $O(1/\sqrt{T})$ stationarity rate, implying convergence to first-order Nash equilibria, and empirically improves personalization and robustness across diverse modality-missing identities.

Optimization · Non-Convex

Jian-Feng Cai, Xueyang Quan, Yang Wang, Jiaxi Ying

Spectrally sparse signal reconstruction arises in a wide range of applications and can be formulated as a low-rank Hankel matrix completion problem. We develop a Jacobi-preconditioned gradient descent method that preserves the low per-iteration complexity of first-order algorithms while achieving linear convergence at a rate independent of the condition number. By introducing a generator that maps factor-based iterates to matrix space, we establish equivalence with manifold-based methods, enabling direct convergence analysis while avoiding the need to define distances under complex-symmetric factorization ambiguity. Extensive experiments demonstrate that the proposed algorithm outperforms state-of-the-art methods in both iteration count and computational time across a broad range of problem settings.

Thai Khanh Nguyen, Ngoc Bich Uyen Vo, Thieu Vo, Tan Nguyen, Cuong Pham

State-space models (SSMs) have emerged as efficient linear-time alternatives to attention for long-sequence modeling. However, existing SSMs often suffer from instability and memory degradation over extended horizons due to poorly conditioned first-order updates and uncontrolled spectral geometry. We introduce MuonSSM, a general framework that stabilizes SSM training by explicitly conditioning the geometry of memory updates rather than the recurrent transition matrix. MuonSSM augments standard SSMs with a momentum-based pathway and lightweight Newton–Schulz iterations on low-rank input injections, yielding approximately norm-preserving and spectrally balanced updates while preserving parallel scan complexity. Theoretical analysis demonstrates substantial improvements in gradient propagation and mitigation of vanishing gradients over long horizons. Extensive experiments across language, vision, and time-series benchmarks show consistent gains in accuracy, robustness, and long-context performance when integrated into diverse SSM backbones. These results establish geometric conditioning of updates as a principled pathway to stable, scalable sequence modeling.

Fahim Tajwar, Guanning Zeng, Yueer Zhou, Yuda Song, Daman Arora, Yiding Jiang, Jeff Schneider, Russ Salakhutdinov, Haiwen Feng, Andrea Zanette

Maximum likelihood is fundamental to supervised learning but it cannot be directly applied in correctness-based problems with non-differentiable sampling. In these settings, reinforcement learning (RL) is typically used to maximize expected reward. We show that for binary correctness tasks, expected-reward RL is a first-order approximation of the maximum likelihood objective, yielding vanishing learning signal on low-success inputs. We introduce **Maximum Likelihood Reinforcement Learning (MaxRL)**, a compute-indexed family of sampling-based objectives derived from a pass@k expansion of the likelihood, which interpolates between standard RL and exact maximum likelihood as compute increases. MaxRL admits a simple unbiased policy-gradient estimator whose optimized objective improves with additional compute. Across multiple domains, MaxRL consistently outperforms standard RL and GRPO, achieving higher $pass@1$ and substantially improved $pass@k$.

Deep Learning · Other Representation Learning

Haoyu Huang, Boyu Liu, Linlin Yang, Yanjing Li, Yuguang Yang, Xuhui Liu, Canyu Chen, Zhongqian Fu, Baochang Zhang

The training of Binary Neural Networks (BNNs) is fundamentally based on gradient approximation for non-differentiable binarization operations (e.g., sign function). However, prevailing methods including the Straight-Through Estimator (STE) and its improved variants, rely on hand-crafted designs that suffer from gradient mismatch problem and information loss induced by fixed-range gradient clipping. To address this, we propose SURrogate GradiEnt Adaptation (SURGE), a novel learnable gradient compensation framework with theoretical grounding. SURGE mitigates gradient mismatch through auxiliary backpropagation. Specifically, we design a Dual-Path Gradient Compensator (DPGC) that constructs a parallel full-precision auxiliary branch for each binarized layer, decoupling gradient flow via output decomposition during backpropagation. DPGC enables bias-reduced gradient estimation by leveraging the full-precision branch to estimate components beyond STE's first-order approximation. To further enhance training stability, we introduce an Adaptive Gradient Scaler (AGS) based on an optimal scale factor to dynamically balance inter-branch gradient contributions via norm-based scaling. Experiments on image classification, object detection, and language understanding tasks demonstrate that SURGE performs best over state-of-the-art methods.

Tuan Dam

Planning with a generative model aims to estimate state values using minimal oracle calls. For entropy-regularized MDPs, SmoothCruiser exploits the smoothness of the $\operatorname{LogSumExp}$ Bellman operator to achieve $\widetilde{\mathcal{O}}(\varepsilon^{-4})$ sample complexity, but its first-order Taylor approximation limits the rate. We develop a curvature--complexity theory showing that if a Bellman aggregator has Taylor remainder of order $\beta \ge 2$, the optimal oracle complexity exponent is $2 + 2/(\beta-1)$---recovering $\widetilde{\mathcal{O}}(\varepsilon^{-4})$ for $\beta=2$ and predicting $\widetilde{\mathcal{O}}(\varepsilon^{-3})$ for $\beta=3$. To achieve $\beta=3$, we introduce an entropic optimal-transport regularizer over action distributions. The resulting OT-smoothed Bellman operator admits a closed-form expression, explicit gradient policy, and Lipschitz Hessian. We derive an unbiased estimator of the quadratic Taylor term via cross-product debiasing, enabling a second-order SmoothCruiser with $\widetilde{\mathcal{O}}(\varepsilon^{-3})$ complexity. We further propose gap-dependent variants and provide a complexity analysis and show advantage of our method.

Optimization · Zero-order and Black-box Optimization

Yonghan Yang, Ye Yuan, Zipeng Sun, Linfeng Du, Bowei He, Haolun Wu, Can Chen, Xue Liu

Offline black-box optimization aims to discover novel designs with high property scores using only a static dataset, a task fundamentally challenged by the out-of-distribution (OOD) extrapolation problem. Existing approaches typically bifurcate into inverse methods, which struggle with the ill-posed nature of mapping scores to designs, and forward methods, which often lack the distributional expressivity to quantify uncertainty effectively. In this work, we propose \textbf{SPADE} (\textbf{S}upport-\textbf{P}roximity \textbf{A}ugmented \textbf{D}iffusion \textbf{E}stimation), a novel framework that reimagines forward surrogate modeling through the lens of conditional generative modeling. SPADE models the forward likelihood $p(y|\boldsymbol{x})$ using a diffusion model, but with two critical enhancements to tailor it for optimization: (1) a \emph{Calibrated Diffusion Estimation} module that enforces global consistency in statistical moments and pairwise rankings, and (2) a \emph{Support-Proximity Regularization} mechanism that implicitly internalizes the data manifold constraint $p(\boldsymbol{x})$ via kNN-based density estimation. Theoretically, we prove that our regularization is first-order equivalent to maximizing a Bayesian posterior with a valid design prior. Empirically, SPADE achieves state-of-the-art performance across Design-Bench tasks and an LLM data mixture optimization benchmark. Our code is available through the anonymous repo \href{https://anonymous.4open.science/r/diffsurr-icml2026-C4FD/}{here}.

Reinforcement Learning · Everything Else

Bosun Liang, Shuo Pei, Zirui Chen, Chuanzhi Fan, Chen Sun, Yuankai Wu, Huachun Tan, Yong Wang

Reinforcement learning often produces high-frequency oscillatory control signals that undermine the safety and stability required for physical deployment. Explicit action chunking addresses this by predicting fixed-horizon trajectories but increases the policy output dimension to R^hd, leading to optimization difficulties and incompatibility with standard step-wise interaction. To overcome these challenges, this paper proposes Dual-Window Smoothing (DWS), an implicit action chunking framework for smooth continuous control. Unlike explicit methods, DWS enforces temporal coherence without expanding the action space. It uses a dual-window design: an execution window that ensures physical smoothness through deterministic modulation, and a value window that aligns temporal-difference targets over the horizon to correct critic bias caused by open-loop execution. DWS also includes a lightweight actor-side temporal regularizer based on first-order action differences to promote global continuity. This design effectively bridges the gap between temporal abstraction and reactive step-wise control. Experiments on benchmarks including the DeepMind Control Suite and industrial energy management tasks with vector states show that DWS outperforms state-of-the-art (SOTA) baselines such as LipsNet++ and SmODE. In complex vision-based autonomous driving tasks, DWS achieves smoother control, safer behavior with reduced jitter, and attains a 100% success rate.

Deep Learning · Everything Else

Su Hyeong Lee, Risi Kondor, Richard Ngo

We develop a theory of intelligent agency grounded in probabilistic modeling for neural models. Agents are represented as outcome distributions with epistemic utility given by log score, and compositions are defined through weighted logarithmic pooling that strictly improves every member's welfare. We prove that strict unanimity is impossible under linear pooling or in binary outcome spaces, but possible with three or more outcomes. Our framework admits recursive structure via cloning invariance, continuity, and openness, while tilt-based analysis rules out trivial duplication. Finally, we formalize an agentic alignment phenomenon in LLMs using our theory: eliciting a benevolent persona ("Luigi'') induces an antagonistic counterpart ("Waluigi''), while a manifest-then-suppress Waluigi strategy yields strictly larger first-order misalignment reduction than pure Luigi reinforcement alone. These results clarify how developing a principled mathematical framework for how subagents can coalesce into coherent higher-level entities provides novel implications for alignment in agentic AI systems.

Deep Learning · Theory

Hoyeon Chang, Bálint Mucsányi, Seong Joon Oh

Neural networks adapt through first-order parameter updates, yet it remains unclear whether such updates preserve logical coherence. We investigate the geometric limits of the Linear Propagation Assumption (LPA), the premise that local updates coherently propagate to logical consequences. To formalize this, we adopt relation algebra and study three core operations on relations: negation flips truth values, converse swaps argument order, and composition chains relations. For negation and converse, we prove that guaranteeing direction-agnostic first-order propagation necessitates a tensor factorization separating entity-pair context from relation content. However, for composition, we identify a fundamental obstruction. We show that composition reduces to conjunction, and prove that any conjunction well-defined on linear features must be bilinear. Since bilinearity is incompatible with negation, this forces the feature map to collapse. These results suggest that failures in knowledge editing, the reversal curse, and multi-hop reasoning may stem from common structural limitations inherent to the LPA.

Optimization · Large Scale, Parallel and Distributed

Qiyuan Chen, Xian Wu, Yi Wang, Xianhao Chen

Fine-tuning large models on edge devices is severely hindered by the memory-intensive backpropagation (BP) in standard frameworks like federated learning and split learning. While substituting BP with zeroth-order optimization can significantly reduce memory footprints, it typically suffers from prohibitively degraded convergence speed. To resolve this dilemma, we propose *Hybrid-Order Split Federated Learning* (HO-SFL). By reformulating the split learning process within a Lagrangian framework, HO-SFL decouples the optimization landscape: The server performs precise first-order updates (i.e., BP), whereas clients conduct memory-efficient zeroth-order optimization. This hybrid design not only eliminates the need for client-side BP but also enables dimension-free model aggregation, drastically lowering communication costs. Crucially, we provide a theoretical convergence analysis, demonstrating that HO-SFL mitigates the dimension-dependent convergence slowdown of zeroth-order optimization, achieving a convergence rate comparable to first-order methods. Extensive experiments on tasks across vision and language modalities validate that HO-SFL achieves convergence speeds comparable to first-order baselines while significantly reducing communication costs and client memory footprints.

Theory · Game Theory

David Yang, Yuan Gao, Tianyi Lin, Christian Kroer

We introduce, to our knowledge, the first direct second-order method for computing Nash equilibria in two-player zero-sum games. To do so, we construct a Douglas-Rachford-style splitting formulation, which we then solve with a semi-smooth Newton (SSN) method. We show that our algorithm enjoys local superlinear convergence. To augment the fast local behavior of our SSN method with global efficiency guarantees, we develop a hybrid method that combines our SSN method with the state-of-the-art first-order method for game solving, Predictive Regret Matching (PRM$^+$). Our hybrid algorithm leverages the global progress provided by PRM$^+$ while achieving a local superlinear convergence rate once it switches to SSN near a Nash equilibrium. Numerical experiments on matrix games demonstrate order-of-magnitude speedups over PRM$^+$ for high-precision solutions.

Theory · Optimization

Motahareh Sohrabi, Jianxin You, Simon Lacoste-Julien, Eduard Gorbunov, Gauthier Gidel

We study first-order methods for solving monotone variational inequalities arising in min-max optimization. Classical approaches such as the extragradient method rely on two gradient queries per iteration, which limits their analysis and applicability in the online and stochastic settings. We propose a family of Generalized Optimistic Methods with Anchoring (GOMA), which combine two time-scale optimistic updates with an anchoring term inspired by Halpern iteration. In particular, we show that for monotone Lipschitz operators, GOMA achieves an accelerated last-iterate convergence rate of $\mathcal{O}(1/k^2)$ in the squared gradient norm which is optimal. We also show that in stochastic games where classical methods, such as the extragradient and optimistic method, fail, GOMA can converge. Theoretically, we show that it has a last-iterate convergence rate of $\mathcal{O}(1/\sqrt{k})$ for monotone Lipschitz operators in stochastic regimes with linearly increasing minibatches.

Optimization · Zero-order and Black-box Optimization

Mingyue Qin, Shuyu Yin, Qinghai Guo, Xiaolin Huang, Peilin Liu, Fei Wen

The human brain is a biologically instantiated on-device neural system that integrates both learning and inference in a unified architecture, which enables rapid and flexible learning on-the-fly. This extraordinary capability is achieved through non-BP learning mechanisms, whereas BP is computationally and memory intensive that unsuitable for on-chip edge learning. Zeroth-order (ZO) optimization methods, which resemble biologically plausible perturbation-based learning, offer a promising alternative that enables learning with only forward passes and hence can significantly reduce the complexity of on-chip hardware implementation. However, in this work we show that applying ZO methods to spiking neural networks (SNNs) is non-trivial due to the step-function nature of spiking activation. We analyze the challenges posed by the spiking activation, and reveal a variance amplification effect of it. Based on this insight, we propose a subspace-based ZO (SZO) method that leverages the intrinsic low-dimensional structure of the SNN optimization trajectory. By learning in a low-dimensional subspace, SZO substantially enhances ZO learning efficacy, achieving accuracy comparable to first-order (FO) methods with faster learning speed than full-space BP. We evaluate SZO on model training from scratch, continual training, and unsupervised adaptation. Experimental results demonstrate that SZO closely approaches FO training performance for the first time while offering fast learning speed.

Social Aspects · Alignment

Itai Shapira, Gerdus Benade, Ariel Procaccia

Large language models often exhibit increased sycophantic behavior after preference-based post-training, showing a stronger tendency to affirm a user’s stated or implied belief even when this conflicts with factual accuracy or sound judgment. We present a formal analysis of how alignment from human feedback can increase this failure mode by identifying an explicit amplification mechanism that causally links optimization against a learned reward to bias in the human preference data used for alignment. We show that the direction of behavioral drift is determined by a covariance under the base policy between endorsing the belief signal in the prompt and the learned reward, and that the first-order effect reduces to a simple mean-gap condition. We then analyze reward learning from pairwise comparisons under random utility models like Bradley–Terry and characterize when bias in human annotators’ preferences induces this reward gap. Next, we propose a training-time intervention designed to neutralize the amplification mechanism itself. Among all post-trained policies that prevent sycophantic behavior from increasing, we characterize the unique policy closest in KL divergence to the unconstrained post-trained policy, and derive the corresponding minimal reward correction as a closed-form agreement penalty. Computational experiments find that reward gaps are common and cause behavioral drift in all the configurations considered.

Social Aspects · Privacy

Martin Van Waerebeke, Giovanni Neglia, Kevin Scaman, Marco Lorenzi, El-Mahdi El-Mhamdi

In machine unlearning, $(\varepsilon,\delta)-$unlearning is a popular framework that provides formal guarantees on the effectiveness of the removal of a subset of training data, the \emph{forget set}, from a trained model. For strongly convex objectives, existing first-order methods achieve $(\varepsilon,\delta)-$unlearning, but they only use the forget set to calibrate injected noise, never as a direct optimization signal. In contrast, efficient empirical heuristics often exploit the forget samples (e.g., via gradient ascent) but come with no formal unlearning guarantees. We bridge this gap by presenting the Variance-Reduced Unlearning (*VRU*) algorithm. To the best of our knowledge, *VRU* is the first first-order algorithm that directly includes forget set gradients in its update rule, while provably satisfying $(\varepsilon,\delta)-$unlearning. We establish the convergence of *VRU* and show that incorporating the forget set yields strictly improved rates, *i.e.*, a better dependence on the achieved error compared to existing first-order $(\varepsilon,\delta)-$unlearning methods. Moreover, we prove that, in a low-error regime *VRU* asymptotically outperforms any first-order methods that ignores the forget set. Experiments corroborate our theory, showing consistent gains over both state-of-the-art certified unlearning methods and over empirical baselines that explicitly leverage the forget set.

Deep Learning · Large Language Models

Li, Yaming Guo, Shenghao Gao, Xinlong Chen, Zuhao Xu, Ying Sun, Chao Wang, Hui Xiong

While Large language models (LLMs) have strong abilities, they generally rely on fine-tuning to supplement downstream task-specific knowledge. Due to the prohibitive memory overhead of full fine-tuning (FT), existing parameter-efficient fine-tuning techniques, e.g., LoRA and Adapters, update parameters only in low-rank or restricted subspaces. However, they fail to approximate FT---the performative fine-tuner---and risk performance degradation in tough tasks. Therefore, we naturally raise a *Low-cost Full Fine-tuning* question: Can we approach standard full fine-tuning in theory, yet with much lower costs in practice? Our key insight is that performing selective updates at each step can, theoretically, recover FT asymptotically, while being cost-effective and ignoring no parameter direction. This motivates a new general fine-tuning paradigm (called *Think-Touch*): we first predict potentials of parameter groups (*think*) and then update only the selected (*touch*) in one step. Theoretically, we show that under a very weak sufficient condition---divergence of the cumulative coverage of the expected gradient norm---any selection strategy can converge in the full-parameter space to a stationary point at which the FT admits no further first-order improvement. Besides, we further derive the general convergence rate for our paradigm and identify a post-hoc greedy strategy that is rate-optimal. Unfortunately, this strategy cannot be directly applied in practice due to its reliance on full and accurate gradient information. Thus, we propose a bandit-based method to online approximate this ideal strategy in the long run with a rigorous regret guarantee. Extensive experimental results on various tasks demonstrate the potential of our paradigm, including much lower space overheads against FT and better performance than LoRAs.