{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/95358"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/95358","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Information-theoretic limitations of distributed information processing","abstract":"In a generic distributed information processing system, a number of agents connected by communication channels aim to accomplish a task collectively through local communications. The fundamental limits of distributed information processing problems depend not only on the intrinsic difficulty of the task, but also on the communication constraints due to the distributedness. In this thesis, we reveal these dependencies quantitatively under information-theoretic frameworks. We consider three typical distributed information processing problems: decentralized parameter estimation, distributed function computation, and statistical learning under adaptive composition. For the first two problems, we derive converse results on the Bayes risk and the computation time, respectively. For the last problem, we first study the relationship between the generalization capability of a learning algorithm and its stability property measured by the mutual information between its input and output, and then derive achievability results on the generalization error of adaptively composed learning algorithms. In all cases, we obtain general results on the fundamental limits with respect to a general model of the problem, so that the results can be applied to various specific scenarios. Our information-theoretic analyses also provide general approaches to inferring global properties of a distributed information processing system from local properties of its components.","abstract_html":"In a generic distributed information processing system, a number of agents connected by communication channels aim to accomplish a task collectively through local communications. The fundamental limits of distributed information processing problems depend not only on the intrinsic difficulty of the task, but also on the communication constraints due to the distributedness. In this thesis, we reveal these dependencies quantitatively under information-theoretic frameworks. We consider three typical distributed information processing problems: decentralized parameter estimation, distributed function computation, and statistical learning under adaptive composition. For the first two problems, we derive converse results on the Bayes risk and the computation time, respectively. For the last problem, we first study the relationship between the generalization capability of a learning algorithm and its stability property measured by the mutual information between its input and output, and then derive achievability results on the generalization error of adaptively composed learning algorithms. In all cases, we obtain general results on the fundamental limits with respect to a general model of the problem, so that the results can be applied to various specific scenarios. Our information-theoretic analyses also provide general approaches to inferring global properties of a distributed information processing system from local properties of its components.","abstract_has_math":false,"creators":["Xu, Aolin"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Raginsky, Maxim","Hajek, Bruce","Milenkovic, Olgica","Srikant, Rayadurgam","Wu, Yihong"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-03-01T15:49:14Z","date_published":"2017-03-01T15:49:14Z","updated_at":"2026-07-22T22:26:37Z","subjects":["distributed function computation","distributed information processing","fundamental limits","information theory","decentralized estimation","Bayes risk","small ball probability","strong data processing inequality","computation time","network reduction","diameter of network","statistical learning","adaptive composition","stability of learning algorithms","generalization error","mutual information","Gibbs algorithm","adaptive data analytics"],"languages":["en"],"rights":["Copyright 2016 Aolin Xu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/95358","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Raginsky, Maxim","Hajek, Bruce","Milenkovic, Olgica","Srikant, Rayadurgam","Wu, Yihong"]},{"key":"dc:creator","label":"Author","values":["Xu, Aolin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-03-01T15:49:14Z","2016-11-30","2016-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["distributed function computation","distributed information processing","fundamental limits","information theory","decentralized estimation","Bayes risk","small ball probability","strong data processing inequality","computation time","network reduction","diameter of network","statistical learning","adaptive composition","stability of learning algorithms","generalization error","mutual information","Gibbs algorithm","adaptive data analytics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2016 Aolin Xu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/95358"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In a generic distributed information processing system, a number of agents connected by communication channels aim to accomplish a task collectively through local communications. The fundamental limits of distributed information processing problems depend not only on the intrinsic difficulty of the task, but also on the communication constraints due to the distributedness. In this thesis, we reveal these dependencies quantitatively under information-theoretic frameworks. We consider three typical distributed information processing problems: decentralized parameter estimation, distributed function computation, and statistical learning under adaptive composition. For the first two problems, we derive converse results on the Bayes risk and the computation time, respectively. For the last problem, we first study the relationship between the generalization capability of a learning algorithm and its stability property measured by the mutual information between its input and output, and then derive achievability results on the generalization error of adaptively composed learning algorithms. In all cases, we obtain general results on the fundamental limits with respect to a general model of the problem, so that the results can be applied to various specific scenarios. Our information-theoretic analyses also provide general approaches to inferring global properties of a distributed information processing system from local properties of its components.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-02-28 without embargo terms","The student, Aolin Xu, accepted the attached license on 2016-11-30 at 09:00.","The student, Aolin Xu, submitted this Dissertation for approval on 2016-11-30 at 09:12.","This Dissertation was approved for publication on 2016-11-30 at 12:00.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10339 on 2017-02-28 at 14:54:30","Made available in DSpace on 2017-03-01T15:49:14Z (GMT). No. of bitstreams: 3 XU-DISSERTATION-2016.pdf: 2062927 bytes, checksum: 27181b763178cf5985f6d27ffe567d1a (MD5) LICENSE.txt: 4205 bytes, checksum: 99b14f62692c8f5fad44db578ef57f47 (MD5) PROQUEST_LICENSE.txt: 4551 bytes, checksum: 4229efe30450fe877b8d5973547caee4 (MD5) Previous issue date: 2016-11-30"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Information-theoretic limitations of distributed information processing"]}]}],"canonical_facts":{"dc:contributor":["Raginsky, Maxim","Hajek, Bruce","Milenkovic, Olgica","Srikant, Rayadurgam","Wu, Yihong"],"dc:creator":["Xu, Aolin"],"dc:date":["2017-03-01T15:49:14Z","2016-11-30","2016-12"],"dc:description":["In a generic distributed information processing system, a number of agents connected by communication channels aim to accomplish a task collectively through local communications. The fundamental limits of distributed information processing problems depend not only on the intrinsic difficulty of the task, but also on the communication constraints due to the distributedness. In this thesis, we reveal these dependencies quantitatively under information-theoretic frameworks. We consider three typical distributed information processing problems: decentralized parameter estimation, distributed function computation, and statistical learning under adaptive composition. For the first two problems, we derive converse results on the Bayes risk and the computation time, respectively. For the last problem, we first study the relationship between the generalization capability of a learning algorithm and its stability property measured by the mutual information between its input and output, and then derive achievability results on the generalization error of adaptively composed learning algorithms. In all cases, we obtain general results on the fundamental limits with respect to a general model of the problem, so that the results can be applied to various specific scenarios. Our information-theoretic analyses also provide general approaches to inferring global properties of a distributed information processing system from local properties of its components.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-02-28 without embargo terms","The student, Aolin Xu, accepted the attached license on 2016-11-30 at 09:00.","The student, Aolin Xu, submitted this Dissertation for approval on 2016-11-30 at 09:12.","This Dissertation was approved for publication on 2016-11-30 at 12:00.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10339 on 2017-02-28 at 14:54:30","Made available in DSpace on 2017-03-01T15:49:14Z (GMT). No. of bitstreams: 3 XU-DISSERTATION-2016.pdf: 2062927 bytes, checksum: 27181b763178cf5985f6d27ffe567d1a (MD5) LICENSE.txt: 4205 bytes, checksum: 99b14f62692c8f5fad44db578ef57f47 (MD5) PROQUEST_LICENSE.txt: 4551 bytes, checksum: 4229efe30450fe877b8d5973547caee4 (MD5) Previous issue date: 2016-11-30"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/95358"],"dc:language":["en"],"dc:rights":["Copyright 2016 Aolin Xu"],"dc:subject":["distributed function computation","distributed information processing","fundamental limits","information theory","decentralized estimation","Bayes risk","small ball probability","strong data processing inequality","computation time","network reduction","diameter of network","statistical learning","adaptive composition","stability of learning algorithms","generalization error","mutual information","Gibbs algorithm","adaptive data analytics"],"dc:title":["Information-theoretic limitations of distributed information processing"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:37Z"}