We introduce a novel incremental decision tree learning algorithm, Hoeffding Anytime Tree, that is statistically more efficient than the current state-of-the-art, Hoeffding Tree. We demonstrate that an implementation of Hoeffding Anytime Tree---"Extremely Fast Decision Tree", a minor modification to the MOA implementat…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “Hoeffding”
HATT improves online decision tree ensembles by using a more eager splitting strategy.
problem Improving the efficiency of online decision tree ensembles.
method Replacing Hoeffding Tree's split strategy with HATT, which uses the Hoeffding Test for candidate splits.
result HATT outperforms Hoeffding Tree in online bagging and boosting ensembles, as shown by significant performance improvements in various testbenches.
The paper extends Hoeffding's inequality for Markov chains using a generalized concentrability condition.
problem Applying Hoeffding's inequality to non-ergodic Markov chains.
method Integrates generalized concentrability condition via IPM to extend traditional hypotheses.
result Demonstrates utility in machine learning applications such as empirical risk minimization and bandits.
Trading strategy uses Hoeffding's Inequality to predict financial regime change.
problem Predicting financial regime change for trading strategies.
method Applies Hoeffding's Inequality to trading performance data.
result Early warning of financial regime change can be detected.
Tree Ensemble Explainability through the Hoeffding Functional Decomposition and TreeHFD Algorithmstat.ML
TreeHFD algorithm explains tree ensemble models through hierarchical orthogonality.
problem Difficulty in explaining black-box tree ensemble models.
method TreeHFD algorithm using hierarchical orthogonality constraints.
result TreeHFD estimates Hoeffding decomposition from data samples.
Generalizes Hoeffding's decomposition for dependent inputs under mild conditions.
problem Performing global sensitivity analysis on black-box models with dependent inputs.
method Proposes a novel framework based on probability theory, functional analysis, and combinatorics to handle dependencies.
result Any square-integrable, real-valued function of random elements with mild dependence assumptions can be uniquely additively decomposed.
New unbiased variance estimator for random forests using Hoeffding decomposition.
problem Uncertainty quantification in random forests with large kernel sizes and small sample sizes.
method Proposes a new Hoeffding decomposition view for variance estimation, establishing unbiased estimators and ratio consistency.
result Establishes the ratio consistency of the proposed variance estimator, justifying confidence interval coverage rates.
Machine learning software accounts for a significant amount of energy consumed in data centers. These algorithms are usually optimized towards predictive performance, i.e. accuracy, and scalability. This is the case of data stream mining algorithms. Although these algorithms are adaptive to the incoming data, they have…
Paper proposes a new confidence dimension to measure DNN generalization.
problem Measuring the generalization ability of deep neural networks is challenging.
method Introduces confidence dimension (CD) based on Hoeffding's inequality and VC-dimension.
result CD provides a feasible framework to calculate the upper bound of generalization.
Motivated by applications in model-free finance and quantitative risk management, we consider Fréchet classes of multivariate distribution functions where additional information on the joint distribution is assumed, while uncertainty in the marginals is also possible. We derive optimal transport duality results for the…
A Hoeffding Inequality for Finite State Markov Chains and its Applications to Markovian Banditsmath.ST
This paper develops a Hoeffding inequality for the partial sums , where is an irreducible Markov chain on a finite state space , and is a real-valued function. Our bound is simple, general, since it only assumes irreducibility and finiteness…
HCBM improves deep learning explainability by non-linear concept aggregation.
problem Lack of explainable and accurate predictions in deep learning for high-stake decisions.
method Introduce Hoeffding Concept Bottleneck Models (HCBM) using Hoeffding functional decomposition of gradient-boosted trees for non-linear and sparse concept aggregation.
result HCBM outperforms standard linear CBM and is robust to interconcept leakage.
In this paper, we propose an R package, called RKHSMetaMod, that implements a procedure for estimating a meta-model of a complex model. The meta-model approximates the Hoeffding decomposition of the complex model and allows us to perform sensitivity analysis on it. It belongs to a reproducing kernel Hilbert space that …
Under Markovian assumptions, we leverage a Central Limit Theorem (CLT) for the empirical measure in the test statistic of the composite hypothesis Hoeffding test so as to establish weak convergence results for the test statistic, and, thereby, derive a new estimator for the threshold needed by the test. We first show t…
A new method combines multiple bounds and betting strategies for selective prediction, improving risk coverage in data-scarce settings.
problem Selective prediction with risk control in data-scarce domains.
method Combines concentration inequalities, multiple-testing corrections, and betting-based confidence sequences.
result Transfer-Informed Betting achieves tighter bounds and better coverage in data-scarce settings.
Paper develops a new inequality for non-causal machine learning.
problem Current concentration inequalities cannot be applied to non-causal machine learning.
method Develops a framework for non-causal random fields and proves a Hoeffding-type inequality.
result Obtains a Hoeffding-type concentration inequality for non-causal random fields.
Dynamic Model Tree improves online learning for evolving data streams.
problem Effective and transparent machine learning on data streams is challenging.
method Revisit Model Trees for data stream applications, introducing Dynamic Model Tree.
result Dynamic Model Tree reduces the number of splits and outperforms state-of-the-art models.
Paper develops probabilistic bounds for a stochastic gradient algorithm in non-convex problems.
problem Stochastic optimization in non-convex finite sum problems.
method Develops a new dimension-free Azuma-Hoeffding type bound for a martingale difference sequence.
result Empirical results show superior probabilistic performance of Prob-SARAH compared to other algorithms.
Paper refines PAC-Bayes bounds for bandit problems.
problem Improving probabilistic bounds for off-policy learning.
method Optimizes PAC-Bayesian bounds using a new parameter optimization approach.
result Provides two parameter-free PAC-Bayes bounds that nearly match optimal rates.
Concentration inequalities are indispensable tools for studying the generalization capacity of learning models. Hoeffding's and McDiarmid's inequalities are commonly used, giving bounds independent of the data distribution. Although this makes them widely applicable, a drawback is that the bounds can be too loose in so…
Unified method for MMD variance estimation improves accuracy and computational efficiency.
problem Variance estimation for MMD in nonparametric testing.
method Unified finite-sample characterization of MMD variance through U-statistic and Hoeffding decomposition; exact acceleration method for univariate case.
result Unified estimators improve accuracy and computational efficiency for MMD variance.
Beyond Consistency: Inference for the Relative risk functional in Deep Nonparametric Cox Modelsstat.ML
Develops asymptotic theory for deep Cox models to enable valid inference.
problem Theoretical gaps in deep neural network estimators for Cox models.
method Asymptotic distribution theory linking in-sample optimization error to population risk.
result Pointwise and multivariate asymptotic normality for subsampled ensemble estimators.
The paper provides mean-square error bounds for stochastic approximation algorithms.
problem Error bounds for recursive equations with Markovian disturbances.
method Analysis of mean-square error for stochastic approximation algorithms.
result Mean-square error achieves the optimal rate of under certain conditions.
We present two alternative ways to apply PAC-Bayesian analysis to sequences of dependent random variables. The first is based on a new lemma that enables to bound expectations of convex functions of certain dependent random variables by expectations of the same functions of independent Bernoulli random variables. This …
This paper improves neural tangent kernels for better generalization and local elasticity.
problem Performance gap between neural tangent kernels and real-world neural networks.
method Introduces label-aware kernels using Hoeffding decomposition.
result Models trained with proposed kernels simulate NNs better in terms of generalization and local elasticity.
The paper improves confidence regions for band-limited functions using tighter norm bounds and majority voting.
problem Constructing reliable confidence regions for band-limited functions from noisy data.
method Improved norm bounds using Hoeffding's inequality and empirical Bernstein bound, majority voting to aggregate intervals.
result Confidence intervals retain their simultaneous coverage guarantee even when aggregated from random subsamples.
New methods for private statistical inference under local differential privacy.
problem Private statistical inference for population means with bounded observations.
method Nonparametric, nonasymptotic statistical inference using a generalized randomized response mechanism.
result Private confidence intervals and sequences for population means under LDP constraints.
The paper develops concentration inequalities for structured random data, extending beyond independent terms.
problem Developing concentration inequalities for structured weighted sums of random data, including tensors and matrix-valued data.
method The paper develops Hoeffding and Bernstein bounds for structured weighted sums under exchangeability, extending beyond the classical framework of independent terms.
result The paper develops a sharper concentration bound for combinatorial sums of matrix arrays.
New method detects changes in high-dimensional Markov processes without explicit likelihood evaluation.
problem Quickest change detection in Markov processes with unknown transition kernels.
method Learn conditional score from sample pairs, develop score-based CUSUM procedure.
result Exponential lower bounds on mean time to false alarm and asymptotic upper bounds on detection delay.
We give concentration bounds for martingales that are uniform over finite times and extend classical Hoeffding and Bernstein inequalities. We also demonstrate our concentration bounds to be optimal with a matching anti-concentration inequality, proved using the same method. Together these constitute a finite-time versi…
Proves new concentration inequalities for sub-gaussian and sub-exponential variables.
problem Understanding functions of independent random variables better.
method Sub-gaussian and sub-exponential conditions, Rademacher complexities, Lipschitz function classes.
result Extension of Rademacher complexities to unbounded sub-exponential distributions.
In this paper, we propose a novel framework to analyze the theoretical properties of the learning process for a representative type of domain adaptation, which combines data from multiple sources and one target (or briefly called representative domain adaptation). In particular, we use the integral probability metric t…
Improves decision tree performance by correcting split selection errors.
problem Invalid statistical guarantees in split selection for decision trees.
method Introduces anytime-valid inference to provide valid statistical guarantees.
result Provides anytime-valid control of false splits under arbitrary data streams.
Automated data-driven decision-making systems are ubiquitous across a wide spread of online as well as offline services. These systems, depend on sophisticated learning algorithms and available data, to optimize the service function for decision support assistance. However, there is a growing concern about the accounta…
Concentration of infinitely exchangeable sequences with bounded-difference constants
problem Quantifying uncertainty in AI benchmarks
method Using a mixture-free Hoeffding-type bound
result Tight, mixture-free Hoeffding-type bound for zero-sum linear contrasts
When I first encountered PAC-Bayesian concentration inequalities they seemed to me to be rather disconnected from good old-fashioned results like Hoeffding's and Bernstein's inequalities. But, at least for one flavour of the PAC-Bayesian bounds, there is actually a very close relation, and the main innovation is a cont…
Fine-grained gap-dependent regret bounds for reinforcement learning.
problem Achieving optimal regret bounds for reinforcement learning with suboptimality gaps.
method Developed novel analytical frameworks and refined algorithms for UCB-based and non-UCB-based reinforcement learning.
result Established the first fine-grained gap-dependent regret bounds for both UCB-based and non-UCB-based algorithms.
In this paper, we develop a general theory of truncated inverse binomial sampling. In this theory, the fixed-size sampling and inverse binomial sampling are accommodated as special cases. In particular, the classical Chernoff-Hoeffding bound is an immediate consequence of the theory. Moreover, we propose a rigorous and…
The betting CI outperforms classical methods in constructing confidence intervals for bounded means.
problem Constructing nonasymptotic confidence intervals for bounded means.
method A betting-based approach to define and time-uniform variants of confidence intervals (CSs).
result The betting CI matches the fundamental limits, outperforming existing empirical Bernstein CIs.
This paper improves Q-learning bounds using reference-advantage decomposition.
problem Improving Q-learning bounds in MDPs with positive suboptimality gaps.
method Develops a novel error decomposition framework to prove gap-dependent regret bounds.
result Establishes logarithmic gap-dependent regret bounds for Q-learning.
Model-free bounds on Value-at-Risk using extreme value information and statistical distancesq-fin.RM
We derive bounds on the distribution function, therefore also on the Value-at-Risk, of where is an aggregation function and is a random vector with known marginal distributions and partially known dependence structure. More specifically, we analyze three type…
Decision tree classifiers are a widely used tool in data stream mining. The use of confidence intervals to estimate the gain associated with each split leads to very effective methods, like the popular Hoeffding tree algorithm. From a statistical viewpoint, the analysis of decision tree classifiers in a streaming setti…
Estimates barycenter in geodesic spaces with finite sample bounds.
problem Estimating the barycenter of a distribution in geodesic spaces.
method Finite sample error bounds, Hoeffding- and Bernstein-type concentration inequalities, efficient algorithms.
result Statistical guarantees for efficient barycenter computation.
Two probability distributions and in second stochastic order can be coupled by a supermartingale, and in fact by many. Is there a canonical choice? We construct and investigate two couplings which arise as optimizers for constrained Monge-Kantorovich optimal transport problems where only supermartingales are al…
We present a set of high-probability inequalities that control the concentration of weighted averages of multiple (possibly uncountably many) simultaneously evolving and interdependent martingales. Our results extend the PAC-Bayesian analysis in learning theory from the i.i.d. setting to martingales opening the way for…
Valid p-value for bounded random variables without distributional assumptions.
problem Calibration of predictive algorithms in a distribution-free setting.
method Built a super-uniform p-value based on a concentration inequality.
result Super-uniform p-value is tighter than existing alternatives.
Bayesian sequence prediction is a simple technique for predicting future symbols sampled from an unknown measure on infinite sequences over a countable alphabet. While strong bounds on the expected cumulative error are known, there are only limited results on the distribution of this error. We prove tight high-probabil…
We consider the Lipschitz bandit optimization problem with an emphasis on practical efficiency. Although there is rich literature on regret analysis of this type of problem, e.g., [Kleinberg et al. 2008, Bubeck et al. 2011, Slivkins 2014], their proposed algorithms suffer from serious practical problems including extre…