# COCO Denoiser: Using Co-Coercivity for Variance Reduction in Stochastic Convex Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 25 references that are in the map.
- First posted on arXiv 7 Sep 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression](https://mlsanity.com/paper/1602.05419/) (2016)
- [Competing with the Empirical Risk Minimizer in a Single Pass](https://mlsanity.com/paper/1412.6606/) (2014)
- [Accelerating Stochastic Gradient Descent For Least Squares Regression](https://mlsanity.com/paper/1704.08227/) (2017)

## Abstract (arXiv)

First-order methods for stochastic optimization have undeniable relevance, in part due to their pivotal role in machine learning. Variance reduction for these algorithms has become an important research topic. In contrast to common approaches, which rarely leverage global models of the objective function, we exploit convexity and L-smoothness to improve the noisy estimates outputted by the stochastic gradient oracle. Our method, named COCO denoiser, is the joint maximum likelihood estimator of multiple function gradients from their noisy observations, subject to co-coercivity constraints between them. The resulting estimate is the solution of a convex Quadratically Constrained Quadratic Problem. Although this problem is expensive to solve by interior point methods, we exploit its structure to apply an accelerated first-order algorithm, the Fast Dual Proximal Gradient method. Besides analytically characterizing the proposed estimator, we show empirically that increasing the number and proximity of the queried points leads to better gradient estimates. We also apply COCO in stochastic settings by plugging it in existing algorithms, such as SGD, Adam or STRSAGA, outperforming their vanilla versions, even in scenarios where our modelling assumptions are mismatched.