{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/106140"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/106140","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Information-theoretic bounds in learning algorithms","abstract":"The focus of this thesis is on understanding machine learning algorithms from an information-theoretic point of view. More specifically, we apply information-theoretic tools to construct performance bounds for the learning algorithms, with the goal of deepening the understanding of current algorithms and inspiring new learning techniques. The first problem considered involves a sequence of machine learning problems that vary in a bounded manner from one time-step to the next. To solve these problems in an accurate and data-efficient way, an active and adaptive learning framework is proposed, in which the labels of the most informative samples are actively queried from an unlabeled data pool, and the adaptation to the change is achieved by utilizing the information acquired in previous steps. The goal is to satisfy a pre-specified bound on the excess risk at each time-step. More specifically, the design of the active querying algorithm is based on minimizing the excess risk using stochastic gradient descent in the maximum likelihood estimation setting. Our algorithm and theoretical results are validated by experiments with synthetic and real data. To determine whether the active and adaptive learning framework is applicable in practice, we then study the problem of model change detection. There are two sets of samples that are generated according to a pre-change probabilistic model with parameter theta, and a post-change model with parameter theta', respectively. The goal is to detect whether the change in the model is significant. We construct an empirical difference test (EDT), which has low computational complexity. Moreover, we provide an approximation method to set the threshold of the EDT to meet the false alarm constraint. Experiments with linear regression and logistic regression are conducted to validate the proposed algorithms. Another key contribution of this thesis is in the area of mutual information-based generalization error bounds of supervised learning algorithms. Our bound is constructed in terms of the mutual information between each individual training sample and the output of the learning algorithm, which requires weaker conditions on the loss function, and provides a tighter characterization of the generalization error than existing studies. Examples are further provided to demonstrate that the proposed bound is tighter and has a broader range of applicability. Finally, an application of this mutual information-based generalization error bound is considered. We show that model compression can improve the population risk of a pre-trained model, by studying the tradeoff between the decrease in the generalization error and the increase in the empirical risk with model compression. We first prove that model compression reduces the mutual information-based generalization error bound; this allows for an interpretation of model compression as a regularization technique to avoid overfitting. We then characterize the increase in empirical risk with model compression using rate distortion theory. We show through a linear regression example that such an improvement in population risk due to model compression is indeed possible. Our theoretical results further suggest that the Hessian-weighted K-means clustering compression approach can be improved by regularizing the distance between the clustering centers. We provide experiments with neural networks to support our theoretical assertions.","abstract_html":"The focus of this thesis is on understanding machine learning algorithms from an information-theoretic point of view. More specifically, we apply information-theoretic tools to construct performance bounds for the learning algorithms, with the goal of deepening the understanding of current algorithms and inspiring new learning techniques. The first problem considered involves a sequence of machine learning problems that vary in a bounded manner from one time-step to the next. To solve these problems in an accurate and data-efficient way, an active and adaptive learning framework is proposed, in which the labels of the most informative samples are actively queried from an unlabeled data pool, and the adaptation to the change is achieved by utilizing the information acquired in previous steps. The goal is to satisfy a pre-specified bound on the excess risk at each time-step. More specifically, the design of the active querying algorithm is based on minimizing the excess risk using stochastic gradient descent in the maximum likelihood estimation setting. Our algorithm and theoretical results are validated by experiments with synthetic and real data. To determine whether the active and adaptive learning framework is applicable in practice, we then study the problem of model change detection. There are two sets of samples that are generated according to a pre-change probabilistic model with parameter theta, and a post-change model with parameter theta', respectively. The goal is to detect whether the change in the model is significant. We construct an empirical difference test (EDT), which has low computational complexity. Moreover, we provide an approximation method to set the threshold of the EDT to meet the false alarm constraint. Experiments with linear regression and logistic regression are conducted to validate the proposed algorithms. Another key contribution of this thesis is in the area of mutual information-based generalization error bounds of supervised learning algorithms. Our bound is constructed in terms of the mutual information between each individual training sample and the output of the learning algorithm, which requires weaker conditions on the loss function, and provides a tighter characterization of the generalization error than existing studies. Examples are further provided to demonstrate that the proposed bound is tighter and has a broader range of applicability. Finally, an application of this mutual information-based generalization error bound is considered. We show that model compression can improve the population risk of a pre-trained model, by studying the tradeoff between the decrease in the generalization error and the increase in the empirical risk with model compression. We first prove that model compression reduces the mutual information-based generalization error bound; this allows for an interpretation of model compression as a regularization technique to avoid overfitting. We then characterize the increase in empirical risk with model compression using rate distortion theory. We show through a linear regression example that such an improvement in population risk due to model compression is indeed possible. Our theoretical results further suggest that the Hessian-weighted K-means clustering compression approach can be improved by regularizing the distance between the clustering centers. We provide experiments with neural networks to support our theoretical assertions.","abstract_has_math":false,"creators":["Bu, Yuheng"],"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":["Veeravalli, Venugopal V.","Raginsky, Maxim","Varshney, Lav R.","Small, Kevin"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-03-02T21:57:53Z","date_published":"2020-03-02T21:57:53Z","updated_at":"2026-07-22T22:24:45Z","subjects":["active and adaptive learning","model change detection","mutual information based generalization bounds","model compression"],"languages":["en"],"rights":["Copyright 2019 Yuheng Bu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/106140","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Veeravalli, Venugopal V.","Raginsky, Maxim","Varshney, Lav R.","Small, Kevin"]},{"key":"dc:creator","label":"Author","values":["Bu, Yuheng"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-03-02T21:57:53Z","2019-08-14","2019-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":["active and adaptive learning","model change detection","mutual information based generalization bounds","model compression"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2019 Yuheng Bu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/106140"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The focus of this thesis is on understanding machine learning algorithms from an information-theoretic point of view. More specifically, we apply information-theoretic tools to construct performance bounds for the learning algorithms, with the goal of deepening the understanding of current algorithms and inspiring new learning techniques. The first problem considered involves a sequence of machine learning problems that vary in a bounded manner from one time-step to the next. To solve these problems in an accurate and data-efficient way, an active and adaptive learning framework is proposed, in which the labels of the most informative samples are actively queried from an unlabeled data pool, and the adaptation to the change is achieved by utilizing the information acquired in previous steps. The goal is to satisfy a pre-specified bound on the excess risk at each time-step. More specifically, the design of the active querying algorithm is based on minimizing the excess risk using stochastic gradient descent in the maximum likelihood estimation setting. Our algorithm and theoretical results are validated by experiments with synthetic and real data. To determine whether the active and adaptive learning framework is applicable in practice, we then study the problem of model change detection. There are two sets of samples that are generated according to a pre-change probabilistic model with parameter theta, and a post-change model with parameter theta', respectively. The goal is to detect whether the change in the model is significant. We construct an empirical difference test (EDT), which has low computational complexity. Moreover, we provide an approximation method to set the threshold of the EDT to meet the false alarm constraint. Experiments with linear regression and logistic regression are conducted to validate the proposed algorithms. Another key contribution of this thesis is in the area of mutual information-based generalization error bounds of supervised learning algorithms. Our bound is constructed in terms of the mutual information between each individual training sample and the output of the learning algorithm, which requires weaker conditions on the loss function, and provides a tighter characterization of the generalization error than existing studies. Examples are further provided to demonstrate that the proposed bound is tighter and has a broader range of applicability. Finally, an application of this mutual information-based generalization error bound is considered. We show that model compression can improve the population risk of a pre-trained model, by studying the tradeoff between the decrease in the generalization error and the increase in the empirical risk with model compression. We first prove that model compression reduces the mutual information-based generalization error bound; this allows for an interpretation of model compression as a regularization technique to avoid overfitting. We then characterize the increase in empirical risk with model compression using rate distortion theory. We show through a linear regression example that such an improvement in population risk due to model compression is indeed possible. Our theoretical results further suggest that the Hessian-weighted K-means clustering compression approach can be improved by regularizing the distance between the clustering centers. We provide experiments with neural networks to support our theoretical assertions.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-02-28 without embargo terms","The student, Yuheng Bu, accepted the attached license on 2019-08-12 at 21:22.","The student, Yuheng Bu, submitted this Dissertation for approval on 2019-08-12 at 21:36.","This Dissertation was approved for publication on 2019-08-14 at 13:48.","DSpace SAF Submission Ingestion Package generated from Vireo submission #14418 on 2020-02-28 at 17:11:04","Made available in DSpace on 2020-03-02T21:57:53Z (GMT). No. of bitstreams: 3 BU-DISSERTATION-2019.pdf: 1254941 bytes, checksum: 6f46c019aee443868a50d31c4ffeecbb (MD5) LICENSE.txt: 4206 bytes, checksum: 5c4496ea0ea0b1803f719e5f53637d67 (MD5) PROQUEST_LICENSE.txt: 4552 bytes, checksum: c08a6d4039038ef902da8fa0ee9ad2c7 (MD5) Previous issue date: 2019-08-14"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Information-theoretic bounds in learning algorithms"]}]}],"canonical_facts":{"dc:contributor":["Veeravalli, Venugopal V.","Raginsky, Maxim","Varshney, Lav R.","Small, Kevin"],"dc:creator":["Bu, Yuheng"],"dc:date":["2020-03-02T21:57:53Z","2019-08-14","2019-12"],"dc:description":["The focus of this thesis is on understanding machine learning algorithms from an information-theoretic point of view. More specifically, we apply information-theoretic tools to construct performance bounds for the learning algorithms, with the goal of deepening the understanding of current algorithms and inspiring new learning techniques. The first problem considered involves a sequence of machine learning problems that vary in a bounded manner from one time-step to the next. To solve these problems in an accurate and data-efficient way, an active and adaptive learning framework is proposed, in which the labels of the most informative samples are actively queried from an unlabeled data pool, and the adaptation to the change is achieved by utilizing the information acquired in previous steps. The goal is to satisfy a pre-specified bound on the excess risk at each time-step. More specifically, the design of the active querying algorithm is based on minimizing the excess risk using stochastic gradient descent in the maximum likelihood estimation setting. Our algorithm and theoretical results are validated by experiments with synthetic and real data. To determine whether the active and adaptive learning framework is applicable in practice, we then study the problem of model change detection. There are two sets of samples that are generated according to a pre-change probabilistic model with parameter theta, and a post-change model with parameter theta', respectively. The goal is to detect whether the change in the model is significant. We construct an empirical difference test (EDT), which has low computational complexity. Moreover, we provide an approximation method to set the threshold of the EDT to meet the false alarm constraint. Experiments with linear regression and logistic regression are conducted to validate the proposed algorithms. Another key contribution of this thesis is in the area of mutual information-based generalization error bounds of supervised learning algorithms. Our bound is constructed in terms of the mutual information between each individual training sample and the output of the learning algorithm, which requires weaker conditions on the loss function, and provides a tighter characterization of the generalization error than existing studies. Examples are further provided to demonstrate that the proposed bound is tighter and has a broader range of applicability. Finally, an application of this mutual information-based generalization error bound is considered. We show that model compression can improve the population risk of a pre-trained model, by studying the tradeoff between the decrease in the generalization error and the increase in the empirical risk with model compression. We first prove that model compression reduces the mutual information-based generalization error bound; this allows for an interpretation of model compression as a regularization technique to avoid overfitting. We then characterize the increase in empirical risk with model compression using rate distortion theory. We show through a linear regression example that such an improvement in population risk due to model compression is indeed possible. Our theoretical results further suggest that the Hessian-weighted K-means clustering compression approach can be improved by regularizing the distance between the clustering centers. We provide experiments with neural networks to support our theoretical assertions.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-02-28 without embargo terms","The student, Yuheng Bu, accepted the attached license on 2019-08-12 at 21:22.","The student, Yuheng Bu, submitted this Dissertation for approval on 2019-08-12 at 21:36.","This Dissertation was approved for publication on 2019-08-14 at 13:48.","DSpace SAF Submission Ingestion Package generated from Vireo submission #14418 on 2020-02-28 at 17:11:04","Made available in DSpace on 2020-03-02T21:57:53Z (GMT). No. of bitstreams: 3 BU-DISSERTATION-2019.pdf: 1254941 bytes, checksum: 6f46c019aee443868a50d31c4ffeecbb (MD5) LICENSE.txt: 4206 bytes, checksum: 5c4496ea0ea0b1803f719e5f53637d67 (MD5) PROQUEST_LICENSE.txt: 4552 bytes, checksum: c08a6d4039038ef902da8fa0ee9ad2c7 (MD5) Previous issue date: 2019-08-14"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/106140"],"dc:language":["en"],"dc:rights":["Copyright 2019 Yuheng Bu"],"dc:subject":["active and adaptive learning","model change detection","mutual information based generalization bounds","model compression"],"dc:title":["Information-theoretic bounds in learning algorithms"],"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:24:45Z"}