Data-Driven Compositional Optimization in Misspecified Regimes

As systems grow in size, scale, and intricacy, the challenges of misspecification become even more pronounced. In this paper, we focus on parametric misspecification in regimes complicated by risk and nonconvexity. When this misspecification may be resolved via a parallel learning process, we develop data-driven schemes for resolving a broad class of misspecified stochastic compositional optimization problems. Notably, this rather broad class of compositional problems can contend with challenges posed by diverse forms of risk, dynamics, and nonconvexity, significantly extending the reach of such avenues. Specifically, we consider the minimization of a stochastic compositional function over a closed and convex set $\mathcal{X}$ in a regime, where certain parameters are unknown or misspecified. Existing algorithms can accommodate settings where the parameters are correctly specified, but efficient first-order schemes are hitherto unavailable for the imperfect information compositional counterparts. Via a data-driven compositional optimization approach, we develop asymptotic and rate guarantees for unaccelerated and accelerated schemes for convex, strongly convex, and nonconvex problems in a two-level regime. Additionally, we extend the accelerated schemes to the general T-level setting. Notably, the nonasymptotic rate guarantees in all instances show no degradation from the rate statements obtained in a correctly specified regime. Further, under mild assumptions, our schemes achieve optimal (or near-optimal) sample complexities for general T-level strongly convex and nonconvex compositional problems, providing a marked improvement over prior work. Our numerical experiments support the theoretical findings based on the resolution of a misspecified three-level compositional risk-averse optimization problem.

Funding: E. X. Fang is partially supported by the National Science Foundation [Grants DMS-2230795 and DMS-2230797]. U. V. Shanbhag is partially supported by the Office of Naval Research [Grant N00014-22-1-2589] and the Department of Energy [Grant DE-SC0023303].

Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2021.0295.