跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+0新增论文
+0其中 AI 相关
+2已有论文修订
+100新增 AI 导读

arXiv 最近完成扫描：2026-11-15 01:33 · 全站最近入库：2026-11-14 15:09各信源进度 →

统计口径与数据新鲜度

统计 2026-11-14 01:53 — 2026-11-15 01:53（北京时间） · 点击数字查看对应简报；AI 相关包含在新增论文内。

最近完成检查：2026-11-15 01:33最近发现新增版本：2026-11-14 15:09库内论文最新更新时间：2026-11-13 02:59

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

23,348 已收录论文19,580 AI 相关6,729 有修订112 HF 社区发现

浏览论文库

研究日报 / 周报 →按信源浏览 →

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

找到 131 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-15 01:32（北京时间）
新论文 · v1arXiv:2611.05195

Ensembles of Random Partition-Based Models under Covariate Shift

Mary Versa Clemens-Sewall, Eliza O'Reilly

原文摘要

Distribution shifts, including covariate shifts, are ubiquitous in real-world applications of machine learning. Empirical evidence suggests that, across a variety of models with and without downstream adaptation, ensembles tend to be more robust to covariate shift than single models. We extend the theory of covariate shift severity from single models to ensembles, providing theoretical justification for the empirical trends. We introduce new discrepancy measures of covariate shift severity to control the risk of partition-based kernel estimators. We then show that with sufficient ensemble size, these models can achieve minimax-optimal risk convergence rates under covariate shift. Our results suggest that modelers can expect to need larger ensemble sizes for more severe covariate shifts.

cs.LG · math.ST

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2605.08505

Scaling Limits of Long-Context Transformers

Giuseppe Bruno, Shi Chen, Zhengjiang Lin, Yury Polyanskiy, Philippe Rigollet

原文摘要

We study the long-context limit of softmax self-attention with a fixed query and a random context of $n$ i.i.d. keys on the sphere with the intrinsic dimension of the key distribution held fixed, viewing the inverse temperature $β_n$ as the scaling parameter that decides whether attention degenerates into uniform averaging or collapses onto the single closest key. We show that the critical scale at which selectivity emerges is determined by the local exponent of the distance-to-query distribution near zero rather than by global features of the context, and scales like $β_n^\ast \asymp n^{2/(d-1)}$ for uniform keys on $\mathbb{S}^{d-1}$. Furthermore, we characterize the limiting laws of the ordered attention weights and of the attention output across all regimes of $β_n$: a subcritical regime in which the output reduces to a local average around $q$ with explicit deterministic bias and Gaussian fluctuations; a critical regime in which a finite collection of nearest keys retains macroscopic mass without single-key collapse; and a supercritical regime in which all mass concentrates on the closest key. Of notable interest is the subcritical case with identity value matrix where the attention map approximately implements a backward heat equation.

cs.LG · cs.AI · math.PR · math.ST

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.05114

Beyond Multi-Index Models: Learning Intersections of Degree-2 PTFs

Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma, Lisheng Ren, Trung Tran

原文摘要

We give an algorithm for PAC learning intersections of $k$ degree-2 polynomial threshold functions over $R^d$ under a Gaussian distribution. Our algorithm achieves classification error $ε$ using $d^{O(k)}2^{O_k(\log^3(1/ε))}$ time and samples, improving over the $d^{O(k^2/ε^2)}$ running time of the polynomial regression approach. To our knowledge, our result is the first to obtain a dimension exponent independent of the accuracy parameter, even for $k=2$. We complement our algorithmic result with an SQ lower bound showing that the complexity dependence of $d^{Ω(k)}$ is unavoidable. Lifting the input to polynomial features turns the target into an intersection of $k$ halfspaces. This suggests using the first two labeled moments for subspace recovery. In the lifted space, however, these moments can reveal nothing. Our starting point is a Gaussian comparison theorem showing that, for sufficiently regular defining quadratics, the labeled moments needed for subspace recovery are approximately preserved. To handle arbitrary defining quadratics, we establish a new structural result showing that every direction with significant resampling influence can be detected through degree-$O(k)$ moments. These results yield an initial $d^{O(k)}2^{\mathrm{poly}_k(1/ε)}$-time learner using adaptive restrictions. To improve the exponential dependence on $1/ε$, we develop a two-stage dimension-reduction approach that avoids the costly adaptive partitioning. After identifying a subspace containing all directions with large influence, we use generalized regularity and Gaussian comparison to recover the remaining relevant quadratic features through a new derivative-based moment operator. The recovered features support an intersection close to the target. Combining them with robust hinge-loss minimization gives our quasipolynomial-time learner.

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

查看论文
arXiv ↗PDF ↗
版本更新 · v3arXiv:2603.04172

The Pivotal Information Criterion

Sylvain Sardy, Maxime van Cutsem, Sara van de Geer

原文摘要

The Bayesian and Akaike information criteria aim at finding a good balance between under- and over-fitting. They are extensively used every day by practitioners. Yet we contend they suffer from at least two afflictions: their penalty parameters $λ=\log n$ and $λ=2$ are too small, leading to many false discoveries, and their inherent (best subset) discrete optimization is infeasible in high dimension. We alleviate these issues with the pivotal information criterion: PIC is defined as a continuous optimization problem, and the PIC penalty parameter $λ$ is selected at the detection boundary (under pure noise). PIC's choice of $λ$ is an upper quantile of a statistic that we prove to be (asymptotically) pivotal, provided the loss function is appropriately transformed. As a result, simulations show a phase transition in the probability of exact support recovery with PIC, a phenomenon studied with no noise in compressed sensing. Applied to real data, for similar predictive performances, PIC selects the least complex model among state-of-the-art learners.

math.ST · cs.IT · stat.ME

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2606.08218

How Deep Are Deep GPs, Really? A Sharp Threshold and a Non-Gaussian Limit for Compositional GPs

Mark Kozdoba, Shie Mannor

原文摘要

Compositional priors describe the generic properties of layered functions in deep Bayesian models, where deep neural networks with random weights are a canonical example. In the wide-network limit, the prior is a Gaussian process (GP) with a depth-dependent kernel, and its behaviour as depth grows has been extensively studied through this kernel. Here, we study another case, where each layer itself is a vector valued Gaussian process, and our aim is similarly to understand the limiting behaviour of the prior as depth grows. Previous GP work has established that for the radial basis function (RBF) kernel and a certain range of bandwidths $r$, the prior degenerates in the limit, converging to the set of constant functions, which is not useful as a probabilistic model. In this paper we establish several new results. First, we identify a sharp bandwidth threshold $r_c(d) = Θ(\sqrt{d})$ above which the limit is degenerate, strengthening the earlier bounds. Second, and more importantly, we show that for $r$ below the threshold $r_c(d)$ the prior converges to a limit distribution $π_{\bar{Z}}$. We also prove that these distributions are non-degenerate and non-Gaussian, with non-vanishing dependence between coordinates. In contrast to the previously known degenerate regime, deep Gaussian process priors can therefore admit non-trivial limits. Empirically, we verify the threshold across a range of dimensions $d$, and demonstrate a complex multimodal behaviour of the limit distributions $π_{\bar{Z}}$, a regime that becomes increasingly narrow with $d$ and would be hard to identify without knowing the threshold.

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

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04598

Estimating "Realized" Skewness using Convolutional Neural Network

Haozhe Jiang, Ostap Okhrin, Michael Rockinger

原文摘要

We propose a new estimator of low-frequency skewness (monthly) that exploits high-frequency data (5 min) through a direct functional mapping consisting of layers of Convolutional Neural Networks followed by Multi Layer Perceptrons. Monte Carlo experiments involving stochastic volatility models, with and without jumps, show that the estimator reduces finite-sample bias relative to existing realized-skewness estimators and remains accurate under model misspecification. Empirically, our estimator exhibits temporal stability and delivers cross-sectional performance in actual skewness-sorted portfolios. We characterize the finite-sample bias of conventional plug-in skewness estimators and establish risk consistency properties of the proposed NN estimator under standard regularity conditions.

math.ST · cs.LG

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2505.21039

Scalable and adaptive prediction bands with kernel sum-of-squares

Louis Allain, S{é}bastien da Veiga, Brian Staber

原文摘要

Conformal Prediction (CP) is a popular framework for constructing prediction bands with valid coverage in finite samples, while being free of any distributional assumption. A well-known limitation of conformal prediction is the lack of adaptivity, although several works introduced practically efficient alternate procedures. In this work, we build upon recent ideas that rely on recasting the CP problem as a statistical learning problem, directly targeting coverage and adaptivity. This statistical learning problem is based on reproducible kernel Hilbert spaces (RKHS) and kernel sum-of-squares (SoS) methods. First, we extend previous results with a general representer theorem and exhibit the dual formulation of the learning problem. Crucially, such dual formulation can be solved efficiently by accelerated gradient methods with several hundreds or thousands of samples, unlike previous strategies based on off-the-shelf semidefinite programming algorithms. Second, we introduce a new hyperparameter tuning strategy tailored specifically to target adaptivity through bounds on test-conditional coverage. This strategy, based on the Hilbert-Schmidt Independence Criterion (HSIC), is introduced here to tune kernel lengthscales in our framework, but has broader applicability since it could be used in any CP algorithm where the score function is learned. Finally, extensive experiments are conducted to show how our method compares to related work. All figures can be reproduced with the accompanying code at \href{https://www.gitlab.com/drti/ksos-bands}{gitlab.com/drti/ksos-bands}.

cs.LG · math.ST

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04450

A Bayesian-Geometric Reading of Classical Model-Based Optimal Design

Mohamed Tarek

原文摘要

The classical model-based optimal design criteria (D-, T-, L-, C-, and A-optimality) are usually motivated via the Cramér--Rao bound as optimizing scalar functions of the Fisher information matrix (FIM). This paper offers a complementary reading in which each criterion appears asymptotically as $N \to \infty$ as the leading-order term of an expected dissimilarity between prior and posterior, with the FIM entering through the Bernstein--von Mises limit. The Kullback--Leibler (KL) divergence of the posterior relative to the prior recovers D-optimality (classically known); a reverse KL of the prior relative to the posterior recovers T-optimality (here defined as maximization of the trace of the FIM, following one common convention) and its weighted-trace generalization; and a first-order approximation of the squared 2-Wasserstein distance recovers L-, C- and A-optimality. The five criteria emerge as instances of a common Bayesian-geometric template, indexed by three choices: the dissimilarity, the prior parametrization, and the approximation scheme used to evaluate it (e.g.\ Taylor expansions of the matrix square root). For the weighted criteria, the Gaussian prior covariance encodes the criterion's weight matrix, so any choice of weights corresponds to a specific prior in the family. The T-, L-, C-, and A-optimality derivations appear novel to the best of my knowledge. A sixth criterion, E-optimality, is recovered not as an independent expected-dissimilarity limit but as a min-max robustification of C-optimality against uncertainty in the modeler's prior direction. The framework is extended to distinguish between a designer's prior over unknown parameters at design time and a modeler's prior used for posterior inference, recovering the classical expected information gain objective as a special case.

math.ST · cs.IT · math.OC · math.PR · stat.ML

查看论文
arXiv ↗PDF ↗
版本更新 · v3arXiv:2510.18410

MAGDrop: Momentum Adaptive Gradient Dropout With Provable Generalization Guarantees

Adeel Safder, Bum Jun Kim

原文摘要

Standard dropout applies a fixed, uniform noise rate to all units, ignoring available gradient information. We propose momentum adaptive gradient dropout (MAGDrop), a Bayesian linear layer that adapts per-unit weight noise by tracking an exponential moving average of gradient magnitudes. Units with large recent gradient magnitudes receive less noise to preserve learned features; units with below-average gradient magnitudes receive more noise to promote exploration. This adaptation transforms the classifier head into a data-dependent Bayesian predictor whose mean predictor has no additional inference cost. Our primary contribution is a certificate-aware low-rank posterior, MAGDrop-Subspace, that addresses the tension between strong accuracy and tight bounds from probably approximately correct (PAC)-Bayes theory. A full-head stochastic posterior incurs a Kullback--Leibler (KL) divergence of approximately 8,625 nats. By confining the posterior to an $r$-dimensional subspace constructed from an independent prior-construction sample $S_0$ and certifying on an independent sample $S$ with $S_0\perp S$, MAGDrop-Subspace reduces KL by approximately a factor of 800 while keeping accuracy close to the baseline. On CIFAR-10 with a 13-layer convolutional neural network and $r=50$, MAGDrop-Subspace achieves a PAC-Bayes Gibbs-risk bound of 0.1882 at 90\% confidence using binary KL inversion, compared with 0.4439 for the full-head baseline. Mean-predictor accuracy is 82.31\%, compared with 83.74\% for the baseline. Complementary accuracy experiments on ImageNet-1K show that MAGDrop reaches top-1 accuracy similar to the strong baseline: 78.57\% compared with 78.51\% on the base Vision Transformer with $16\times16$ patches, and 82.14\% compared with 82.23\% on ConvNeXt-Base.

cs.LG · math.ST

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04157

Nonparametric GARCH: An Iterated Neural Estimator

Ruizhi Deng, Guohao Shen, Ngai Hang Chan

原文摘要

We study nonparametric estimation and forecasting for GARCH-type processes and propose an iterated neural estimator that alternates between estimating the recursion map and updating the unobserved conditional variances. Under mild conditions, we establish finite-sample bounds for the time-averaged in-sample variance-path error and show that the estimator is minimax rate-optimal up to logarithmic factors. Under stationarity and mixing conditions, we establish the same rate for recursion-map estimation and derive finite-sample bounds for out-of-sample variance forecasts and expected excess Gaussian quasi-likelihood (QLIKE) loss. The convergence rates depend on the true lag orders and remain unchanged when the fitted orders are overspecified. Simulation studies illustrate the effectiveness of our estimators under nonlinear and time-varying volatility dynamics. Real-data applications suggest that our neural methods perform competitively and can incorporate option-price and high-frequency information.

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

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04062

StreamLTT: Risk Certification for Policy Selection under Stream Dependence

Jinwen Xu, Qin Lu

原文摘要

Learn-then-Test (LTT) provides a general framework for certifying deployment policies against a prescribed risk target, but its standard formulation targets a fixed population risk estimated from calibration losses. In sequential deployment, losses may instead be dependent and nonstationary, so the risk of a fixed policy can evolve with the observed history. We introduce StreamLTT, which replaces this fixed population risk with average predictable risk, defined by conditioning each decision's loss on the information available before its outcome is revealed. Conditional centering turns empirical deviations from this target into a martingale sum, enabling both a test that adapts to predictable variance and a finite-sample Hoeffding alternative. Combined with family-wise error rate control, StreamLTT yields a simultaneously certified policy region that supports subsequent deployment selection. Across seven forecasting datasets and seven deployment risks, StreamLTT places the certified frontier substantially closer to the prescribed risk target than IID, robust-variance, block-bootstrap, and concentration-based alternatives, while empirical family-wise error closely follows the prescribed level. A finite-sample ablation further shows that the predictable-risk formulation drives the tighter risk frontier, while adaptation to predictable variance makes more effective use of the available family-wise error budget. StreamLTT therefore extends risk-certified policy selection to dependent deployment streams by addressing both what risk should be certified and how it should be tested.

cs.LG · math.ST · stat.ML

查看论文
arXiv ↗PDF ↗
版本更新 · v4arXiv:2603.26029

Statistical and Computational Limits for Cumulant Tensor Inference: A Regime in Which Efficient Detection Is Harder Than Efficient Estimation

Runshi Tang, Yuefeng Han, Anru R. Zhang

原文摘要

We study estimation and detection of high-order cumulant tensors from $n$ i.i.d. observations of a $p$-dimensional random vector, with performance measured in the tensor spectral norm. Under sub-Gaussianity, we show that the minimax rate for estimating the order-$d$ cumulant tensor is $\sqrt{p/n}\wedge 1$. In contrast to covariance estimation, the natural plug-in estimator obtained by replacing population moments in the moment--cumulant formula with sample moments, which we call the sample cumulant tensor, is generally not rate-optimal for $d\ge 3$, and we construct an estimator that attains the minimax rate. On the computational side, we study testing whether the $d$-th order cumulant tensor vanishes after whitening. We provide evidence, under a model-specific low-degree conjecture, that detection is computationally hard when $n\ll p^{d/2}$. At the same time, we identify a regime in which an efficiently computable estimator achieves error smaller than the separation at which polynomial-time tests can reliably distinguish the null from the alternative under the same conjecture. This reveals an unusual reverse detection--estimation gap: computationally efficient detection can be harder than computationally efficient estimation. The underlying reason is that the relevant loss, tensor spectral norm, is itself NP-hard to compute, creating a new form of computational--statistical gap.

math.ST · cs.CC

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.03552

Nonparametric Intensity Estimation for Covariate-Driven Poisson Processes Using Deep Learning

Atsutomo Yara, Yoshikazu Terada

原文摘要

We consider nonparametric maximum likelihood estimation of the intensity function of a Poisson process, allowing the intensity to depend on observed covariates. Such models describe how event rates vary with external conditions, including conditions under which the intensity becomes arbitrarily small or vanishes. However, risk analysis based on the Kullback-Leibler (KL) divergence typically requires the true intensity to be bounded away from zero, a restrictive assumption in applications. We develop a unified approach that avoids this assumption and derive an oracle inequality for the covariate-averaged Hellinger distance between the true intensity and the nonparametric maximum likelihood estimator (NPMLE). As an application of the oracle inequality, we establish convergence rates for NPMLEs based on deep neural networks (DNNs). Our results show that, as in nonparametric regression, the ability of DNNs to capture underlying structure leads to improved convergence rates. Specifically, DNN-based NPMLEs mitigate the curse of dimensionality when the true intensity has a compositional structure and automatically adapt to a low-dimensional Riemannian manifold structure of the event space. For intensity functions with a compositional structure, DNN-based NPMLEs achieve nearly minimax-optimal convergence rates without explicitly incorporating this structure into the network architecture. Simulations demonstrate that DNN-based estimators outperform kernel estimators in most settings, while manifold kernels remain competitive in some designs. Finally, we analyze stimulus-evoked neural spiking using data from the Allen Brain Observatory Visual Coding Neuropixels project. DNN-based NPMLEs provide better out-of-sample performance than a conditional kernel estimator, as evaluated by held-out log-likelihood.

math.ST · cs.LG

查看论文
arXiv ↗PDF ↗
版本更新 · v3arXiv:2601.06514

Inference-Time Alignment for Diffusion Models via Variationally Stable Doob's Matching

Jinyuan Chang, Chenguang Duan, Yuling Jiao, Ruoxuan Li, Yi Xu, Jerry Zhijian Yang

原文摘要

Inference-time alignment for diffusion models aims to adapt a pre-trained reference diffusion model toward a target distribution without retraining the reference score network, thereby preserving the generative capacity of the reference model while enforcing desired properties at inference time. A central mechanism for achieving such alignment is guidance, which modifies the sampling dynamics through an additional drift term. In this work, we introduce variationally stable Doob's matching, a novel framework for provable guidance estimation grounded in Doob's $h$-transform. Our approach formulates guidance as the gradient of the logarithm of an underlying Doob's $h$-function and employs gradient-regularized regression to simultaneously estimate both the $h$-function and its gradient, resulting in a consistent estimator of the guidance. Theoretically, we establish non-asymptotic convergence rates for the estimated guidance. Moreover, we analyze the resulting controllable diffusion processes and prove non-asymptotic convergence guarantees for the generated distributions in the Wasserstein-2 distance. Finally, we show that variationally stable guidance estimators are adaptive to unknown low dimensionality, effectively mitigating the curse of dimensionality under low-dimensional linear subspace assumptions. Numerical experiments demonstrate the effectiveness of our proposed method and show the advantages compared to the baselines.

stat.ML · cs.LG · math.NA · math.OC · math.ST

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.03442

Subpolynomial-Query Proximal Sampling Beyond Log-Concavity

Wei Guo, Bo Yuan, Ye He, Jiaming Liang, Molei Tao, Yongxin Chen

原文摘要

We study the gradient query complexity of sampling from a density $π(x)\propto\mathrm{e}^{-V(x)}$ on $\mathbb{R}^d$, where $V$ has a $β$-Lipschitz gradient but need not be convex. Our approach uses the proximal sampler, which alternates Gaussian perturbation with sampling a position conditional on the noisy observation. We implement its observation chain using the high-order noisy conditional sampler of [OpenAI 2026], obtaining improved dimension dependence under functional inequalities. If $π$ satisfies a log-Sobolev inequality (LSI) with constant $α$, then for every fixed $ν>0$, there is a finite constant $C_ν$ depending only on $ν$ such that the algorithm returns a sample within total-variation distance $\varepsilon$ using at most $C_νκ(d+κ+\varepsilon^{-1}+\|\nabla V(x_0)\|^2/β)^ν$ queries, where $κ=β/α$ and $x_0$ is an arbitrary reference point for initialization. The analysis controls center-dependent local errors along exact proximal histories and removes the final observation noise by conditional decoding. Under a Poincaré inequality (PI), we obtain a corresponding guarantee from a warm start with a known bound on its Rényi divergence. An oracle lower bound shows that a stationary point alone, which suffices under LSI, is insufficient under PI.

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

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.03305

Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity

Jiuyao Lu, Georgy Noarov, Aaron Roth

原文摘要

Calibrated multiaccuracy asks that a predictor be globally calibrated and multiaccurate with respect to a bounded test family $G$; that is, its residuals should be uncorrelated with every test $g(x)\in G$. This weakening of multicalibration suffices for many applications. Its sample complexity was not known to improve on that of full multicalibration, which is $\widetildeΘ\left(\frac{\log|G|}{\varepsilon^2} + \frac{1}{\varepsilon^{3}}\right)$ when $|G|$ is at least a sufficiently large power of $\log(1/\varepsilon)$. We resolve the sample complexity of $\varepsilon$-calibrated multiaccuracy, showing that it scales as $$ \widetildeΘ\left(\frac{\log|G|}{\varepsilon^2} + \frac{1}{\varepsilon^{5/2}}\right), $$ separating it from the complexity of multicalibration. The upper bound is obtained by an algorithm that outputs a randomized predictor. For deterministic predictors, we establish the tight rate $$ \widetildeΘ\left( \frac{\log|G|}{\varepsilon^2} + \frac{(\log|G|)^{1/3}}{\varepsilon^{8/3}} \right) $$ whenever $\log|G|=Ω(\log(1/\varepsilon))$. When $\log|G|\le\varepsilon^{-1+κ}$ for any fixed $κ\in(0,1)$, this rate is polynomially larger than the rate for randomized predictors. Thus, unlike for multicalibration, calibrated multiaccuracy exhibits a genuine sample-complexity separation between deterministic and randomized predictors. The matching upper and lower bounds show that the unusual cube-root dependence on $\log|G|$ is intrinsic. At $\log|G|\asymp\varepsilon^{-1}$, the minimax rates for randomized and deterministic calibrated multiaccuracy both coincide with the minimax rate for multicalibration.

cs.LG · cs.DS · math.ST

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.02808

Sketching in Regression: Sketchy in Practice?

Somarddha Das, Soupayan Das Gupta, Koustav Goswami

原文摘要

The Johnson-Lindenstrauss (JL) lemma and its extensions provide tools for solving the $L_2$ regression problem in high-dimensional settings with $n>d$, by transforming a subspace of $\mathbb{R}^{n}$ to a subspace of $\mathbb{R}^{m}$, (where $m<n$) while approximately preserving the norms of elements of the subspace. In this paper, we study the theoretical guarantees made by various JL-based subspace embeddings critically and concretely to gauge their practical applicability. We derive concrete versions of results on subspace embeddings in the literature to establish lower bounds on the reduced dimension as well as to concretely analyze the complexity of the Fast JL, OSNAP Transforms among other embeddings. These analyses suggest that guaranteeing substantial computational savings while maintaining the accuracy of the sketched solution requires data dimensions larger than those typically encountered in practice. We also see that, for practically necessary accuracy requirements or for sparsity requirements for computational gain, existing theoretical guarantees lead to substantially large reduced dimensions. This leads to very stringent data requirements for establishing guarantees of any kind.

cs.DS · math.ST · stat.CO

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2610.33610

On the Error Analysis of Triangular Transport Maps for Conditional Generation via MMD-based Objectives

Michele Martino, Bamdad Hosseini, Amir Sagiv, Amirhossein Taghvaei

原文摘要

Conditional generative models parameterized by triangular transport maps are widely used for conditional sampling, yet theoretical guarantees on the quality of the conditional measures they produce remain scarce. We address this question for minimum divergence estimators of triangular maps. We use MMD-based objectives as a tractable setting in which the gap between joint and conditional errors can be analyzed precisely, and we measure performance through the average conditional estimation error, defined as the squared maximum mean discrepancy (MMD) between the estimated and the true conditionals, averaged over the conditioning variable. We first show that the common practice of minimizing a joint MMD may fail to recover the conditionals: writing the joint and the conditional criteria as quadratic energies of the same conditional mean embedding residual, we prove that, for parametric classes, joint minimizers are generically inconsistent in the misspecified setting. We then analyze an estimator that directly minimizes the conditional criterion through a surrogate loss computable from joint target samples and reference samples. We prove a non-asymptotic error bound that decomposes the average conditional estimation error into approximation, estimation, and reference sampling errors, with fast rates independent of the ambient dimension in the parametric setting. Finally, for joint MMDs built from concentrating Gaussian kernels on the conditioning variable, we show that the joint criterion approximates a density-reweighted version of the conditional one, and we derive an error bound for the joint minimizer whose rate suffers from a curse of dimensionality in the conditioning variable. Our results suggest that training criteria for conditional generative models should target the conditional rather than the joint error, a principle that extends to other divergences and to dynamic transport.

stat.ML · cs.LG · math.ST

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2609.04822

Minimax Rate for Diffusion-Guided Local Intrinsic Dimension Estimation based on Fokker-Planck Equation

Jaehee Seo, Wontae Jeong, Jisu Kim

原文摘要

Diffusion-guided methods have recently emerged as effective tools for probing the intrinsic geometry of high-dimensional data. Understanding their accuracy requires quantifying both (i) finite-scale approximation error relative to the true local intrinsic dimension (LID) and (ii) estimation error from finite samples. We address these two questions for the FLIPD field (Kamkari et al., 2024; arXiv:2406.03537), defined at the population level through the logarithmic scale derivative of a Gaussian-smoothed density and admitting a Fokker--Planck representation. For $α$-smooth densities on a regular $d$-dimensional manifold, we establish a uniform $O(σ^2)$ approximation bound relative to the manifold dimension $d$. Under expected integrated squared loss, we prove a minimax lower bound of order $(nσ^d)^{-1}$ for estimating the FLIPD field from $n$ observations when $n^{-1/(2α+d)}\leσ\leσ_0$. A plug-in FLIPD estimator based on the empirical denoising score matching (DSM) solution attains a matching upper bound. Thus the minimax rate is of order $(nσ^d)^{-1}$ and it becomes $n^{-2α/(2α+d)}$ at its smallest scale.

stat.ML · cs.LG · math.ST

查看论文
arXiv ↗PDF ↗
版本更新 · v4arXiv:2501.14974

Private Minimum Hellinger Distance Estimation via Hellinger Distance Differential Privacy

Fengnan Deng, Anand N. Vidyashankar

原文摘要

Objective functions based on Hellinger distance yield robust and efficient estimators of model parameters. Motivated by privacy and regulatory requirements encountered in contemporary applications, we derive in this paper \emph{private minimum Hellinger distance estimators}. The estimators satisfy a new privacy constraint, namely, Hellinger differential privacy, while retaining the robustness and efficiency properties. We demonstrate that Hellinger differential privacy shares several features of standard differential privacy while allowing for sharper inference. Additionally, for computational purposes, we also develop Hellinger differentially private gradient descent and Newton-Raphson algorithms. We illustrate the behavior of our estimators in finite samples using numerical experiments and verify that they retain robustness properties under gross-error contamination.

math.ST · cs.CR · math.PR · stat.ME · stat.ML

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.02281

Near-Quadratic Error-Free Graph Matching above Otter's Threshold via Approximate Local Tree Correlation Testing

Jiale Cheng, Ziao Wang, Lei Ying

原文摘要

This paper presents a near-quadratic-time algorithm that correctly matches almost all nodes of two correlated Erdős-Rényi graphs without any incorrect matches. Each graph has average degree $λ$ and its edges are subsampled from a common parent Erdős-Rényi graph with $n$ nodes, with subsampling probability $s$. The nodes of one graph are then relabeled by an unknown permutation. The algorithm is built on a test for correlated versus independent Galton-Watson trees with approximated likelihood ratios. For every constant $s>\sqrt{C_{\mathrm{Otter}}}$, where $C_{\mathrm{Otter}}\approx0.338$ is Otter's tree-counting constant, and every $λ=ω(1)$ with $λ=(\log n)^{O(1)}$, the algorithm outputs a partial matching of size $n-o(n)$ that contains no incorrect matches with high probability. If, in addition, $λs\ge(1+ε)\log n$ for a constant $ε>0$, a seeded completion step recovers the permutation exactly. In both cases, the time complexity of the algorithm is $n^{2+o(1)}$ with high probability, whereas previous polynomial-time algorithms with the same guarantees either have a time-complexity bound whose exponent goes to $\infty$ as $s$ approaches $\sqrt{C_{\mathrm{Otter}}}$ from above, or apply only when $s$ is close to $1$.

cs.DS · math.ST · stat.ML

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.02255

Multiclass Classification with Rare Useful Features: Fundamental Limits and the Optimality of Diversity Pursuit Higher Criticism Thresholding

Gabriel Moryoussef, Alon Kipnis

原文摘要

We consider classification in high-dimensional feature spaces where only a vanishing fraction of features are useful and the number of classes may be large. While this rare-and-weak useful-feature regime is well understood in the binary setting, its multiclass version raises new questions: a feature can be useful for class discrimination without separating any specific pair of classes. We focus on a rare feature diversity model, in which most features are useless, but a small fraction promote discrimination among classes in a way that can be detected by a per-feature diversity test, such as one-way ANOVA or the Kruskal-Wallis test. For this setting, we propose Diversity Pursuit Higher Criticism Thresholding (DP-HCT), a feature-screening procedure that applies a higher-criticism threshold to the collection of p-values obtained from per-feature diversity tests. We justify DP-HCT under a Gaussian multiclass Rare-and-Weak Useful Feature model with class-mean contrasts of fixed magnitude in random directions, extending the binary model of Donoho and Jin (2008). When the number of classes is fixed, our model recovers the binary phase transition. When the number of classes grows logarithmically with the number of features, however, we derive a new and strictly harder phase transition, driven by the growing degrees of freedom and their effect on the useful-feature tail rate. We show that whenever classification beyond chance is possible, DP-HCT with ANOVA, followed by a simple classifier based on similarity to class means, achieves asymptotically perfect accuracy. Experiments on real multiclass classification benchmarks demonstrate substantial improvements, and numerical simulations confirm that the derived phase-transition curve accurately predicts the finite-sample behavior of DP-HCT in the growing-class regime.

stat.ML · cs.LG · math.ST

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.02055

Rare Event Constrained Reinforcement Learning with Large Deviations

Rahul Misra

原文摘要

We study finite-horizon reinforcement learning with a safety constraint on the probability of reaching a failure set. In contrast to the well-studied safe reinforcement learning literature, we consider problems where the probability of reaching the failure set is vanishingly small, but the consequences of reaching the failure set are catastrophic. Direct simulation and estimation of the optimal policy is naturally ineffective when the failure probability is extremely small. Moreover, on a real system the controller can only choose actions, and this is not enough to make failures frequent. In contrast to the rare event simulation literature, our goal is not to estimate the probability of the rare event occurrence, but to upper bound it such that the failure constraint is satisfied. Thus, instead of sampling failures, we use the large deviations principle. We define a damage variable that on exceeding a certain threshold indicates failure. We study the cumulant generating function (CGF) as its positive root provides an upper bound on the failure probability via Cramer's theorem. We extend this approach to Markov decision processes with hitting times through state-action CGFs, and give finite-horizon and state-dependent versions of the bound. The state-action CGFs do not depend on the policy and can be estimated from regular transitions, so the bound can be checked for any policy a priori. This gives a policy improvement algorithm in which every policy satisfies the failure constraint with high probability.

stat.ML · cs.LG · eess.SY · math.OC · math.PR · math.ST

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2607.26065

Kernel Ridge Regression over Hölder Classes: Function and Derivative Losses

Yuxuan Hou, Yicheng Li

原文摘要

We study ordinary kernel ridge regression over full Hölder-Zygmund balls, measuring errors in Sobolev norms and in pointwise and uniform losses for mixed derivatives. For targets of smoothness $s$, every RKHS norm equivalent to $H^{s+d/2}$ gives the optimal $H^r$ risk for $0\le r<s$; integer choices of $r$ include integrated squared derivative losses. Pointwise and uniform guarantees require additional kernel structure. A localized wavelet kernel attains the sharp derivative rates with the same regularization orders as for function estimation, whereas equivalent changes of the RKHS norm can destroy the population bias rates. For the ordinary Gaussian kernel with a shrinking bandwidth, we prove a uniform derivative risk bound with the optimal polynomial rate and an explicit, unoptimized logarithmic factor. The results allow bounded measurable design densities bounded away from zero and conditionally sub-Gaussian noise.

stat.ML · cs.LG · math.ST

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.01903

Federated Estimation of Loading Spaces in Tensor Factor Models under Differential Privacy

Zetai Cen, Fan Wang, Haeran Cho

原文摘要

Tensor factor models provide low-dimensional representations of tensor-valued observations while preserving their multiway structure. When these observations are held by different clients, privacy constraints may prevent them from being pooled for centralized analysis. We study estimation of common loading spaces in Tucker tensor factor models under federated differential privacy, allowing heterogeneous sample sizes, privacy budgets, and factor strengths. The proposed method combines private stability testing, Huber aggregation, and Gaussian perturbation at each client with weighted aggregation at the server. We establish non-asymptotic upper bounds governed by a scaled harmonic mean of the squared local error rates, and prove minimax optimality up to logarithmic factors under strong factors, fixed factor ranks, and fixed noise variance. We further develop a private calibration procedure that selects the local tuning parameters and aggregation weights without knowledge of the noise level or client-specific factor strengths. The resulting adaptive estimator preserves the privacy guarantee and attains the error rate obtained with oracle tuning. We illustrate the finite-sample performance of the proposed estimators through simulation experiments and an application to a Meditation Traits EEG dataset.

math.ST · cs.IT · stat.ML

查看论文
arXiv ↗PDF ↗
版本更新 · v4arXiv:2601.15500

Low-Dimensional Adaptation of Rectified Flow: A Diffusion and Stochastic Localization Perspective

Saptarshi Roy, Alessandro Rinaldo, Purnamrita Sarkar

原文摘要

In recent years, Rectified flow (RF) has gained considerable popularity largely due to its generation efficiency and state-of-the-art performance. In this paper, we investigate how well RF automatically adapts to the intrinsic low dimensionality of the support of the target distribution to accelerate sampling. We show that, using a carefully designed \blue{end-point adapted} time-discretization scheme and with sufficiently accurate drift estimates, the RF sampler enjoys an iteration complexity of order $O(k/\varepsilon)$ (up to log factors), where $\varepsilon$ is the precision in total variation distance and $k$ is the intrinsic dimension of the target distribution. In addition, we show that the denoising diffusion probabilistic model (DDPM) procedure is equivalent to a stochastic version of RF by establishing a novel connection between these processes and stochastic localization. Building on this connection, we further design a stochastic RF sampler that also adapts to the low-dimensionality of the target distribution under mild requirements on the accuracy of the drift estimates, and also with a specific time schedule. We illustrate the efficacy of newly designed time-discretization schedules with simulations on the synthetic data and text-to-image (T2I) data experiments.

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

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.01828

Instance-Specific Sharp Convergence Rate of the Add-$λ$ Estimator via Feature Space Decomposition

Zong Shang

原文摘要

Using the Feature Space Decomposition framework, we establish non-asymptotic matching upper and lower bounds for the expected Kullback-Leibler estimation error of the Add-$λ$ estimator of a discrete probability distribution, for any signal, any dimension, any sample size, and any $λ>0$.

cs.IT · math.ST

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.01300

Accelerating posterior sampling in Bayesian inverse problems with diffusion models: an online-offline perspective

Duc-Lam Duong

原文摘要

Bayesian inverse problems require both informative prior models and computationally feasible posterior inference. Score-based diffusion models provide expressive learned priors, but their use for inversion introduces a conditioning problem: the score of a noised posterior is generally unavailable from a prior score alone. This selective survey reviews the principal approaches to that problem, including likelihood guidance, spectral and projection methods, sequential Monte Carlo corrections, and amortized conditional training. We organize methods by how they split cost between offline preparation and online inference, and compare their assumptions, advantages and limitations, with emphasis on computational speedups. Some ongoing directions and open questions are gathered at the end.

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

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.01218

Optimal Conversion from Zero-Concentrated to Gaussian Differential Privacy

Yu-Wei Chen, Aaradhya Pandey, Jordan Awan

原文摘要

Gaussian differential privacy (GDP) and zero-concentrated differential privacy (zCDP) are two competing privacy accounting frameworks, but they share similar minimax lower bounds in various estimation problems. Moreover, it is known that a mechanism satisfying $μ$-GDP satisfies $(μ^2/2)$-zCDP, whereas the converse fails to hold at the same calibration. In this paper, we establish the optimal reverse conversion, showing that every $ρ$-zCDP mechanism satisfies $μ_{\mathrm{zCDP}}(ρ)$-GDP, where $μ_{\mathrm{zCDP}}(ρ)=2Φ^{-1}((1+e^{-t_ρ})^{-1})$ and $t_ρ$ uniquely solves the equation $ρ=t_ρ\tanh(t_ρ/2)$. We also obtain simplified bounds $\sqrt{πρ}\leqμ_{\mathrm{zCDP}}(ρ)\leq\sqrt{8ρ}$, with sharp constants, which imply equivalence of the two frameworks up to constants. This explains why their minimax risks agree up to a constant rescaling of the privacy budget. We show that the squared conversion is strictly convex, which implies that converting zCDP to GDP before applying composition or group privacy yields a tighter GDP guarantee than converting afterward. We also derive the sharp conversion from bounded-range and logistic DP mechanisms (e.g., exponential mechanism) to GDP, where converting before composition but after group privacy gives the tighter guarantee.

cs.CR · math.ST

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.01216

Adaptive Optimizers Can Get a Policy Ranking Wrong: Momentum, Dependent Data, and a Two-Run Remedy

Sunyoung An, Xiaoming Huo

原文摘要

Operators choosing among decision rules, such as when a battery charges or where an idle taxi goes, rank them by estimated long-run value. A standard estimator, linear temporal-difference (TD) learning, fits values from one stream of correlated observations. Large fits often use an adaptive optimizer, such as adaptive moment estimation (Adam), with fixed averaging rates. We show that these rates can change what is estimated, not just how fast: the same observations drive the updates and the optimizer's step-size scaling, moving the fit away from the intended TD value. The shift differs across rules, so it need not cancel in a comparison, and more data only makes a wrong ranking look more certain. Our remedy refits the same data at a second averaging rate that halves the effective gain, the number to which the leading shift is proportional. Twice the new fit minus the original removes that shift. In New York taxi and battery models calibrated to real data, common optimizer settings leave the selected rule unchanged but order close rules wrongly and misstate its value. Our remedy corrects nearly every wrong ordering, with one extra fit when the shift is moderate and two when it is larger.

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

查看论文
arXiv ↗PDF ↗