{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/97298"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/97298","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Accelerated first-order optimization methods using inertia and error bounds","abstract":"Optimization is an important discipline of applied mathematics with far-reaching applications. Optimization algorithms often form the backbone of practical systems in machine learning, image processing, signal processing, computer vision, data analysis, and statistics. In an age of massive data sets and huge numbers of variables, a deep understanding of optimization is a necessary condition for developing scalable, computationally inexpensive, and reliable algorithms. In this thesis we design and analyze efficient algorithms for solving the large-scale nonsmooth optimization problems arising in modern signal processing and machine learning applications. The focus is on first-order methods which have low per-iteration complexity and can exploit problem structure to a high degree. First-order methods have the capacity to address large-scale problems for which all alternative methods fail. However, first-order methods can take many iterations to reach the desired accuracy. This has led optimization researchers to ask the following question: is it possible to improve the convergence rate of first-order methods without jeopardizing their low per-iteration complexity? In this thesis, we address this question in three areas. Firstly we investigate the use of inertia to accelerate the convergence of proximal gradient methods for convex composite optimization problems. We pay special attention to the famous lasso problem for which we develop an improved version of the well-known Fast Iterative Soft-Thresholding Algorithm. Secondly we investigate the use of inertia for nonconvex composite problems, making use of the Kurdukya-Lojaziewicz inequality in our analysis. Finally, when the objective function satisfies an error bound which is fairly common in practice, we develop stepsize selections for the subgradient method which significantly outperform the classical approach. The overarching message of this thesis is the following: with careful analysis and design, the convergence rate of first-order methods can be significantly improved.","abstract_html":"Optimization is an important discipline of applied mathematics with far-reaching applications. Optimization algorithms often form the backbone of practical systems in machine learning, image processing, signal processing, computer vision, data analysis, and statistics. In an age of massive data sets and huge numbers of variables, a deep understanding of optimization is a necessary condition for developing scalable, computationally inexpensive, and reliable algorithms. In this thesis we design and analyze efficient algorithms for solving the large-scale nonsmooth optimization problems arising in modern signal processing and machine learning applications. The focus is on first-order methods which have low per-iteration complexity and can exploit problem structure to a high degree. First-order methods have the capacity to address large-scale problems for which all alternative methods fail. However, first-order methods can take many iterations to reach the desired accuracy. This has led optimization researchers to ask the following question: is it possible to improve the convergence rate of first-order methods without jeopardizing their low per-iteration complexity? In this thesis, we address this question in three areas. Firstly we investigate the use of inertia to accelerate the convergence of proximal gradient methods for convex composite optimization problems. We pay special attention to the famous lasso problem for which we develop an improved version of the well-known Fast Iterative Soft-Thresholding Algorithm. Secondly we investigate the use of inertia for nonconvex composite problems, making use of the Kurdukya-Lojaziewicz inequality in our analysis. Finally, when the objective function satisfies an error bound which is fairly common in practice, we develop stepsize selections for the subgradient method which significantly outperform the classical approach. The overarching message of this thesis is the following: with careful analysis and design, the convergence rate of first-order methods can be significantly improved.","abstract_has_math":false,"creators":["Johnstone, Patrick Royce"],"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":["Moulin, Pierre","Bresler, Yoram","He, Niao","Nedich, Angelia","Srikant, Rayadurgam"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-08-10T19:14:42Z","date_published":"2017-08-10T19:14:42Z","updated_at":"2026-07-22T22:24:32Z","subjects":["Optimization","Convergence analysis","Accelerated first-order methods","Subgradient methods"],"languages":["en"],"rights":["Copyright 2017 Patrick Royce Johnstone"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/97298","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Moulin, Pierre","Bresler, Yoram","He, Niao","Nedich, Angelia","Srikant, Rayadurgam"]},{"key":"dc:creator","label":"Author","values":["Johnstone, Patrick Royce"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-08-10T19:14:42Z","2017-04-07","2017-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":["Optimization","Convergence analysis","Accelerated first-order methods","Subgradient methods"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2017 Patrick Royce Johnstone"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/97298"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Optimization is an important discipline of applied mathematics with far-reaching applications. Optimization algorithms often form the backbone of practical systems in machine learning, image processing, signal processing, computer vision, data analysis, and statistics. In an age of massive data sets and huge numbers of variables, a deep understanding of optimization is a necessary condition for developing scalable, computationally inexpensive, and reliable algorithms. In this thesis we design and analyze efficient algorithms for solving the large-scale nonsmooth optimization problems arising in modern signal processing and machine learning applications. The focus is on first-order methods which have low per-iteration complexity and can exploit problem structure to a high degree. First-order methods have the capacity to address large-scale problems for which all alternative methods fail. However, first-order methods can take many iterations to reach the desired accuracy. This has led optimization researchers to ask the following question: is it possible to improve the convergence rate of first-order methods without jeopardizing their low per-iteration complexity? In this thesis, we address this question in three areas. Firstly we investigate the use of inertia to accelerate the convergence of proximal gradient methods for convex composite optimization problems. We pay special attention to the famous lasso problem for which we develop an improved version of the well-known Fast Iterative Soft-Thresholding Algorithm. Secondly we investigate the use of inertia for nonconvex composite problems, making use of the Kurdukya-Lojaziewicz inequality in our analysis. Finally, when the objective function satisfies an error bound which is fairly common in practice, we develop stepsize selections for the subgradient method which significantly outperform the classical approach. The overarching message of this thesis is the following: with careful analysis and design, the convergence rate of first-order methods can be significantly improved.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-08-10 without embargo terms","The student, Patrick Johnstone, accepted the attached license on 2017-04-06 at 16:12.","The student, Patrick Johnstone, submitted this Dissertation for approval on 2017-04-06 at 16:23.","This Dissertation was approved for publication on 2017-04-07 at 15:21.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10644 on 2017-08-10 at 13:38:43","Made available in DSpace on 2017-08-10T19:14:42Z (GMT). No. of bitstreams: 3 JOHNSTONE-DISSERTATION-2017.pdf: 1101037 bytes, checksum: c5007a0d4fa3aa7c5f81d3f8d172907b (MD5) LICENSE.txt: 4214 bytes, checksum: bcc4970db5a6ae227e75a9a8a2671bfb (MD5) PROQUEST_LICENSE.txt: 4560 bytes, checksum: 713076ba6ca35cf666b8afd2cd292896 (MD5) Previous issue date: 2017-04-07"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Accelerated first-order optimization methods using inertia and error bounds"]}]}],"canonical_facts":{"dc:contributor":["Moulin, Pierre","Bresler, Yoram","He, Niao","Nedich, Angelia","Srikant, Rayadurgam"],"dc:creator":["Johnstone, Patrick Royce"],"dc:date":["2017-08-10T19:14:42Z","2017-04-07","2017-05"],"dc:description":["Optimization is an important discipline of applied mathematics with far-reaching applications. Optimization algorithms often form the backbone of practical systems in machine learning, image processing, signal processing, computer vision, data analysis, and statistics. In an age of massive data sets and huge numbers of variables, a deep understanding of optimization is a necessary condition for developing scalable, computationally inexpensive, and reliable algorithms. In this thesis we design and analyze efficient algorithms for solving the large-scale nonsmooth optimization problems arising in modern signal processing and machine learning applications. The focus is on first-order methods which have low per-iteration complexity and can exploit problem structure to a high degree. First-order methods have the capacity to address large-scale problems for which all alternative methods fail. However, first-order methods can take many iterations to reach the desired accuracy. This has led optimization researchers to ask the following question: is it possible to improve the convergence rate of first-order methods without jeopardizing their low per-iteration complexity? In this thesis, we address this question in three areas. Firstly we investigate the use of inertia to accelerate the convergence of proximal gradient methods for convex composite optimization problems. We pay special attention to the famous lasso problem for which we develop an improved version of the well-known Fast Iterative Soft-Thresholding Algorithm. Secondly we investigate the use of inertia for nonconvex composite problems, making use of the Kurdukya-Lojaziewicz inequality in our analysis. Finally, when the objective function satisfies an error bound which is fairly common in practice, we develop stepsize selections for the subgradient method which significantly outperform the classical approach. The overarching message of this thesis is the following: with careful analysis and design, the convergence rate of first-order methods can be significantly improved.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-08-10 without embargo terms","The student, Patrick Johnstone, accepted the attached license on 2017-04-06 at 16:12.","The student, Patrick Johnstone, submitted this Dissertation for approval on 2017-04-06 at 16:23.","This Dissertation was approved for publication on 2017-04-07 at 15:21.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10644 on 2017-08-10 at 13:38:43","Made available in DSpace on 2017-08-10T19:14:42Z (GMT). No. of bitstreams: 3 JOHNSTONE-DISSERTATION-2017.pdf: 1101037 bytes, checksum: c5007a0d4fa3aa7c5f81d3f8d172907b (MD5) LICENSE.txt: 4214 bytes, checksum: bcc4970db5a6ae227e75a9a8a2671bfb (MD5) PROQUEST_LICENSE.txt: 4560 bytes, checksum: 713076ba6ca35cf666b8afd2cd292896 (MD5) Previous issue date: 2017-04-07"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/97298"],"dc:language":["en"],"dc:rights":["Copyright 2017 Patrick Royce Johnstone"],"dc:subject":["Optimization","Convergence analysis","Accelerated first-order methods","Subgradient methods"],"dc:title":["Accelerated first-order optimization methods using inertia and error bounds"],"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:32Z"}