Statistics Theory
Separating Oblivious and Adaptive Models of Variable Selection
Ziyun Chen, Jerry Li, Kevin Tian et al. (+1 more)
Sparse recovery is among the most well-studied problems in learning theory and high-dimensional statistics. In this work, we investigate the statistical and computational landscapes of sparse recovery with $\ell_\infty$ error guarantees. This variant of the problem is motivated by variable selection tasks, where the goal is to estimate the support of a $k$-sparse signal in $\mathbb{R}^d$. Our main contribution is a provable separation between the oblivious (“for each”) and adaptive (“for all”) models of $\ell_\infty$ sparse recovery. We show that under an oblivious model, the optimal $\ell_\infty$ error is attainable in near-linear time with $\approx k\log d$ samples, whereas in an adaptive model, $\gtrsim k^2$ samples are necessary for any
algorithm to achieve this bound. This establishes a surprising contrast with the standard $\ell_2$ setting, where $\approx k \log d$ samples suffice even for adaptive sparse recovery. We conclude with a preliminary examination of a partially-adaptive model, where we show nontrivial variable selection guarantees are possible with $\approx k\log d$ measurements.
Read the full abstract ▾
All authors Ziyun Chen, Jerry Li, Kevin Tian, Yusong Zhu
Statistics Applications · Cross-listed from physics.space-ph
Scattering and sputtering on the lunar surface; Insights from negative ions observed at the surface
Romain Canu-Blot, Martin Wieser, Umberto Rollero et al. (+6 more)
Context. Airless planetary bodies are directly exposed to
solar wind ions, which can scatter or become implanted upon impact with the regolith-covered surface, while also sputtering surface atoms. Aims. We construct a semi-analytical model for the scattering of ions of hundreds of eV and the sputtering of surface atoms, both resulting in the emission of negative ions from the lunar surface. Our model contains a novel description of the scattering process that is physics-based and constrained by observations. Methods. We use data from the Negative Ions at the Lunar Surface (NILS) instrument on the Chang'e-6 lander to update prior knowledge of ion scattering and sputtering from lunar regolith through
Bayesian inference. Results. Our model shows good agreement with the NILS data. A precipitating
solar wind
proton has roughly a 22% chance of scattering from the lunar surface in any charge state, and about an 8% chance of sputtering a surface hydrogen atom. The resulting ratio of scattered to sputtered hydrogen flux is eta_sc / eta_sp = 1.5 for a
proton speed of 300 km/s. We find a high probability (7-20%) that a hydrogen atom leaves the surface negatively charged. The angular emission distributions at near-grazing angles for both scattered and sputtered fluxes are controlled by surface roughness. Our model also indicates significant inelastic energy losses for hydrogen interacting with the regolith, suggesting a longer effective path length than previously assumed. Finally, we estimate a surface binding energy of 5.5 eV, consistent with the observations. Conclusions. Our model describes the scattering and sputtering of particles of any charge state from any homogeneous, multi-species surface. Using NILS data, we successfully applied the model to update our understanding of
solar wind interacting with lunar regolith, and the emission of negative hydrogen ions.
Read the full abstract ▾
All authors Romain Canu-Blot, Martin Wieser, Umberto Rollero, Thomas Maynadié, Stas Barabash, Gabriella Stenberg Wieser, Aibing Zhang, Wenjing Wang, Chi Wang
Statistical Methodology
Generalised Linear Models Driven by Latent Processes: Asymptotic Theory and Applications
Wagner Barreto-Souza and Ngai Hang Chan
This paper introduces a class of generalised linear models (GLMs) driven by latent processes for modelling count, real-valued, binary, and positive continuous time series. Extending earlier latent-process regression frameworks based on Poisson or one-parameter exponential family assumptions, we allow the conditional distribution of the response to belong to a bi-parameter exponential family, with the latent process entering the conditional mean multiplicatively. This formulation substantially broadens the scope of latent-process GLMs, for instance, it naturally accommodates gamma responses for positive continuous data, enables estimation of an unknown dispersion parameter via method of moments, and avoids restrictive conditions on link functions that arise under existing formulations. We establish the asymptotic normality of the GLM
estimators obtained from the GLM likelihood that ignores the latent process, and we derive the correct information
matrix for valid inference. In addition, we provide a principled approach to prediction and
forecasting in GLMs driven by latent processes, a topic not previously addressed in the literature. We present two real data applications on measles infections in North Rhine-Westphalia (Germany) and paleoclimatic glacial varves, which highlight the practical advantages and enhanced flexibility of the proposed modelling framework.
Read the full abstract ▾
Statistics Theory
Optimal training-conditional regret for online conformal prediction
Jiadong Liang, Zhimei Ren and Yuxin Chen
We study online conformal prediction for non-stationary data streams subject to unknown distribution drift. While most prior work studied this problem under
adversarial settings and/or assessed performance in terms of gaps of time-averaged marginal coverage, we instead evaluate performance through training-conditional cumulative regret. We specifically focus on independently generated data with two types of distribution shift: abrupt change points and smooth drift. When non-conformity score functions are pretrained on an independent
dataset, we propose a split-conformal style
algorithm that leverages drift detection to adaptively update calibration sets, which provably achieves minimax-optimal regret. When non-conformity scores are instead trained online, we develop a full-conformal style
algorithm that again incorporates drift detection to handle non-stationarity; this approach relies on stability - rather than permutation
symmetry - of the model-fitting
algorithm, which is often better suited to online learning under evolving environments. We establish non-asymptotic regret guarantees for our online full conformal
algorithm, which match the minimax lower bound under appropriate restrictions on the prediction sets. Numerical experiments corroborate our theoretical findings.
Read the full abstract ▾
Machine Learning (Statistics)
Functional Decomposition and Shapley Interactions for Interpreting Survival Models
Sophie Hanna Langbein, Hubert Baniecki, Fabian Fumagalli et al. (+3 more)
Hazard and survival functions are natural, interpretable targets in time-to-event prediction, but their inherent non-additivity fundamentally limits standard additive explanation methods. We introduce Survival Functional Decomposition (SurvFD), a principled approach for analyzing feature interactions in machine learning survival models. By decomposing higher-order effects into time-dependent and time-independent components, SurvFD offers a previously unrecognized perspective on survival explanations, explicitly characterizing when and why additive explanations fail. Building on this theoretical decomposition, we propose SurvSHAP-IQ, which extends Shapley interactions to time-indexed functions, providing a practical
estimator for higher-order, time-dependent interactions. Together, SurvFD and SurvSHAP-IQ establish an interaction- and time-aware interpretability approach for survival modeling, with broad applicability across time-to-event prediction tasks.
Read the full abstract ▾
All authors Sophie Hanna Langbein, Hubert Baniecki, Fabian Fumagalli, Niklas Koenen, Marvin N. Wright, Julia Herbinger
Statistical Methodology
Factor-Adjusted Multiple Testing for High-Dimensional Individual Mediation Effects
Chen Shi, Zhao Chen and Christina Dan Wang
Identifying individual mediators is a central goal of high-dimensional mediation analysis, yet pervasive dependence among mediators can invalidate standard debiased inference and lead to substantial false discovery rate (FDR) inflation. We propose a Factor-Adjusted Debiased Mediation Testing (FADMT) framework that enables large-scale inference for individual mediation effects with FDR control under complex dependence structures. Our approach posits an approximate factor structure on the unobserved errors of the mediator model, extracts common latent factors, and constructs decorrelated pseudo-mediators for the subsequent inferential procedure. We establish the asymptotic normality of the debiased
estimator and develop a multiple testing procedure with theoretical FDR control under mild high-dimensional conditions. By adjusting for latent factor induced dependence, FADMT also improves robustness to spurious associations driven by shared latent variation in observational studies. Extensive simulations demonstrate the superior finite-sample performance across a wide range of correlation structures. Applications to TCGA-BRCA multi-omics data and to China's stock connect study further illustrate the practical utility of the proposed method.
Read the full abstract ▾
Machine Learning (Statistics)
Learning Preference from Observed Rankings
Yu-Chang Chen, Chen Chian Fuh and Shang En Tsai
Estimating consumer preferences is central to many problems in economics and marketing. This paper develops a flexible framework for learning individual preferences from partial ranking information by interpreting observed rankings as collections of pairwise comparisons with logistic choice probabilities. We model latent utility as the sum of interpretable product attributes, item fixed effects, and a low-rank user-item factor structure, enabling both interpretability and information sharing across consumers and items. We further correct for selection in which comparisons are observed: a comparison is recorded only if both items enter the consumer's consideration set, inducing exposure bias toward frequently encountered items. We model pair observability as the product of item-level observability propensities and estimate these propensities with a logistic model for the marginal probability that an item is observable. Preference parameters are then estimated by maximizing an inverse-probability-weighted (IPW), ridge-regularized log-likelihood that reweights observed comparisons toward a target comparison population. To scale computation, we propose a
stochastic gradient descent (SGD)
algorithm based on inverse-probability resampling, which draws comparisons in proportion to their IPW weights. In an application to transaction data from an online wine retailer, the method improves out-of-sample recommendation performance relative to a popularity-based
benchmark, with particularly strong gains in predicting purchases of previously unconsumed products.
Read the full abstract ▾
Statistics Theory
Estimation of Conformal Metrics
Jérôme Taupin
We study deformations of the geodesic distances on a domain of R N induced by a function called conformal factor. We show that under a positive reach assumption on the domain (not necessarily a submanifold) and mild assumptions on the conformal factor, geodesics for the conformal metric have good regularity properties in the form of a lower bounded reach. This regularity allows for efficient estimation of the conformal metric from a random point cloud with a relative error proportional to the Hausdorff distance between the point cloud and the original domain. We then establish convergence rates of order n^(-1/d) that are close to sharp when the intrinsic dimension d of the domain is large, for an
estimator that can be computed in O(n^2 ) time. Finally, this paper includes a useful equivalence result between ball graphs and nearest-neighbors graphs when assuming Ahlfors regularity of the sampling measure, allowing to transpose results from one setting to another.
Read the full abstract ▾
Statistical Methodology
Focused Relative Risk Information Criterion for Variable Selection in Linear Regression
Nils Lid Hjort
This paper motivates and develops a novel and focused approach to variable selection in linear regression models. For estimating the regression mean $\mu=\E\,(Y\midd x_0)$, for the
covariate vector of a given individual, there is a list of competing
estimators, say $\hatt\mu_S$ for each submodel $S$. Exact expressions are found for the relative mean squared error risks, when compared to the widest model available, say $\mse_S/\mse_\wide$. The theory of confidence distributions is used for accurate assessments of these relative risks. This leads to certain Focused Relative Risk Information Criterion scores, and associated FRIC plots and FRIC tables, as well as to Confidence plots to exhibit the confidence the data give in the submodels. The machinery is extended to handle many focus parameters at the same time, with appropriate averaged FRIC scores. The particular case where all available
covariate vectors have equal importance yields a new overall criterion for variable selection, balancing complexity and fit in a natural fashion. A connection to the Mallows criterion is demonstrated, leading also to natural modifications of the latter. The FRIC and AFRIC strategies are illustrated for real data.
Read the full abstract ▾
Machine Learning (Statistics) · Cross-listed from cs.LG
GICDM: Mitigating Hubness for Reliable Distance-Based Generative Model Evaluation
Nicolas Salvy, Hugues Talbot and Bertrand Thirion
Generative model evaluation commonly relies on high-dimensional
embedding spaces to compute distances between samples. We show that
dataset representations in these spaces are affected by the hubness phenomenon, which distorts nearest-neighbor relationships and biases distance-based metrics. Building on the classical Iterative Contextual Dissimilarity Measure (ICDM), we introduce Generative ICDM (GICDM), a method to correct neighborhood estimation for both real and generated data. We introduce a multi-scale extension to improve empirical behavior. Extensive experiments on synthetic and real
benchmarks demonstrate that GICDM resolves hubness-induced failures, restores reliable metric behavior, and improves
alignment with human assessment.
Read the full abstract ▾
Machine Learning (Statistics) · Cross-listed from cs.LG
Learning with Locally Private Examples by Inverse Weierstrass Private Stochastic Gradient Descent
Jean Dufraiche, Paul Mangold, Michaël Perrot et al. (+1 more)
Releasing data once and for all under noninteractive Local Differential
Privacy (LDP) enables complete data reusability, but the resulting noise may create bias in subsequent analyses. In this work, we leverage the Weierstrass transform to characterize this bias in binary classification. We prove that inverting this transform leads to a bias-correction method to compute unbiased estimates of nonlinear functions on examples released under LDP. We then build a novel
stochastic gradient descent
algorithm called Inverse Weierstrass Private SGD (IWP-SGD). It converges to the true population risk minimizer at a rate of $\mathcal{O}(1/n)$, with $n$ the number of examples. We empirically validate IWP-SGD on binary classification tasks using synthetic and real-world
datasets.
Read the full abstract ▾
All authors Jean Dufraiche, Paul Mangold, Michaël Perrot, Marc Tommasi
Statistics Applications · Cross-listed from econ.EM
Two-way Clustering Robust Variance Estimator in Quantile Regression Models
Ulrich Hounyo and Jiahao Lin
We study inference for linear
quantile regression with two-way clustered data. Using a separately exchangeable array framework and a projection decomposition of the
quantile score, we characterize regime-dependent convergence rates and establish a self-normalized Gaussian approximation. We propose a two-way cluster-robust sandwich variance
estimator with a kernel-based density “bread” and a projection-matched “meat”, and prove consistency and validity of inference in Gaussian regimes. We also show an impossibility result for uniform inference in a non-Gaussian interaction regime.
Read the full abstract ▾
Machine Learning (Statistics)
Machine Learning in Epidemiology
Marvin N. Wright, Lukas Burk, Pegah Golchian et al. (+3 more)
In the age of digital epidemiology, epidemiologists are faced by an increasing amount of data of growing complexity and dimensionality. Machine learning is a set of powerful tools that can help to analyze such enormous amounts of data. This chapter lays the methodological foundations for successfully applying machine learning in epidemiology. It covers the principles of supervised and unsupervised learning and discusses the most important machine learning methods. Strategies for model evaluation and hyperparameter optimization are developed and interpretable machine learning is introduced. All these theoretical parts are accompanied by code examples in R, where an example
dataset on heart disease is used throughout the chapter.
Read the full abstract ▾
All authors Marvin N. Wright, Lukas Burk, Pegah Golchian, Jan Kapar, Niklas Koenen, Sophie Hanna Langbein
Machine Learning (Statistics) · Cross-listed from cs.LG
The Implicit Bias of Adam and Muon on Smooth Homogeneous Neural Networks
Eitan Gronich and Gal Vardi
We study the implicit bias of momentum-based optimizers on smooth homogeneous models. We show that momentum steepest descent
algorithms like
Muon (spectral norm), MomentumGD ($\ell_2$ norm), and Signum ($\ell_\infty$ norm) are approximate steepest descent trajectories under a decaying learning rate schedule, proving that these
algorithms have a bias towards KKT points of the corresponding margin maximization problem. We extend the analysis to Adam (without the stability constant), which maximizes the $\ell_\infty$ margin, and to
Muon-Signum and
Muon-Adam, which maximize a hybrid norm. Our experiments corroborate the theory and show that the identity of the margin maximized depends on the choice of optimizer. Overall, our results extend earlier lines of work on steepest descent in homogeneous models and momentum-based optimizers in linear models.
Read the full abstract ▾
Statistical Methodology
A general framework for modeling Gaussian process with qualitative and quantitative factors
Linsui Deng and C. F. Jeff Wu
Computer experiments involving both qualitative and quantitative (QQ) factors have attracted increasing
attention. Gaussian process (GP) models have proven effective in this context by choosing specialized covariance functions for QQ factors. In this work, we extend the latent variable-based GP approach, which maps qualitative factors into a continuous latent space, by establishing a general framework to apply standard kernel functions to continuous latent variables. This approach provides a novel perspective for interpreting some existing GP models for QQ factors and introduces new covariance structures in some situations. The ordinal structure can be incorporated naturally and seamlessly in this framework. Furthermore, the
Bayesian information criterion and leave-one-out cross-validation are employed for model selection and model averaging. The performance of the proposed method is comprehensively studied on several examples.
Read the full abstract ▾
Statistical Methodology
Introducing the b-value: combining unbiased and biased estimators from a sensitivity analysis perspective
Zhexiao Lin, Peter J. Bickel and Peng Ding
In empirical research, when we have multiple
estimators for the same parameter of interest, a central question arises: how do we combine unbiased but less precise
estimators with biased but more precise ones to improve the inference? Under this setting, the point estimation problem has attracted considerable
attention. In this paper, we focus on a less studied inference question: how can we conduct valid statistical inference in such settings with unknown bias? We propose a strategy to combine unbiased and biased
estimators from a sensitivity analysis perspective. We derive a sequence of confidence intervals indexed by the magnitude of the bias, which enable researchers to assess how conclusions vary with the bias levels. Importantly, we introduce the notion of the b-value, a critical value of the unknown maximum relative bias at which combining
estimators does not yield a significant result. We apply this strategy to three canonical combined
estimators: the precision-weighted
estimator, the pretest
estimator, and the soft-thresholding
estimator. For each
estimator, we characterize the sequence of confidence intervals and determine the bias threshold at which the conclusion changes. Based on the theory, we recommend reporting the b-value based on the soft-thresholding
estimator and its associated confidence intervals, which are robust to unknown bias and achieve the lowest worst-case risk among the alternatives.
Read the full abstract ▾
Statistics Theory
Orthogonal parametrisations of Extreme-Value distributions
Nathan Huet and Ilaria Prosdocimi
Extreme value distributions are routinely employed to assess risks connected to extreme events in a large number of applications. They typically are two- or three- parameter distributions: the inference can be unstable, which is particularly problematic given the fact that often times these distributions are fitted to small samples. Furthermore, the distribution's parameters are generally not directly interpretable and not the key aim of the estimation. We present several orthogonal reparametrisations of the main extreme-value distributions, key in the modelling of rare events. In particular, we apply the theory developed in Cox and Reid (1987) to the Generalised Extreme-Value, Generalised Pareto, and Gumbel distributions. We illustrate the principal advantage of these reparametrisations in a simulation study.
Read the full abstract ▾
Machine Learning (Statistics) · Cross-listed from cs.LG
Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains
Rahul Singh, Siddharth Chandak, Eric Moulines et al. (+2 more)
We present the first regret bound for classical online Q-learning in infinite-horizon discounted Markov decision processes (MDPs), without relying on optimism or bonus terms. We first analyze Boltzmann Q-learning with decaying temperature and show that its regret depends critically on the suboptimality gap of the MDP: for sufficiently large gaps, the regret is sublinear, while for small gaps it deteriorates and can approach linear growth. To address this limitation, we study a Smoothed $\epsilon_n$-Greedy exploration scheme that combines $\epsilon_n$-greedy and Boltzmann exploration, for which we prove a gap-robust regret bound of near-$\tilde{O}(N^{9/10})$. We also obtain sample complexity guarantees, with both regret and sample complexity bounds holding with high probability. To analyze these
algorithms, we develop a high-probability concentration bound for contractive Markovian
stochastic approximation with iterate- and time-dependent transition dynamics. This bound may be of independent interest as the contraction factor in our framework is allowed to converge to one asymptotically.
Read the full abstract ▾
All authors Rahul Singh, Siddharth Chandak, Eric Moulines, Vivek S. Borkar, Nicholas Bambos
Machine Learning (Statistics)
On sparsity, extremal structure, and monotonicity properties of Wasserstein and Gromov-Wasserstein optimal transport plans
Titouan Vayer
This note gives a self-contained overview of some important properties of the Gromov-Wasserstein (GW) distance, compared with the standard linear optimal transport (OT) framework. More specifically, I explore the following questions: are GW optimal transport plans sparse? Under what conditions are they supported on a permutation? Do they satisfy a form of cyclical monotonicity? In particular, I present the conditionally negative semi-definite property and show that, when it holds, there are GW optimal plans that are sparse and supported on a permutation.
Read the full abstract ▾
Statistics Theory
HAL-MLE Log-Splines Density Estimation (Part I: Univariate)
Yilong Hou, Zhengpu Zhao, Yi Li et al. (+1 more)
We study nonparametric maximum likelihood estimation of probability densities under a total variation (TV) type penalty, sectional variation norm (also named as Hardy-Krause variation). TV regularization has a long history in regression and density estimation, including results on $L^2$ and KL divergence convergence rates. Here, we revisit this task using the Highly Adaptive Lasso (HAL) framework. We formulate a HAL-based maximum likelihood
estimator (HAL-MLE) using the log-spline link function from \citet{kooperberg1992logspline}, and show that in the univariate setting the bounded sectional variation norm assumption underlying HAL coincides with the classical bounded TV assumption. This equivalence directly connects HAL-MLE to existing TV-penalized approaches such as local adaptive splines \citep{mammen1997locally}. We establish three new theoretical results: (i) the univariate HAL-MLE is asymptotically linear, (ii) it admits pointwise asymptotic normality, and (iii) it achieves uniform convergence at rate $n^{-(k+1)/(2k+3)}$ up to logarithmic factors for the smoothness order $k \geq 1$. These results extend existing results from \citet{van2017uniform}, which previously guaranteed only uniform consistency without rates when $k=0$. We will include the uniform convergence for general dimension $d$ in the follow-up work of this paper. The intention of this paper is to provide a unified framework for the TV-penalized density estimation methods, and to connect the HAL-MLE to the existing TV-penalized methods in the univariate case, despite that the general HAL-MLE is defined for multivariate cases.
Read the full abstract ▾
All authors Yilong Hou, Zhengpu Zhao, Yi Li, Mark van der Laan
Statistics Theory
Nonparametric estimation of linear multiplier for processes driven by a Hermite process
B.L.S. Prakasa Rao
We study the problem of nonparametric estimation of the linear multiplier function $\theta(t)$ for processes satisfying
stochastic differential equations of the type $$dX_t=\theta(t) X_tdt+ \epsilon dZ^{q,H}_t, X_0=x_0, 0\leq t \leq T$$ where $\{Z^{q,H}_t, t \geq 0\}$ is a Hermite process with known order $q$ and known self-similarity parameter $H \in (\frac{1}{2},1).$ We investigate the asymptotic behaviour of the
estimator of the unknown function $\theta(t)$ as $\epsilon \rightarrow 0.$
Read the full abstract ▾
Machine Learning (Statistics) · Cross-listed from cs.LG
Maren Mahsereci and Toni Karvonen
Bayesian quadrature is a probabilistic, model-based approach to numerical integration, the estimation of intractable integrals, or expectations. Although
Bayesian quadrature was popularised already in the 1980s, no systematic and comprehensive treatment has been published. The purpose of this survey is to fill this gap. We review the mathematical foundations of
Bayesian quadrature from different points of view; present a systematic taxonomy for classifying different
Bayesian quadrature methods along the three axes of modelling, inference, and sampling; collect general theoretical guarantees; and provide a controlled numerical study that explores and illustrates the effect of different choices along the axes of the taxonomy. We also provide a realistic assessment of practical challenges and limitations to application of
Bayesian quadrature methods and include an up-to-date and nearly exhaustive bibliography that covers not only machine learning and statistics literature but all areas of mathematics and engineering in which
Bayesian quadrature or equivalent methods have seen use.
Read the full abstract ▾
Statistics Applications
Phase Transitions in Collective Damage of Civil Structures under Natural Hazards
Sebin Oh, Jinyan Zhao, Raul Rincon et al. (+2 more)
The fate of cities under natural hazards depends not only on hazard intensity but also on the coupling of structural damage, a collective process that remains poorly understood. Here we show that urban structural damage exhibits phase-transition phenomena. As hazard intensity increases, the system can shift abruptly from a largely safe to a largely damaged state, analogous to a discontinuous phase transition in statistical physics. Higher diversity in the building portfolio smooths this transition, but multiscale damage clustering traps the system in a highly volatile regime that suppresses the emergence of predictable Gaussian statistics. The observed phenomenological patterns are interpreted through an effective random-field Ising model, with its key parameters translated into tangible engineering variables such as hazard demand, structural diversity, and modeling uncertainty. These insights establish a phase-aware description of collective damage, revealing that common engineering simplifications can distort the inherent phase of real urban portfolios. Critically, such phase distortions can substantially bias hazard loss estimates, producing relative errors of up to 50% in exceedance probabilities under moderate earthquakes—equivalent to a several-fold gap in anticipated repair costs. The phase-aware description turns the collective behavior of civil infrastructure damage into actionable diagnostics for urban risk assessment and planning.
Read the full abstract ▾
All authors Sebin Oh, Jinyan Zhao, Raul Rincon, Jamie E. Padgett, Ziqi Wang
Machine Learning (Statistics) · Cross-listed from cs.GT
Multi-Agent Combinatorial-Multi-Armed-Bandit framework for the Submodular Welfare Problem under Bandit Feedback
Subham Pokhriyal, Shweta Jain and Vaneet Aggarwal
We study the Submodular Welfare Problem (SWP), where items are partitioned among
agents with monotone submodular utilities to maximize the total welfare under bandit feedback. Classical SWP assumes full value-oracle access, achieving $(1-1/e)$ approximations via continuous-greedy
algorithms. We extend this to a multi-
agent combinatorial bandit framework (MA-CMAB), where actions are partitions under full-bandit feedback with non-communicating
agents. Unlike prior single-
agent or separable multi-
agent CMAB models, our setting couples
agents through shared allocation constraints. We propose an explore-then-commit strategy with randomized assignments, achieving $\tilde{\mathcal{O}}(T^{2/3})$ regret against a $(1-1/e)$
benchmark, the first such guarantee for partition-based submodular welfare problem under bandit feedback.
Read the full abstract ▾
Machine Learning (Statistics)
Conjugate Learning Theory: Uncovering the Mechanisms of Trainability and Generalization in Deep Neural Networks
Binchuan Qi
In this work, we propose a notion of practical learnability grounded in finite sample settings, and develop a conjugate learning theoretical framework based on convex conjugate duality to characterize this learnability property. Building on this foundation, we demonstrate that training deep neural networks (DNNs) with mini-batch
stochastic gradient descent (SGD) achieves global optima of empirical risk by jointly controlling the extreme
eigenvalues of a structure
matrix and the gradient energy, and we establish a corresponding convergence
theorem. We further elucidate the impact of batch size and model architecture (including depth, parameter count, sparsity, skip connections, and other characteristics) on non-convex optimization. Additionally, we derive a model-agnostic lower bound for the achievable empirical risk, theoretically demonstrating that data determines the fundamental limit of trainability. On the generalization front, we derive deterministic and probabilistic bounds on generalization error based on generalized conditional
entropy measures. The former explicitly delineates the range of generalization error, while the latter characterizes the distribution of generalization error relative to the deterministic bounds under independent and identically distributed (i.i.d.) sampling conditions. Furthermore, these bounds explicitly quantify the influence of three key factors: (i) information loss induced by irreversibility in the model, (ii) the maximum attainable loss value, and (iii) the generalized conditional
entropy of features with respect to labels. Moreover, they offer a unified theoretical lens for understanding the roles of regularization, irreversible transformations, and network depth in shaping the generalization behavior of deep neural networks. Extensive experiments validate all theoretical predictions, confirming the framework's correctness and consistency.
Read the full abstract ▾
Statistical Methodology
Uncertainty-Aware Neural Multivariate Geostatistics
Yeseul Jeon, Aaron Scheffler and Rajarshi Guhaniyogi
We propose Deep Neural Coregionalization, a scalable framework for uncertainty-aware multivariate geostatistics. DNC models multivariate spatial effects through spatially varying latent factors and loadings, assigning deep Gaussian process (DGP) priors to both the factors and the entries of the loading
matrix. This joint construction learns shared latent spatial structure together with response-specific, location-dependent mixing weights, enabling flexible nonlinear and space-dependent associations within and across variables. A key contribution is a variational formulation that makes the DGP to deep neural network (DNN) correspondence explicit: maximizing the DGP evidence lower bound (ELBO) is equivalent to training DNNs with weight decay and Monte Carlo (MC) dropout. This yields fast mini-batch
stochastic optimization without Markov Chain Monte Carlo (MCMC), while providing principled uncertainty quantification through MC-dropout forward passes as approximate posterior draws, producing calibrated credible surfaces for prediction and spatial effect estimation. Across simulations, DNC is competitive with existing spatial factor models, particularly under strong nonstationarity and complex cross-dependence, while delivering substantial computational gains. In a multivariate environmental case study, DNC captures spatially varying cross-variable interactions, produces interpretable maps of multivariate outcomes, and scales uncertainty quantification to large
datasets with orders-of-magnitude reductions in runtime.
Read the full abstract ▾
Statistics Theory
Ratio Covers of Convex Sets and Optimal Mixture Density Estimation
Spencer Compton, Gábor Lugosi, Jaouad Mourtada et al. (+2 more)
We study density estimation in Kullback-Leibler divergence: given an i.i.d. sample from an unknown density $p^\star$, the goal is to construct an
estimator $\widehat{p}$ such that $\mathrm{KL}(p^\star,\widehat{p})$ is small with high probability. We consider two fundamental settings involving a finite dictionary of densities: (i) model aggregation, where $p^\star$ belongs to the dictionary, and (ii) convex aggregation (mixture density estimation), where $p^\star$ is a mixture of densities from the dictionary. Crucially, we make no assumption on the base densities: their ratios may be unbounded and their supports may differ. For both problems, we identify the best possible high-probability guarantees in terms of the dictionary size, sample size, and confidence level. These optimal rates are higher than those achievable when density ratios are bounded by absolute constants; for mixture density estimation, they match existing lower bounds in the special case of discrete distributions. Our analysis of the mixture case hinges on two new covering results. First, we provide a sharp, distribution-free upper bound on the local Hellinger
entropy of the class of mixtures of $M$ distributions. Second, we prove an optimal ratio covering
theorem for convex sets: for every convex compact set $K \subset \mathbb{R}_+^d$, there exists a subset $A \subset K$ with at most $2^{O(d)}$ elements such that each element of $K$ is coordinate-wise dominated by an element of $A$ up to a universal constant factor. This
geometric result is of independent interest; notably, it yields new cardinality estimates for $\varepsilon$-approximate Pareto sets in multi-objective optimization with convex feasible set.
Read the full abstract ▾
All authors Spencer Compton, Gábor Lugosi, Jaouad Mourtada, Jian Qian, Nikita Zhivotovskiy
Statistical Methodology
Experimental Assortments for Choice Estimation and Nest Identification
Xintong Yu, Will Ma and Michael Zhao
What assortments (subsets of items) should be offered, to collect data for estimating a choice model over $n$ total items? We propose a structured, non-adaptive experiment design requiring only $O(\log n)$ distinct assortments, each offered repeatedly, that consistently outperforms randomized and other heuristic designs across an extensive numerical
benchmark that estimates multiple different choice models under a variety of (possibly mis-specified) ground truths. We then focus on Nested Logit choice models, which cluster items into "nests" of close substitutes. Whereas existing Nested Logit estimation procedures assume the nests to be known and fixed, we present a new
algorithm to identify nests based on collected data, which when used in conjunction with our experiment design, guarantees correct identification of nests under any Nested Logit ground truth. Our experiment design was deployed to collect data from over 70 million users at Dream11, an Indian fantasy sports platform that offers different types of betting contests, with rich substitution patterns between them. We identify nests based on the collected data, which lead to better out-of-sample choice prediction than ex-ante clustering from contest features. Our identified nests are ex-post justifiable to Dream11 management.
Read the full abstract ▾
Machine Learning (Statistics)
Empirical Cumulative Distribution Function Clustering for LLM-based Agent System Analysis
Chihiro Watanabe and Jingyu Sun
Large
language models (LLMs) are increasingly used as
agents to solve complex tasks such as question answering (QA), scientific debate, and software development. A standard evaluation procedure aggregates multiple responses from LLM
agents into a single final answer, often via majority voting, and compares it against reference answers. However, this process can obscure the quality and distributional characteristics of the original responses. In this paper, we propose a novel evaluation framework based on the empirical cumulative distribution function (ECDF) of cosine similarities between generated responses and reference answers. This enables a more nuanced assessment of response quality beyond exact match metrics. To analyze the response distributions across different
agent configurations, we further introduce a clustering method for ECDFs using their distances and the $k$-medoids
algorithm. Our experiments on a QA
dataset demonstrate that ECDFs can distinguish between
agent settings with similar final accuracies but different quality distributions. The clustering analysis also reveals interpretable group structures in the responses, offering insights into the impact of temperature, persona, and question topics.
Read the full abstract ▾
Statistics Applications · Cross-listed from cs.LG
Feature-based morphological analysis of shape graph data
Murad Hossen, Demetrio Labate and Nicolas Charon
This paper introduces and demonstrates a computational pipeline for the statistical analysis of shape graph
datasets, namely
geometric networks embedded in 2D or 3D spaces. Unlike traditional abstract graphs, our purpose is not only to retrieve and distinguish variations in the connectivity structure of the data but also
geometric differences of the network branches. Our proposed approach relies on the extraction of a specifically curated and explicit set of topological,
geometric and directional features, designed to satisfy key invariance properties. We leverage the resulting feature representation for tasks such as group comparison, clustering and classification on cohorts of shape graphs. The effectiveness of this representation is evaluated on several real-world
datasets including urban road/street networks, neuronal traces and astrocyte imaging. These results are benchmarked against several alternative methods, both feature-based and not.
Read the full abstract ▾