Fast Averaging
We are interested in the following question: given n numbers x[subscript 1], ..., x[subscript n], what sorts of approximation of average x[subscript ave] = 1overn (x[subscript 1] + ... + x[subscript n]) can be achieved by knowing only r of these n numbers. Indeed the answer depends on the variation...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72577 https://orcid.org/0000-0003-0737-3259 |
| _version_ | 1811090336977518592 |
|---|---|
| author | Bodas, Shreeshankar Shah, Devavrat |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Bodas, Shreeshankar Shah, Devavrat |
| author_sort | Bodas, Shreeshankar |
| collection | MIT |
| description | We are interested in the following question: given n numbers x[subscript 1], ..., x[subscript n], what sorts of approximation of average x[subscript ave] = 1overn (x[subscript 1] + ... + x[subscript n]) can be achieved by knowing only r of these n numbers. Indeed the answer depends on the variation in these n numbers. As the main result, we show that if the vector of these n numbers satisfies certain regularity properties captured in the form of finiteness of their empirical moments (third or higher), then it is possible to compute approximation of x[subscript ave] that is within 1 ±ε multiplicative factor with probability at least 1 - δ by choosing, on an average, r = r(ε, δ, σ) of the n numbers at random with r is dependent only on ε, δ and the amount of variation σ in the vector and is independent of n. The task of computing average has a variety of applications such as distributed estimation and optimization, a model for reaching consensus and computing symmetric functions. We discuss implications of the result in the context of two applications: load-balancing in a computational facility running MapReduce, and fast distributed averaging. |
| first_indexed | 2024-09-23T14:43:10Z |
| format | Article |
| id | mit-1721.1/72577 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:43:10Z |
| publishDate | 2012 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/725772022-10-01T22:07:13Z Fast Averaging Bodas, Shreeshankar Shah, Devavrat Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Shah, Devavrat Bodas, Shreeshankar Shah, Devavrat We are interested in the following question: given n numbers x[subscript 1], ..., x[subscript n], what sorts of approximation of average x[subscript ave] = 1overn (x[subscript 1] + ... + x[subscript n]) can be achieved by knowing only r of these n numbers. Indeed the answer depends on the variation in these n numbers. As the main result, we show that if the vector of these n numbers satisfies certain regularity properties captured in the form of finiteness of their empirical moments (third or higher), then it is possible to compute approximation of x[subscript ave] that is within 1 ±ε multiplicative factor with probability at least 1 - δ by choosing, on an average, r = r(ε, δ, σ) of the n numbers at random with r is dependent only on ε, δ and the amount of variation σ in the vector and is independent of n. The task of computing average has a variety of applications such as distributed estimation and optimization, a model for reaching consensus and computing symmetric functions. We discuss implications of the result in the context of two applications: load-balancing in a computational facility running MapReduce, and fast distributed averaging. United States. Defense Advanced Research Projects Agency. Information Theory for Mobile Ad-Hoc Networks Program 2012-09-07T18:37:03Z 2012-09-07T18:37:03Z 2011-10 Article http://purl.org/eprint/type/ConferencePaper 978-1-4577-0594-6 978-1-4577-0596-0 2157-8095 http://hdl.handle.net/1721.1/72577 Bodas, Shreeshankar, and Devavrat Shah. “Fast Averaging.” IEEE International Symposium on Information Theory Proceedings 2011 (ISIT). 2153–2157. https://orcid.org/0000-0003-0737-3259 en_US http://dx.doi.org/10.1109/ISIT.2011.6033939 IEEE International Symposium on Information Theory Proceedings 2011 (ISIT) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Bodas, Shreeshankar Shah, Devavrat Fast Averaging |
| title | Fast Averaging |
| title_full | Fast Averaging |
| title_fullStr | Fast Averaging |
| title_full_unstemmed | Fast Averaging |
| title_short | Fast Averaging |
| title_sort | fast averaging |
| url | http://hdl.handle.net/1721.1/72577 https://orcid.org/0000-0003-0737-3259 |
| work_keys_str_mv | AT bodasshreeshankar fastaveraging AT shahdevavrat fastaveraging |