{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/44389"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/44389","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Optimization over networks: Efficient algorithms and analysis","abstract":"A number of important problems that arise in various application domains can be formulated as a distributed convex constrained minimization problem over a multi-agent network. The problem is usually defined as a sum of convex objective functions over an intersection of convex constraint sets. The first part of this thesis is focused on the development and analysis of efficient distributed algorithms for a constrained convex optimization problem over a multi-agent network where each agent has its own objective function and constraint set. We propose gradient descent algorithms with random projections which use various communication protocols. First, we present a distributed random projection (DRP) algorithm whereby each agent exchanges local information only with its immediate neighbors at each iteration. With reasonable assumptions, we prove that the iterates of all agents converge to the same point in the optimal set with probability 1. In addition, we consider a variant of the method that uses a mini-batch of consecutive random projections and establish its convergence. Experiments on distributed support vector machines demonstrate fast convergence of the DRP algorithm. It actually shows that the number of iterations required for convergence is much smaller than that for scanning over all training samples just once. Second, we propose an asynchronous gossip-based random projection (GRP) algorithm that solves the distributed problem using gossip type communications and local computations. We analyze the convergence properties of the algorithm for an uncoordinated diminishing stepsize and a constant stepsize. For a diminishing stepsize, we prove that the iterates of all agents converge to the same optimal point with probability 1. For a constant stepsize, we establish an error bound on the expected distance from the optimal point to the iterates of the algorithm. In addition, we consider a variant of the method that uses a mini-batch of consecutive random projections and, also, establish its convergence. Furthermore, we provide simulation results on a distributed robust model predictive control problem. In the second part of the thesis, we discuss an efficient epoch gradient descent algorithm for obtaining fast and exact solutions of linear support vector machines (SVMs). SVMs penalized with the popular hinge-loss are strongly convex but they do not have Lipschitz continuous gradient. We find SVMs that have both strong-convexity and Lipschitz continuous gradient using a smooth approximation technique.","abstract_html":"A number of important problems that arise in various application domains can be formulated as a distributed convex constrained minimization problem over a multi-agent network. The problem is usually defined as a sum of convex objective functions over an intersection of convex constraint sets. The first part of this thesis is focused on the development and analysis of efficient distributed algorithms for a constrained convex optimization problem over a multi-agent network where each agent has its own objective function and constraint set. We propose gradient descent algorithms with random projections which use various communication protocols. First, we present a distributed random projection (DRP) algorithm whereby each agent exchanges local information only with its immediate neighbors at each iteration. With reasonable assumptions, we prove that the iterates of all agents converge to the same point in the optimal set with probability 1. In addition, we consider a variant of the method that uses a mini-batch of consecutive random projections and establish its convergence. Experiments on distributed support vector machines demonstrate fast convergence of the DRP algorithm. It actually shows that the number of iterations required for convergence is much smaller than that for scanning over all training samples just once. Second, we propose an asynchronous gossip-based random projection (GRP) algorithm that solves the distributed problem using gossip type communications and local computations. We analyze the convergence properties of the algorithm for an uncoordinated diminishing stepsize and a constant stepsize. For a diminishing stepsize, we prove that the iterates of all agents converge to the same optimal point with probability 1. For a constant stepsize, we establish an error bound on the expected distance from the optimal point to the iterates of the algorithm. In addition, we consider a variant of the method that uses a mini-batch of consecutive random projections and, also, establish its convergence. Furthermore, we provide simulation results on a distributed robust model predictive control problem. In the second part of the thesis, we discuss an efficient epoch gradient descent algorithm for obtaining fast and exact solutions of linear support vector machines (SVMs). SVMs penalized with the popular hinge-loss are strongly convex but they do not have Lipschitz continuous gradient. We find SVMs that have both strong-convexity and Lipschitz continuous gradient using a smooth approximation technique.","abstract_has_math":false,"creators":["Lee, Soomin"],"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":["Nedich, Angelia","Roth, Dan","Milenkovic, Olgica","Veeravalli, Venugopal V."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-05-24T22:10:00Z","date_published":"2013-05-24T22:10:00Z","updated_at":"2026-07-22T22:25:34Z","subjects":["Distributed optimization","Random projections","Large-scale optimization","Machine learning","Support vector machines","Convergence analysis","Random gossip networks","Consensus","Multi-agent systems"],"languages":["en"],"rights":["Copyright 2013 Soomin Lee"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/44389","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Nedich, Angelia","Roth, Dan","Milenkovic, Olgica","Veeravalli, Venugopal V."]},{"key":"dc:creator","label":"Author","values":["Lee, Soomin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2013-05-24T22:10:00Z","2019-02-20T10:15:37Z","2013-05"]},{"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 optimization","Random projections","Large-scale optimization","Machine learning","Support vector machines","Convergence analysis","Random gossip networks","Consensus","Multi-agent systems"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2013 Soomin Lee"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/44389"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["A number of important problems that arise in various application domains can be formulated as a distributed convex constrained minimization problem over a multi-agent network. The problem is usually defined as a sum of convex objective functions over an intersection of convex constraint sets. The first part of this thesis is focused on the development and analysis of efficient distributed algorithms for a constrained convex optimization problem over a multi-agent network where each agent has its own objective function and constraint set. We propose gradient descent algorithms with random projections which use various communication protocols. First, we present a distributed random projection (DRP) algorithm whereby each agent exchanges local information only with its immediate neighbors at each iteration. With reasonable assumptions, we prove that the iterates of all agents converge to the same point in the optimal set with probability 1. In addition, we consider a variant of the method that uses a mini-batch of consecutive random projections and establish its convergence. Experiments on distributed support vector machines demonstrate fast convergence of the DRP algorithm. It actually shows that the number of iterations required for convergence is much smaller than that for scanning over all training samples just once. Second, we propose an asynchronous gossip-based random projection (GRP) algorithm that solves the distributed problem using gossip type communications and local computations. We analyze the convergence properties of the algorithm for an uncoordinated diminishing stepsize and a constant stepsize. For a diminishing stepsize, we prove that the iterates of all agents converge to the same optimal point with probability 1. For a constant stepsize, we establish an error bound on the expected distance from the optimal point to the iterates of the algorithm. In addition, we consider a variant of the method that uses a mini-batch of consecutive random projections and, also, establish its convergence. Furthermore, we provide simulation results on a distributed robust model predictive control problem. In the second part of the thesis, we discuss an efficient epoch gradient descent algorithm for obtaining fast and exact solutions of linear support vector machines (SVMs). SVMs penalized with the popular hinge-loss are strongly convex but they do not have Lipschitz continuous gradient. We find SVMs that have both strong-convexity and Lipschitz continuous gradient using a smooth approximation technique.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-04-05T14:09:38Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Lee_Soomin.pdf: 635319 bytes, checksum: e7d94095056659a9396dbc826712c012 (MD5)","Made available in DSpace on 2013-05-24T22:10:00Z (GMT). No. of bitstreams: 2 Soomin_Lee.pdf: 635319 bytes, checksum: e7d94095056659a9396dbc826712c012 (MD5) license.txt: 4058 bytes, checksum: 265ac04ecc9cdbcc6c6dbc0970fac65b (MD5)","Updated title so that it was in sentence case correctly. Changes made by astein@illinois.edu on 2017/02/20 at 10:26AM-CST","U of I Only Restriction set for Item 44362 on 2017-02-20T16:34:44Z with date 2019-02-20 by astein@illinois.edu.","U of I Only Restriction set for Item 44362 on 2017-02-20T16:34:53Z with date 2019-02-20 by astein@illinois.edu.","U of I Only Restriction Lifted for Item 44362 on 2019-02-20T10:15:37Z."]},{"key":"dc:title","label":"Title","values":["Optimization over networks: Efficient algorithms and analysis"]}]}],"canonical_facts":{"dc:contributor":["Nedich, Angelia","Roth, Dan","Milenkovic, Olgica","Veeravalli, Venugopal V."],"dc:creator":["Lee, Soomin"],"dc:date":["2013-05-24T22:10:00Z","2019-02-20T10:15:37Z","2013-05"],"dc:description":["A number of important problems that arise in various application domains can be formulated as a distributed convex constrained minimization problem over a multi-agent network. The problem is usually defined as a sum of convex objective functions over an intersection of convex constraint sets. The first part of this thesis is focused on the development and analysis of efficient distributed algorithms for a constrained convex optimization problem over a multi-agent network where each agent has its own objective function and constraint set. We propose gradient descent algorithms with random projections which use various communication protocols. First, we present a distributed random projection (DRP) algorithm whereby each agent exchanges local information only with its immediate neighbors at each iteration. With reasonable assumptions, we prove that the iterates of all agents converge to the same point in the optimal set with probability 1. In addition, we consider a variant of the method that uses a mini-batch of consecutive random projections and establish its convergence. Experiments on distributed support vector machines demonstrate fast convergence of the DRP algorithm. It actually shows that the number of iterations required for convergence is much smaller than that for scanning over all training samples just once. Second, we propose an asynchronous gossip-based random projection (GRP) algorithm that solves the distributed problem using gossip type communications and local computations. We analyze the convergence properties of the algorithm for an uncoordinated diminishing stepsize and a constant stepsize. For a diminishing stepsize, we prove that the iterates of all agents converge to the same optimal point with probability 1. For a constant stepsize, we establish an error bound on the expected distance from the optimal point to the iterates of the algorithm. In addition, we consider a variant of the method that uses a mini-batch of consecutive random projections and, also, establish its convergence. Furthermore, we provide simulation results on a distributed robust model predictive control problem. In the second part of the thesis, we discuss an efficient epoch gradient descent algorithm for obtaining fast and exact solutions of linear support vector machines (SVMs). SVMs penalized with the popular hinge-loss are strongly convex but they do not have Lipschitz continuous gradient. We find SVMs that have both strong-convexity and Lipschitz continuous gradient using a smooth approximation technique.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-04-05T14:09:38Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Lee_Soomin.pdf: 635319 bytes, checksum: e7d94095056659a9396dbc826712c012 (MD5)","Made available in DSpace on 2013-05-24T22:10:00Z (GMT). No. of bitstreams: 2 Soomin_Lee.pdf: 635319 bytes, checksum: e7d94095056659a9396dbc826712c012 (MD5) license.txt: 4058 bytes, checksum: 265ac04ecc9cdbcc6c6dbc0970fac65b (MD5)","Updated title so that it was in sentence case correctly. Changes made by astein@illinois.edu on 2017/02/20 at 10:26AM-CST","U of I Only Restriction set for Item 44362 on 2017-02-20T16:34:44Z with date 2019-02-20 by astein@illinois.edu.","U of I Only Restriction set for Item 44362 on 2017-02-20T16:34:53Z with date 2019-02-20 by astein@illinois.edu.","U of I Only Restriction Lifted for Item 44362 on 2019-02-20T10:15:37Z."],"dc:identifier":["http://hdl.handle.net/2142/44389"],"dc:language":["en"],"dc:rights":["Copyright 2013 Soomin Lee"],"dc:subject":["Distributed optimization","Random projections","Large-scale optimization","Machine learning","Support vector machines","Convergence analysis","Random gossip networks","Consensus","Multi-agent systems"],"dc:title":["Optimization over networks: Efficient algorithms and analysis"],"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:25:34Z"}