Median trick: Difference between revisions
Content deleted Content added
→top: Expanding article Tag: harv-error |
→Sources: added source |
||
| Line 10: | Line 10: | ||
* {{cite book | last=Kogler | first=Alexander | last2=Traxler | first2=Patrick | title=Mathematical Aspects of Computer and Information Sciences | chapter=Parallel and Robust Empirical Risk Minimization via the Median Trick | publisher=Springer International Publishing | publication-place=Cham | year=2017 | isbn=978-3-319-72452-2 | issn=0302-9743 | doi=10.1007/978-3-319-72453-9_31}} |
* {{cite book | last=Kogler | first=Alexander | last2=Traxler | first2=Patrick | title=Mathematical Aspects of Computer and Information Sciences | chapter=Parallel and Robust Empirical Risk Minimization via the Median Trick | publisher=Springer International Publishing | publication-place=Cham | year=2017 | isbn=978-3-319-72452-2 | issn=0302-9743 | doi=10.1007/978-3-319-72453-9_31}} |
||
* {{cite journal | last=Jerrum | first=Mark R. | last2=Valiant | first2=Leslie G. | last3=Vazirani | first3=Vijay V. | title=Random generation of combinatorial structures from a uniform distribution | journal=Theoretical Computer Science | publisher=Elsevier BV | volume=43 | year=1986 | issn=0304-3975 | doi=10.1016/0304-3975(86)90174-x | pages=169–188}} |
* {{cite journal | last=Jerrum | first=Mark R. | last2=Valiant | first2=Leslie G. | last3=Vazirani | first3=Vijay V. | title=Random generation of combinatorial structures from a uniform distribution | journal=Theoretical Computer Science | publisher=Elsevier BV | volume=43 | year=1986 | issn=0304-3975 | doi=10.1016/0304-3975(86)90174-x | pages=169–188}} |
||
* {{cite book | last=Wang | first=Dan | last2=Han | first2=Zhu | title=Sublinear Algorithms for Big Data Applications | chapter=Basics for Sublinear Algorithms | publisher=Springer International Publishing | publication-place=Cham | year=2015 | isbn=978-3-319-20447-5 | issn=2191-5768 | doi=10.1007/978-3-319-20448-2_2}} |
|||
{{algorithm-stub}} |
{{algorithm-stub}} |
||
Revision as of 22:19, 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 22:19, 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 approximate counting algorithms, the technique was later applied to a broad selection of classification and regression problems.[2]
The idea of median trick is very simple: run the randomized algorithm with real number-output multiple times, and output the median of the obtained results. For example, for sublinear algorithms, the same algorithm can be run repeatedly over random subsets of input data, and, per Chernoff inequality, the median of the results will converge to solution very fast.[4]
References
- ^ Kogler & Traxler 2017, p. 378.
- ^ a b Kogler & Traxler 2017, p. 380.
- ^ Jerrum, Valiant & Vazirani 1986, p. 182, Lemma 6.1.
- ^ Wang & Han 2015, p. 11.
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.
- Wang, Dan; Han, Zhu (2015). "Basics for Sublinear Algorithms". Sublinear Algorithms for Big Data Applications. Cham: Springer International Publishing. doi:10.1007/978-3-319-20448-2_2. ISBN 978-3-319-20447-5. ISSN 2191-5768.
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |