Machine Learning (Statistics) · Cross-listed from cs.LG
Position: The Complexity of Perfect AI Alignment – Formalizing the RLHF Trilemma
Subramanyam Sahoo, Aman Chadha, Vinija Jain et al. (+1 more)
Reinforcement Learning from Human Feedback (RLHF) is widely used for aligning large
language models, yet practitioners face a persistent puzzle: improving safety often reduces
fairness, scaling to diverse populations becomes computationally intractable, and making systems robust often amplifies majority biases. We formalize this tension as the
Alignment Trilemma: no RLHF system can simultaneously achieve (i) epsilon-representativeness across diverse human values, (ii)
polynomial tractability in sample and compute complexity, and (iii) delta-robustness against
adversarial perturbations and distribution shift. Through a complexity-theoretic analysis integrating statistical learning theory and robust optimization, we prove that achieving both representativeness (epsilon <= 0.01) and robustness (delta <= 0.001) for global-scale populations requires Omega(2^{d_context}) operations, which is super-
polynomial in the context dimensionality. We show that current RLHF implementations resolve this trilemma by sacrificing representativeness: they collect only 10^3–10^4 samples from homogeneous annotator pools while 10^7–10^8 samples are needed for true global representation. Our framework provides a unified explanation for documented RLHF pathologies including preference collapse, sycophancy, and systematic bias amplification. We conclude with concrete directions for navigating these fundamental trade-offs through strategic relaxations of
alignment requirements.
Read the full abstract ▾
All authors Subramanyam Sahoo, Aman Chadha, Vinija Jain, Divya Chaudhary
Statistical Methodology · Cross-listed from cs.LG
RFX: High-Performance Random Forests with GPU Acceleration and QLORA Compression
Chris Kuchar
RFX (Random Forests X), where X stands for compression or quantization, presents a production-ready implementation of Breiman and Cutler's Random Forest classification methodology in Python. RFX v1.0 provides complete classification: out-of-bag error estimation, overall and local importance measures, proximity
matrices with QLORA compression, case-wise analysis, and interactive visualization (rfviz)–all with CPU and GPU acceleration. Regression, unsupervised learning, CLIQUE importance, and RF-GAP proximity are planned for v2.0. This work introduces four solutions addressing the proximity
matrix memory bottleneck limiting Random Forest analysis to ~60,000 samples: (1) QLORA (Quantized Low-Rank Adaptation) compression for GPU proximity
matrices, reducing
memory from 80GB to 6.4MB for 100k samples (12,500x compression with INT8 quantization) while maintaining 99%
geometric structure preservation, (2) CPU TriBlock proximity–combining upper-triangle storage with block-sparse thresholding–achieving 2.7x
memory reduction with lossless quality, (3) SM-aware GPU batch sizing achieving 95% GPU utilization, and (4) GPU-accelerated 3D MDS visualization computing
embeddings directly from low-rank factors using power iteration. Validation across four implementation modes (GPU/CPU x case-wise/non-case-wise) demonstrates correct implementation. GPU achieves 1.4x speedup over CPU for overall importance with 500+ trees. Proximity computation scales from 1,000 to 200,000+ samples (requiring GPU QLORA), with CPU TriBlock filling the gap for medium-scale
datasets (10K-50K samples). RFX v1.0 eliminates the proximity
memory bottleneck, enabling proximity-based Random Forest analysis on
datasets orders of magnitude larger than previously feasible. Open-source production-ready classification following Breiman and Cutler's original methodology.
Read the full abstract ▾
Machine Learning (Statistics) · Cross-listed from cs.LG
The Generalized Proximity Forest
Ben Shaw, Adam Rustad, Sofia Pelagalli Maia et al. (+2 more)
Recent work has demonstrated the utility of Random Forest (RF) proximities for various supervised machine learning tasks, including outlier detection, missing data imputation, and visualization. However, the utility of the RF proximities depends upon the success of the RF model, which itself is not the ideal model in all contexts. RF proximities have recently been extended to time series by means of the distance-based Proximity Forest (PF) model, among others, affording time series analysis with the benefits of RF proximities. In this work, we introduce the generalized PF model, thereby extending RF proximities to all contexts in which supervised distance-based machine learning can occur. Additionally, we introduce a variant of the PF model for regression tasks. We also introduce the notion of using the generalized PF model as a meta-learning framework, extending supervised imputation capability to any pre-trained classifier. We experimentally demonstrate the unique advantages of the generalized PF model compared with both the RF model and the $k$-nearest neighbors model.
Read the full abstract ▾
All authors Ben Shaw, Adam Rustad, Sofia Pelagalli Maia, Jake S. Rhodes, Kevin R. Moon
Statistics Theory
Estimation of High-dimensional Nonlinear Vector Autoregressive Models
Yuefeng Han, Likai Chen and Wei Biao Wu
High-dimensional vector autoregressive (VAR) models have numerous applications in fields such as econometrics, biology, climatology, among others. While prior research has mainly focused on linear VAR models, these approaches can be restrictive in practice. To address this, we introduce a high-dimensional non-parametric sparse additive model, providing a more flexible framework. Our method employs basis expansions to construct high-dimensional nonlinear VAR models. We derive convergence rates and model selection consistency for least squared
estimators, considering dependence measures of the processes, error moment conditions, sparsity, and basis expansions. Our theory significantly extends prior linear VAR models by incorporating both non-Gaussianity and non-linearity. As a key contribution, we derive sharp Bernstein-type inequalities for tail probabilities in both non-sub-Gaussian linear and nonlinear VAR processes, which match the classical Bernstein inequality for independent random variables. Additionally, we present numerical experiments that support our theoretical findings and demonstrate the advantages of the nonlinear VAR model for a gene expression time series
dataset.
Read the full abstract ▾
Statistical Methodology · Cross-listed from cs.LG
Majority of the Bests: Improving Best-of-N via Bootstrapping
Amin Rakhsha, Kanika Madan, Tianyu Zhang et al. (+2 more)
Sampling multiple outputs from a Large
Language Model (LLM) and selecting the most frequent (Self-consistency) or highest-scoring (Best-of-N) candidate is a popular approach to achieve higher accuracy in tasks with discrete final answers. Best-of-N (BoN) selects the output with the highest reward, and with perfect rewards, it often achieves near-perfect accuracy. With imperfect rewards from reward models, however, BoN fails to reliably find the correct answer and its performance degrades drastically. We consider the distribution of BoN's outputs and highlight that, although the correct answer does not usually have a probability close to one under imperfect rewards, it is often the most likely outcome. This suggests that the mode of this distribution can be more reliably correct than a sample from it. Based on this idea, we propose Majority-of-the-Bests (MoB), a novel selection mechanism that estimates the output distribution of BoN via bootstrapping and selects its mode. Experimental results across five
benchmarks, three different base LLMs, and two reward models demonstrate consistent improvements over BoN in 25 out of 30 setups. We also provide theoretical results for the consistency of the bootstrapping. MoB serves as a simple, yet strong alternative to BoN and self-consistency, and more broadly, motivates further research in more nuanced selection mechanisms.
Read the full abstract ▾
All authors Amin Rakhsha, Kanika Madan, Tianyu Zhang, Amir-massoud Farahmand, Amir Khasahmadi
Machine Learning (Statistics) · Cross-listed from cs.LG
Bayesian-based Online Label Shift Estimation with Dynamic Dirichlet Priors
Jiawei Hu and Javier A. Barria
Label shift, a prevalent challenge in supervised learning, arises when the class prior distribution of test data differs from that of training data, leading to significant degradation in classifier performance. To accurately estimate the test priors and enhance classification accuracy, we propose a
Bayesian framework for label shift estimation, termed Full Maximum A Posterior Label Shift (FMAPLS), along with its online version, online-FMAPLS. Leveraging batch and online Expectation-Maximization (EM)
algorithms, these methods jointly and dynamically optimize Dirichlet hyperparameters $\boldsymbol{\alpha}$ and class priors $\boldsymbol{\pi}$, thereby overcoming the rigid constraints of the existing Maximum A Posterior Label Shift (MAPLS) approach. Moreover, we introduce a linear surrogate function (LSF) to replace gradient-based hyperparameter updates, yielding closed-form solutions that reduce computational complexity while retaining asymptotic equivalence. The online variant substitutes the batch E-step with a
stochastic approximation, enabling real-time adaptation to streaming data. Furthermore, our theoretical analysis reveals a fundamental trade-off between online convergence rate and estimation accuracy. Extensive experiments on CIFAR100 and ImageNet
datasets under shuffled long-tail and Dirichlet test priors demonstrate that FMAPLS and online-FMAPLS respectively achieve up to 40% and 12% lower KL divergence and substantial improvements in post-shift accuracy over state-of-the-art baselines, particularly under severe class imbalance and distributional uncertainty. These results confirm the robustness, scalability, and suitability of the proposed methods for large-scale and dynamic learning scenarios.
Read the full abstract ▾
Machine Learning (Statistics)
Differential privacy with dependent data
Valentin Roth and Marco Avella-Medina
Dependent data underlies many statistical studies in the social and health sciences, which often involve sensitive or private information. Differential
privacy (DP) and in particular user-level DP provide a natural formalization of
privacy requirements for processing dependent data where each individual provides multiple observations to the
dataset. However, dependence introduced, e.g., through repeated measurements challenges the existing statistical theory under DP-constraints. In \iid{} settings, noisy Winsorized mean
estimators have been shown to be minimax optimal for standard (item-level) and user-level DP estimation of a mean $\mu \in \R^d$. Yet, their behavior on potentially dependent observations has not previously been studied. We fill this gap and show that Winsorized mean
estimators can also be used under dependence for bounded and unbounded data, and can lead to asymptotic and finite sample guarantees that resemble their \iid{} counterparts under a weak notion of dependence. For this, we formalize dependence via log-Sobolev inequalities on the joint distribution of observations. This enables us to adapt the stable histogram by Karwa and Vadhan (2018) to a non-\iid{} setting, which we then use to estimate the private projection intervals of the Winsorized
estimator. The resulting guarantees for our item-level mean
estimator extend to user-level mean estimation and transfer to the local model via a randomized response histogram. Using the mean
estimators as building blocks, we provide extensions to random effects models, longitudinal linear regression and nonparametric regression. Therefore, our work constitutes a first step towards a systematic study of DP for dependent data.
Read the full abstract ▾
Machine Learning (Statistics)
Ensuring Calibration Robustness in Split Conformal Prediction Under Adversarial Attacks
Xunlei Qian and Yue Xing
Conformal prediction (CP) provides distribution-free, finite-sample coverage guarantees but critically relies on exchangeability, a condition often violated under distribution shift. We study the robustness of split conformal prediction under
adversarial perturbations at test time, focusing on both coverage validity and the resulting prediction set size. Our theoretical analysis characterizes how the strength of
adversarial perturbations during calibration affects coverage guarantees under
adversarial test conditions. We further examine the impact of
adversarial training at the model-training stage. Extensive experiments support our theory: (i) Prediction coverage varies monotonically with the calibration-time attack strength, enabling the use of nonzero calibration-time attack to predictably control coverage under
adversarial tests; (ii) target coverage can hold over a range of test-time attacks: with a suitable calibration attack, coverage stays within any chosen tolerance band across a contiguous set of perturbation levels; and (iii)
adversarial training at the training stage produces tighter prediction sets that retain high informativeness.
Read the full abstract ▾
Statistical Methodology
A joint optimization approach to identifying sparse dynamics using least squares kernel collocation
Alexander W. Hsu, Ike Griss Salas, Jacob M. Stevens-Haas et al. (+3 more)
We develop an all-at-once modeling framework for learning systems of ordinary differential equations (ODE) from scarce, partial, and noisy observations of the states. The proposed methodology amounts to a combination of sparse recovery strategies for the ODE over a function library combined with techniques from reproducing kernel
Hilbert space (RKHS) theory for estimating the state and discretizing the ODE. Our numerical experiments reveal that the proposed strategy leads to significant gains in terms of accuracy, sample efficiency, and robustness to noise, both in terms of learning the equation and estimating the unknown states. This work demonstrates capabilities well beyond existing and widely used
algorithms while extending the modeling flexibility of other recent developments in equation discovery.
Read the full abstract ▾
All authors Alexander W. Hsu, Ike Griss Salas, Jacob M. Stevens-Haas, J. Nathan Kutz, Aleksandr Aravkin, Bamdad Hosseini
Statistics Theory
Matching correlated VAR time series
Ernesto Araya and Hemant Tyagi
We study the problem of matching correlated VAR time series databases, where a multivariate time series is observed along with a perturbed and permuted version, and the goal is to recover the unknown matching between them. To model this, we introduce a probabilistic framework in which two time series $(x_t)_{t\in[T]},(x^\#_t)_{t\in[T]}$ are jointly generated, such that $x^\#_t=x_{\pi^*(t)}+\sigma \tilde{x}_{\pi^*(t)}$, where $(x_t)_{t\in[T]},(\tilde{x}_t)_{t\in[T]}$ are independent and identically distributed vector autoregressive (VAR) time series of order $1$ with Gaussian increments, for a hidden $\pi^*$. The objective is to recover $\pi^*$, from the observation of $(x_t)_{t\in[T]},(x^\#_t)_{t\in[T]}$. This generalizes the classical problem of matching independent point clouds to the time series setting. We derive the maximum likelihood
estimator (MLE), leading to a quadratic optimization over permutations, and theoretically analyze an
estimator based on linear assignment. For the latter approach, we establish recovery guarantees, identifying thresholds for $\sigma$ that allow for perfect or partial recovery. Additionally, we propose solving the MLE by considering convex relaxations of the set of permutation
matrices (e.g., over the Birkhoff polytope). This allows for efficient estimation of $\pi^*$ and the VAR parameters via alternating minimization. Empirically, we find that linear assignment often matches or outperforms MLE relaxation based approaches.
Read the full abstract ▾
Statistical Methodology · Cross-listed from econ.EM
Robust Inference Methods for Latent Group Panel Models under Possible Group Non-Separation
Oguzhan Akgun and Ryo Okui
We develop robust inference methods for general linear hypotheses in linear panel data models with latent group structure in the coefficients. We employ a selective conditional inference approach based on the conditional distribution of coefficient estimates given the group structure estimated from the data. The resulting inference procedures remain valid even when group separation fails (i.e., when the distributional properties of the group-specific coefficients are not established) and, because they account for uncertainty in estimating the group structure, they also improve on conventional asymptotic procedures in finite samples when separation does hold. Our tests are exactly valid under Gaussian errors with known variances and asymptotically valid under general error distributions. Unlike much of the post-clustering inference literature, which focuses on testing group homogeneity, our framework accommodates arbitrary linear restrictions on the group-specific coefficients. Inverting the conditional tests yields selective confidence sets with valid coverage conditional on the estimated group structure. We illustrate the methods through Monte Carlo simulations and an application to growth convergence clubs. Simulations demonstrate accurate size control and good power in finite samples, including in the presence of serial correlation and cross-sectional dependence. The applications show sharp differences between the traditional inference methods and robust methods proposed in this paper, illustrating the importance of taking the estimated group structure into account.
Read the full abstract ▾
Statistical Methodology
Hyperevent network modelling of partially observed gossip data
Veronica Poda, Veronica Vinciotti and Ernst C. Wit
Gossiping is a widespread social phenomenon that shapes relationships and information flow in communities. From a network theoretic point of view, gossiping can be seen as a higher-order interaction, as it involves at least two persons talking about a non-present third. The mechanism of gossiping is complex: it is most likely dynamic, as its intensity changes over time, and possibly viral, if a gossiping event induces future gossiping, such as a repetition or retaliation. We define
covariates of interest for these effects and propose a relational hyperevent model to study and quantify these complex dynamics. We consider survey data collected yearly from 44 secondary schools in Hungary. No information is available about the exact timing of the events nor about the aggregate number of events within the yearly time interval. What is measured is whether at least one gossiping event has occurred in a given time interval. We extend inference for relational hyperevent models to the case of rightcensored interval-time data and show how flexible and efficient generalized additive models can be used for estimation of effects of interest. Our analysis on the school data illustrates how a model that accounts for linear, smooth and random effects can identify the social drivers of gossiping, while revealing complex temporal dynamics.
Read the full abstract ▾
Machine Learning (Statistics)
Transforming Conditional Density Estimation Into a Single Nonparametric Regression Task
Alexander G. Reisach, Olivier Collier, Alex Luedtke et al. (+1 more)
We propose a way of transforming the problem of conditional density estimation into a single nonparametric regression task via the introduction of auxiliary samples. This allows leveraging regression methods that work well in high dimensions, such as neural networks and decision trees. Our main theoretical result characterizes and establishes the convergence of our
estimator to the true conditional density in the data limit. We develop condensité, a method that implements this approach. We demonstrate the benefit of the auxiliary samples on synthetic data and showcase that condensité can achieve good out-of-the-box results. We evaluate our method on a large population survey
dataset and on a satellite imaging
dataset. In both cases, we find that condensité matches or outperforms the state of the art and yields conditional densities in line with established findings in the literature on each
dataset. Our contribution opens up new possibilities for regression-based conditional density estimation and the empirical results indicate strong promise for applied research.
Read the full abstract ▾
All authors Alexander G. Reisach, Olivier Collier, Alex Luedtke, Antoine Chambaz
Statistics Theory
Multiple change-points detection based on U-Statistics under weak dependence
Joseph Ngatchou-Wandji, Echarif Elharfaoui and Michel Harel
We study multiple change-points detection using multi-samples tests based on U-statistics for absolutely regular observations. Our results extend those of Ngatchou-Wandji et al. (2022) concerned with the study of one single changepoint. The asymptotic distributions of the test statistics under the null hypothesis and under a sequence of local alternatives are given explicitly, and the tests are shown to be consistent. A small set of simulations is done for evaluating the performance of the tests in detecting multiple changes in the mean, variance and autocorrelation of some simple times series models.
Read the full abstract ▾
Statistics Applications · Cross-listed from cs.CY
Optimal Meal Schedule for a Local Nonprofit Using LLM-Aided Data Extraction
Sergio Marin, Nhu Nguyen, Max Zheng et al. (+1 more)
We present a data-driven pipeline developed in collaboration with the Power Packs Project, a nonprofit addressing food insecurity in local communities. The system integrates data extraction from PDFs, large
language models for ingredient standardization, and binary integer programming to generate a 15-week recipe schedule that minimizes projected wholesale costs while meeting nutritional constraints. All 157 recipes were mapped to a nutritional database and assigned estimated and predicted costs using historical invoice data and category-specific inflation adjustments. The model effectively handles real-world price
volatility and is structured for easy updates as new recipes or cost data become available. Optimization results show that constraint-based selection yields nutritionally balanced and cost-efficient plans under uncertainty. To facilitate real-time decision-making, we deployed a searchable web platform that integrates analytical models into daily operations by enabling staff to explore recipes by ingredient, category, or through an optimized meal plan.
Read the full abstract ▾
All authors Sergio Marin, Nhu Nguyen, Max Zheng, Christina M. Weaver
Machine Learning (Statistics)
Reliable Selection of Heterogeneous Treatment Effect Estimators
Jiayi Guo and Zijun Gao
We study the problem of selecting the best heterogeneous treatment effect (HTE)
estimator from a collection of candidates in settings where the treatment effect is fundamentally unobserved. We cast
estimator selection as a multiple testing problem and introduce a ground-truth-free procedure based on a cross-fitted, exponentially weighted test statistic. A key component of our method is a two-way sample splitting scheme that decouples nuisance estimation from weight learning and ensures the stability required for valid inference. Leveraging a stability-based central limit
theorem, we establish asymptotic familywise error rate control under mild regularity conditions. Empirically, our procedure provides reliable error control while substantially reducing false selections compared with commonly used methods across ACIC 2016, IHDP, and Twins
benchmarks, demonstrating that our method is feasible and powerful even without ground-truth treatment effects.
Read the full abstract ▾
Statistical Methodology
Change-Point Detection With Multivariate Repeated Measures
Serim Han, Jingru Zhang and Hoseung Song
Graph-based methods have shown particular strengths in change-point detection (CPD) tasks for high-dimensional nonparametric settings. However, existing CPD research has rarely addressed data with repeated measurements or local group structures. A common treatment is to average repeated measurements, which can result in the loss of important within-individual information. In this paper, we propose a new graph-based method for detecting change-points in data with repeated measurements or local structures by incorporating both within-individual and between-individual information. Analytical approximations to the significance of the proposed statistics are derived, enabling efficient computation of p-values for the combined test statistic. We also establish consistency of the proposed test and the estimated change-point location. The proposed method effectively detects change-points across a wide range of alternatives, particularly when within-individual differences are present. The new method is illustrated through an analysis of the New York City taxi
dataset.
Read the full abstract ▾
Statistics Theory
Time-uniform concentration bounds for iterative algorithms
Tuan Pham, Alessandro Rinaldo and Purnamrita Sarkar
We develop a new framework for deriving time-uniform concentration bounds for the output of
stochastic sequential
algorithms satisfying certain recursive inequalities akin to those defining the almost-supermartingale processes introduced by \cite{robbins1971convergence}. Our approach is of wide applicability, and can be deployed in settings in which exponential supermartingale processes, required by prevailing methodologies for anytime-valid concentration inequalities, are not readily available. Our results can be viewed as quantitative versions of the classical Robbins-Siegmund Lemma. We demonstrate the effectiveness of our method by providing new and optimal time-uniform concentration bounds for Oja's
algorithm for streaming PCA,
stochastic gradient descent, and
stochastic approximations.
Read the full abstract ▾
Statistical Methodology
Efficient Covariance Estimation for Sparsified Functional Data
Sijie Zheng, Fandong Meng and Jie Zhou
Motivated by recent work involving the analysis of leveraging spatial correlations in sparsified mean estimation, we present a novel procedure for constructing covariance
estimator. The proposed Random-
knots (Random-
knots-Spatial) and B-spline (Bspline-Spatial)
estimators of the covariance function are computationally efficient. Asymptotic pointwise of the covariance are obtained for sparsified individual trajectories under some regularity conditions. Our proposed nonparametric method well perform the functional principal components analysis for the case of sparsified data, where the number of repeated measurements available per subject is small. In contrast, classical functional data analysis requires a large number of regularly spaced measurements per subject. Model selection techniques, such as the Akaike information criterion, are used to choose the model dimension corresponding to the number of eigenfunctions in the model. Theoretical results are illustrated with Monte Carlo simulation experiments. Finally, we cluster multi-domain data by replacing the covariance function with our proposed covariance
estimator during PCA.
Read the full abstract ▾
Machine Learning (Statistics) · Cross-listed from cs.LG
Adaptive Conformal Prediction for Quantum Machine Learning
Douglas Spencer, Samual Nicholls and Michele Caprio
Quantum machine learning seeks to leverage
quantum computers to improve upon classical machine learning
algorithms. Currently, robust uncertainty quantification methods remain underdeveloped in the
quantum domain, despite the critical need for reliable and trustworthy predictions. Recent work has introduced
quantum conformal prediction, a framework that produces prediction sets that are guaranteed to contain the true outcome with a user-specified probability. In this work, we formalise how the time-varying noise inherent in
quantum processors can undermine conformal guarantees, even when calibration and test data are exchangeable. To address this challenge, we draw on Adaptive Conformal Inference, a method which maintains validity over time via repeated recalibration. We introduce Adaptive
Quantum Conformal Prediction (AQCP), an
algorithm which provides asymptotic average coverage guarantees under arbitrary hardware noise conditions. Empirical studies on an IBM
quantum processor demonstrate that AQCP achieves the target coverage level and exhibits greater stability than
quantum conformal prediction.
Read the full abstract ▾