pwc-archive/papers-with-abstracts huggingface dataset:
Statistical Inference in Reinforcement Learning: A Selective Survey
Authors: Chengchun Shi
Date: 2025-02-22 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Survey

Reinforcement learning (RL) is concerned with how intelligence agents take actions in a given environment to maximize the cumulative reward they receive. In healthcare, applying RL algorithms could assist patients in improving their health status. In ride-sharing platforms, applying RL algorithms could increase drivers' income and customer satisfaction. For large language models, applying RL algorithms could align their outputs with human preferences. Over the past decade, RL has been arguably one of the most vibrant research frontiers in machine learning. Nevertheless, statistics as a field, as opposed to computer science, has only recently begun to engage with RL both in depth and in breadth. This chapter presents a selective review of statistical inferential tools for RL, covering both hypothesis testing and confidence interval construction. Our goal is to highlight the value of statistical inference in RL for both the statistics and machine learning communities, and to promote the broader application of classical statistical inference tools in this vibrant area of research.
Rectifying Conformity Scores for Better Conditional Coverage
Authors: Vincent Plassier, Alexander Fishkov, Victor Dheur, Mohsen Guizani, Souhaib Ben Taieb, Maxim Panov, Eric Moulines
Date: 2025-02-22 00:00:00
Tasks: Conformal Prediction, quantile regression

We present a new method for generating confidence sets within the split conformal prediction framework. Our method performs a trainable transformation of any given conformity score to improve conditional coverage while ensuring exact marginal coverage. The transformation is based on an estimate of the conditional quantile of conformity scores. The resulting method is particularly beneficial for constructing adaptive confidence sets in multi-output problems where standard conformal quantile regression approaches have limited applicability. We develop a theoretical bound that captures the influence of the accuracy of the quantile estimate on the approximate conditional validity, unlike classical bounds for conformal prediction methods that only offer marginal coverage. We experimentally show that our method is highly adaptive to the local data structure and outperforms existing methods in terms of conditional coverage, improving the reliability of statistical inference in various applications.
Subspace Recovery in Winsorized PCA: Insights into Accuracy and Robustness
Authors: Sangil Han, Kyoowon Kim, Sungkyu Jung
Date: 2025-02-23 00:00:00

In this paper, we explore the theoretical properties of subspace recovery using Winsorized Principal Component Analysis (WPCA), utilizing a common data transformation technique that caps extreme values to mitigate the impact of outliers. Despite the widespread use of winsorization in various tasks of multivariate analysis, its theoretical properties, particularly for subspace recovery, have received limited attention. We provide a detailed analysis of the accuracy of WPCA, showing that increasing the number of samples while decreasing the proportion of outliers guarantees the consistency of the sample subspaces from WPCA with respect to the true population subspace. Furthermore, we establish perturbation bounds that ensure the WPCA subspace obtained from contaminated data remains close to the subspace recovered from pure data. Additionally, we extend the classical notion of breakdown points to subspace-valued statistics and derive lower bounds for the breakdown points of WPCA. Our analysis demonstrates that WPCA exhibits strong robustness to outliers while maintaining consistency under mild assumptions. A toy example is provided to numerically illustrate the behavior of the upper bounds for perturbation bounds and breakdown points, emphasizing winsorization's utility in subspace recovery.
Variable transformations in consistent loss functions
Authors: Hristos Tyralis, Georgia Papacharalampous
Date: 2025-02-23 00:00:00

Loss functions constructed by applying transformations to the realization and prediction variables of (strictly) consistent loss functions have been extensively studied empirically, yet their theoretical foundations remain unexplored. To address this gap, we establish formal characterizations of (strict) consistency for such transformed loss functions and their corresponding elicitable functionals. Our analysis focuses on two interrelated cases: (a) transformations applied solely to the realization variable and (b) bijective transformations applied jointly to both the realization and prediction variables. These cases extend the well-established framework of transformations applied exclusively to the prediction variable, as formalized by Osband's revelation principle. We further develop analogous characterizations for (strict) identification functions. The resulting theoretical framework is broadly applicable to statistical and machine learning methodologies. When applied to Bregman and expectile loss functions, our framework enables two key advancements: (a) the interpretation of empirical findings from models trained with transformed loss functions and (b) the systematic construction of novel identifiable and elicitable functionals, including the g-transformed expectation and g-transformed expectile. By unifying theoretical insights with practical applications, this work advances principled methodologies for designing loss functions in complex predictive tasks. Applications of the framework to simulated and real-world data illustrate its practical utility in diverse settings.
Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning
Authors: Yang Xu, Washim Uddin Mondal, Vaneet Aggarwal
Date: 2025-02-24 00:00:00
Tasks: Learning Theory

We present the first finite-sample analysis for policy evaluation in robust average-reward Markov Decision Processes (MDPs). Prior works in this setting have established only asymptotic convergence guarantees, leaving open the question of sample complexity. In this work, we address this gap by establishing that the robust Bellman operator is a contraction under the span semi-norm, and developing a stochastic approximation framework with controlled bias. Our approach builds upon Multi-Level Monte Carlo (MLMC) techniques to estimate the robust Bellman operator efficiently. To overcome the infinite expected sample complexity inherent in standard MLMC, we introduce a truncation mechanism based on a geometric distribution, ensuring a finite constant sample complexity while maintaining a small bias that decays exponentially with the truncation level. Our method achieves the order-optimal sample complexity of $\tilde{\mathcal{O}}(\epsilon^{-2})$ for robust policy evaluation and robust average reward estimation, marking a significant advancement in robust reinforcement learning theory.
Provable Benefits of Unsupervised Pre-training and Transfer Learning via Single-Index Models
Authors: Taj Jones-McCormick, Aukosh Jagannath, Subhabrata Sen
Date: 2025-02-24 00:00:00
Tasks: Transfer Learning, Unsupervised Pre-training

Unsupervised pre-training and transfer learning are commonly used techniques to initialize training algorithms for neural networks, particularly in settings with limited labeled data. In this paper, we study the effects of unsupervised pre-training and transfer learning on the sample complexity of high-dimensional supervised learning. Specifically, we consider the problem of training a single-layer neural network via online stochastic gradient descent. We establish that pre-training and transfer learning (under concept shift) reduce sample complexity by polynomial factors (in the dimension) under very general assumptions. We also uncover some surprising settings where pre-training grants exponential improvement over random initialization in terms of sample complexity.
Your Assumed DAG is Wrong and Here's How To Deal With It
Authors: Kirtan Padh, Zhufeng Li, Cecilia Casolo, Niki Kilbertus
Date: 2025-02-24 00:00:00
Tasks: Causal Discovery, valid

Assuming a directed acyclic graph (DAG) that represents prior knowledge of causal relationships between variables is a common starting point for cause-effect estimation. Existing literature typically invokes hypothetical domain expert knowledge or causal discovery algorithms to justify this assumption. In practice, neither may propose a single DAG with high confidence. Domain experts are hesitant to rule out dependencies with certainty or have ongoing disputes about relationships; causal discovery often relies on untestable assumptions itself or only provides an equivalence class of DAGs and is commonly sensitive to hyperparameter and threshold choices. We propose an efficient, gradient-based optimization method that provides bounds for causal queries over a collection of causal graphs -- compatible with imperfect prior knowledge -- that may still be too large for exhaustive enumeration. Our bounds achieve good coverage and sharpness for causal queries such as average treatment effects in linear and non-linear synthetic settings as well as on real-world data. Our approach aims at providing an easy-to-use and widely applicable rebuttal to the valid critique of `What if your assumed DAG is wrong?'.
Random Projections and Natural Sparsity in Time-Series Classification: A Theoretical Analysis
Authors: Jorge Marco-Blanco, Rubén Cuevas
Date: 2025-02-24 00:00:00
Tasks: Activity Recognition, compressed sensing, Computational Efficiency, Human Activity Recognition, Medical Diagnosis, Time Series, Time Series Classification

Time-series classification is essential across diverse domains, including medical diagnosis, industrial monitoring, financial forecasting, and human activity recognition. The Rocket algorithm has emerged as a simple yet powerful method, achieving state-of-the-art performance through random convolutional kernels applied to time-series data, followed by non-linear transformation. Its architecture approximates a one-hidden-layer convolutional neural network while eliminating parameter training, ensuring computational efficiency. Despite its empirical success, fundamental questions about its theoretical foundations remain unexplored. We bridge theory and practice by formalizing Rocket's random convolutional filters within the compressed sensing framework, proving that random projections preserve discriminative patterns in time-series data. This analysis reveals relationships between kernel parameters and input signal characteristics, enabling more principled approaches to algorithm configuration. Moreover, we demonstrate that its non-linearity, based on the proportion of positive values after convolutions, expresses the inherent sparsity of time-series data. Our theoretical investigation also proves that Rocket satisfies two critical conditions: translation invariance and noise robustness. These findings enhance interpretability and provide guidance for parameter optimization in extreme cases, advancing both theoretical understanding and practical application of time-series classification.
On Quantile Regression Forests for Modelling Mixed-Frequency and Longitudinal Data
Authors: Mila Andreani
Date: 2025-02-24 00:00:00
Tasks: quantile regression, regression

The aim of this thesis is to extend the applications of the Quantile Regression Forest (QRF) algorithm to handle mixed-frequency and longitudinal data. To this end, standard statistical approaches have been exploited to build two novel algorithms: the Mixed- Frequency Quantile Regression Forest (MIDAS-QRF) and the Finite Mixture Quantile Regression Forest (FM-QRF). The MIDAS-QRF combines the flexibility of QRF with the Mixed Data Sampling (MIDAS) approach, enabling non-parametric quantile estimation with variables observed at different frequencies. FM-QRF, on the other hand, extends random effects machine learning algorithms to a QR framework, allowing for conditional quantile estimation in a longitudinal data setting. The contributions of this dissertation lie both methodologically and empirically. Methodologically, the MIDAS-QRF and the FM-QRF represent two novel approaches for handling mixed-frequency and longitudinal data in QR machine learning framework. Empirically, the application of the proposed models in financial risk management and climate-change impact evaluation demonstrates their validity as accurate and flexible models to be applied in complex empirical settings.
Differential privacy guarantees of Markov chain Monte Carlo algorithms
Authors: Andrea Bertazzi, Tim Johnston, Gareth O. Roberts, Alain Durmus
Date: 2025-02-24 00:00:00
Tasks: Privacy Preserving

This paper aims to provide differential privacy (DP) guarantees for Markov chain Monte Carlo (MCMC) algorithms. In a first part, we establish DP guarantees on samples output by MCMC algorithms as well as Monte Carlo estimators associated with these methods under assumptions on the convergence properties of the underlying Markov chain. In particular, our results highlight the critical condition of ensuring the target distribution is differentially private itself. In a second part, we specialise our analysis to the unadjusted Langevin algorithm and stochastic gradient Langevin dynamics and establish guarantees on their (R\'enyi) DP. To this end, we develop a novel methodology based on Girsanov's theorem combined with a perturbation trick to obtain bounds for an unbounded domain and in a non-convex setting. We establish: (i) uniform in $n$ privacy guarantees when the state of the chain after $n$ iterations is released, (ii) bounds on the privacy of the entire chain trajectory. These findings provide concrete guidelines for privacy-preserving MCMC.
Linear Bandits on Ellipsoids: Minimax Optimal Algorithms
Authors: Raymond Zhang, Hedi Hadiji, Richard Combes
Date: 2025-02-24 00:00:00

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

Machine Unlearning (MU) aims at removing the influence of specific data points from a trained model, striving to achieve this at a fraction of the cost of full model retraining. In this paper, we analyze the efficiency of unlearning methods and establish the first upper and lower bounds on minimax computation times for this problem, characterizing the performance of the most efficient algorithm against the most difficult objective function. Specifically, for strongly convex objective functions and under the assumption that the forget data is inaccessible to the unlearning method, we provide a phase diagram for the unlearning complexity ratio -- a novel metric that compares the computational cost of the best unlearning method to full model retraining. The phase diagram reveals three distinct regimes: one where unlearning at a reduced cost is infeasible, another where unlearning is trivial because adding noise suffices, and a third where unlearning achieves significant computational advantages over retraining. These findings highlight the critical role of factors such as data dimensionality, the number of samples to forget, and privacy constraints in determining the practical feasibility of unlearning.
A Refined Analysis of UCBVI
Authors: Simone Drago, Marco Mussi, Alberto Maria Metelli
Date: 2025-02-24 00:00:00

In this work, we provide a refined analysis of the UCBVI algorithm (Azar et al., 2017), improving both the bonus terms and the regret analysis. Additionally, we compare our version of UCBVI with both its original version and the state-of-the-art MVP algorithm. Our empirical validation demonstrates that improving the multiplicative constants in the bounds has significant positive effects on the empirical performance of the algorithms.
Function-Space Learning Rates
Authors: Edward Milsom, Ben Anson, Laurence Aitchison
Date: 2025-02-24 00:00:00

We consider layerwise function-space learning rates, which measure the magnitude of the change in a neural network's output function in response to an update to a parameter tensor. This contrasts with traditional learning rates, which describe the magnitude of changes in parameter space. We develop efficient methods to measure and set function-space learning rates in arbitrary neural networks, requiring only minimal computational overhead through a few additional backward passes that can be performed at the start of, or periodically during, training. We demonstrate two key applications: (1) analysing the dynamics of standard neural network optimisers in function space, rather than parameter space, and (2) introducing FLeRM (Function-space Learning Rate Matching), a novel approach to hyperparameter transfer across model scales. FLeRM records function-space learning rates while training a small, cheap base model, then automatically adjusts parameter-space layerwise learning rates when training larger models to maintain consistent function-space updates. FLeRM gives hyperparameter transfer across model width, depth, initialisation scale, and LoRA rank in various architectures including MLPs with residual connections and transformers with different layer normalisation schemes.
Universality of High-Dimensional Logistic Regression and a Novel CGMT under Dependence with Applications to Data Augmentation
Authors: Matthew Esmaili Mallory, Kevin Han Huang, Morgane Austern
Date: 2025-02-10 00:00:00
Tasks: Data Augmentation

Over the last decade, a wave of research has characterized the exact asymptotic risk of many high-dimensional models in the proportional regime. Two foundational results have driven this progress: Gaussian universality, which shows that the asymptotic risk of estimators trained on non-Gaussian and Gaussian data is equivalent, and the convex Gaussian min-max theorem (CGMT), which characterizes the risk under Gaussian settings. However, these results rely on the assumption that the data consists of independent random vectors--an assumption that significantly limits its applicability to many practical setups. In this paper, we address this limitation by generalizing both results to the dependent setting. More precisely, we prove that Gaussian universality still holds for high-dimensional logistic regression under block dependence, $m$-dependence and special cases of mixing, and establish a novel CGMT framework that accommodates for correlation across both the covariates and observations. Using these results, we establish the impact of data augmentation, a widespread practice in deep learning, on the asymptotic risk.
Financial fraud detection system based on improved random forest and gradient boosting machine (GBM)
Authors: Tianzuo Hu
Date: 2025-02-20 00:00:00
Tasks: Computational Efficiency, Ensemble Learning, feature selection, Fraud Detection

This paper proposes a financial fraud detection system based on improved Random Forest (RF) and Gradient Boosting Machine (GBM). Specifically, the system introduces a novel model architecture called GBM-SSRF (Gradient Boosting Machine with Simplified and Strengthened Random Forest), which cleverly combines the powerful optimization capabilities of the gradient boosting machine (GBM) with improved randomization. The computational efficiency and feature extraction capabilities of the Simplified and Strengthened Random Forest (SSRF) forest significantly improve the performance of financial fraud detection. Although the traditional random forest model has good classification capabilities, it has high computational complexity when faced with large-scale data and has certain limitations in feature selection. As a commonly used ensemble learning method, the GBM model has significant advantages in optimizing performance and handling nonlinear problems. However, GBM takes a long time to train and is prone to overfitting problems when data samples are unbalanced. In response to these limitations, this paper optimizes the random forest based on the structure, reducing the computational complexity and improving the feature selection ability through the structural simplification and enhancement of the random forest. In addition, the optimized random forest is embedded into the GBM framework, and the model can maintain efficiency and stability with the help of GBM's gradient optimization capability. Experiments show that the GBM-SSRF model not only has good performance, but also has good robustness and generalization capabilities, providing an efficient and reliable solution for financial fraud detection.
Challenges of Multi-Modal Coreset Selection for Depth Prediction
Authors: Viktor Moskvoretskii, Narek Alvandian
Date: 2025-02-20 00:00:00
Tasks: Depth Estimation, Depth Prediction, Dimensionality Reduction, Prediction

Coreset selection methods are effective in accelerating training and reducing memory requirements but remain largely unexplored in applied multimodal settings. We adapt a state-of-the-art (SoTA) coreset selection technique for multimodal data, focusing on the depth prediction task. Our experiments with embedding aggregation and dimensionality reduction approaches reveal the challenges of extending unimodal algorithms to multimodal scenarios, highlighting the need for specialized methods to better capture inter-modal relationships.
A non-parametric optimal design algorithm for population pharmacokinetics
Authors: Markus Hovd, Alona Kryshchenko, Michael N. Neely, Julian Otalvaro, Alan Schumitzky, Walter M. Yamada
Date: 2025-02-20 00:00:00

This paper introduces a non-parametric estimation algorithm designed to effectively estimate the joint distribution of model parameters with application to population pharmacokinetics. Our research group has previously developed the non-parametric adaptive grid (NPAG) algorithm, which while accurate, explores parameter space using an ad-hoc method to suggest new support points. In contrast, the non-parametric optimal design (NPOD) algorithm uses a gradient approach to suggest new support points, which reduces the amount of time spent evaluating non-relevant points and by this the overall number of cycles required to reach convergence. In this paper, we demonstrate that the NPOD algorithm achieves similar solutions to NPAG across two datasets, while being significantly more efficient in both the number of cycles required and overall runtime. Given the importance of developing robust and efficient algorithms for determining drug doses quickly in pharmacokinetics, the NPOD algorithm represents a valuable advancement in non-parametric modeling. Further analysis is needed to determine which algorithm performs better under specific conditions.