{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/116050"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/116050","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Communication efficient large scale distributed optimization with curvature acceleration","abstract":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2024-08-01","abstract_html":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2024-08-01","abstract_has_math":false,"creators":["Li, Yichuan"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mechanical Engineering","degree_department":null,"school":null,"contributors":["Freris, Nikolaos M.","Voulgaris, Petros G.","Hovakimyan, Naira","Stipanovic, Dusan M.","Salapaka, Srinivasa M."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-08","date_published":"2022-08","updated_at":"2026-07-22T22:24:55Z","subjects":["Decentralized optimization","large scale machine learning","Federated Learning"],"languages":["en","eng"],"rights":["Copyright 2022 Yichuan Li"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/116050","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Freris, Nikolaos M.","Voulgaris, Petros G.","Hovakimyan, Naira","Stipanovic, Dusan M.","Salapaka, Srinivasa M."]},{"key":"dc:creator","label":"Author","values":["Li, Yichuan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-08","2022-07-11"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mechanical Engineering"]},{"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":["Decentralized optimization","large scale machine learning","Federated 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":["Copyright 2022 Yichuan Li"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/116050"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2024-08-01","The student, Yichuan Li, accepted the attached license on 2022-07-06 at 11:46.","The student, Yichuan Li, submitted this Dissertation for approval on 2022-07-06 at 11:48.","This Dissertation was approved for publication on 2022-07-11 at 12:24.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18138 on 2022-11-15 at 19:16:58","Distributed optimization has proven to be an effective scheme to tackle numerous emerging problems that are surged by the development of digital technologies and mobile smart devices. Examples include control of robot swarms, distributed and large scale machine learning, estimation in sensor networks, and management of smart grids. In such setups, the individual interests of agents (machines) have to be collectively optimized under stringent restrictions on communication bandwidth, computation resources, and security concerns. To balance the efforts on optimizing local objectives and cooperation among the network is challenging while necessary to achieve a global solution. Many endeavors have been made to design efficient algorithms that can harness the computation power of a heterogeneous network, in terms of both machine hardware and data distribution. The majority of existing algorithms can be categorized as first-order methods, where the computation process is guided only by the objective (sub) gradient information. Such practices have found many successes due to their economical computation costs and uninvolved implementation. Nevertheless, first-order algorithms suffer from a common drawback: slow convergence rate, especially when the objective curvature is skewed. This induces large overall iteration numbers and prevents the implementation of first order algorithms to applications where accurate solutions are sought in few rounds, such as real time computation on embedded systems and communication expensive learning practices. In this dissertation, we shift our attention to second-order methods that aim to accelerate the iterative process through use of objective curvature. The main challenge of designing second-order methods in large scale networks is threefold: (i) distributed implementation, (ii) computation and communication balance, and (iii) network synchronization. These challenges are not unique to devising decentralized second-order methods, but become more pronounced due to the involvement of Hessian matrices, solving linear systems, backtracking line search, and approximation of curvature information etc. We address these challenges in several steps. Chapter \\ref{chapter_acc} tackles the distributed convex composite problem by presenting two algorithms that distributedly approximate the curvature information from the perspective of Method of Multipliers and Alternating Direction Method of Multipliers. By increasing the accuracy of approximation, we show both theoretically and empirically that the proposed algorithms achieve faster convergence rate, and thus providing a tunable adjustment between convergence speed and algorithm expenditures. Chapter \\ref{chapter_druid} presents a unified framework for designing algorithms that can harness curvature information with communication efficiency. Several algorithms are designed and analyzed in a unified fashion, including computation schemes using gradient descent, Newton method, and BFGS. Their differences and advantages are discussed, analyzed, and demonstrated. This offers significant flexibility for agents in choosing updating schemes that are most suitable for their local environments. Chapter \\ref{chapter_asy} further extends the previous framework to the asynchronous setting, where agents participate in the computation without coordination. This eliminates the need for network wide synchronization among agents. The proposed framework imposes minimal assumptions in terms of the participating frequency and asynchrony between agents, which further broadens the applicability of the proposed algorithms. Chapter \\ref{chapter_FL} studies an emerging topic termed Federated Learning, which embodies the challenges we considered in previous chapters. Namely, stringent requirement on communication costs in terms of both frequencies and message sizes, highly heterogeneous networks with massive number of agents with drastically different local environments, non-i.i.d data distributions with imbalanced data volumes, and strict limits on privacy. We present a novel algorithm that accommodates all these difficulties, and show that it achieves optimal algorithmic complexity. Extensive experiments are conducted to demonstrate its superiority over existing methods."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Communication efficient large scale distributed optimization with curvature acceleration"]}]}],"canonical_facts":{"dc:contributor":["Freris, Nikolaos M.","Voulgaris, Petros G.","Hovakimyan, Naira","Stipanovic, Dusan M.","Salapaka, Srinivasa M."],"dc:creator":["Li, Yichuan"],"dc:date":["2022-08","2022-07-11"],"dc:description":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2024-08-01","The student, Yichuan Li, accepted the attached license on 2022-07-06 at 11:46.","The student, Yichuan Li, submitted this Dissertation for approval on 2022-07-06 at 11:48.","This Dissertation was approved for publication on 2022-07-11 at 12:24.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18138 on 2022-11-15 at 19:16:58","Distributed optimization has proven to be an effective scheme to tackle numerous emerging problems that are surged by the development of digital technologies and mobile smart devices. Examples include control of robot swarms, distributed and large scale machine learning, estimation in sensor networks, and management of smart grids. In such setups, the individual interests of agents (machines) have to be collectively optimized under stringent restrictions on communication bandwidth, computation resources, and security concerns. To balance the efforts on optimizing local objectives and cooperation among the network is challenging while necessary to achieve a global solution. Many endeavors have been made to design efficient algorithms that can harness the computation power of a heterogeneous network, in terms of both machine hardware and data distribution. The majority of existing algorithms can be categorized as first-order methods, where the computation process is guided only by the objective (sub) gradient information. Such practices have found many successes due to their economical computation costs and uninvolved implementation. Nevertheless, first-order algorithms suffer from a common drawback: slow convergence rate, especially when the objective curvature is skewed. This induces large overall iteration numbers and prevents the implementation of first order algorithms to applications where accurate solutions are sought in few rounds, such as real time computation on embedded systems and communication expensive learning practices. In this dissertation, we shift our attention to second-order methods that aim to accelerate the iterative process through use of objective curvature. The main challenge of designing second-order methods in large scale networks is threefold: (i) distributed implementation, (ii) computation and communication balance, and (iii) network synchronization. These challenges are not unique to devising decentralized second-order methods, but become more pronounced due to the involvement of Hessian matrices, solving linear systems, backtracking line search, and approximation of curvature information etc. We address these challenges in several steps. Chapter \\ref{chapter_acc} tackles the distributed convex composite problem by presenting two algorithms that distributedly approximate the curvature information from the perspective of Method of Multipliers and Alternating Direction Method of Multipliers. By increasing the accuracy of approximation, we show both theoretically and empirically that the proposed algorithms achieve faster convergence rate, and thus providing a tunable adjustment between convergence speed and algorithm expenditures. Chapter \\ref{chapter_druid} presents a unified framework for designing algorithms that can harness curvature information with communication efficiency. Several algorithms are designed and analyzed in a unified fashion, including computation schemes using gradient descent, Newton method, and BFGS. Their differences and advantages are discussed, analyzed, and demonstrated. This offers significant flexibility for agents in choosing updating schemes that are most suitable for their local environments. Chapter \\ref{chapter_asy} further extends the previous framework to the asynchronous setting, where agents participate in the computation without coordination. This eliminates the need for network wide synchronization among agents. The proposed framework imposes minimal assumptions in terms of the participating frequency and asynchrony between agents, which further broadens the applicability of the proposed algorithms. Chapter \\ref{chapter_FL} studies an emerging topic termed Federated Learning, which embodies the challenges we considered in previous chapters. Namely, stringent requirement on communication costs in terms of both frequencies and message sizes, highly heterogeneous networks with massive number of agents with drastically different local environments, non-i.i.d data distributions with imbalanced data volumes, and strict limits on privacy. We present a novel algorithm that accommodates all these difficulties, and show that it achieves optimal algorithmic complexity. Extensive experiments are conducted to demonstrate its superiority over existing methods."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/116050"],"dc:language":["en","eng"],"dc:rights":["Copyright 2022 Yichuan Li"],"dc:subject":["Decentralized optimization","large scale machine learning","Federated Learning"],"dc:title":["Communication efficient large scale distributed optimization with curvature acceleration"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Mechanical Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:55Z"}