Fetching the paper…

Reading the bibliography…

2017

Climbing a shaky ladder: Better adaptive risk estimation

Hardt, Moritz

Original
PDF
Post on X

Understand

We revisit the \emph{leaderboard problem} introduced by Blum and Hardt (2015) in an effort to reduce overfitting in machine learning benchmarks.

We show that a randomized version of their Ladder algorithm achieves leaderboard error O(1/n^{0.4}) compared with the previous best rate of O(1/n^{1/3}).
Short of proving that our algorithm is optimal, we point out a major obstacle toward further progress.
Specifically, any improvement to our upper bound would lead to asymptotic improvements in the general adaptive estimation setting as have remained elusive in recent years.

Climbing a shaky ladder: Better adaptive risk estimation · Around

Built on

The algorithmic foundations of differential privacy
Cynthia Dwork and Aaron Roth · 2014
Earlier work this paper cites.
Preventing false discovery in interactive data analysis is hard
Moritz Hardt and Jonathan Ullman · 2014
Earlier work this paper cites.
Interactive fingerprinting codes and the hardness of preventing false discovery
Original
Thomas Steinke and Jonathan Ullman · 2014
Earlier work this paper cites.

Similar

The Ladder: A reliable leaderboard for machine learning competitions
Avrim Blum and Moritz Hardt · 2015
Cited alongside, same era.
Preserving validity in adaptive data analysis
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth · 2015
Cited alongside, same era.
The reusable holdout: Preserving validity in adaptive data analysis
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth · 2015
Cited alongside, same era.
How much does your data exploration overfit? controlling bias via information usage
Original
Daniel Russo and James Zou
Cited in the paper.

Then

Algorithmic stability for adaptive data analysis
Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman · 2016
Later among the works it cites.
Reducing overfitting in challenge-based competitions
Original
Elias Chaibub Neto, Bruce R Hoff, Chris Bare, Brian M Bot, Thomas Yu, Lara Magravite, Andrew D Trister, Thea Norman, Pablo Meyer, Julio Saez-Rodrigues, James C Costello, Justin Guinney, and Gustavo Stolovitzky · 2016
Later among the works it cites.
A minimax theory for adaptive data analysis
Original
Yu-Xiang Wang, Jing Lei, and Stephen E. Fienberg · 2016
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…