论文检索

Theory · Optimization

Alex Saad-Falcon, Brighton Ancelin, Justin Romberg

We analyze a compressed variant of Oja's algorithm for estimating the principal eigenvector of the data covariance matrix using only two adaptive measurements per sample. At each iteration, we observe one measurement along the current estimate and one in a random orthogonal direction. We prove that after $t$ iterations, the expected sine-squared error to the true eigenvector is $\mathcal{O}(\lambda_1\lambda_2 d^2 / (\Delta^2 t))$, where $d$ is the ambient dimension, $\lambda_1, \lambda_2$ are the leading eigenvalues, and $\Delta = \lambda_1 - \lambda_2$ is the eigengap. We complement this with a matching information-theoretic lower bound of $\Omega(\lambda_1\lambda_2 d^2 / (\Delta^2 t))$ --- the first for compressed eigenvector estimation --- proving that the $d^2$ factor, an additional factor of $d$ compared to full-observation PCA, is the fundamental cost of compression and cannot be improved. Our analysis handles the noisy setting where the covariance has nonzero trailing eigenvalues, providing the first convergence guarantee for adaptive compressed subspace tracking beyond the noiseless case.

Deep Learning · Large Language Models

Xiaodong Lu, Xiaohan Wang, Jiajun Chai, Guojun Yin, Wei Lin, Zhijun Chen, Yu Luo, Fuzhen Zhuang, Yikun Ban, deqing wang

Reinforcement Learning with Verifiable Rewards (RLVR) is an effective paradigm for improving the reasoning capabilities of large language models. However, existing RLVR methods utilize rollouts in an indiscriminate and short-horizon manner: responses of heterogeneous quality within each prompt are treated uniformly, and historical rollouts are discarded after a single use. This leads to noisy supervision, poor sample efficiency, and suboptimal policy updates. We address these issues by formulating rollout scheduling in RLVR as a contextual bandit problem and proposing a unified neural scheduling framework that adaptively selects high-value rollouts throughout training. Each rollout is treated as an arm whose reward is defined by the induced performance gain between consecutive optimization steps. The resulting scheduler supports both noise-aware intra-group selection and adaptive global reuse of historical rollouts within a single principled framework. We provide theoretical justification by deriving sublinear regret bounds and showing that enlarging the rollout buffer improves the achievable performance upper bound. Experiments on six mathematical reasoning benchmarks demonstrate consistent gains in performance and training efficiency across multiple RLVR optimization methods.

Xuejie Liu, Vit Chun Yap, Yitao Liang, Anji Liu

Diffusion Large Language Models (dLLMs) support arbitrary-order generation, yet their inference performance critically depends on the unmasking order. Existing strategies rely on heuristics that greedily optimize local confidence, offering limited guidance for identifying unmasking paths that are globally consistent and accurate. To bridge this gap, we introduce path log-likelihood (Path LL), a trajectory-conditioned objective that strongly correlates with downstream accuracy and enables principled selection of unmasking paths. To optimize Path LL at inference time, we propose POKE, an efficient value estimator that predicts the expected future Path LL of a partial decoding trajectory. We then integrate this lookahead signal into POKE-SMC, a Sequential Monte Carlo-based search framework for dynamically identifying optimal unmasking paths. Extensive experiments across 6 reasoning tasks show that POKE-SMC consistently improves accuracy, achieving 2\%--3\% average gains over strong decoding-time scaling baselines at comparable inference overhead on LLaDA models and advancing the accuracy--compute Pareto frontier.

Yanhao Jin, Krishna Balasubramanian, Debashis Paul

Meta-learning involves training models on a variety of training tasks in a way that enables them to generalize well on new, unseen test tasks. In this work, we consider meta-learning within the framework of high-dimensional multivariate random-effects linear models and study generalized ridge-regression based predictions. The statistical intuition of using generalized ridge regression in this setting is that the covariance structure of the random regression coefficients could be leveraged to make better predictions on new tasks. Accordingly, we first characterize the precise asymptotic behavior of the predictive risk for a new test task when the data dimension grows proportionally to the number of samples per task. We next show that this predictive risk is optimal when the weight matrix in generalized ridge regression is chosen to be the inverse of the covariance matrix of random coefficients. Finally, we propose and analyze an estimator of the inverse covariance matrix of random regression coefficients based on data from the training tasks. As opposed to intractable MLE-type estimators, the proposed estimators could be computed efficiently as they could be obtained by solving (global) geodesically-convex optimization problems. Our analysis and methodology use tools from random matrix theory and Riemannian optimization. Simulation results demonstrate the improved generalization performance of the proposed method on new unseen test tasks within the considered framework.

General Machine Learning · Representation Learning

Ali Kayyam

Whether deep vision models recognize objects primarily by shape or texture remains a central and unresolved question in computer vision. Early studies report a strong texture bias in convolutional neural networks (CNNs), while other work reports shape-biased representations. We argue that much of this apparent discrepancy reflects methodological confounds and a conflation of local contour sensitivity with genuine global shape understanding. Using minimal, tightly controlled stimuli, we directly compare cue-conflict and cue-suppression paradigms within a unified experimental framework. We show that standard CNNs consistently prioritize texture over global shape when cues compete, even when shape information is explicitly available. Evidence for shape bias typically reflects reliance on local fragments rather than invariant, relational representations of object structure. Our findings support the view that texture bias is fundamentally rooted in architectural inductive biases rather than data or optimization alone. This gap has direct consequences for robustness, safety, and generalization, and motivates the development of architectures that explicitly support global integration and relational reasoning, moving beyond incremental data-driven fixes.

Deep Learning · Large Language Models

Yuanjian Xu, Jianing Hao, Wanbo Zhang, Zhong Li, Guang Zhang

The annealing stage of Large Language Model (LLM) training is a critical phase where model loss drops sharply and downstream capabilities solidify. Despite its importance, current practices rely on empirical heuristics like quality filtering or context extension, lacking a principled understanding of the underlying optimization dynamics. We address this gap by providing a theoretical characterization of the spectral properties targeted during annealing. We demonstrate that effective annealing requires balancing global Hessian geometry with sample-wise gradient noise, navigating a landscape of highly anisotropic curvature. Based on these insights, we formulate sample selection as a constrained optimization problem to suppress noise in sharp directions while preserving descent signals in flat subspaces. Our method, solved via Successive Convex Programming (SCP), achieves state-of-the-art results across multiple model scales. Code is available at \url{https://anonymous.4open.science/r/LLM-Annealing-Phase}.

Reinforcement Learning · Everything Else

Yizhi Li, Qingshui Gu, Zhoufutu Wen, Ziniu Li, Ruibin Yuan, Tianshun Xing, Shuyue Guo, Tuney Zheng, 周欣, Xingwei Qu 等

Recent advancements in aligning large language models via reinforcement learning have achieved remarkable gains in solving complex reasoning problems, but at the cost of expensive on-policy rollouts and limited exploration of diverse reasoning paths. In this work, we introduce TreePO, involving a self-guided rollout algorithm that views sequence generation as a tree-structured searching process. Composed of dynamic tree sampling policy and fixed-length segment decoding, TreePO leverages local uncertainty to warrant additional branches. By amortizing computation across common prefixes and pruning low-value paths early, TreePO essentially reduces the per-update compute burden while preserving or enhancing exploration diversity. Key contributions include: (1) a segment-wise sampling algorithm that alleviates the KV cache burden through contiguous segments and spawns new branches along with an early-stop mechanism; (2) a tree-based segment-level advantage estimation that considers both global and local proximal policy optimization. and (3) analysis on the effectiveness of probability and quality-driven dynamic divergence and fallback strategy. We empirically validate the performance gain of \modelname on a set reasoning benchmarks and the efficiency saving of GPU hours from 22% up to 43% of the sampling design for the trained models, meanwhile showing up to 40% reduction at trajectory-level and 35% at token-level sampling compute for the existing models. While offering a free lunch of inference efficiency, TreePO reveals a practical path toward scaling RL-based post-training with fewer samples and less compute.

Deep Learning · Large Language Models

Yingru Li, Jiawei Xu, Ziniu Li, Jiacai Liu, Wei Liu, Yuxuan Tong, Longtao Zheng, Zhenghai Xue, Yaxiang Zhang, Tianle Cai 等

Reinforcement Learning for Large Language Models (LLMs) often suffers from training collapse in long-horizon tasks due to exploding gradient variance. To mitigate this, baseline is commonly introduced for advantage computation; however, traditional value models remain difficult to optimize, and standard group-based baselines overlook sequence heterogeneity. Although classic optimal baseline theory can achieve global variance reduction, it neglects token heterogeneity and requires prohibitive gradient-based computation. In this work, we derive the Optimal Token Baseline (OTB) from first principles, proving that gradient updates should be weighted inversely to their cumulative gradient norm. To ensure efficiency, we propose the Logit-Gradient Proxy that approximates the gradient norm using only forward-pass probabilities. Our method achieves training stability and matches the performance of large group sizes ($N=32$) with only $N=4$, reducing token consumption by over 65\% across single-turn and tool-integrated reasoning tasks.

Reinforcement Learning · Deep RL

Shaojun Xu, Xiaoling Zhou, Yihan Lin, Yapeng Meng, Xinglong Ji, Luping Shi, Rong Zhao

Model-Based Reinforcement Learning (MBRL) leverages latent imagination for sample efficiency, yet remains constrained by **Historical Tethering**: imagination is typically initialized from observed states. This creates a learning asymmetry, where the world model’s manifold discovery outpaces the policy's sparse-reward optimization. We propose **Mind Dreamer (MD)**, a framework that operationalizes **Active Counterfactual Reasoning (ACR)** to transcend Markovian continuity. MD reformulates discovery as the minimization of a global Relay Manifold Expected Free Energy (R-EFE); by invoking a latent-space $do$-operator, MD utilizes an adversarial generator to synthesize non-continuous **latent jumps** to epistemic blind spots that are physically plausible yet cognitively challenging. To resolve the credit assignment paradox across these spatial ruptures, we derive the **Relay Value Function (RVF)** and **Relay Uncertainty Function (RUF)**. These potentials treat synthesized anchors as latent bridges, propagating pragmatic and epistemic value through a principled Bellman-style formulation. Notably, we prove that the Uncertainty propagation across discontinuities necessitates a quadratic discount $\gamma^2$, establishing a formal epistemic horizon. Theoretically, MD acts as an optimal importance sampler that expands the manifold's spectral gap, reducing the hitting time to critical bottleneck states. Empirically, MD achieves a **1.67$\times$ average speedup** over DreamerV3 on DeepMind Control Suite, reaching **8.8$\times$** in sparse-reward tasks.

Deep Learning · Large Language Models

Ziyao Tang, Pengkun Jiao, Xinhang Chen, LiuWei Liu, Shiyong Li, Jingjing Chen

Given the quadratic complexity of attention, KV cache eviction is vital to accelerate model inference. Current KV cache eviction methods typically rely on instantaneous heuristic metrics, implicitly assuming that score magnitudes are consistent proxies for importance across all heads. However, this overlooks the heterogeneity in predictive fidelity across attention heads. While certain heads prioritize the \textit{instantaneous contribution} of tokens, others are dedicated to capturinglong-horizon utility. In this paper, we propose that optimal budget allocation should be governed by the marginal utility in preserving long-term semantic information. Based on this insight, we propose LU-KV, a novel framework that optimizes head-level budget allocation through a convex-hull relaxation and a marginal-utility-based greedy solver to achieve near-optimal precision. Furthermore, we implement a data-driven offline profiling protocol to facilitate the practical deployment of LU-KV.

Optimization · Large Scale, Parallel and Distributed

Xiuwen Fang, Xuliang Yang, Mang Ye

Federated Learning (FL) enables collaborative training across distributed clients while preserving data privacy. However, fine-tuning large-scale pre-trained models in FL is hindered by resource constraints and communication costs. Although introducing parameter-efficient fine-tuning strategies such as Low-Rank Adaptation (LoRA) effectively reduces trainable parameters, this low-rank constraint exacerbates noise sensitivity, leading to overfitting and aggregation bias. Existing robust federated fine-tuning methods rely on additional proxy data and treat low-rank adapters as generic weight vectors. In this paper, we investigate the structural properties of LoRA and reveal a robustness asymmetry. The down-projection matrix $A$ extracts stable general features, whereas the up-projection matrix $B$ is highly susceptible to fitting noise patterns. Based on this finding, we propose Federated Decoupled LoRA (FDLoRA), which employs a dual-branch mechanism to decouple robust feature learning from noise modeling and mitigates noise interference through noisy branch negative learning. During federated aggregation, we establish global consensus through aggregating $B$ while preserving local feature alignment in $A$. Extensive experiments demonstrate that FDLoRA outperforms existing state-of-the-art methods across various noisy federated scenarios. Our code and models will be released.

General Machine Learning · Kernel methods

Zonghao Chen, Aratrika Mustafi, Pierre Glaser, Anna Korba, Arthur Gretton, Bharath K. Sriperumbudur

We introduce a (de)-regularization of the Maximum Mean Discrepancy (DrMMD) and its Wasserstein gradient flow. Existing gradient flows that transport samples from source distribution to target distribution with only target samples, either lack tractable numerical implementation ($f$-divergence flows) or require strong assumptions and modifications, such as noise injection, to ensure convergence (Maximum Mean Discrepancy flows). In contrast, DrMMD flow can simultaneously (i) guarantee near-global convergence for a broad class of targets in both continuous and discrete time, and (ii) be implemented in closed form using only samples. The former is achieved by leveraging the connection between the DrMMD and the $\chi^2$-divergence, while the latter comes by treating DrMMD as MMD with a de-regularized kernel. Our numerical scheme employs an adaptive de-regularization schedule throughout the flow to optimally balance the trade-off between discretization errors and deviations from the $\chi^2$ regime. The potential application of the DrMMD flow is demonstrated across several numerical experiments, including a large-scale setting of training student/teacher networks.

Theory · Game Theory

Anna Lunghi, Mattia Piccinato, Matteo Castiglioni, Alberto Marchesi

We study online bilateral trade, where a learner facilitates repeated exchanges between a buyer and a seller to maximize the Gain From Trade (GFT), i.e., the social welfare. In doing so, the learner must guarantee not to subsidize the market. This constraint is usually imposed per round through Weak Budget Balance (WBB). Despite that, (Bernasconi et al.,2024) shows that a Global Budget Balance (GBB) constraint on the profit--enforced over the entire time horizon--can improve the GFT by a multiplicative factor of two. While this might appear to be a marginal relaxation, this implies that all existing WBB-focused algorithms suffer linear regret when measured against the GBB optimum. In this work, we provide the first algorithm to achieve sublinear regret against the GBB benchmark in stochastic environments under one-bit feedback. In particular, we show that when the joint distribution of valuations has a bounded density, our algorithm achieves $\widetilde{\mathcal{O}}(T^{3/4})$ regret. Our result shows that there is no separation between the one-dimensional problem of learning the optimal WBB price and the two-dimensional problem of learning the optimal GBB distribution over *couples* of prices.

Applications · Health / Medicine

Marcin Możejko, Adam Bielecki, Jurand Prądzyński, Marcin Traskowski, Antoni Janowski, Hyun-Su Lee, Marcelo Torres, Michal Kmicikiewicz, Paulina Szymczak, Karol Jurasz 等

Antimicrobial peptide discovery is challenged by the astronomical size of peptide space and the relative scarcity of active peptides. While generative models provide latent maps of this space, they typically ignore decoder-induced geometry and rely on flat Euclidean metrics, making exploration distorted and inefficient. Existing manifold-based approaches assume fixed intrinsic dimensionality, which fails for real peptide data. We introduce **PepCompass**, a geometry-aware framework based on a **Union of $\kappa$-Stable Riemannian Manifolds** that captures local decoder geometry while maintaining computational stability. PepCompass performs global interpolation via **Potential-minimizing Geodesic Search (PoGS)** to bias discovery toward promising seeds and enables local exploration through **Second-Order Riemannian Brownian Efficient Sampling** and **Mutation Enumeration in Tangent Space**, which together form **Local Enumeration Bayesian Optimization (LE-BO)**. PepCompass achieves a 100% *in-vitro* validation rate: PoGS identifies four novel seeds and LE-BO optimizes them into 25 highly active, broad-spectrum peptides, demonstrating that geometry-informed exploration is a powerful paradigm for antimicrobial peptide design.

Brian Cho, Raaz Dwivedi, Nathan Kallus

Inference on the conditional mean function (CMF) is central to tasks from adaptive experimentation to optimal treatment assignment and algorithmic fairness auditing. In this work, we provide a novel asymptotic anytime-valid test for a CMF global null (e.g., that all conditional means are zero) and contrasts between CMFs, enabling experimenters to make high confidence decisions at \textit{any} time during the experiment beyond a minimum sample size. We provide mild conditions under which our tests achieve (i) asymptotic type-I error guarantees, (i) power one, and, unlike past tests, (iii) optimal sample complexity relative to a Gaussian location testing. By inverting our tests, we show how to construct function-valued asymptotic confidence sequences for the CMF and contrasts thereof. Experiments on both synthetic and real-world data show our method is well-powered across various distributions while preserving the nominal error rate under continuous monitoring.

Deep Learning · Large Language Models

Zhihao Dou, Qinjian Zhao, Zhongwei Wan, Zhang Dinggen, Weida Wang, Benteng Chen, Towsif Raiyan, Qingtao Pan, Yang Ouyang, Chaoda Song 等

Large language models (LLMs) demonstrate strong reasoning abilities via Chain-of-Thought (CoT), but their token-level generation encourages local decisions and lacks global planning, often leading to redundant or inaccurate reasoning. Existing methods, such as tree-based search and reinforcement learning (RL), attempt to address this issue but incur high computational costs and still struggle to produce reliable reasoning trajectories. To address these challenges, we propose Plan-Then-Action Enhanced Reasoning with Group Relative Policy Optimization (PTA-GRPO), a two-stage framework designed to jointly improve high-level planning and fine-grained CoT reasoning. Specifically, in the first stage, a given LLM is responsible for summarizing CoT reasoning into compact high-level guidance, which is then leveraged for supervised fine-tuning. Then, we introduce a guidance-aware reinforcement learning method that jointly optimizes the final output and the quality of guidance, enhancing reasoning effectiveness. We evaluate PTA-GRPO on ten reasoning benchmarks across mathematics and natural sciences, using five diverse base models spanning multiple data modalities. The results show that PTA-GRPO consistently delivers stable and significant improvements across models and tasks, demonstrating strong effectiveness and generalization.

Optimization · Large Scale, Parallel and Distributed

Zhenshen Liu, Kai Fan, Wenjie Li, Kuan Zhang, HUI LI, Yintang Yang

Federated learning enables decentralized clients to collaboratively train models without sharing local data. However, heterogeneous client distributions often induce client drift and hinder convergence. This paper proposes FedCDWA, a decoupled hierarchical federated distillation framework. FedCDWA decouples client-side personalized distillation from server-side mutual distillation to mitigate distillation-induced optimization conflicts. It further adopts Hierarchical Wasserstein Aggregation to aggregate prototypes without restrictive parametric assumptions while preserving intra-class structure and inter-class geometry. To achieve finer-grained feature alignment, Prototype–Variance Dual Alignment matches feature means and variances in the feature space. We prove convergence guarantees for FedCDWA. Experiments on three datasets demonstrate that FedCDWA consistently improves both global and personalized accuracy across heterogeneity levels, with smaller performance degradation under more severe heterogeneity.

Deep Learning · Large Language Models

Ruiyuan Xu, shuoming zhang, Guangli Li, Qiuchu Yu, Rui Zhang, Yangyu Zhang, Hao Qian, Chunwei Xia, Jiacheng Zhao, Chenxi Wang 等

Automating end-to-end GPU kernel generation with Large Language Models (LLMs) faces a critical tension between global performance and exploration efficiency. We present LEGO, a hierarchical framework that resolves this trade-off via a parallel multi-agent search over a recursive AND-OR FusionTree. LEGO synergizes two complementary flows: Top-Down Construction decomposes complex graphs into valid, context-isolated sub-problems to guarantee correctness and enable parallel exploration, while Bottom-Up Mutation speculatively fuses verified sub-plans to recover global locality for peak performance. This bi-directional mechanism effectively prunes the search space to avoid repetitive unguided sampling, while naturally parallelizing exploration, and enabling the discovery of sophisticated fusion strategies. Evaluations demonstrate that LEGO achieves 2.18x–13.48x speedups over PyTorch Eager and reduces end-to-end exploration time by up to 2.47x (with 7x token reduction) compared to monolithic baselines across diverse end-to-end models.

Deep Learning · Algorithms

Xing Hu, Dawei Yang, Yuan Cheng, Zhixuan Chen, Zukang Xu

The rapid growth in the parameter scale of large language models (LLMs) has created a high demand for efficient compression techniques. As a hardware-agnostic and highly compatible technique, low-rank compression has been widely adopted. However, existing methods typically compress each layer independently by minimizing per-layer reconstruction error, overlooking a critical limitation: the reconstruction error propagates and accumulates through the network, which leads to amplified global deviations from the full-precision baseline. To address this, we propose **Self-Adaptive Error Suppression SVD (SAES-SVD)**, a LLMs compression framework that jointly optimizes intra-layer reconstruction and inter-layer error compensation. SAES-SVD is composed of two novel components: **Cumulative Error-Aware Layer Compression (CEALC),** which formulates the compression objective as a combination of local reconstruction and weighted cumulative error compensation. Based on it, we derive a closed-form low-rank solution relied on second-order activation statistics, which explicitly aligns each layer's output with its full-precision counterpart to compensate for accumulated errors. \ding{183} Adaptive Collaborative Error Suppression (ACES), which automatically adjusts the weighting coefficient to enhance the low-rank structure of the compression objective in CELAC. Specifically, the coefficient is optimized to maximize the ratio between the Frobenius norm of the compressed layer's output and that of the compression objective under a fixed rank, thus ensuring that the rank budget is utilized effectively. Extensive experiments across multiple LLM architectures and tasks show that, without fine-tuning or additional tricks, SAES-SVD consistently improves post-compression performance. For example, at a 0.2 compression ratio on LLaMA-7B, existing methods exhibit an average accuracy drop exceeding 0.05, whereas SAES-SVD restricts the drop to only 0.02. These improvements underscore the potential of SAES-SVD to effectively narrow the gap between compressed models and their full-precision counterparts, paving the way for more reliable compression of LLMs.

Reinforcement Learning · Deep RL

Fang Wu, Weihao Xuan, Heli Qi, Aaron Tu, Ximing Lu, Li Li, Yejin Choi

Although Reinforcement Learning with Verifiable Rewards (RLVR) has become an essential component for developing advanced reasoning skills in language models, contemporary studies have documented training plateaus after thousands of optimization steps, i.e., notable decreases in performance gains despite increased computational investment. This limitation stems from the sparse exploration patterns inherent in current RLVR practices, where models rely on limited rollouts that often miss critical reasoning paths and fail to provide systematic coverage of the solution space. We present DeepSearch, a framework that integrates Monte Carlo Tree Search (MCTS) directly into RLVR training. In contrast to existing methods that rely on tree search only at inference, DeepSearch embeds structured search into the training loop, enabling systematic exploration and fine-grained credit assignment across reasoning steps. Through training-time exploration, DeepSearch addresses the fundamental bottleneck of insufficient exploration, which leads to diminishing performance gains over prolonged training. Our contributions include: (1) a global frontier selection strategy that prioritizes promising nodes across the search tree, (2) selection with entropy-based guidance that identifies confident paths for supervision, and (3) adaptive replay buffer training with solution caching for efficiency. Experiments on mathematical reasoning benchmarks show that DeepSearch achieves an average accuracy of 62.95% and establishes a new state-of-the-art reasoning model, while using 5.7x fewer GPU hours than extended training approaches. These results highlight the importance of strategic exploration over brute-force scaling and demonstrate the promise of algorithmic innovation for advancing RLVR methodologies. DeepSearch establishes a new direction for scaling reasoning capabilities through systematic search rather than prolonged computation.