{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/124716"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/124716","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Breaking the dimension dependence in distributed learning","abstract":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2026-05-01","abstract_html":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2026-05-01","abstract_has_math":false,"creators":["Shrivastava, Mayank"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Banerjee, Arindam"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-05","date_published":"2024-05","updated_at":"2026-07-22T22:25:02Z","subjects":["Distributed Learning","Deep Learning","Sketching","Overparametrized Models","Machine Learning"],"languages":["en","eng"],"rights":["2024 Mayank Shrivastava"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/124716","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Banerjee, Arindam"]},{"key":"dc:creator","label":"Author","values":["Shrivastava, Mayank"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2024-05","2024-04-30"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"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 Learning","Deep Learning","Sketching","Overparametrized Models","Machine Learning"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["2024 Mayank Shrivastava"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/124716"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2026-05-01","The student, Mayank Shrivastava, accepted the attached license on 2024-04-29 at 17:21.","The student, Mayank Shrivastava, submitted this Thesis for approval on 2024-04-29 at 17:26.","This Thesis was approved for publication on 2024-04-30 at 09:47.","DSpace SAF Submission Ingestion Package generated from Vireo submission #20698 on 2024-09-16 at 00:51:09","The high communication cost between the server and the clients is a significant bottleneck in scaling distributed learning for modern overparameterized deep models. One popular approach to reduce this cost is linear sketching, where the sender projects the updates into a lower dimension before communication, and the receiver desketches before any subsequent computation. While sketched distributed learning is known to scale effectively in practice, existing theoretical analyses suggest that the convergence error depends on the ambient dimension — impacting scalability. This thesis aims to shed light on this apparent mismatch between theory and practice. Our main result is a tighter analysis that eliminates the dimension dependence in sketching without imposing unrealistic restrictive assumptions in the distributed learning setup. With the approximate restricted strong smoothness property of overparameterized deep models and using the second-order geometry of the loss, we present optimization results for the single-local step and K-local step distributed learning and subsequent bounds on communication complexity, with implications for analyzing and implementing distributed learning for overparameterized deep models."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Breaking the dimension dependence in distributed learning"]}]}],"canonical_facts":{"dc:contributor":["Banerjee, Arindam"],"dc:creator":["Shrivastava, Mayank"],"dc:date":["2024-05","2024-04-30"],"dc:description":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2026-05-01","The student, Mayank Shrivastava, accepted the attached license on 2024-04-29 at 17:21.","The student, Mayank Shrivastava, submitted this Thesis for approval on 2024-04-29 at 17:26.","This Thesis was approved for publication on 2024-04-30 at 09:47.","DSpace SAF Submission Ingestion Package generated from Vireo submission #20698 on 2024-09-16 at 00:51:09","The high communication cost between the server and the clients is a significant bottleneck in scaling distributed learning for modern overparameterized deep models. One popular approach to reduce this cost is linear sketching, where the sender projects the updates into a lower dimension before communication, and the receiver desketches before any subsequent computation. While sketched distributed learning is known to scale effectively in practice, existing theoretical analyses suggest that the convergence error depends on the ambient dimension — impacting scalability. This thesis aims to shed light on this apparent mismatch between theory and practice. Our main result is a tighter analysis that eliminates the dimension dependence in sketching without imposing unrealistic restrictive assumptions in the distributed learning setup. With the approximate restricted strong smoothness property of overparameterized deep models and using the second-order geometry of the loss, we present optimization results for the single-local step and K-local step distributed learning and subsequent bounds on communication complexity, with implications for analyzing and implementing distributed learning for overparameterized deep models."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/124716"],"dc:language":["en","eng"],"dc:rights":["2024 Mayank Shrivastava"],"dc:subject":["Distributed Learning","Deep Learning","Sketching","Overparametrized Models","Machine Learning"],"dc:title":["Breaking the dimension dependence in distributed learning"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:02Z"}