Empirical Bernstein stopping

By Volodymyr Mnih, Csaba Szepesvari, Jean-Yves Audibert. 2008

238 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization (2016, neutral): “Springenberg et al. (2016) proposed using Bayesian neural networks, which scale linearly with n, to model the posterior. Adaptive conguration evaluation is not a new idea. Maron and Moore (1997) and Mnih and Audibert (2008) considered a setting where the training time is relatively inexpensive (e.g.”
Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, background): “[113] V.”
Empirical Bernstein Bounds and Sample-Variance Penalization (2009, methodology): “For this reason it has been called an empirical Bernstein bound in [9].”
Best Arm Identification in Multi-Armed Bandits (2010, background): “The target of Hoeffding and Bernstein races, see Maron and Moore (1993); Mnih et al. (2008) among others, is more similar to ours.”
Adaptive Batch Size for Safe Policy Gradients (2017, background): “An empirical Bernstein bound from [22] allows to use sample variance instead of the variance bounds from [21] and to limit the impact of the gradient range.”
Preference-based Evolutionary Direct Policy Search (2013, methodology): “This algorithm was improved in [23], where the empirical Bernstein bound was used instead of the Hoeffding bound.”
Preference-based reinforcement learning: evolutionary direct policy search using a preference-based racing algorithm (2014, methodology): “This algorithm was improved in [23], where the empirical Bernstein bound was used instead of the Hoeﬀding bound.”
Multi-Bandit Best Arm Identification (2011, unknown): “, [10, 12])”
Optimization for machine learning (2010, background): “The strategy must stop as soon as possible with the guarantee that an ε-optimal option has been found with probability at least 1− δ, where ε and δ are fixed before the procedure starts (Maron and Moore, 1993; Domingo et al., 2002; Dagum et al., 2000; Even-Dar et al., 2006; Mnih et al., 2008).”
Empirical Bernstein Boosting (2010, background): “Previously, these bounds have been applied in sampling procedures (Mnih et al., 2008).”
Algorithms for Reinforcement Learning (2010, methodology): “Apart from constant factors and using estimated variances in the confidence bounds, this algorithm is unimprovable (EvenDar et al., 2002; Tsitsiklis and Mannor, 2004; Mnih et al., 2008).”
Estimating means of bounded random variables by betting (2020, methodology): “’s concentration inequality [44, Theorem 1] with the “stitching” technique [85, 52, 36] — a method to obtain infinite-horizon concentration inequalities by taking a union bound over exponentiallyspaced finite time horizons.”
PAC-Bayesian Inequalities for Martingales (2011, result): “lk without prior knowledge on its variance, if the empirical drift is close to zero or to nthe kl inequality is tighter. In this case the kl inequality is comparable with empirical Bernstein’s bounds [22], [23], [24]. Comparison of Inequalities for Individual Martingales with PAC-Bayesian Inequaliti”
Towards scaling up Markov chain Monte Carlo: an adaptive subsampling approach (2014, methodology): “This adaptive stopping rule adapted from (Mnih et al., 2008) is inspired by bandit algorithms, Hoeffding races (Maron & Moore, 1993) and procedures developed to scale up boosting algorithms to large datasets (Domingo & Watanabe, 2000).”
LEAPSANDBOUNDS: A Method for Approximately Optimal Algorithm Configuration (2018, background): “Mnih et al. (2008) also describe EBGStop, a slightly improved version of empirical Bernstein stopping, which applies Bernstein inequalities to bound the means of an exponentially increasing number of samples.”
Variance Penalizing AdaBoost (2011, background): “Previously, these bounds have been applied in sampling procedures [6] and in multiarmed bandit problems [1].”