Information-Theoretic Limits of Algorithmic Noise Tolerance

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... [ view full 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.