Journal article
A Data Efficient and Feasible Level Set Method for Stochastic Convex Optimization with Expectation Constraints
Journal of machine learning research, Vol.21(1), pp.5664-5708
01/01/2020
Abstract
Stochastic convex optimization problems with expectation constraints (SOECs) are encountered in statistics and machine learning, business, and engineering. The SOEC objective and constraints contain expectations defined with respect to complex distributions or large data sets, leading to high computational complexity when solved by the algorithms that use exact functions and their gradients. Recent stochastic first order methods exhibit low computational complexity when handling SOECs but guarantee near-feasibility and near-optimality only at convergence. These methods may thus return highly infeasible solutions when heuristically terminated, as is often the case, due to theoretical convergence criteria being highly conservative. This issue limits the use of first order methods in several applications where the SOEC constraints encode implementation requirements. We design a stochastic feasible level set method (SFLS) for SOECs that has low complexity and emphasizes feasibility before convergence. Specifically, our level-set method solves a root-finding problem by calling a novel first order oracle that computes a stochastic upper bound on the level-set function by extending mirror descent and online validation techniques. We establish that SFLS maintains a high-probability feasible solution at each root-finding iteration and exhibits favorable complexity compared to state-of-the-art deterministic feasible level set and stochastic subgradient methods. Numerical experiments on three diverse applications highlight how SFLS finds feasible solutions with small optimality gaps with lower complexity than the former approaches.
Details
- Title: Subtitle
- A Data Efficient and Feasible Level Set Method for Stochastic Convex Optimization with Expectation Constraints
- Creators
- Qihang Lin - Univ Iowa, Tippie Coll Business, Iowa City, IA 52242 USASelvaprabu Nadarajah - Univ Illinois, Coll Business Adm, Chicago, IL 60607 USANegar Soheili - Univ Illinois, Coll Business Adm, Chicago, IL 60607 USATianbao Yang - Univ Iowa, Dept Comp Sci, Iowa City, IA 52242 USA
- Resource Type
- Journal article
- Publication Details
- Journal of machine learning research, Vol.21(1), pp.5664-5708
- Publisher
- Microtome Publ
- ISSN
- 1532-4435
- eISSN
- 1533-7928
- Number of pages
- 45
- Language
- English
- Date published
- 01/01/2020
- Academic Unit
- Business Analytics; Computer Science
- Record Identifier
- 9984259422502771
Metrics
9 Record Views