# Provable Constrained Stochastic Convex Optimization with XOR-Projected Gradient Descent

arXiv: https://arxiv.org/abs/2203.11829 · HTML: https://mlsanity.com/paper/2203.11829/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 45 references that are in the map.
- First posted on arXiv 22 Mar 2022.

## Builds on (most cited first, 16 of 16)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [An overview of gradient descent optimization algorithms](https://mlsanity.com/paper/1609.04747/) (2016)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Loopy Belief Propagation for Approximate Inference: An Empirical Study](https://mlsanity.com/paper/1301.6725/) (2013)
- [Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent](https://mlsanity.com/paper/1711.10456/) (2017)
- [Natasha 2: Faster Non-Convex Optimization Than SGD](https://mlsanity.com/paper/1708.08694/) (2017)
- [Improved Algorithms for Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2006.06359/) (2020)
- [Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity](https://mlsanity.com/paper/1802.01504/) (2018)
- [Taming the Curse of Dimensionality: Discrete Integration by Hashing and Optimization](https://mlsanity.com/paper/1302.6677/) (2013)
- [Learning Graphical Model Parameters with Approximate Marginal Inference](https://mlsanity.com/paper/1301.3193/) (2013)
- [Stochastic Variance-Reduced ADMM](https://mlsanity.com/paper/1604.07070/) (2016)
- [Solving Marginal MAP Problems with NP Oracles and Parity Constraints](https://mlsanity.com/paper/1610.02591/) (2016)
- [Accelerated Variance Reduced Stochastic ADMM](https://mlsanity.com/paper/1707.03190/) (2017)
- [Variational Algorithms for Marginal MAP](https://mlsanity.com/paper/1302.6584/) (2013)
- [XOR-Sampling for Network Design with Correlated Stochastic Events](https://mlsanity.com/paper/1705.08218/) (2017)

## Abstract (arXiv)

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.