Algorithms for stochastic optimization with expectation constraints

By Guanghui Lan, Zhiqiang Zhou. 2016

52 citations recorded by the source corpus.

This paper considers the problem of minimizing an expectation function over a closed convex set, coupled with an expectation constraint on either decision variables or problem parameters. We first present a new stochastic approximation (SA) type algorithm, namely the cooperative SA (CSA), to handle problems with the expectation constraint on devision variables. We show that this algorithm exhibits the optimal ${\cal O}(1/\sqrt{N})$ rate of convergence, in terms of both optimality gap and constraint violation, when the objective and constraint functions are generally convex, where $N$ denotes the number of iterations. Moreover, we show that this rate of convergence can be improved to ${\cal O}(1/N)$ if the objective and constraint functions are strongly convex. We then present a variant of CSA, namely the cooperative stochastic parameter approximation (CSPA) algorithm, to deal with the situation when the expectation constraint is defined over problem parameters and show that it exhibits similar optimal rate of convergence to CSA. It is worth noting that CSA and CSPA are primal methods which do not require the iterations on the dual space and/or the estimation on the size of the dual variables. To the best of our knowledge, this is the first time that such optimal SA methods for solving expectation constrained stochastic optimization are presented in the literature.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Amrit Singh Bedi
2. Ketan Rajawat
3. Zeeshan Akhtar
4. Michael J. Neely
5. Xiaohan Wei
6. Hao Yu
7. Paris V. Giampouras
8. Liangzu Peng

In Management Science and Operations Research

1. Zeeshan Akhtar
2. Ketan Rajawat
3. Amrit Singh Bedi
4. Michael J. Neely
5. Xiaohan Wei
6. Hao Yu
7. René Vidal
8. Paris V. Giampouras

Citations in the corpus

• Online Convex Optimization with Stochastic Constraints (2017, methodology): “The work [17] proposes a stochastic approximation based (batch) offline algorithm for stochastic convex optimization [ √ T ) regret and O (1) constraint violations.”
• Conservative Stochastic Optimization With Expectation Constraints (2020, methodology): “The cooperative stochastic approximation (CSA) algorithm proposed in [26] considered the special case of a single expectation constraint, while its extended version proposed in [27] studied the case of multiple expectation constraints.”