Conservative Stochastic Optimization With Expectation Constraints

By Zeeshan Akhtar, Amrit Singh Bedi, Ketan Rajawat. 2020

25 citations recorded by the source corpus.

This paper considers stochastic convex optimization problems where the objective and constraint functions involve expectations with respect to the data indices or environmental variables, in addition to deterministic convex constraints on the domain of the variables. Since the underlying data distribution is unknown a priori, a closed-form solution is generally not available, and classical deterministic optimization paradigms are not applicable. State-of-the-art approaches, such as those using the saddle point framework, are able to ensure that the optimality gap as well as the constraint violation decay as <inline-formula><tex-math notation="LaTeX">$\mathcal{O}(T^{-\frac{1}{2}})$</tex-math></inline-formula> where <inline-formula><tex-math notation="LaTeX">$T$</tex-math></inline-formula> is the number of stochastic gradients. In this work, we propose a novel conservative stochastic optimization algorithm (CSOA) that achieves zero average constraint violation and <inline-formula><tex-math notation="LaTeX">$\mathcal{O}(T^{-\frac{1}{2}})$</tex-math></inline-formula> optimality gap.</p> <p>Further, we also consider the scenario where carrying out a projection step onto the convex domain constraints at every iteration is not viable. Traditionally, the projection operation can be avoided by considering the conditional gradient or Frank-Wolfe (FW) variant of the algorithm. The state-of-the-art stochastic FW variants achieve an optimality gap of <inline-formula><tex-math notation="LaTeX">$\mathcal{O}(T^{-\frac{1}{3}})$</tex-math></inline-formula> after <inline-formula><tex-math notation="LaTeX">$T$</tex-math></inline-formula> iterations, though these algorithms have not been applied to problems with functional expectation constraints. In this work, we propose the FW-CSOA algorithm that is not only projection-free but also achieves zero average constraint violation with <inline-formula><tex-math notation="LaTeX">$\mathcal{O}(T^{-\frac{1}{4}})$</tex-math></inline-formula> decay of the optimality gap. The efficacy of the proposed algorithms is tested on two relevant problems: fair classification and structured matrix completion.

Subfields: Artificial Intelligence, Computational Mechanics, 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. René Vidal
  2. Paris V. Giampouras
  3. Liangzu Peng

In Computational Mechanics

  1. René Vidal
  2. Paris V. Giampouras
  3. Liangzu Peng
  4. Ehsan Elhamifar
  5. Zhouchen Lin
  6. Paolo Favaro
  7. Shuicheng Yan
  8. Guangcan Liu

In Management Science and Operations Research

  1. René Vidal
  2. Paris V. Giampouras
  3. Liangzu Peng

Citations in the corpus