Provable Constrained Stochastic Convex Optimization with XOR-Projected
  Gradient Descent
  Provably solving stochastic convex optimization problems with constraints is
essential for various problems in science, business, and statistics. Recently
proposed XOR-Stochastic Gradient Descent (XOR-SGD) provides a convergence rate
guarantee solving the constraints-free version of the problem by leveraging
XOR-Sampling. However, the task becomes more difficult when additional equality
and inequality constraints are needed to be satisfied. Here we propose XOR-PGD,
a novel algorithm based on Projected Gradient Descent (PGD) coupled with the
XOR sampler, which is guaranteed to solve the constrained stochastic convex
optimization problem still in linear convergence rate by choosing proper step
size. We show on both synthetic stochastic inventory management and real-world
road network design problems that the rate of constraints satisfaction of the
solutions optimized by XOR-PGD is $10\%$ more than the competing approaches in
a very large searching space. The improved XOR-PGD algorithm is demonstrated to
be more accurate and efficient than both XOR-SGD and SGD coupled with MCMC
based samplers. It is also shown to be more scalable with respect to the number
of samples and processor cores via experiments with large dimensions.
