Stochastic Optimization under Hidden Convexity
METADATA ONLY
Loading...
Author / Producer
Date
2023-12-15
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
In this work, we consider constrained stochastic optimization problems under hidden convexity, i.e., those that admit a convex reformulation via non-linear (but invertible) map c : X → U. A number of non-convex problems ranging from optimal control, revenue and inventory management, to convex reinforcement learning all admit such a hidden convex structure. Unfortunately, in the majority of applications considered, the map c(⋅) is unavailable or implicit; therefore, directly solving the convex reformulation is not possible. On the other hand, the stochastic gradients with respect to the original variable x ϵ X are often easy to obtain. Motivated by these observations, we examine the basic projected stochastic (sub-) gradient methods for solving such problems under hidden convexity. We provide the first sample complexity guarantees for global convergence in smooth and non-smooth settings. Additionally, in the smooth setting, we improve our results to the last iterate convergence in terms of function value gap using the momentum variant of projected stochastic gradient descent.
Permanent link
Publication status
published
External links
Editor
Book title
OPT 2023: Optimization for Machine Learning (NeurIPS 2023 Workshop)
Journal / series
Volume
Pages / Article No.
Publisher
OpenReview
Event
15th International OPT Workshop on Optimization for Machine Learning (OPT 2023) held at NeurIPS 2023
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Optimization and Control (math.OC); Computational Complexity (cs.CC); FOS: Mathematics; FOS: Computer and information sciences; 90C06, 90C15, 90C26; hidden convexity; stochastic optimization; global convergence
Organisational unit
09729 - He, Niao / He, Niao
Notes
Poster presentation on December 15, 2023.
Funding
Related publications and datasets
Is new version of: 10.48550/arXiv.2401.00108