{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/116105"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/116105","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Exploitable structures and complexities of modern nonconvex optimization: Fundamental limits and efficient algorithms","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":["Zhang, Siqi"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["He, Niao","Chen, Xin","Chen, Yuguo","Sun, Ruoyu"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-08","date_published":"2022-08","updated_at":"2026-07-22T22:24:55Z","subjects":["Nonconvex optimization","Minimax optimization","Oracle complexity","Generalization","Machine Learning"],"languages":["en","eng"],"rights":["Copyright 2022 Siqi Zhang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/116105","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["He, Niao","Chen, Xin","Chen, Yuguo","Sun, Ruoyu"]},{"key":"dc:creator","label":"Author","values":["Zhang, Siqi"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-08","2022-07-14"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial 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":["Nonconvex optimization","Minimax optimization","Oracle complexity","Generalization","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":["Copyright 2022 Siqi Zhang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/116105"]}]},{"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, Siqi Zhang, accepted the attached license on 2022-07-14 at 15:02.","The student, Siqi Zhang, submitted this Dissertation for approval on 2022-07-14 at 15:05.","This Dissertation was approved for publication on 2022-07-14 at 17:21.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18313 on 2022-11-15 at 21:40:12","Many modern machine learning applications are formulated as nonconvex optimization problems. Generally speaking, the study of nonconvex optimization comes with two perspectives: finding the fundamental computational limits and designing efficient algorithms, which corresponds to upper and lower complexity bounds in optimization theory. Recently the rapidly developing machine learning technology, e.g., adversarial training, meta-learning and deep learning, brings many new computational challenges. They are more difficult to solve due to that, for example, the objective function is no longer differentiable, or it is hard to get the true gradient or its unbiased estimator, which urges the development of new theory and efficient algorithms. The thesis studies several nonconvex optimization problems with special structures, which have broad applications in machine learning and other areas, the discussion covers both the upper and lower complexity bound perspectives. In the first part, we study the non-asymptotic stationarity convergence of Stochastic Mirror Descent (SMD) for nonsmooth nonconvex minimization in non-Euclidean settings. We focus on a general class of nonconvex nonsmooth stochastic optimization problems which consists of relatively weakly convex functions (possibly nonsmooth and non-Lipschitz) and a simple nonsmooth convex regularizer. We prove that, without the use of mini-batch, SMD is guaranteed to converge to a stationary point with an $ \\mathcal{O}(\\epsilon^{-4}) $ sample complexity. The efficiency estimate matches with existing results for stochastic subgradient method, while evaluated under a stronger stationarity measure. In the second part, we consider Conditional Stochastic Optimization (CSO) problems, which covers a variety of applications like invariant learning, causal inference and meta-learning. However, constructing unbiased gradient estimators for such problems is challenging due to its composition structure. We propose Biased Stochastic Gradient Descent (BSGD) algorithm and establish its sample complexities for general nonconvex problems. To improve the performance, we propose an accelerated algorithm called Biased SpiderBoost (BSpiderBoost) algorithm based on the recursive variance reduction technique with an improved sample complexity, which matches the corresponding lower complexity bound. We further conduct numerical experiments on several tasks to illustrate the performance of proposed algorithms. In the third part, we study lower complexity bounds of Nonconvex-Strongly-Concave (NC-SC) minimax optimization problems, in both general and averaged smooth finite-sum settings. We establish nontrivial lower complexity bounds of $\\Omega(\\sqrt{\\kappa}\\Delta L\\epsilon^{-2})$ and $\\Omega(n+\\sqrt{n\\kappa}\\Delta L\\epsilon^{-2})$ for the two settings, respectively, where $\\kappa$ is the condition number, $L$ is the smoothness constant, and $\\Delta$ is the initial gap. Our results reveals substantial gaps between these limits and best-known upper bounds in the literature. In the last part, we turn to investigate the generalization performances of nonconvex minimax optimization problems. Existing literature on this topic is restricted in terms that they generally requires a case-by-case study for each specific algorithm, also their analysis often resort to function value based measurement, which may not fit well the nonconvex structure. Here we initialize to study generalization performances measured by the stationarity of primal functions, and resort to the uniform convergence argument which provides generalization error independent of the choice of algorithms. Specifically, the sample complexities to achieve an $\\epsilon$-uniform convergence and an $\\epsilon$-generalization error are $\\tilde{\\mathcal{O}}\\autopar{d\\kappa^2\\epsilon^{-2}}$ and $\\tilde{\\mathcal{O}}\\autopar{d\\epsilon^{-4}}$ for the NC-SC and NC-C settings, respectively. The results also help us to derive the gradient complexity for solving the population problems, which matches with existing SOTA literature."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Exploitable structures and complexities of modern nonconvex optimization: Fundamental limits and efficient algorithms"]}]}],"canonical_facts":{"dc:contributor":["He, Niao","Chen, Xin","Chen, Yuguo","Sun, Ruoyu"],"dc:creator":["Zhang, Siqi"],"dc:date":["2022-08","2022-07-14"],"dc:description":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2024-08-01","The student, Siqi Zhang, accepted the attached license on 2022-07-14 at 15:02.","The student, Siqi Zhang, submitted this Dissertation for approval on 2022-07-14 at 15:05.","This Dissertation was approved for publication on 2022-07-14 at 17:21.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18313 on 2022-11-15 at 21:40:12","Many modern machine learning applications are formulated as nonconvex optimization problems. Generally speaking, the study of nonconvex optimization comes with two perspectives: finding the fundamental computational limits and designing efficient algorithms, which corresponds to upper and lower complexity bounds in optimization theory. Recently the rapidly developing machine learning technology, e.g., adversarial training, meta-learning and deep learning, brings many new computational challenges. They are more difficult to solve due to that, for example, the objective function is no longer differentiable, or it is hard to get the true gradient or its unbiased estimator, which urges the development of new theory and efficient algorithms. The thesis studies several nonconvex optimization problems with special structures, which have broad applications in machine learning and other areas, the discussion covers both the upper and lower complexity bound perspectives. In the first part, we study the non-asymptotic stationarity convergence of Stochastic Mirror Descent (SMD) for nonsmooth nonconvex minimization in non-Euclidean settings. We focus on a general class of nonconvex nonsmooth stochastic optimization problems which consists of relatively weakly convex functions (possibly nonsmooth and non-Lipschitz) and a simple nonsmooth convex regularizer. We prove that, without the use of mini-batch, SMD is guaranteed to converge to a stationary point with an $ \\mathcal{O}(\\epsilon^{-4}) $ sample complexity. The efficiency estimate matches with existing results for stochastic subgradient method, while evaluated under a stronger stationarity measure. In the second part, we consider Conditional Stochastic Optimization (CSO) problems, which covers a variety of applications like invariant learning, causal inference and meta-learning. However, constructing unbiased gradient estimators for such problems is challenging due to its composition structure. We propose Biased Stochastic Gradient Descent (BSGD) algorithm and establish its sample complexities for general nonconvex problems. To improve the performance, we propose an accelerated algorithm called Biased SpiderBoost (BSpiderBoost) algorithm based on the recursive variance reduction technique with an improved sample complexity, which matches the corresponding lower complexity bound. We further conduct numerical experiments on several tasks to illustrate the performance of proposed algorithms. In the third part, we study lower complexity bounds of Nonconvex-Strongly-Concave (NC-SC) minimax optimization problems, in both general and averaged smooth finite-sum settings. We establish nontrivial lower complexity bounds of $\\Omega(\\sqrt{\\kappa}\\Delta L\\epsilon^{-2})$ and $\\Omega(n+\\sqrt{n\\kappa}\\Delta L\\epsilon^{-2})$ for the two settings, respectively, where $\\kappa$ is the condition number, $L$ is the smoothness constant, and $\\Delta$ is the initial gap. Our results reveals substantial gaps between these limits and best-known upper bounds in the literature. In the last part, we turn to investigate the generalization performances of nonconvex minimax optimization problems. Existing literature on this topic is restricted in terms that they generally requires a case-by-case study for each specific algorithm, also their analysis often resort to function value based measurement, which may not fit well the nonconvex structure. Here we initialize to study generalization performances measured by the stationarity of primal functions, and resort to the uniform convergence argument which provides generalization error independent of the choice of algorithms. Specifically, the sample complexities to achieve an $\\epsilon$-uniform convergence and an $\\epsilon$-generalization error are $\\tilde{\\mathcal{O}}\\autopar{d\\kappa^2\\epsilon^{-2}}$ and $\\tilde{\\mathcal{O}}\\autopar{d\\epsilon^{-4}}$ for the NC-SC and NC-C settings, respectively. The results also help us to derive the gradient complexity for solving the population problems, which matches with existing SOTA literature."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/116105"],"dc:language":["en","eng"],"dc:rights":["Copyright 2022 Siqi Zhang"],"dc:subject":["Nonconvex optimization","Minimax optimization","Oracle complexity","Generalization","Machine Learning"],"dc:title":["Exploitable structures and complexities of modern nonconvex optimization: Fundamental limits and efficient algorithms"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Industrial 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"}