{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/116224"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/116224","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Stochastic optimization with biased oracles and hidden convexity","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms","abstract_has_math":false,"creators":["Hu, Yifan"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["Chen, Xin","He, Niao","Srikant, Rayadurgam","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":["Stochastic Optimization","Sample Average Approximation","Gradient Descent","Nonconvex optimization"],"languages":["en","eng"],"rights":["Copyright 2022 Yifan Hu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/116224","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Chen, Xin","He, Niao","Srikant, Rayadurgam","Sun, Ruoyu"]},{"key":"dc:creator","label":"Author","values":["Hu, Yifan"]}]},{"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":["Stochastic Optimization","Sample Average Approximation","Gradient Descent","Nonconvex optimization"]}]},{"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 Yifan Hu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/116224"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms","The student, Yifan Hu, accepted the attached license on 2022-07-13 at 13:01.","The student, Yifan Hu, submitted this Dissertation for approval on 2022-07-13 at 13:02.","This Dissertation was approved for publication on 2022-07-14 at 09:00.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18268 on 2022-11-15 at 18:20:48","Stochastic optimization is the engine for modern machine learning tasks. However, various modern machine learning tasks, i.e., distributionally robust optimization, invariant learning, personalized federated learning, meta-learning, and continual learning cannot be modeled as classical stochastic optimization. Consequently, it is hard to obtain unbiased zeorth-order or first-order information for these problems. For various problems, it remains unclear how to handle the potential bias and demonstrate the sample complexity and the oracle complexity for achieving approximate optimal solutions for (strongly) convex objectives and approximate stationary points for nonconvex objectives. In the first part of the thesis, we first propose the \\emph{conditional stochastic optimization} (CSO). It provides strong modeling capability for a wide spectrum of applications, including portfolio selection, reinforcement learning, robust learning, causal inference, and model-agnostic meta-learning. We study the sample complexities of a modified sample average approximation and a proposed biased stochastic gradient descent method for the conditional stochastic optimization. In addition, we show the lower bounds on the expected error of the CSO problem using a biased oracle model. On various applications, we demonstrate the superior performance of the proposed methods. We further consider the \\emph{stochastic optimization with biased oracles}, which is a generalization of the CSO problem. It is used to model stochastic optimization when one only has access to biased stochastic oracles of the objective, and obtaining stochastic gradients with low biases comes at high costs. We examine a family of multi-level Monte Carlo (MLMC) gradient methods that exploit a delicate trade-off among the bias, the variance, and the oracle cost. We provide a systematic study of their convergences and total computation complexities for strongly convex, convex, and nonconvex objectives and demonstrate their superiority over the naive biased stochastic gradient method. We show that when applying the MLMC gradient methods to conditional stochastic optimization, it significantly improves the sample complexity of the previously proposed biased gradient method. When applied to Wasserstein distributionally robust optimization and contextual stochastic optimization, the MLMC gradient methods also outperform the naive biased gradient methods. In the second part of the thesis, we consider the \\emph{stochastic nonconvex optimization with hidden convexity}, i.e., there exists a convex reformulation of the original nonconvex problem via an (implicit) variable change. A notable difference comparing to the first part of the work is that we aim to find an approximate global optimal solution rather than an approximate stationary point for the nonconvex problem. In particular, we study a special case when the nonconvex objective is the expectation of a composition of a convex function and a random function, i.e., $\\min_{x\\in\\mathcal{X}} F(x):=\\EE_\\xi [f(\\phi(x,\\xi))]$. Leveraging an (implicit) convex reformulation via a variable transformation $u=\\EE[\\phi(x,\\xi)]$, we develop a regularized stochastic gradient method and a mirror stochastic gradient method that converge to an $\\eps$-global optimal solution and establish their sample and gradient complexities. Interestingly, both methods operate only in the original $x$-space using gradient estimators of the original nonconvex objective $F$ and the mirror stochastic gradient method achieves $\\tilde \\cO(\\eps^{-2})$ sample and gradient complexities, which matches the lower bounds for solving stochastic convex optimization problems. Under booking limits control, we formulate the air-cargo network revenue management (NRM) problem with random two-dimensional capacity, random consumption, and routing flexibility as a special case of such stochastic nonconvex optimization, where the random function $\\phi(x,\\xi)=x\\wedge\\xi$, i.e., the random demand $\\xi$ truncates the booking limit decision $x$. Extensive numerical experiments demonstrate the superior performance of our proposed MSG algorithm for booking limit control with higher revenue and lower computation cost than state-of-the-art bid-price-based control policies, especially when the variance of random capacity is large."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Stochastic optimization with biased oracles and hidden convexity"]}]}],"canonical_facts":{"dc:contributor":["Chen, Xin","He, Niao","Srikant, Rayadurgam","Sun, Ruoyu"],"dc:creator":["Hu, Yifan"],"dc:date":["2022-08","2022-07-14"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms","The student, Yifan Hu, accepted the attached license on 2022-07-13 at 13:01.","The student, Yifan Hu, submitted this Dissertation for approval on 2022-07-13 at 13:02.","This Dissertation was approved for publication on 2022-07-14 at 09:00.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18268 on 2022-11-15 at 18:20:48","Stochastic optimization is the engine for modern machine learning tasks. However, various modern machine learning tasks, i.e., distributionally robust optimization, invariant learning, personalized federated learning, meta-learning, and continual learning cannot be modeled as classical stochastic optimization. Consequently, it is hard to obtain unbiased zeorth-order or first-order information for these problems. For various problems, it remains unclear how to handle the potential bias and demonstrate the sample complexity and the oracle complexity for achieving approximate optimal solutions for (strongly) convex objectives and approximate stationary points for nonconvex objectives. In the first part of the thesis, we first propose the \\emph{conditional stochastic optimization} (CSO). It provides strong modeling capability for a wide spectrum of applications, including portfolio selection, reinforcement learning, robust learning, causal inference, and model-agnostic meta-learning. We study the sample complexities of a modified sample average approximation and a proposed biased stochastic gradient descent method for the conditional stochastic optimization. In addition, we show the lower bounds on the expected error of the CSO problem using a biased oracle model. On various applications, we demonstrate the superior performance of the proposed methods. We further consider the \\emph{stochastic optimization with biased oracles}, which is a generalization of the CSO problem. It is used to model stochastic optimization when one only has access to biased stochastic oracles of the objective, and obtaining stochastic gradients with low biases comes at high costs. We examine a family of multi-level Monte Carlo (MLMC) gradient methods that exploit a delicate trade-off among the bias, the variance, and the oracle cost. We provide a systematic study of their convergences and total computation complexities for strongly convex, convex, and nonconvex objectives and demonstrate their superiority over the naive biased stochastic gradient method. We show that when applying the MLMC gradient methods to conditional stochastic optimization, it significantly improves the sample complexity of the previously proposed biased gradient method. When applied to Wasserstein distributionally robust optimization and contextual stochastic optimization, the MLMC gradient methods also outperform the naive biased gradient methods. In the second part of the thesis, we consider the \\emph{stochastic nonconvex optimization with hidden convexity}, i.e., there exists a convex reformulation of the original nonconvex problem via an (implicit) variable change. A notable difference comparing to the first part of the work is that we aim to find an approximate global optimal solution rather than an approximate stationary point for the nonconvex problem. In particular, we study a special case when the nonconvex objective is the expectation of a composition of a convex function and a random function, i.e., $\\min_{x\\in\\mathcal{X}} F(x):=\\EE_\\xi [f(\\phi(x,\\xi))]$. Leveraging an (implicit) convex reformulation via a variable transformation $u=\\EE[\\phi(x,\\xi)]$, we develop a regularized stochastic gradient method and a mirror stochastic gradient method that converge to an $\\eps$-global optimal solution and establish their sample and gradient complexities. Interestingly, both methods operate only in the original $x$-space using gradient estimators of the original nonconvex objective $F$ and the mirror stochastic gradient method achieves $\\tilde \\cO(\\eps^{-2})$ sample and gradient complexities, which matches the lower bounds for solving stochastic convex optimization problems. Under booking limits control, we formulate the air-cargo network revenue management (NRM) problem with random two-dimensional capacity, random consumption, and routing flexibility as a special case of such stochastic nonconvex optimization, where the random function $\\phi(x,\\xi)=x\\wedge\\xi$, i.e., the random demand $\\xi$ truncates the booking limit decision $x$. Extensive numerical experiments demonstrate the superior performance of our proposed MSG algorithm for booking limit control with higher revenue and lower computation cost than state-of-the-art bid-price-based control policies, especially when the variance of random capacity is large."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/116224"],"dc:language":["en","eng"],"dc:rights":["Copyright 2022 Yifan Hu"],"dc:subject":["Stochastic Optimization","Sample Average Approximation","Gradient Descent","Nonconvex optimization"],"dc:title":["Stochastic optimization with biased oracles and hidden convexity"],"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"}