Learning to Rank

As network data has become ubiquitous in the sciences, there has been growing interest in network models whose structure is driven by latent node-level variables in a (typically low-dimensional) latent geometric space. These "latent positions" are often estimated via embeddings, whereby the nodes of a network are mapped to points in Euclidean space so that "similar" nodes are mapped to nearby points. Under certain model assumptions, these embeddings are consistent estimates of the latent positions, but most such results require the embedding dimension to be chosen correctly. Methods for choosing the embedding dimension have been studied extensively, but little is known about the behavior of embeddings when the dimension is misspecified. In this work, we provide a theoretical description of the effects of dimension misspecification under the random dot product graph, a class of latent space network models that includes several widely-used network models, most notably the stochastic blockmodel, as special cases. We show that when the dimension is chosen too large, consistent estimation still holds, albeit at a slower rate than when the embedding dimension is chosen correctly. On the other hand, when the dimension is chosen too small, there is a fundamental estimation error lower bound that need not go to zero in the large-network limit. A range of synthetic data experiments support our theoretical results. Our main technical result, which may be of independent interest, is a generalization of earlier work in random matrix theory showing that all non-signal eigenvectors of a low-rank matrix subject to additive noise are delocalized.

Reinforcement learning (RL) is a fundamental framework for sequential decision-making, in which an agent learns an optimal policy through interactions with an unknown environment. In settings with function approximation, many existing RL algorithms achieve favorable sample complexity, but often rely on computationally intractable oracles. In this paper, we use supervised learning as a computational proxy to establish a clear hierarchy of commonly adopted RL oracles under low-rank Markov Decision Processes (MDPs). This hierarchy shows that policy evaluation is the most computationally efficient oracle, provided that supervised learning can be efficiently solved. Motivated by this observation, we propose a novel optimistic actor–critic algorithm that relies solely on the policy evaluation oracle. We prove that our algorithm outperforms the existing sample complexity guarantees for low-rank MDPs while avoiding computationally expensive planning or optimization oracles commonly assumed in prior works. We further extend our theoretical results to approximately low-rank MDPs and demonstrate that this setting captures a broad class of real-world environments. Finally, we validate our theoretical results with experiments on several standard Gym benchmarks.

Low-rank adaptation (LoRA) enables parameter-efficient specialization of foundation models, but the proliferation of task-specific adapters fragments capabilities across many adapters, complicating reuse and deployment. We study the problem of **merging $T$ LoRAs into a single rank-$r$ LoRA**, thereby preserving the benefits of low-rank structure. Existing Merge-then-Compress pipelines treat the rank constraint as an afterthought: they merge adapters in the full parameter space, then compress the merged result to rank $r$ via truncated SVD. However, full-parameter merging may destroy the low-rank structure, making it difficult for subsequent compression to recover an effective rank-$r$ LoRA. We propose Compress-then-Merge (CtM), a reversed pipeline that enforces the rank-$r$ bottleneck _before_ merging: CtM computes shared $r$-dimensional subspaces using only the LoRA weights to capture cross-adapter common structure, projects each adapter into the shared subspaces to obtain $r\times r$ coordinates, and then applies standard merging rules in this reduced space. CtM guarantees a rank-$r$ LoRA by construction, avoiding post-hoc truncation, and enables efficient computation in the core space spanned by concatenated LoRA factors. Experiments across multiple models and tasks show that CtM consistently outperforms existing single-LoRA-output baselines while narrowing the performance gap to full-parameter merging methods.

The deployment of Large Language Models is constrained by the memory and bandwidth demands of static weights and dynamic Key-Value cache. SVD-based compression provides a hardware-friendly solution to reduce these costs. However, existing methods suffer from two key limitations: some are suboptimal in reconstruction error, while others are theoretically optimal but practically inefficient. In this paper, we propose Swift-SVD, an activation-aware, closed-form compression framework that simultaneously guarantees theoretical optimum, practical efficiency and numerical stability. Swift-SVD incrementally aggregates covariance of output activations given a batch of inputs and performs a single eigenvalue decomposition after aggregation, enabling training-free, fast, and optimal layer-wise low-rank approximation. We employ effective rank to analyze local layer-wise compressibility and design a dynamic rank allocation strategy that jointly accounts for local reconstruction loss and end-to-end layer importance. Extensive experiments across six LLMs and eight datasets demonstrate that Swift-SVD outperforms state-of-the-art baselines, achieving optimal compression accuracy while delivering 3–70$\times$ speedups in end-to-end compression time. Our code is available at https://github.com/hiahei/Swift-SVD.

Optimal transport (OT) finds a least-cost transport plan between two probability distributions. Unlike standard OT, which infers unstructured pointwise mappings, low-rank optimal transport explicitly constrains the rank of the transport plan to infer latent structure. This improves statistical robustness, yields sharper parametric rates for estimating Wasserstein distances, and generalizes $K$-means to co-clustering. However, these advantages come at the cost of a non-convex and NP-hard optimization problem. We introduce Transport Clustering, an algorithm to compute a low-rank OT plan that reduces low-rank OT to a clustering problem on correspondences obtained from a full-rank transport registration step. We prove that this reduction yields polynomial-time, constant-factor approximation algorithms for low-rank OT: specifically, a $(1+\gamma)$ approximation for negative-type metrics, a $(1+\gamma+\sqrt{2\gamma}\,)$ approximation for kernel costs, and a $(1+\gamma+\rho)$ approximation for general metrics satisfying the triangle inequality. Here, $\gamma \in [0,1]$ is the cost ratio of the optimal full-rank to low-rank solutions, and $\rho\in[0,1]$ is an asymmetry coefficient on the cluster variances. Numerically, Transport Clustering outperforms existing solvers on synthetic benchmarks and large-scale datasets.

Learning to rank can be cast as a probabilistic modeling problem over permutations, where the goal is to estimate the likelihood of an observed total ordering of items. This formulation naturally involves full-order probabilities of the form $\mathbb{P}(z_1 \leq \cdots \leq z_n)$, whose exact computation and optimization are intractable due to the factorial growth of the permutation space with respect to the list size. In this work, we introduce the *Full-Order Bound* (FOB), a tractable lower bound on the probability of an observed ordering, constructed from a subset of ordering constraints that factorizes across items while preserving full-order structure and order-reversal invariance. Under log-concave latent densities, the bound induces a convex inner tightening problem over latent cut points, which we solve efficiently during training using a *safe-region gradient ascent* (SRGA) procedure. Experiments on synthetic ranking tasks and large-scale learning-to-rank benchmarks show that FOB improves full-list ordering metrics and remains competitive on NDCG, while an optional metric-aligned variant recovers NDCG gains. Our code is available at https://github.com/tyxaaron/FOB.

Model merging has emerged as a lightweight paradigm for enhancing Large Language Models (LLMs), yet its underlying mechanisms remain poorly understood. In this work, we analyze late-stage pre-training trajectories and uncover a \textbf{Rank-1 Subspace} phenomenon: while raw optimization steps oscillate violently, consecutive \emph{merged} checkpoints collapse onto a stable, approximately one-dimensional linear manifold. We theoretically ground this observation in a \emph{river-valley} landscape analysis: averaging acts as a geometric low-pass filter that dampens high-curvature noise to reveal the optimal descent direction. Capitalizing on this insight, we propose \textbf{Extra-Merge}, a training-free strategy that extrapolates along this subspace to minimize loss without additional gradient updates. Extensive experiments across GPT-2 and LLaMA families (124M to 2B) demonstrate that Extra-Merge consistently outperforms standard merging baselines. Notably, it yields consistent zero-shot accuracy gains on Pythia-12B downstream tasks and generalizes effectively to the Muon optimizer (Jordan et al., 2024).

In domains such as recommender systems and information retrieval, learning from human-generated feedback is especially challenging because the information provided is often sparse and incomplete. In this work, we address the problem of learning the top-$k$ items from incomplete rankings. Most existing models for incomplete rankings rely on rigid assumptions regarding both the ranking model that generates the latent ranking and the censoring mechanism that determines which comparisons remain unobserved. On the one hand, the ranking model is often assumed to follow a Plackett-Luce (PL) or Mallows distribution. On the other hand, the censoring mechanism is typically assumed to be Missing Completely At Random (MCAR) or to exhibit well-behaved dependencies on the latent ranking, such as winner feedback or top-$h$ feedback. We introduce a new, general framework for learning from incomplete rankings that unifies and strictly generalizes the established frameworks in the literature. We consider the broad class of ranking models that satisfy the complete consensus property, which comprehends all widely adopted models, including PL and Mallows. Furthermore, we present a new preference-based feedback model, named positional censoring, which generalizes winner and top-$h$ feedback. We show that it is possible to learn in this general setting by presenting the PIRATE algorithm and providing a near-optimal instance-dependent bound to the sample complexity. Finally, we show that, under the PL ranking, PIRATE matches the sample complexity of state-of-the-art algorithms in the relevant scenarios of winner and top-$h$ feedback.

Rank estimation under label noise poses a fundamental challenge, as ordinal annotations often exhibit structured uncertainty rather than simple label corruption. In this paper, we reformulate rank estimation with noisy ordinal labels as a stochastic ordering problem, in which each instance is inherently associated with multiple plausible ranks instead of a single deterministic label. Based on this view, we propose stochastic order learning (SOL), a learning framework that captures ordinal label uncertainty and learns an embedding space through two complementary objectives: a discriminative loss that structures instance-centroid interactions and a stochastic order loss that enforces probabilistic ordering relations between instances. Extensive experiments across diverse datasets demonstrate that SOL enables reliable rank estimation under various types and levels of label noise. The source code is available at https://github.com/cwlee00/SOL.

Representations on the Symmetric Positive Definite (SPD) manifold have garnered significant attention across different applications. In contrast, the manifold of full-rank correlation matrices, a normalized alternative to SPD matrices, remains largely underexplored. This paper introduces Riemannian networks over the correlation manifold, leveraging five recently developed correlation geometries. We systematically extend basic layers, including Multinomial Logistic Regression (MLR), Fully Connected (FC), and convolutional layers, to these geometries. Besides, we present methods for accurate backpropagation for two correlation geometries. Experiments comparing our approach against existing SPD and Grassmannian networks demonstrate its effectiveness.

We introduce a rank-statistic approximation of $f$-divergences that avoids explicit density-ratio estimation by working directly with the distribution of ranks. For a resolution parameter $K$, we map the mismatch between two univariate distributions $\mu$ and $\nu$ to a rank histogram on $\{ 0, \ldots, K\}$ and measure its deviation from uniformity via a discrete $f$-divergence, yielding a rank-statistic divergence estimator. We prove that the resulting estimator of the divergence is monotone in $K$, is always a lower bound of the true $f$-divergence, and we establish quantitative convergence rates for $K\to\infty$ under mild regularity of the quantile-domain density ratio. To handle high-dimensional data, we define the sliced rank-statistic $f$-divergence by averaging the univariate construction over random projections, and we provide convergence results for the sliced limit as well. We also derive finite-sample deviation bounds along with asymptotic normality results for the estimator. Finally, we empirically validate the approach by benchmarking against neural baselines and illustrating its use as a learning objective in generative modeling experiments.

Traditional evaluations measure a learning algorithm's final performance on an i.i.d. test set, reducing learning to a single aggregate score. This approach obscures a fundamental question: to what extent does learning from a specific example generalize to others? Such per-sample generalization—akin to learning by analogy in human cognition—captures how far the knowledge extracted from one example can transfer, yet remains invisible to standard benchmarks. We introduce the Generalization Spectrum, an evaluation framework designed to expose this hidden dimension. For each training example, we construct a controlled suite of test variants arranged by increasing transfer distance—from exact recall to implementation transfer across languages, context transfer under complete narrative re-framing, category-matched in-domain problems, and an unpaired baseline. By tracking performance across these distances, we reveal not just whether an algorithm learns, but how far that learning extends. We instantiate this framework on competitive programming, using a synthetic generation pipeline seeded with recent problems to mitigate contamination. We first compare **three canonical learning paradigms** under matched memorization. RL converts memorization into near-transfer more efficiently than SFT-family baselines, while ICL exhibits strong but correspondence-dependent transfer. We then use the Spectrum to diagnose **within-family variants**. The resulting profiles show that local gains need not expand the generalization radius: abstractions and hints mainly lift local transfer, RFT preserves a stronger far-transfer tail than reference SFT, and self-distillation or hint-assisted RL can reduce far transfer even when local transfer or optimization improves.

Uncertainty quantification (UQ) is an important technique for ensuring the trustworthiness of LLMs, given their tendency to hallucinate. Existing state-of-the-art UQ approaches for free-form generation rely heavily on sampling, which incurs high computational cost and variance. In this work, we propose the first gradient-based UQ method for free-form generation, SemGrad, which is sampling-free and computationally efficient. Unlike prior gradient-based methods developed for classification tasks that operates in parameter space, we propose to consider gradients in semantic space. Our method builds on the key intuition that a confident LLM should maintain stable output distributions under semantically equivalent input perturbations. We interpret the stability as the gradients in semantic space and introduce a Semantic Preservation Score (SPS) to identify embeddings that best capture semantics, with respect to which gradients are computed. We further propose HybridGrad, which combines the strengths of SemGrad and parameter gradients. Experiments demonstrate that both of our methods provide efficient and effective uncertainty estimates, achieving superior performance than state-of-the-art methods, particularly in settings with multiple valid responses.

Federated Prompt Learning (FPL) adapts Vision-Language Models to privacy-sensitive medical imaging, typically via a textual tuning paradigm that assumes the frozen visual encoder provides a discriminative feature geometry. We argue this assumption breaks down in medical settings, leading to two geometric pathologies: (1) Intra-client: Medical Manifold Collapse, where high morphological similarity reduces the effective rank of visual features; and (2) Inter-client: Medical Topological Misalignment, where heterogeneous acquisition protocols induce inconsistent geometry across clients. To address these, we propose FedMAP, which shifts the paradigm to Visual Manifold Anchoring. FedMAP utilizes an LLM-derived codebook as a client-invariant synchronization signal to restructure the visual space, via Manifold Semantic Anchoring (MSA) and Topology Structural Alignment (TSA) to enforce consistent inter-class relations. Experiments on FedISIC, FedCamelyon17, and a private ultrasound dataset show that FedMAP consistently outperforms state-of-the-art methods, especially in high-noise regimes where manifold collapse is most severe.

State-of-the-art reasoning models utilize long chain-of-thought (CoT) to solve increasingly complex problems using more test-time computation. In this work, we explore a long CoT setting where the model makes up to K successive attempts at solving a problem, in which each attempt is allowed to build on earlier ones after the model receives a hard verifier feedback. This motivates RL methods that can harness per-attempt rewards by carefully weighting individual attempts. We study optimizing the Verification@K reward (the model succeeds by the K-th attempt) and show that naively weighing the attempts by their pass/fail results in biased gradients. We introduce Calibrated Attempt-Level (CAL) GRPO by devising a weighing strategy to obtain unbiased gradients while maintaining small variance. Our theory reveals how incorporating per-attempt rewards influences the training and the eventual Verification@K performance. Experiments, baselines, and ablations on synthetic and real data corroborate our theory and the benefits of CAL-GRPO over vanilla GRPO as well as naive weighting.

With the on-going integration of machine learning systems into the everyday social life of millions the notion of fairness becomes an ever increasing priority in their development. Fairness notions commonly rely on protected attributes to assess potential biases. Here, the majority of literature focuses on discrete setups regarding both target and protected attributes. The literature on continuous attributes especially in conjunction with regression - we refer to this as *continuous fairness* - is scarce. A common strategy is iterative null-space projection which as of now has only been explored for linear models or embeddings such as obtained by a non-linear encoder. We improve on this by extending this to kernel induced feature spaces by means of the ``empirical feature space''. We theoretically derive this as a direct transformation of the kernel matrix yielding a model and fairness-score agnostic method applicable to continuous protected attributes. We demonstrate that our novel approach in conjunction with Support Vector Regression (SVR) provides competitive or improved performance across multiple datasets in comparison to other contemporary methods.

Feature-map knowledge distillation (KD) transfers internal representations well between comparably sized Vision Transformers (ViTs), but it often fails in compression. We revisit this failure and uncover a paradox. Sample-wise SVD shows that each image is highly compressible, which seems to suggest that a narrow student with a linear projector should match the teacher "in principle". However, a dataset-level view contradicts this intuition: PCA shows that the teacher is a union of low-rank subspaces with significant subspace rotation across inputs. We further introduce token-level Spectral Energy Patterns (SEP) and find an architecture-invariant encoding law: tokens spread energy broadly across channel modes even when they live in low-rank subspace, creating a bandwidth mismatch. We refer to this combined phenomenon as an encoding mismatch. We propose two minimal remedies, Lift or WideLast: (i) Lift retains a lightweight lifting projector at inference to provide wider channel, or (ii) WideLast widens only the student’s last block, enabling an input-dependent expansion. On ImageNet-1K, these fixes revive feature KD for ViT compression, improving DeiT-Tiny distilled from CaiT-S24 from 74.86% to 77.53%/78.23% top-1 accuracy, and they also strengthen students trained without distillation. Our analyses clarify when and why feature-map KD fails and then how to fix it. Code and raw data are provided in https://github.com/thy960112/From-Per-Image-Low-Rank-to-Encoding-Mismatch.

The rapid development of large language models (LLMs) has raised concerns regarding the inclusion of private or inappropriate data during training, which has led to growing interest in LLM unlearning. Many existing LLM unlearning approaches rely on prediction loss-based optimizations, such as maximizing the loss on the forget set. However, these methods often face issues such as over-forgetting and poor model utility. In this work, we address these issues by introducing a novel perspective that shifts the unlearning optimization target to reducing data attribution instead. We propose the first LLM unlearning framework based on data attribution rewards called DareU that employs reinforcement learning to update the LLM and reduce the attribution score of generated responses (i.e., de-attribute) to the forget data owners. Experimental results using an LLM classifier as an efficient approximation of attribution demonstrate that DareU outperforms existing baseline approaches, achieving effective unlearning while balancing forget quality and model utility.

The Tubal Nuclear Norm (TNN), derived from the tensor Singular Value Decomposition (t-SVD), is a widely used low-rank modeling tool that promotes sparsity of frequency-domain singular values. However, as a direct extension of the matrix nuclear norm, TNN applies a uniform element-wise penalty to transformed singular values, without explicitly distinguishing sparsity across frequency components from low-rankness within each component. This can be restrictive for real-world tensor data that exhibit multi-level spectral structures, where spectral energy is concentrated in a subset of frequency components while active components remain low-rank. To overcome this limitation, we propose the tensor $\ell_p$-Schatten-$q$ quasi-norm ($p,q\in(0,1]$), which enables explicit control of dual spectral sparsity by jointly regularizing inter-frequency sparsity and intra-frequency low-rankness. This formulation includes TNN as a special case and subsumes several existing tensor regularizers by coupling global frequency sparsity with local spectral low-rankness, yielding a more flexible modeling principle. We establish minimax error bounds under the proposed dual spectral sparsity model, develop a reweighted optimization algorithm for the resulting nonconvex problem, and demonstrate its effectiveness and robustness on noisy and Poisson tensor completion as well as image clustering tasks.

Large language models~(LLMs) are trained on heterogeneous multilingual corpora, yet existing policy optimization methods often implicitly restrict each training question to a single response language or rely on a fixed dominant language for supervision. We propose language-routed policy optimization (LRPO), an online reinforcement learning framework that treats language as a selectable variable. LRPO elicits multilingual rollouts for each training question and integrates their relative quality into preference-based policy updates, increasing the diversity and informativeness of training signals under the fixed rollout budget. To adaptively determine which languages to explore during reinforcement learning, we introduce a trainable language router formulated as a multi-armed bandit, balancing exploration of underutilized languages with exploitation of more informative ones. Extensive experiments show that LRPO consistently improves multilingual performance, demonstrating that adaptive language routing enables effective cross-lingual knowledge exploitation for training. We release all the resources at \url{https://github.com/Guochry/LRPO}.