{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/139333"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/139333","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Learning-Augmented Algorithms","abstract":"Traditional worst case analysis of algorithms does not fully capture real world behavior in many instances. Inspired by the great success of machine learning algorithms for various practical tasks, there has been recent interest in moving beyond pessimistic analysis of algorithms through the use of additional learned information. In this thesis, we consider further application of this “learning-augmented” framework for three classical algorithms problems: 𝑘-means clustering, counting triangles in a graph stream, and estimating the support of a discrete distribution. The problems we study are fundamental in their own right; clustering is typically one of the first methods used to understand the structure of large datasets and 𝑘-means is the most popular clustering formulation by far. In addition, counting triangles in a graph is a basic tool of network analytics and community detection in social networks. Lastly, the problem of estimating the number of distinct elements in a large data set (or, equivalently, the support size of the distribution induced by the data set) from a random sample of its element occurs in many applications, including biology, genomics, computer systems and linguistics. In each of these applications, we design algorithms that use predictors (that are based, e.g., on prior instances of the problem) which provide structural information about the inputs. Our theoretical analysis shows that such information can indeed be leveraged to overcome worst case barriers. In addition, we also show that such predictors can be implemented in practice and our algorithms are evaluated on real world datasets. Our experiments demonstrate substantial improvements in the performance compared to prior state-of-the-art algorithms that do not employ any learned information.","abstract_html":"Traditional worst case analysis of algorithms does not fully capture real world behavior in many instances. Inspired by the great success of machine learning algorithms for various practical tasks, there has been recent interest in moving beyond pessimistic analysis of algorithms through the use of additional learned information. In this thesis, we consider further application of this “learning-augmented” framework for three classical algorithms problems: 𝑘-means clustering, counting triangles in a graph stream, and estimating the support of a discrete distribution. The problems we study are fundamental in their own right; clustering is typically one of the first methods used to understand the structure of large datasets and 𝑘-means is the most popular clustering formulation by far. In addition, counting triangles in a graph is a basic tool of network analytics and community detection in social networks. Lastly, the problem of estimating the number of distinct elements in a large data set (or, equivalently, the support size of the distribution induced by the data set) from a random sample of its element occurs in many applications, including biology, genomics, computer systems and linguistics. In each of these applications, we design algorithms that use predictors (that are based, e.g., on prior instances of the problem) which provide structural information about the inputs. Our theoretical analysis shows that such information can indeed be leveraged to overcome worst case barriers. In addition, we also show that such predictors can be implemented in practice and our algorithms are evaluated on real world datasets. Our experiments demonstrate substantial improvements in the performance compared to prior state-of-the-art algorithms that do not employ any learned information.","abstract_has_math":false,"creators":["Silwal, Sandeep"],"institution":"Massachusetts Institute of Technology","degree_name":"Master","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","school":null,"contributors":[],"advisors":["Indyk, Piotr"],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021-06","date_published":"2021-06","updated_at":"2026-07-22T22:22:14Z","subjects":[],"languages":[],"rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"rights_urls":["http://rightsstatements.org/page/InC-EDU/1.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/139333","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Indyk, Piotr"]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"]},{"key":"dc:creator","label":"Author","values":["Silwal, Sandeep"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2022-01-14T15:04:40Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2022-01-14T15:04:40Z"]},{"key":"dc:date.issued","label":"Date","values":["2021-06"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master","Master of Science in Electrical Engineering and Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright - Educational Use Permitted","Copyright MIT"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/page/InC-EDU/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/139333"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Traditional worst case analysis of algorithms does not fully capture real world behavior in many instances. Inspired by the great success of machine learning algorithms for various practical tasks, there has been recent interest in moving beyond pessimistic analysis of algorithms through the use of additional learned information. In this thesis, we consider further application of this “learning-augmented” framework for three classical algorithms problems: 𝑘-means clustering, counting triangles in a graph stream, and estimating the support of a discrete distribution. The problems we study are fundamental in their own right; clustering is typically one of the first methods used to understand the structure of large datasets and 𝑘-means is the most popular clustering formulation by far. In addition, counting triangles in a graph is a basic tool of network analytics and community detection in social networks. Lastly, the problem of estimating the number of distinct elements in a large data set (or, equivalently, the support size of the distribution induced by the data set) from a random sample of its element occurs in many applications, including biology, genomics, computer systems and linguistics. In each of these applications, we design algorithms that use predictors (that are based, e.g., on prior instances of the problem) which provide structural information about the inputs. Our theoretical analysis shows that such information can indeed be leveraged to overcome worst case barriers. In addition, we also show that such predictors can be implemented in practice and our algorithms are evaluated on real world datasets. Our experiments demonstrate substantial improvements in the performance compared to prior state-of-the-art algorithms that do not employ any learned information."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:title","label":"Title","values":["Learning-Augmented Algorithms"]}]}],"canonical_facts":{"dc:contributor.advisor":["Indyk, Piotr"],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"],"dc:creator":["Silwal, Sandeep"],"dc:date.accessioned":["2022-01-14T15:04:40Z"],"dc:date.available":["2022-01-14T15:04:40Z"],"dc:date.issued":["2021-06"],"dc:description.abstract":["Traditional worst case analysis of algorithms does not fully capture real world behavior in many instances. Inspired by the great success of machine learning algorithms for various practical tasks, there has been recent interest in moving beyond pessimistic analysis of algorithms through the use of additional learned information. In this thesis, we consider further application of this “learning-augmented” framework for three classical algorithms problems: 𝑘-means clustering, counting triangles in a graph stream, and estimating the support of a discrete distribution. The problems we study are fundamental in their own right; clustering is typically one of the first methods used to understand the structure of large datasets and 𝑘-means is the most popular clustering formulation by far. In addition, counting triangles in a graph is a basic tool of network analytics and community detection in social networks. Lastly, the problem of estimating the number of distinct elements in a large data set (or, equivalently, the support size of the distribution induced by the data set) from a random sample of its element occurs in many applications, including biology, genomics, computer systems and linguistics. In each of these applications, we design algorithms that use predictors (that are based, e.g., on prior instances of the problem) which provide structural information about the inputs. Our theoretical analysis shows that such information can indeed be leveraged to overcome worst case barriers. In addition, we also show that such predictors can be implemented in practice and our algorithms are evaluated on real world datasets. Our experiments demonstrate substantial improvements in the performance compared to prior state-of-the-art algorithms that do not employ any learned information."],"dc:description.degree":["S.M."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/139333"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"dc:rights.uri":["http://rightsstatements.org/page/InC-EDU/1.0/"],"dc:title":["Learning-Augmented Algorithms"],"dc:type":["Thesis"],"thesis:degree_name":["Master","Master of Science in Electrical Engineering and Computer Science"]},"updated_at":"2026-07-22T22:22:14Z"}