Median trick: Difference between revisions
Content deleted Content added
new page in the works |
(No difference)
|
Revision as of 21:30, 11 September 2023
This article is actively undergoing a major edit for a short while. To help avoid edit conflicts, please do not edit this page while this message is displayed. This page was last edited at 21:30, 11 September 2023 (UTC) (8 months ago) – this estimate is cached, . Please remove this template if this page hasn't been edited for a significant time. If you are the editor who added this template, please be sure to remove it or replace it with {{Under construction}} between editing sessions. |
The median trick is a generic approach that increases the chances of a probabilistic algorithm to succeed.[1] Probably first used in 1986[2] by Jerrum et al.[3] for an approximate counting algorithms, the technique proved applicable to a broad selection of classification and regression problems.[2]
References
- ^ Kogler & Traxler 2017, p. 378.
- ^ a b Kogler & Traxler 2017, p. 380.
- ^ Jerrum, Valiant & Vazirani 1986, p. 182, Lemma 6.1.
Sources
- Kogler, Alexander; Traxler, Patrick (2017). "Parallel and Robust Empirical Risk Minimization via the Median Trick". Mathematical Aspects of Computer and Information Sciences. Cham: Springer International Publishing. doi:10.1007/978-3-319-72453-9_31. ISBN 978-3-319-72452-2. ISSN 0302-9743.
- Jerrum, Mark R.; Valiant, Leslie G.; Vazirani, Vijay V. (1986). "Random generation of combinatorial structures from a uniform distribution". Theoretical Computer Science. 43. Elsevier BV: 169โ188. doi:10.1016/0304-3975(86)90174-x. ISSN 0304-3975.