GenAI4ELab/papercli-papers huggingface dataset:
White-Box Transformers via Sparse Rate Reduction: Compression Is All There Is?
Authors: Yaodong Yu; Sam Buchanan; Druv Pai; Tianzhe Chu; Ziyang Wu; Shengbang Tong; Hao Bai; Yuexiang Zhai; Benjamin D. Haeffele; Yi Ma
Venue: JMLR 2024 (main)

Abstract: In this paper, we contend that a natural objective of representation learning is to compress and transform the distribution of the data, say sets of tokens, towards a low-dimensional Gaussian mixture supported on incoherent subspaces. The goodness of such a representation can be evaluated by a principled measure, called sparse rate reduction, that simultaneously maximizes the intrinsic information gain and extrinsic sparsity of the learned representation. From this perspective, popular deep network architectures, including transformers, can be viewed as realizing iterative schemes to optimize this measure. Particularly, we derive a transformer block from alternating optimization on parts of this objective: the multi-head self-attention operator compresses the representation by implementing an approximate gradient descent step on the coding rate of the features, and the subsequent multi-layer perceptron sparsifies the features. This leads to a family of white-box transformer-like deep network architectures, named CRATE, which are mathematically fully interpretable. We show, by way of a novel connection between denoising and compression, that the inverse to the aforementioned compressive encoding can be realized by the same class of CRATE architectures. Thus, the so-derived white-box architectures are universal to both encoders and decoders. Experiments show that these networks, despite their simplicity, indeed learn to compress and sparsify representations of large-scale real-world image and text datasets, and achieve strong performance across different settings: ViT, MAE, DINO, BERT, and GPT2. We believe the proposed computational framework demonstrates great potential in bridging the gap between theory and practice of deep learning, from a unified perspective of data compression.
RLtools: A Fast, Portable Deep Reinforcement Learning Library for Continuous Control
Authors: Jonas Eschmann; Dario Albani; Giuseppe Loianno
Venue: JMLR 2024 (main)

Abstract: Deep Reinforcement Learning (RL) can yield capable agents and control policies in several domains but is commonly plagued by prohibitively long training times. Additionally, in the case of continuous control problems, the applicability of learned policies on real-world embedded devices is limited due to the lack of real-time guarantees and portability of existing libraries. 
To address these challenges, we present RLtools, a dependency-free, header-only, pure C++ library for deep supervised and reinforcement learning.
Its novel architecture allows RLtools to be used on a wide variety of platforms, from HPC clusters over workstations and laptops to smartphones, smartwatches, and microcontrollers. 
Specifically, due to the tight integration of the RL algorithms with simulation environments, RL can solve popular RL problems up to 76 times faster than other popular RL frameworks.
We also benchmark the inference on a diverse set of microcontrollers and show that in most cases our optimized implementation is by far the fastest. Finally, RLtools enables the first-ever demonstration of training a deep RL algorithm directly on a microcontroller, giving rise to the field of TinyRL. 
The source code as well as documentation and live demos are available through our project page at https://rl.tools.
Identifying Causal Eï¬ects using Instrumental Time Series: Nuisance IV and Correcting for the Past
Authors: Nikolaj Thams; Rikke SÃ¸ndergaard; Sebastian Weichwald; Jonas Peters
Venue: JMLR 2024 (main)

Abstract: Instrumental variable (IV) regression relies on instruments to infer causal eï¬ects from observational data with unobserved confounding. We consider IV regression in time series models, such as vector auto-regressive (VAR) processes. Direct applications of i.i.d. techniques are generally inconsistent as they do not correctly adjust for dependencies in the past. In this paper, we outline the diï¬culties that arise due to time structure and propose methodology for constructing identifying equations that can be used for consistent parametric estimation of causal eï¬ects in time series data. One method uses extra nuisance covariates to obtain identifiability (an idea that can be of interest even in the i.i.d. case). We further propose a graph marginalization framework that allows us to apply nuisance IV and other IV methods in a principled way to time series. Our methods make use of a version of the global Markov property, which we prove holds for VAR(p) processes. For VAR(1) processes, we prove identifiability conditions that relate to Jordan forms and are diï¬erent from the well-known rank conditions in the i.i.d. case (they do not require as many instruments as covariates, for example). We provide methods, prove their consistency, and show how the inferred causal eï¬ect can be used for distribution generalization. Simulation experiments corroborate our theoretical results. We provide ready-to-use Python code.
Instrumental Variable Value Iteration for Causal Offline Reinforcement Learning
Authors: Luofeng Liao; Zuyue Fu; Zhuoran Yang; Yixin Wang; Dingli Ma; Mladen Kolar; Zhaoran Wang
Venue: JMLR 2024 (main)

Abstract: In offline reinforcement learning (RL) an optimal policy is learned solely from a priori collected observational data. However, in observational data, actions are often confounded by unobserved variables. Instrumental variables (IVs), in the context of RL, are the variables whose influence on the state variables is all mediated by the action. When a valid instrument is present, we can recover the confounded transition dynamics through observational data. We study a confounded Markov decision process where the transition dynamics admit an additive nonlinear functional form. Using IVs, we derive a conditional moment restriction through which we can identify transition dynamics based on observational data. We propose a provably efficient IV-aided Value Iteration (IVVI) algorithm based on a primal-dual reformulation of the conditional moment restriction. To our knowledge, this is the first provably efficient algorithm for instrument-aided offline RL.
Sparse Recovery With Multiple Data Streams: An Adaptive Sequential Testing Approach
Authors: Weinan Wang; Bowen Gang; Wenguang Sun
Venue: JMLR 2024 (main)

Abstract: Multistage design has been utilized across a variety of scientific fields, enabling the adaptive allocation of sensing resources to effectively eliminate null locations and localize signals. We present a decision-theoretic framework for multi-stage adaptive testing that minimizes the total number of measurements while ensuring pre-specified constraints on both the false positive rate (FPR) and the missed discovery rate (MDR). Our method, SMART, explicitly addresses the often-overlooked aspect of uncertainty quantification in machine learning algorithms, incorporating it at every decision stage. This enables SMART to respond adaptively to important patterns in the data streams, adjusting its decisions based on the strength of evidence at specific locations. By leveraging technical tools and key concepts from multiple testing, adaptive thresholding, and compound decision theory, SMART not only enhances the aggregation of information across individual tests but also allows for varying thresholds tailored to the observed data, thereby ensuring effective error rate control and resulting in significant savings on total study costs. Through comprehensive analyses of large-scale A/B tests, high-throughput screening, and image analysis, we demonstrate that our approach yields substantial efficiency gains and improved control over error rates compared to existing methodologies.
Pure Differential Privacy for Functional Summaries with a Laplace-like Process
Authors: Haotian Lin; Matthew Reimherr
Venue: JMLR 2024 (main)

Abstract: Many existing mechanisms for achieving differential privacy (DP) on infinite-dimensional functional summaries typically involve embedding these functional summaries into finite-dimensional subspaces and applying traditional multivariate DP techniques. These mechanisms generally treat each dimension uniformly and struggle with complex, structured summaries. This work introduces a novel mechanism to achieve pure DP for functional summaries in a separable infinite-dimensional Hilbert space, named the Independent Component Laplace Process (ICLP) mechanism. This mechanism treats the summaries of interest as truly infinite-dimensional functional objects, thereby addressing several limitations of the existing mechanisms. Several statistical estimation problems are considered, and we demonstrate how one can enhance the utility of private summaries by oversmoothing the non-private counterparts. Numerical experiments on synthetic and real datasets demonstrate the effectiveness of the proposed mechanism.
Stochastic Regularized Majorization-Minimization with weakly convex and multi-convex surrogates
Authors: Hanbaek Lyu
Venue: JMLR 2024 (main)

Abstract: Stochastic majorization-minimization (SMM) is a class of stochastic optimization algorithms that proceed by sampling new data points and minimizing a  recursive average of surrogate functions of an objective function. The surrogates are required to be strongly convex and the existing convergence rate analysis for the general non-convex setting was not available.  In this paper, we propose an extension of SMM where surrogates are allowed to be only weakly convex or block multi-convex, and the averaged surrogates are approximately minimized with proximal regularization or block-minimized within diminishing radii, respectively. For the general nonconvex constrained setting with non-i.i.d. data samples,  we show that the first-order optimality gap of the proposed algorithm decays at the rate $\widetilde{O}(n^{-1/4})$ for the empirical loss and $\widetilde{O}(n^{-1/8})$ for the expected loss, where $n$ denotes the number of data samples processed. Under some additional assumption, the latter convergence rate can be improved to $\widetilde{O}(n^{-1/4})$. As a corollary, we obtain the first convergence rate bounds for various optimization methods under general nonconvex non-i.i.d. data setting: Double-averaging projected gradient descent and its generalizations, proximal point empirical risk minimization,  and online matrix/tensor decomposition algorithms. We also provide experimental validation of our results.
Non-Euclidean Monotone Operator Theory and Applications
Authors: Alexander Davydov; Saber Jafarpour; Anton V. Proskurnikov; Francesco Bullo
Venue: JMLR 2024 (main)

Abstract: While monotone operator theory is often studied on Hilbert spaces, many interesting problems in machine learning and optimization arise naturally in finite-dimensional vector spaces endowed with non-Euclidean norms, such as diagonally-weighted $\ell_{1}$ or $\ell_{\infty}$ norms. This paper provides a natural generalization of monotone operator theory to finite-dimensional non-Euclidean spaces. The key tools are weak pairings and logarithmic norms. We show that the resolvent and reflected resolvent operators of non-Euclidean monotone mappings exhibit similar properties to their counterparts in Hilbert spaces. Furthermore, classical iterative methods and splitting methods for finding zeros of monotone operators are shown to converge in the non-Euclidean case. We apply our theory to equilibrium computation and Lipschitz constant estimation of recurrent neural networks, obtaining novel iterations and tighter upper bounds via forward-backward splitting.
Matryoshka Policy Gradient for Entropy-Regularized RL: Convergence and Global Optimality
Authors: FranÃ§ois G. Ged; Maria Han Veiga
Venue: JMLR 2024 (main)

Abstract: A novel Policy Gradient (PG) algorithm, called Matryoshka Policy Gradient (MPG), is introduced and studied, in the context of fixed-horizon max-entropy reinforcement learning, where an agent aims at maximizing entropy bonuses additional to its cumulative rewards.
In the linear function approximation setting with softmax policies, we prove uniqueness and characterize the optimal policy of the entropy regularized objective, together with global convergence of MPG.
These results are proved in the case of continuous state and action space.
MPG is intuitive, theoretically sound and we furthermore show that the optimal policy of the infinite horizon max-entropy objective can be approximated arbitrarily well by the optimal policy of the MPG framework.
Finally, we provide a criterion for global optimality when the policy is parametrized by a neural network in terms of the neural tangent kernel at convergence.
As a proof of concept, we evaluate numerically MPG on standard test benchmarks.
Spectral Regularized Kernel Goodness-of-Fit Tests
Authors: Omar Hagrass; Bharath K. Sriperumbudur; Bing Li
Venue: JMLR 2024 (main)

Abstract: Maximum mean discrepancy (MMD) has enjoyed a lot of success in many machine learning and statistical applications, including non-parametric hypothesis testing, because of its ability to handle non-Euclidean data. Recently, it has been demonstrated in Balasubramanian et al. (2021) that the goodness-of-fit test based on MMD is not minimax optimal while a Tikhonov regularized version of it is, for an appropriate choice of the regularization parameter. However, the results in Balasubramanian et al. (2021) are obtained under the restrictive assumptions of the mean element being zero, and the uniform boundedness condition on the eigenfunctions of the integral operator. Moreover, the test proposed in Balasubramanian et al. (2021) is not practical as it is not computable for many kernels. In this paper, we address these shortcomings and extend the results to general spectral regularizers that include Tikhonov regularization.
Causal Discovery with Generalized Linear Models through Peeling Algorithms
Authors: Minjie Wang; Xiaotong Shen; Wei Pan
Venue: JMLR 2024 (main)

Abstract: This article presents a novel method for causal discovery with generalized structural equation models suited for analyzing diverse types of outcomes, including discrete, continuous, and mixed data. Causal discovery often faces challenges due to unmeasured confounders that hinder the identification of causal relationships. The proposed approach addresses this issue by developing two peeling algorithms (bottom-up and top-down) to ascertain causal relationships and valid instruments. This approach first reconstructs a super-graph to represent ancestral relationships between variables, using a peeling algorithm based on nodewise GLM regressions that exploit relationships between primary and instrumental variables. Then, it estimates parent-child effects from the ancestral relationships using another peeling algorithm while deconfounding a child's model with information borrowed from its parents' models. The article offers a theoretical analysis of the proposed approach, establishing conditions for model identifiability and providing statistical guarantees for accurately discovering parent-child relationships via the peeling algorithms. Furthermore, the article presents numerical experiments showcasing the effectiveness of our approach in comparison to state-of-the-art structure learning methods without confounders. Lastly, it demonstrates an application to Alzheimer's disease (AD), highlighting the method's utility in constructing gene-to-gene and gene-to-disease regulatory networks involving Single Nucleotide Polymorphisms (SNPs) for healthy and AD subjects.
Estimating the Replication Probability of Significant Classification Benchmark Experiments
Authors: Daniel Berrar
Venue: JMLR 2024 (main)

Abstract: A fundamental question in machine learning is: "What are the chances that a statistically significant result will replicate?" The standard framework of null hypothesis significance testing, however, cannot answer this question directly. In this work, we derive formulas for estimating the replication probability that are applicable in two of the most widely used experimental designs in machine learning: the comparison of two classifiers over multiple benchmark datasets and the comparison of two classifiers in k-fold cross-validation. Using simulation studies, we show that p-values just below the common significance threshold of 0.05 are insufficient to warrant a high confidence in the replicability of significant results, as such p-values are barely more informative than the flip of a coin. If a replication probability of around 0.95 is desired, then the significance threshold should be lowered to at least 0.003. This observation might explain, at least in part, why many published research findings fail to replicate.
Just Wing It: Near-Optimal Estimation of Missing Mass in a Markovian Sequence
Authors: Ashwin Pananjady; Vidya Muthukumar; Andrew Thangaraj
Venue: JMLR 2024 (main)

Abstract: We study the problem of estimating the stationary mass---also called the unigram mass---that is missing from a single trajectory of a discrete-time, ergodic Markov chain. This problem has several applications---for example, estimating the stationary missing mass is critical for accurately smoothing probability estimates in sequence models. While the classical Good--Turing estimator from the 1950s has appealing properties for i.i.d. data, it is known to be biased in the Markovian setting, and other heuristic estimators do not come equipped with guarantees. Operating in the general setting in which the size of the state space may be much larger than the length $n$ of the trajectory, we develop a linear-runtime estimator called Windowed Good--Turing (WingIt) and show that its risk decays as $\widetilde{O}(\mathsf{T_{mix}}/n)$, where $\mathsf{T_{mix}}$ denotes the mixing time of the chain in total variation distance. Notably, this rate is independent of the size of the state space and minimax-optimal up to a logarithmic factor in $n / \mathsf{T_{mix}}$. We also present an upper bound on the variance of the missing mass random variable, which may be of independent interest. We extend our estimator to approximate the stationary mass placed on elements occurring with small frequency in the trajectory.  Finally, we demonstrate the efficacy of our estimators both in simulations on canonical chains and on sequences constructed from natural language text.
Data-Efficient Policy Evaluation Through Behavior Policy Search
Authors: Josiah P. Hanna; Yash Chandak; Philip S. Thomas; Martha White; Peter Stone; Scott Niekum
Venue: JMLR 2024 (main)

Abstract: We consider the task of evaluating a policy for a Markov decision process (MDP). The standard unbiased technique for evaluating a policy is to deploy the policy and observe its performance. We show that the data collected from deploying a different policy, commonly called the behavior policy, can be used to produce unbiased estimates with lower mean squared error than this standard technique. We derive an analytic expression for a minimal variance behavior policy -- a behavior policy that minimizes the mean squared error of the resulting estimates. Because this expression depends on terms that are unknown in practice, we propose a novel policy evaluation sub-problem, behavior policy search: searching for a behavior policy that reduces mean squared error. We present two behavior policy search algorithms and empirically demonstrate their effectiveness in lowering the mean squared error of policy performance estimates.
Optimal Learning Policies for Differential Privacy in Multi-armed Bandits
Authors: Siwei Wang; Jun Zhu
Venue: JMLR 2024 (main)

Abstract: This paper studies the multi-armed bandit problem with a requirement of differential privacy guarantee or global differential privacy guarantee. We first prove that, the lower bound for the extra regret to protect $(\epsilon,\delta)$-global differential privacy is $\Omega({N\over \epsilon }\log {(e^{\epsilon} -1)T + \delta T \over (e^{\epsilon}-1) + \delta T})$ ($N$ is the number of arms and $T$ is the time horizon), which is independent with $T$ for $\delta > 0$ and large enough $T$. Moreover, the lower bound for the extra regret to protect $(\epsilon,\delta)$-differential privacy can be no more than the above bound. This means that, different with the case $\delta = 0$, it is possible to design algorithms that protect privacy and achieve the same asymptotical regret upper bound as the non-private algorithms when $\delta > 0$. Then we adapt the Follow the Perturbed Leader (FTPL) framework, and propose learning policies with both Gaussian and Beta perturbed distributions (DP-FTPL-Gauss and DP-FTPL-Beta) to protect $(\epsilon,\delta)$-differential privacy. The analysis shows that they achieve an $O({N\log T\over \Delta_{\min}} + N \min\{{1\over \delta^2}, {1\over \epsilon^2}\log{1\over \delta}\})$ regret upper bound, where $\Delta_{\min}$ is the minimum expected reward gap between the optimal arm and any other ones. We also design a unique perturbed distribution to protect $(\epsilon,\delta)$-differential privacy in the FTPL framework (DP-FTPL-New), which reduces the regret upper bound to $O({N\log T\over \Delta_{\min}} + {N\over \epsilon }\log {(e^{\epsilon} -1)T + \delta T \over (e^{\epsilon}-1) + \delta T})$. We further show that this perturbed distribution could also be used to protect $(\epsilon,\delta)$-global differential privacy, and design a corresponding algorithm GDP-Elim-New. We show that its regret upper bound is  $O({\Delta_{\max} \over \Delta_{\min}}({N\log T\over \Delta_{\min}} + {N\over \epsilon }\log {(e^{\epsilon} -1)T + \delta T \over (e^{\epsilon}-1) + \delta T}))$. This shows that our $\Omega({N\over \epsilon }\log {(e^{\epsilon} -1)T + \delta T \over (e^{\epsilon}-1) + \delta T})$ regret lower bound is tight (e.g. when ${\Delta_{\max}\over \Delta_{\min}}$ is bounded).
Debiasing Evaluations That Are Biased by Evaluations
Authors: Jingyan Wang; Ivan Stelmakh; Yuting Wei; Nihar Shah
Venue: JMLR 2024 (main)

Abstract: It is common to evaluate a set of items by soliciting people to rate them. For example, universities ask students to rate the teaching quality of their instructors, and conference organizers ask authors of submissions to evaluate the quality of the reviews. However, in these applications, students often give a higher rating to a course if they receive higher grades in a course, and authors often give a higher rating to the reviews if their papers are accepted to the conference. In this work, we call these external factors the "outcome" experienced by people, and consider the problem of mitigating these outcome-induced biases in the given ratings when some information about the outcome is available. We formulate the information about the outcome as a known partial ordering on the bias. We propose a debiasing method by solving a regularized optimization problem under this ordering constraint, and also provide a carefully designed cross-validation method that adaptively chooses the appropriate amount of regularization. We provide theoretical guarantees on the performance of our algorithm, as well as experimental evaluations.