Information-theoretic limits of algorithmic noise tolerance

Daewon Seo, Lav R Varshney

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Statistical error compensation techniques in computing circuits are becoming prevalent, especially as implemented on nanoscale physical substrates. One such technique that has been developed and deployed is algorithmic noise tolerance (ANT), which aggregates information from several computational branches operating at different points along energy-reliability circuit tradeoffs. To understand this practical approach better, it is of interest to develop limit theorems on optimal designs, no matter how much design effort is put in. The purpose of this paper is to develop a fundamental limit for ANT by making an analogy to the CEO problem in multiterminal source coding, extended to the setting with a mixed set of discrete and continuous random variables. Since statistical signal processing and machine learning are key workloads for modern computing, we specifically discuss performance measured according to logarithmic distortion, in addition to mean-squared error. We find the Gaussian CEO problem provides performance bounds for ANT under both kinds of distortion.

Original languageEnglish (US)
Title of host publication2016 IEEE International Conference on Rebooting Computing, ICRC 2016 - Conference Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781509013708
DOIs
StatePublished - Nov 8 2016
Event2016 IEEE International Conference on Rebooting Computing, ICRC 2016 - San Diego, United States
Duration: Oct 17 2016Oct 19 2016

Publication series

Name2016 IEEE International Conference on Rebooting Computing, ICRC 2016 - Conference Proceedings

Other

Other2016 IEEE International Conference on Rebooting Computing, ICRC 2016
CountryUnited States
CitySan Diego
Period10/17/1610/19/16

Fingerprint

Error compensation
Networks (circuits)
Random variables
Learning systems
Signal processing
Substrates
Optimal design

ASJC Scopus subject areas

  • Hardware and Architecture

Cite this

Seo, D., & Varshney, L. R. (2016). Information-theoretic limits of algorithmic noise tolerance. In 2016 IEEE International Conference on Rebooting Computing, ICRC 2016 - Conference Proceedings [7738715] (2016 IEEE International Conference on Rebooting Computing, ICRC 2016 - Conference Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICRC.2016.7738715

Information-theoretic limits of algorithmic noise tolerance. / Seo, Daewon; Varshney, Lav R.

2016 IEEE International Conference on Rebooting Computing, ICRC 2016 - Conference Proceedings. Institute of Electrical and Electronics Engineers Inc., 2016. 7738715 (2016 IEEE International Conference on Rebooting Computing, ICRC 2016 - Conference Proceedings).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Seo, D & Varshney, LR 2016, Information-theoretic limits of algorithmic noise tolerance. in 2016 IEEE International Conference on Rebooting Computing, ICRC 2016 - Conference Proceedings., 7738715, 2016 IEEE International Conference on Rebooting Computing, ICRC 2016 - Conference Proceedings, Institute of Electrical and Electronics Engineers Inc., 2016 IEEE International Conference on Rebooting Computing, ICRC 2016, San Diego, United States, 10/17/16. https://doi.org/10.1109/ICRC.2016.7738715
Seo D, Varshney LR. Information-theoretic limits of algorithmic noise tolerance. In 2016 IEEE International Conference on Rebooting Computing, ICRC 2016 - Conference Proceedings. Institute of Electrical and Electronics Engineers Inc. 2016. 7738715. (2016 IEEE International Conference on Rebooting Computing, ICRC 2016 - Conference Proceedings). https://doi.org/10.1109/ICRC.2016.7738715
Seo, Daewon ; Varshney, Lav R. / Information-theoretic limits of algorithmic noise tolerance. 2016 IEEE International Conference on Rebooting Computing, ICRC 2016 - Conference Proceedings. Institute of Electrical and Electronics Engineers Inc., 2016. (2016 IEEE International Conference on Rebooting Computing, ICRC 2016 - Conference Proceedings).
@inproceedings{09c222c08e49495dad52757ab5ea48b6,
title = "Information-theoretic limits of algorithmic noise tolerance",
abstract = "Statistical error compensation techniques in computing circuits are becoming prevalent, especially as implemented on nanoscale physical substrates. One such technique that has been developed and deployed is algorithmic noise tolerance (ANT), which aggregates information from several computational branches operating at different points along energy-reliability circuit tradeoffs. To understand this practical approach better, it is of interest to develop limit theorems on optimal designs, no matter how much design effort is put in. The purpose of this paper is to develop a fundamental limit for ANT by making an analogy to the CEO problem in multiterminal source coding, extended to the setting with a mixed set of discrete and continuous random variables. Since statistical signal processing and machine learning are key workloads for modern computing, we specifically discuss performance measured according to logarithmic distortion, in addition to mean-squared error. We find the Gaussian CEO problem provides performance bounds for ANT under both kinds of distortion.",
author = "Daewon Seo and Varshney, {Lav R}",
year = "2016",
month = "11",
day = "8",
doi = "10.1109/ICRC.2016.7738715",
language = "English (US)",
series = "2016 IEEE International Conference on Rebooting Computing, ICRC 2016 - Conference Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
booktitle = "2016 IEEE International Conference on Rebooting Computing, ICRC 2016 - Conference Proceedings",
address = "United States",

}

TY - GEN

T1 - Information-theoretic limits of algorithmic noise tolerance

AU - Seo, Daewon

AU - Varshney, Lav R

PY - 2016/11/8

Y1 - 2016/11/8

N2 - Statistical error compensation techniques in computing circuits are becoming prevalent, especially as implemented on nanoscale physical substrates. One such technique that has been developed and deployed is algorithmic noise tolerance (ANT), which aggregates information from several computational branches operating at different points along energy-reliability circuit tradeoffs. To understand this practical approach better, it is of interest to develop limit theorems on optimal designs, no matter how much design effort is put in. The purpose of this paper is to develop a fundamental limit for ANT by making an analogy to the CEO problem in multiterminal source coding, extended to the setting with a mixed set of discrete and continuous random variables. Since statistical signal processing and machine learning are key workloads for modern computing, we specifically discuss performance measured according to logarithmic distortion, in addition to mean-squared error. We find the Gaussian CEO problem provides performance bounds for ANT under both kinds of distortion.

AB - Statistical error compensation techniques in computing circuits are becoming prevalent, especially as implemented on nanoscale physical substrates. One such technique that has been developed and deployed is algorithmic noise tolerance (ANT), which aggregates information from several computational branches operating at different points along energy-reliability circuit tradeoffs. To understand this practical approach better, it is of interest to develop limit theorems on optimal designs, no matter how much design effort is put in. The purpose of this paper is to develop a fundamental limit for ANT by making an analogy to the CEO problem in multiterminal source coding, extended to the setting with a mixed set of discrete and continuous random variables. Since statistical signal processing and machine learning are key workloads for modern computing, we specifically discuss performance measured according to logarithmic distortion, in addition to mean-squared error. We find the Gaussian CEO problem provides performance bounds for ANT under both kinds of distortion.

UR - http://www.scopus.com/inward/record.url?scp=85006010303&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85006010303&partnerID=8YFLogxK

U2 - 10.1109/ICRC.2016.7738715

DO - 10.1109/ICRC.2016.7738715

M3 - Conference contribution

AN - SCOPUS:85006010303

T3 - 2016 IEEE International Conference on Rebooting Computing, ICRC 2016 - Conference Proceedings

BT - 2016 IEEE International Conference on Rebooting Computing, ICRC 2016 - Conference Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

ER -