跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+1111新增论文
+874其中 AI 相关
+133已有论文修订
+97新增 AI 导读

arXiv 最近完成扫描:2026-11-20 06:44 · 全站最近入库:2026-11-19 19:09各信源进度 →

统计口径与数据新鲜度

统计 2026-11-19 07:38 — 2026-11-20 07:38(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-20 06:44最近发现新增版本:2026-11-19 19:09库内论文最新更新时间:2026-11-19 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

27,982 已收录论文23,249 AI 相关8,559 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 955 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-20 06:42(北京时间)
版本更新 · v2arXiv:2609.07868

SGD in Multiclass Logistic Regression: Sequential Learning and Scaling Laws

Konstantinos Christopher Tsiolis, Denny Wu, Christos Thrampoulidis, Murat A. Erdogdu

原文摘要

We study the training dynamics of multiclass logistic regression on high-dimensional mixture models with a large number of classes and establish precise scaling laws governing the cross-entropy risk under gradient-based optimization. We show that learning proceeds sequentially across classes, from most to least frequent. When the class priors follow a power law distribution, the risk dynamics decompose into three phases: an initial plateau until the first class is learned, a power-law decay regime during which sequential learning occurs, and a final convergence regime. We then analyze how model capacity interacts with optimization under a fixed compute budget. When the effective dimension is restricted via projection onto leading principal components, the risk decomposes into a capacity term (a power law in the retained dimension) and an optimization term (a power law in training time). Optimizing this tradeoff yields a compute-optimal scaling law for logistic regression, with explicit prescriptions for model size and training time as functions of compute. These results extend theoretical scaling laws from linear regression to multiclass classification, while connecting to empirical scaling laws observed in large-scale neural networks.

stat.ML · cs.LG

新论文 · v1arXiv:2611.10338

On the universal structure in deterministic generative diffusion

Defang Chen, Zhenyu Zhou, Can Wang, Zeyu Zheng, Siwei Lyu

原文摘要

Diffusion-based generative modeling has emerged as a general computational framework for simulating high-dimensional, structured data across various domains. Understanding its generative mechanisms is paramount for advancing model training and inference in a principled way. Here, we demonstrate that deterministic sampling trajectories share a universal geometric structure invariant to data modalities and diffusion model implementations. This structure can be largely explained by an exactly solvable model based on the optimal linear denoiser.

cs.LG · cond-mat.stat-mech · cs.CV · stat.ML

版本更新 · v4arXiv:2605.01729

Stable GFlowNets with TV Monitoring and Probabilistic Guarantees

Zengxiang Lei, Ananth Shreekumar, Jonathan Rosenthal, Ruoyu Song, Alvaro A. Cardenas, Daniel J. Fremont, Dongyan Xu, Satish Ukkusuri 等 9 位作者

原文摘要

Generative Flow Networks (GFlowNets) sample diverse structured objects in proportion to reward and have been applied to molecular discovery and biological-sequence design, where finding multiple high-quality candidates is more useful than returning a single optimum. Despite their theoretical promise, practical training is often unstable, exhibiting severe loss spikes and mode collapse. To address this, we first assess the sensitivity of GFlowNet objectives, demonstrating that a small Total Variation (TV) distance between the learned and target distributions does not preclude an unbounded training loss. Motivated by this mismatch, we establish converse guarantees by deriving loss-to-TV bounds that certify global fidelity from bounded trajectory balance losses. Lastly, we propose Stable GFlowNets, which leverages our theory to stabilize training via adaptive reference flow and improves the trade-off among mode coverage, robustness, and certifiability. Code is available at: https://github.com/tjleizeng/StableGFlowNets.

cs.LG · stat.ML

版本更新 · v2arXiv:2606.15964

PromptShift-CRC: What Drift-Aware Weighting Adds to Online Conformal Risk Control for Foundation Models

Jeffery Opoku, David Banahene

原文摘要

A risk threshold calibrated on old prompts can stop being valid when prompts to a foundation model drift. We study PromptShift-CRC, a rule that weights past prompts by feature similarity, falls back to recent prompts when the current prompt is unlike the past, and updates its level online. We prove that the update controls the long-run violation rate for any weights, so marginal coverage cannot separate weighting schemes. We give a conditional bound at a fixed level whose cost is a weighted total variation distance, bounded by a computable prompt-drift term up to an unknown Lipschitz constant. We propose a comparison protocol: a matched short-window baseline, a validity and sharpness frontier, 30-seed synthetic streams, and real-output streams ordered without using the model's output. On MMLU, TruthfulQA (Qwen2.5-1.5B) and RealToxicityPrompts (GPT-2, replicated with a second generator and classifier), every online method reaches the target. PromptShift-CRC stays within 0.0055 of the Adaptive CRC frontier and avoids the worst window, but DtACI matches or beats it in most settings. The rule performs like a mid-ranked window without having to choose one. Tests fixed in advance to favor the weights show no consistent gain over the frontier. Code, outputs and streams are released.

stat.ML · cs.LG

版本更新 · v3arXiv:2410.02504

Dual Active Learning for Reinforcement Learning from Human Feedback

Pangpang Liu, Chengchun Shi, Will Wei Sun

原文摘要

Aligning large language models (LLMs) with human preferences is critical to recent advances in generative artificial intelligence. Reinforcement learning from human feedback (RLHF) is widely applied to achieve this objective. A key step in RLHF is to learn the reward function from human feedback. However, human feedback is costly and time-consuming, making it essential to collect high-quality conversation data for human teachers to label. Additionally, different human teachers have different levels of expertise. It is thus critical to query the most appropriate teacher for their opinions. In this paper, we use reinforcement learning (RL) to formulate the alignment problem. Motivated by the idea of $D$-optimal design, we first propose a dual active reward learning algorithm for the simultaneous selection of conversations and teachers. Next, we apply pessimistic RL to solve the alignment problem, based on the learned reward estimator. Theoretically, we show that the reward estimator obtained through our proposed adaptive selection strategy achieves minimal generalized variance asymptotically, and prove that the sub-optimality of our pessimistic policy scales as $O(1/\sqrt{T})$ with a given sample budget $T$. Through simulations and experiments on LLMs, including annotator-level preference data and downstream Best-of-$N$ response-selection evaluations, we demonstrate the effectiveness of our algorithm and its superiority over existing baselines.

stat.ML · cs.LG

版本更新 · v2arXiv:2602.03461

Soft-Radial Projection for Constrained End-to-End Learning

Philipp J. Schneider, Daniel Kuhn

原文摘要

Constrained end-to-end learning trains neural networks whose outputs must satisfy feasibility constraints, such as resource, budget, or operational limits. While projection and optimization layers guarantee constraint satisfaction, boundary-based projections can introduce unfavorable optimization geometry: regions of the unconstrained output space are mapped to the same active face of the feasible set. This makes the resulting map locally rank-deficient, suppressing gradients in constrained directions and potentially impairing optimization - a bottleneck known as gradient saturation. We propose Soft-Radial Projection (SRP), a differentiable reparameterization layer that maps unconstrained network outputs into the relative interior of a convex feasible set by smoothly rescaling rays from a strictly feasible anchor point. Unlike hard radial or orthogonal projections, the resulting map is one-to-one and has a full-rank Jacobian almost everywhere, while guaranteeing strict feasibility. We prove that constrained networks equipped with SRP retain universal approximation guarantees. For polytopes and balls, the layer admits a closed-form forward pass, while for general convex sets, the ray-boundary intersection reduces to a one-dimensional search. Experiments on decision-focused learning benchmarks demonstrate strong solution quality at low computational cost, with particularly favorable results in portfolio optimization and substantially lower inference latency than differentiable optimization layers in the evaluated settings.

cs.LG · math.OC · q-fin.CP · stat.ML

版本更新 · v3arXiv:2508.00110

funOCLUST: Clustering Functional Data with Outliers

Katharine M. Clark, Paul D. McNicholas

原文摘要

Functional data present unique challenges for clustering due to their infinite-dimensional nature and potential sensitivity to outliers. An extension of the OCLUST algorithm to the functional setting is proposed to address these issues. The approach leverages the OCLUST framework, creating a robust method to cluster curves and trim outliers. The methodology is evaluated on both simulated and real-world functional datasets, demonstrating strong performance in clustering and outlier identification.

stat.ML · cs.LG · stat.ME

版本更新 · v2arXiv:2605.07972

It Just Takes Two: Scaling Amortized Inference to Large Sets

Antoine Wehenkel, Michael Kagan, Lukas Heinrich, Chris Pollard

原文摘要

Neural posterior estimation has emerged as a powerful tool for amortized inference, with growing adoption across scientific and applied domains. In many of these applications, the conditioning variable is a set of observations whose elements depend not only on the target but also on unknown factors shared across the set. Optimal inference therefore requires treating the set jointly, which in turn requires training the estimator at the deployment set size -- a regime where memory and compute quickly become prohibitive. We introduce a simple, theoretically grounded strategy that decouples representation learning from posterior modeling. Our method trains a mean-pool Deep Set on sets of size at most two, producing an encoder that generalizes to arbitrary set sizes. The inference head is then finetuned on pre-aggregated embeddings, making training cost essentially independent of the deployment set size N. Across scalar, image, multi-view 3D, molecular, and high-dimensional conditional generation benchmarks with N in the thousands, our approach matches or outperforms standard baselines at a fraction of the compute.

cs.LG · cs.AI · hep-ex · hep-ph · stat.ML

新论文 · v1arXiv:2611.10267

Match the Geometry Before the Surrogate: Extreme Low-Budget Optimization in High Dimensions

Michal Průšek, Adam Novozámský, Filip Šroubek

原文摘要

Low-budget molecular optimization is often framed as Bayesian optimization in a learned latent space, but standard benchmarks typically allow hundreds or thousands of evaluations, whereas a realistic wet-lab round may allow only a few dozen. We revisit this regime using a SELFIES molecular variational autoencoder (VAE) with a Gaussian prior and GuacaMol objectives at N = 30 evaluations. The main finding is not a new surrogate model, but an interaction in candidate generation. The encoder means of a reference set of molecules concentrate near a narrow spherical shell, while many high-dimensional optimizers propose candidates from boxes or box-shaped trust regions. We study a simple constraint, the on-sphere scaffold, that restricts candidate generation to this shell. We then introduce two minimal optimizers to probe what remains useful once the support is fixed. GeoWalk performs geodesic local search on the shell without a surrogate. After 30 evaluations, it shows no detected difference from a Gaussian-process (GP) surrogate on the shell, which is ahead earlier in the budget. GeoCMA adds covariance learning in a random subspace. It does not improve on GeoWalk in the molecular benchmark. On LassoBench it has a lower mean loss than GeoWalk, but full-dimensional CMA-ES remains stronger on most tasks. A factorial experiment with a single GP crosses the candidate support (shell or box) with the acquisition maximizer (a finite candidate set or a continuous optimizer). In this benchmark, shell candidates outperformed box candidates when acquisition was maximized over a candidate set, but not with continuous maximization by L-BFGS-B. These results come from a controlled study of one Gaussian-prior VAE benchmark and do not recommend VAEs for molecular optimization. The practical lesson is to control the candidate support and the acquisition maximizer before attributing a gain to the surrogate.

cs.LG · stat.ML

新论文 · v1arXiv:2611.10223

Lower-Level Agnostic Bilevel Optimization

Peiwen Qiu, Prashant Khanduri, Jia Liu

原文摘要

Bilevel optimization is a fundamental framework for machine learning problems, where an upper-level (UL) objective depends on the solution of a nested lower-level (LL) problem. Existing bilevel algorithms typically assume that the LL objective is available for evaluation, differentiation, or unrolling. However, this assumption can fail when the LL response is produced by a black-box solver, simulator, adversary, or learned predictor. In this paper, we study LL agnostic bilevel optimization, where the UL learner has access only to an approximate LL solution $\bar{\mathbf{y}}(\mathbf{x})$ and cannot query the LL objective, its gradients, Hessian/Jacobian information, or the procedure that generates the LL response. We propose LeGo-BiO, a coordinate-wise pseudo-hypergradient method that estimates the missing Jacobian $\nabla _{\mathbf{x}}\bar{\mathbf{y}}(\mathbf{x})$ using finite differences of $\bar{\mathbf{y}}(\cdot)$. For each UL coordinate, LeGo-BiO constructs a decision vector subject to 1-sparse updates, thereby isolating the corresponding Jacobian column needed in the UL gradient computation. This avoids the directional-projection limitation of full-parameter response differences and, unlike derivative-free/zeroth-order approximations of the entire UL gradient, preserves the available first-order gradient information with respect to the UL variables for more accurate UL gradient evaluation. We establish convergence guarantees for LeGo-BiO in both deterministic and stochastic settings under an LL error-bound/Polyak-Lojasiewicz-type condition, without requiring LL strong convexity. Our bounds yield an $O(T^{-1})$ rate in the deterministic setting and an $O(T^{-1/2})$ rate in the stochastic setting when the LL approximation error decreases geometrically. Experiments demonstrate competitive performance of LeGo-BiO despite being agnostic to the LL objective.

cs.LG · math.OC · stat.ML

版本更新 · v4arXiv:2601.21636

Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation

Jan Schuchardt, Nikita Kalinin

原文摘要

We study privacy amplification for differentially private model training with matrix factorization under random allocation (also known as the balls-in-bins model). Recent work by Choquette-Choo et al. (2025) proposes a sampling-based Monte Carlo approach to compute amplification parameters in this setting. However, their guarantees either only hold with some high probability or require random abstention by the mechanism. Furthermore, the required number of samples for ensuring $(ε,δ)$-DP is inversely proportional to $δ$. In contrast, we develop sampling-free bounds based on Rényi divergence and conditional composition. The former is facilitated by a dynamic programming formulation to efficiently compute the bounds. The latter complements it by offering stronger privacy guarantees for small $ε$, where Rényi divergence bounds inherently lead to an over-approximation. Our framework applies to arbitrary banded and non-banded matrices. Through numerical comparisons, we demonstrate the efficacy of our approach across a broad range of matrix mechanisms used in research and practice.

cs.LG · cs.CR · stat.ML

版本更新 · v2arXiv:2611.06348

Flexible Intensities Matter: A Comprehensive Re-evaluation of Hawkes Processes and Neural Temporal Point Processes

Hendrik Mehrtens, Florian Buettner, Oliver Stegle

原文摘要

Temporal point processes (TPPs) are the canonical model class for event sequences in continuous time, with applications ranging from seismology to electronic health records. Recent benchmarks report that neural TPPs substantially outperform their classical counterparts, such as Hawkes processes. However, these comparisons set flexible neural models against Hawkes processes in their most restricted forms and covered only a narrow range of domains. We revisit this comparison under autoregressive next-event prediction, evaluating Poisson and Hawkes processes of increasing flexibility against neural TPPs on five established benchmarks and two large-scale medical tasks derived from UK Biobank disease histories and MIMIC-IV ICU records. First, once Hawkes processes are equipped with flexible, learnable baselines and kernels, the previously reported gap to neural TPPs largely closes. Second, neural TPPs are likewise limited by their intensity parametrization: a Transformer with a spline-based intensity head outperforms previous intensity-based neural TPPs and matches or exceeds the intensity-free model. Decomposing the log-likelihood into time and type terms shows that this gain lies almost entirely in modeling when events occur (log p(t)) rather than which type occurs (log p(d|t)). Third, only on MIMIC-IV do neural TPPs retain an advantage in predicting event types, underscoring the value of complex datasets for evaluating TPPs. We release TorchPP, an open-source PyTorch framework with unified implementations of classical and neural TPPs.

cs.LG · stat.ML

版本更新 · v2arXiv:2611.05557

支持向量机直接最小化KL散度

Support Vector Machines Directly Minimise KL Divergence

Ivan Silajev

AI 速读 基于摘要

作者证明支持向量分类与回归的对偶目标等价于两个高斯测度间带约束的KL散度最小化,并据此将核岭回归纳入同一信息论框架。

cs.LG · stat.ML

查看原文摘要

Support vector machines (SVMs) are fundamentally grounded in geometric margin maximisation and currently lack a mainstream probabilistic interpretation. This keeps them theoretically isolated from probabilistic machine learning models that are naturally comparable and combinable. In this paper, we bridge this gap by proving that the dual objectives of both support vector classification and support vector regression are exact, constrained Kullback-Leibler (KL) divergence minimisation tasks between two Gaussian measures. We further show that this same divergence formulation recovers the exact objective function for kernel ridge regression when domain constraints are removed and $L^2$ regularisation is applied. By demonstrating that SVM duals directly minimise relative entropy, our results provide a unified information-theoretic model for standard kernel machines and lay the foundation for unifying broader kernel-based algorithms under probability theory.

版本更新 · v3arXiv:2606.15950

Spectral Similarity Weights for Adaptive Conformal Prediction: A Bias-Variance Account and a Benchmark

Jeffery Opoku, David Banahene

原文摘要

Conformal prediction intervals lose their guarantee when a series is not exchangeable. We study weighting calibration residuals by the similarity of local Fourier power features, combined with the adaptive level update of ACI. A two-term account of the coverage error, mismatch that falls and sampling error that rises as the bandwidth shrinks, holds with exogenous features and conditionally independent residuals, but not for features computed from the series itself, which is how the method is used. In four simulations, spectral weighting lowered the mean regime-level deviation of coverage by 17% to 19% when the features came from the response and by 75% when they were exogenous, and not clearly under gradual drift. In each recurring-regime design a scaled-error baseline or Conformal PID control calibrated better. On nine public series with 36 forecast origins, spectral weighting with the plain weighted quantile did not differ from projected ACI in coverage error, and Conformal PID and scaled ACI were the best calibrated methods. The features are blind to seasonal phase, so the weights act like a recency kernel. A pure recency kernel did at least as well, especially with a finite-sample rank correction (mean absolute coverage error 0.039 against 0.090 for ACI; a post hoc check). Calendar phase weights narrowed German electricity intervals by 23% at equal coverage, but were not better than ACI across the series. We suggest trying adaptive baselines first, and similarity weights only where regimes differ in spectral shape or season and the effective sample size stays large.

stat.ML · cs.LG

新论文 · v1arXiv:2611.09778

可解码POMDP的拟多项式时间规划

Quasipolynomial-Time Planning for Decodable POMDPs

Oliver Dobson, Varun Jog, Chun Hei Michael Shiu

AI 速读 基于摘要

作者提出对每个固定ρ>0的ρ-可解码POMDP给出拟多项式时间近似规划算法,并论证可解码性是比可观测性更弱且易检验的统一假设。

cs.LG · cs.DS · cs.IT · math.OC · stat.ML

查看原文摘要

We study planning for finite-horizon partially observable Markov decision processes (POMDPs) with finite state, action, and observation spaces. Both exact and approximate planning are known to be computationally hard in this setting, so prior work has explored natural assumptions that make planning easier. Recent work [Golowich et al., 2022] gave quasipolynomial-time approximate planning algorithms for observable POMDPs. These are POMDPs whose observation channels satisfy an $\ell_1$-observability condition, but notably, no assumptions are required on the transition dynamics. In a similar vein, for every fixed $ρ>0$, we give quasipolynomial-time approximate planning algorithms for $ρ$-decodable POMDPs. We show that decodability is implied by both $\ell_1$- and $\ell_2$-observability and is strictly weaker than observability. Moreover, we show that the optimal decodability constant can be computed in polynomial time, whereas computing the optimal $\ell_1$-observability constant is NP-hard in the worst case. We also show that the fast filter-forgetting guarantee underlying the approach of [Golowich et al., 2022] does not extend directly from $\ell_1$-observability to constant $\ell_2$-observability. Thus, decodability is an easy-to-check, unifying assumption under which quasipolynomial-time approximate planning for POMDPs is possible.

版本更新 · v2arXiv:2605.23362

预算约束下多LLM评审的实例最优估计

Instance-Optimal Estimation with Multiple LLM Judges on a Budget

Junghyun Lee, Sanghwa Kim, Yassir Jedra, Alexandre Proutière, Se-Young Yun

AI 速读 基于摘要

在固定预算下,研究如何将评估查询分配给价格与可靠性各异的多个LLM评审和不同难度的实例,以最准确地估计得分向量。

cs.LG · cs.IT · math.ST · stat.ML

查看原文摘要

Evaluating large language models increasingly relies on LLM-as-a-judge protocols, but such evaluations remain costly: different judges have different prices and reliabilities, and the difficulty of each prompt-response pair can vary substantially. This raises a basic allocation question: under a fixed budget, how should one distribute evaluation queries across heterogeneous judges and instances to obtain the most accurate score estimates? We formalize this question as budgeted heteroskedastic multi-judge estimation under independent, unbiased score observations. Given $K$ prompt-response pairs and $J$ judges with known costs but unknown query-judge variances, our goal is to estimate the bounded score vector while minimizing an $\ell_p$-error. Our first contribution is to analyze the inverse-variance weighted estimator (IVWE) and to derive the oracle allocation that minimizes its leading error bound. Since this allocation depends on the unknown variances, we then address the unknown-variance setting by proposing EST-IVWE, an adaptive algorithm that constructs and uses optimistic variance estimates to stabilize the empirical allocation. We prove that EST-IVWE matches the oracle IVWE rate up to lower-order terms in the budget. Our second and central theoretical contribution is a local minimax lower bound matching the leading allocation-dependent rate, establishing asymptotic instance-optimality up to logarithmic factors. An Assouad-type construction based on local, variance-preserving perturbations yields this bound both in expectation and with constant probability. A complementary Fano-type change-of-measure argument captures the logarithmic dependence on the confidence level with a different (suboptimal) allocation geometry. Finally, we numerically validate our approach on synthetic data and resampled HelpSteer2 evaluations, demonstrating improvements over naïve uniform allocation.

新论文 · v1arXiv:2611.10095

Adaptive Budgeted Data Acquisition for Robust Off-Policy Evaluation from Multiple Loggers

Amitakshar Biswas, Ruoqing Zhu

原文摘要

We consider off-policy evaluation when additional data can be purchased from several existing logging policies (or loggers) with heterogeneous costs per observation. While existing work on multiple loggers presumes a fixed number of observations from each logger, we study how to allocate a limited budget across them sequentially to evaluate a finite class of target policies. We propose Adaptive Greedy, an algorithm that purchases observations sequentially from the affordable logger that has the most cost-normalized variance reduction across the target policies. It turns out that each such purchase is an 'approximate conditional-gradient step' for the corresponding design problem. Under mild assumptions, we establish that the empirical allocation converges almost surely to the optimal design at an explicit rate. We also derive the asymptotic normality of the final pooled estimator and show that it attains the semiparametric efficiency bound. Simulations and a semi-synthetic application based on the AIDS Clinical Trials Group Study 175 show that Adaptive Greedy outperforms standard allocation strategies, remains accurate if stopped early, and matches the final accuracy of repeated integer programming at a fraction of its computational cost.

stat.ML · cs.LG

新论文 · v1arXiv:2611.09701

Where Should Learning Live? Regret Analysis for Text, Parameter, and Joint Adaptation

Jungtaek Kim, Jaden Park, Jongwon Jeong, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Kangwook Lee

原文摘要

Language-model systems can select prompts and parameter adapters repeatedly during deployment, using feedback to guide later choices. Earlier choices may change the context or environment inherited by later configurations. We study selection among preconstructed candidates and compare cumulative loss with the best fixed prompt--parameter pair used from the beginning. This excess loss separates into three terms: selection regret within the available family, the gap from restricting that family, and the benefit or harm of the actual deployment history. Selection is evaluated using the history each candidate would have produced if used throughout, which separates candidate quality from the effects of switching. When loss functions are fixed independently of selector randomness, past choices affect loss for only a bounded number of rounds, and every candidate's own-history loss is revealed, limiting switches yields sublinear expected regret within the selected family. We also quantify the costs and additional assumptions of independent probing and deployment-only feedback. Controlled experiments show that fewer switches can either lower or raise deployed loss, depending on whether inherited histories are harmful or helpful. With Qwen3.5-9B on Spider, text-only selection has lower within-family regret than joint selection, yet produces more failures because its candidate family excludes stronger configurations.

stat.ML · cs.LG

版本更新 · v3arXiv:2510.04606

Closed-Form Last Layer Optimization

Alexandre Galashov, Nathaël Da Costa, Liyuan Xu, Philipp Hennig, Arthur Gretton

原文摘要

Neural networks are typically optimized with variants of stochastic gradient descent. Under a squared loss, however, the optimal solution to the linear last layer weights is known in closed-form. We propose to leverage this during optimization, treating the last layer as a function of the backbone parameters, and optimizing solely for these parameters. We show this is equivalent to alternating between gradient descent steps on the backbone and closed-form updates on the last layer. We adapt the method for the setting of stochastic gradient descent, by trading off the loss on the current batch against the accumulated information from previous batches. We provide theoretical analyses showing convergence of the method to an optimal solution in the neural tangent kernel regime, as well as quantifying the gains compared to standard SGD in a one-step analysis. Finally, we demonstrate the effectiveness of our approach compared with SGD and Adam on a squared loss in several regression tasks, including neural operators and causal inference.

cs.LG · stat.ML

版本更新 · v2arXiv:2605.20122

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation

Peter Matthew Jacobs, Jeff M. Phillips

原文摘要

Squared Wasserstein distance is a frequently used tool to measure discrepancy between probability distributions. This distance is typically computed between empirical measures of size $n$ from two underlying random samples. Unfortunately, even in lower dimensional Euclidean space problems $\left( d \in \{2,3\} \right)$, algorithms for Wasserstein distance computation with approximate or exact precision guarantees scale poorly in the runtime as a function of $n$ and the desired precision. In response, we consider the computational-statistical runtime, where the goal is to estimate from samples the Wasserstein distance between potentially smooth measures up to $ε$-additive error in expectation with respect to the sampling; we allow $O(1)$ computational cost for collecting a sample. Towards this, we develop a Sample-Sketch-Solve paradigm where we introduce a regular cartesian grid sketch of the samples. We show that (especially under $α$-Hölder smooth distributions) this can compress the data without increasing asymptotic error, and also regularizes the structure which enables faster exact algorithms. Ultimately, we approximate $W_2^2(P,Q)$ within $ε$ error in $ε^{-\max(2,\frac{d+1+o(1)}{1+α})}$ time for $0 < α< 1$ Hölder smooth distributions $P,Q$ on $(0,1)^{d}$; an optimal $Θ(ε^{-2})$ for $α> 1/2$ when $d=2$ and nearly optimal as $α\to 1$ when $d = 3$.

stat.ML · cs.CC · cs.LG

新论文 · v1arXiv:2611.09665

Online Causal Configuration for Networked Systems via Doubly Robust Steady-State Learning

Yuli Liu, Zhiheng Zhang

原文摘要

Measurement exploration reveals how interacting local controllers behave but can alter the steady-state regime a network operator seeks to optimize. Exploratory rewards may therefore fail to identify a configuration's no-exploration value: under full exploration, identical logged distributions can conceal different target values. Identification requires accounting for both action-law mismatch and shifts in the steady-state context distribution. We introduce CAUSAL-UCB, which selects configurations using optimistic bounds on target causal values. Its interference-aware clipped doubly robust evaluator produces predecision certificates separating statistical variation from calibrated identification, transport, and temporal-dependence errors. For any finite horizon and predetermined schedule of measurement-exploration rates $\{η_t\}$, we prove lower bounds of $Ω((1+\sum_tη_t)^{-1/2})$ on minimax inference error and $Ω(\sum_tη_t)$ on measurement-induced deployment loss in a stationary, potentially slow-mixing family. We bound regret under valid certificates and selected-information growth, and establish an anytime finite-sample certificate with a shared radius for estimation, selection, and reporting in a restricted known-local-interference model. In a high-mismatch benchmark with 24 paired seeds and 200 rounds, CAUSAL-UCB attains target regret of $1.732$ versus $6.326$ for certified IPS-UCB, with deployment gaps of $30.607$ and $23.217$, respectively. Independent-audit coverage tests and trace-driven semi-synthetic studies further assess certificate coverage and deployment trade-offs.

cs.LG · stat.ML

版本更新 · v2arXiv:2510.26401

Outlier-Robust Multi-Output Gaussian Processes

Joshua Rooijakkers, Leiv Rønneberg, François-Xavier Briol, Jeremias Knoblauch, Matias Altamirano

原文摘要

Multi-output Gaussian process (MOGP) regression allows modelling dependencies among multiple correlated response variables. Similarly to standard Gaussian processes (GPs), MOGPs are sensitive to model misspecification and outliers, which can distort predictions within individual outputs. In the multi-output case, this situation can be further exacerbated as anomalous observations in one response can adversely influence predictions for other correlated outputs. To handle this situation, we propose R-MOGP, an MOGP that is provably robust to outliers in any individual response. Our approach preserves conjugacy, achieving robustness without sacrificing computational efficiency, and integrates naturally with sparse variational inference for scalability. Empirically, we show that R-MOGP achieves performance comparable to existing state-of-the-art robust MOGPs at a fraction of their computational costs.

stat.ML · cs.LG

新论文 · v1arXiv:2611.09612

Kernel-Based Learning of Analytic Operators and Parametric PDEs

Giovanni S. Alberti, Markus Holzleitner, Lorenzo Rosasco, Matteo Santacesaria

原文摘要

We study kernel-based learning of analytic operators from finite samples, with a focus on how the regularity of the target should determine the choice of the kernel. We establish embeddings of analytic operators into vector-valued reproducing kernel Hilbert spaces and derive finite-sample, high-probability guarantees that quantify the uncertainty due to random sampling: in the noiseless setting, suitable analytic kernels yield rates exponential in a fractional power of the sample size, while Sobolev-type kernels yield polynomial rates. We apply the theory to the solution operator of a parametric elliptic PDE, where the training data are themselves finite-element approximations, and obtain bounds that separate the sampling and discretization contributions to the error and prescribe how the mesh size should be coupled to the sample size. The results are illustrated numerically.

stat.ML · cs.LG · math.ST

版本更新 · v2arXiv:2502.17175

Linear Bandits on Ellipsoids: Minimax Optimal Algorithms

Raymond Zhang, Hedi Hadiji, Richard Combes

原文摘要

We consider linear stochastic bandits where the set of actions is an ellipsoid. We provide the first known minimax optimal algorithm for this problem. We first derive a novel information-theoretic lower bound on the regret of any algorithm, which must be at least $Ω(\min(d σ\sqrt{T} + d \|θ\|_{A}, \|θ\|_{A} T))$ where $d$ is the dimension, $T$ the time horizon, $σ^2$ the noise variance, $A$ a matrix defining the set of actions and $θ$ the vector of unknown parameters. We then provide an algorithm whose regret matches this bound to a multiplicative universal constant. The algorithm is non-classical in the sense that it is not optimistic, and it is not a sampling algorithm. The main idea is to combine a novel sequential procedure to estimate $\|θ\|$, followed by an explore-and-commit strategy informed by this estimate. The algorithm is highly computationally efficient, and a run requires only time $O(dT + d^2 \log(T/d) + d^3)$ and memory $O(d^2)$, in contrast with known optimistic algorithms, which are not implementable in polynomial time. We go beyond minimax optimality and show that our algorithm is locally asymptotically minimax optimal, a much stronger notion of optimality. We further provide numerical experiments to illustrate our theoretical findings.

stat.ML · cs.LG

版本更新 · v2arXiv:2605.07297

Spectrum-Adaptive Generalization Bounds for Trained Deep Transformers

Mana Sakai, Masaaki Imaizumi

原文摘要

Understanding why trained Transformers generalize well is a fundamental problem in modern machine learning theory, and complexity-based generalization bounds provide a principled way to study this question. While existing norm-based bounds for Transformers remove the explicit polynomial dependence on the hidden dimension, they typically impose fixed norm constraints specified a priori and can exhibit unfavorable exponential dependence on depth. In this paper, we derive spectrum-adaptive post hoc generalization bounds for multi-layer Transformers. Under layerwise spectral norm control, the bounds are expressed in terms of layerwise Schatten quantities of the query-key, value, and feedforward weight matrices. Since the Schatten indices need not be fixed a priori and can instead be selected after training, separately for each matrix type and layer, the bounds adaptively trade off spectral complexity against the dimension- and depth-dependent factors according to the learned singular-value profiles. Empirical comparisons of BERT-adapted proxies for the leading complexity factors suggest that the proxies induced by our bounds grow more slowly with depth and hidden dimension than the corresponding norm-based proxies. Overall, our results provide a complexity-based perspective on how the spectral structure of trained Transformers is reflected in generalization analyses.

stat.ML · cs.LG

新论文 · v1arXiv:2611.09579

Locally Adaptive Conformal Prediction for Polynomial Chaos Expansions

Dimitrios Loukrezis, Arthur Hatstatt, Bruno Sudret, Dimitris G. Giovanis

原文摘要

This work develops a locally adaptive jackknife+ conformal prediction framework for polynomial chaos expansions. Therein, the non-conformity scores are normalized with an auxiliary polynomial chaos expansion trained on the log-transformed leave-one-out residuals of the base model. We show that the coverage guarantee of jackknife+ conformal prediction carries over to the adaptive intervals if the leave-one-out auxiliary models are trained on nested leave-one-out residuals. For fixed-basis polynomial chaos expansions fitted by ordinary least squares, all required quantities are derived in closed form and the guarantee-preserving adaptive intervals are obtained from a single model fit, without any model retraining. For sparse polynomial chaos expansions, where multiple model fits are necessary, we propose a heuristic simplification that limits the computational overhead of adaptivity at the cost of the formal coverage guarantee. Numerical experiments on an academic benchmark with known heteroscedastic noise and on an engineering simulation dataset show that the suggested method attains the target coverage while providing intervals that adapt to local prediction uncertainty, therefore being considerably more statistically efficient. These advantages are particularly prominent in high-uncertainty regions of the input space, where the performance of non-adaptive methods degrades substantially.

stat.CO · cs.CE · stat.ME · stat.ML

新论文 · v1arXiv:2611.09543

Marginal-Nonuniform Multiclass Learning

Nataly Brukhim, Steve Hanneke, Amirreza Shaeiri, Maximilian Thiessen

原文摘要

We study the problem of multiclass classification within the framework of marginal-nonuniform learning, where the constants in the learning rate may depend on the unknown marginal distribution generating the unlabeled data, but not on the target concept. This notion naturally lies between classical PAC learning, where the constants are independent of both the marginal distribution and the target concept, and more recent universal learning, where the constants may depend on both. We give a complete characterization of the optimal marginal-nonuniform learning rates, establishing a fundamental trichotomy: exponential, linear, and arbitrarily slow rates. This characterization is witnessed by a new combinatorial dimension, termed the uncentered DS-eluder dimension. A key ingredient in the upper-bound proofs is a set of new distributional exhaustion lemmas that exploit the sequential nature of this dimension and may be of independent interest.

cs.LG · stat.ML

版本更新 · v3arXiv:2605.19823

Smooth Piecewise Cutting for Neural Operator to Handle Discontinuities and Sharp Transitions

Ha Dang, Sebastian Schmidt, Juergen Hesser

原文摘要

Neural operators have achieved strong performance in learning solution operators of partial differential equations (PDEs), but their inherently continuous representations struggle to capture discontinuities and sharp transitions. Existing approaches typically approximate such features within continuous function spaces, often requiring increased model capacity and high-resolution data. In this work, we propose Cut-DeepONet, a two-stage training framework that explicitly models discontinuities while reducing learning complexity. Our approach reformulates the problem via a lifting strategy, partitioning the domain into smooth subregions while representing discontinuities as boundaries in a higher-dimensional space. This separation aligns the operator learning task with the inductive bias of neural networks and avoids directly approximating discontinuities. An additional network predicts input-dependent discontinuity locations for unseen inputs, which are then used to guide the neural operator in generating smooth components within each region. Experiments on benchmark PDEs show that Cut-DeepONet outperforms state-of-the-art methods, even when trained on low-resolution datasets. The method excels on problems with discontinuities and sharp transitions, while using fewer trainable parameters. Our results highlight the benefits of changing the representation of operator learning rather than increasing model complexity.

cs.LG · cs.AI · math.AP · math.DS · stat.ML

版本更新 · v3arXiv:2601.06262

Matrix Factorization Framework for Community Detection under the Degree-Corrected Block Model

Alexandra Dache, Arnaud Vandaele, Nicolas Gillis

原文摘要

Community detection is a fundamental task in data analysis, and block models provide an approach for identifying diverse community structures. The degree-corrected block model (DCBM) is an established model that captures node degree heterogeneity. However, inference methods are computationally costly and sensitive to initialization, while cheaper alternatives, such as spectral or modularity-based approaches, may be less effective at recovering certain non-assortative structures. In this work, we show that DCBM inference can be reformulated as a constrained nonnegative matrix trifactorization problem. Leveraging this insight, we propose a scalable community detection method with a theoretically grounded initialization providing an initial partition for inference algorithms. Our approach is agnostic to network structure and applies to any graph representable by a DCBM. Experiments on synthetic and real-world benchmark networks show that our method achieves community recovery comparable to, and sometimes better than, that achieved by the DCBM inference methods, while being faster: it processes a graph with 100,000 nodes and 500,000 edges in about 30 seconds. Moreover, the initialization significantly improves solution quality. Overall, this work provides a scalable and robust framework for community detection and highlights the benefits of a matrix-factorization perspective for the DCBM.

cs.SI · math.OC · stat.ML

版本更新 · v5arXiv:2510.23254

Optimal In-context Adaptivity and Distributional Robustness of Transformers

Tianyi Ma, Tengyao Wang, Richard J. Samworth

原文摘要

We study in-context learning problems where a Transformer is pretrained on tasks drawn from a mixture distribution $π=\sum_{α\in\mathcal{A}} λ_α π_α$, called the pretraining prior, in which each mixture component $π_α$ is a distribution on tasks of a specific difficulty level indexed by $α$. Our goal is to understand the performance of the pretrained Transformer when evaluated on a different test distribution $μ$, consisting of tasks of fixed difficulty $β\in\mathcal{A}$, and with potential distribution shift relative to $π_β$, subject to the chi-squared divergence $χ^2(μ,π_β)$ being at most $κ$. In particular, we consider nonparametric regression problems with random smoothness, and multi-index models with both random smoothness and random effective dimension. We prove that a large Transformer pretrained on sufficient data achieves the optimal rate of convergence corresponding to the difficulty level $β$, uniformly over test distributions $μ$ in the chi-squared divergence ball. Thus, the pretrained Transformer is able to achieve faster rates of convergence on easier tasks and is robust to distribution shift at test time. Finally, we prove that even if an estimator had access to the test distribution $μ$, the convergence rate of its expected risk over $μ$ could not be faster than that of our pretrained Transformers, thereby providing a more appropriate optimality guarantee than minimax lower bounds.

stat.ML · cs.LG · math.ST