Stochastic Compositional Gradient Descent under Compositional
  constraints
  This work studies constrained stochastic optimization problems where the
objective and constraint functions are convex and expressed as compositions of
stochastic functions. The problem arises in the context of fair classification,
fair regression, and the design of queuing systems. Of particular interest is
the large-scale setting where an oracle provides the stochastic gradients of
the constituent functions, and the goal is to solve the problem with a minimal
number of calls to the oracle. Owing to the compositional form, the stochastic
gradients provided by the oracle do not yield unbiased estimates of the
objective or constraint gradients. Instead, we construct approximate gradients
by tracking the inner function evaluations, resulting in a quasi-gradient
saddle point algorithm. We prove that the proposed algorithm is guaranteed to
find the optimal and feasible solution almost surely. We further establish that
the proposed algorithm requires $\mathcal{O}(1/\epsilon^4)$ data samples in
order to obtain an $\epsilon$-approximate optimal point while also ensuring
zero constraint violation. The result matches the sample complexity of the
stochastic compositional gradient descent method for unconstrained problems and
improves upon the best-known sample complexity results for the constrained
settings. The efficacy of the proposed algorithm is tested on both fair
classification and fair regression problems. The numerical results show that
the proposed algorithm outperforms the state-of-the-art algorithms in terms of
the convergence rate.
