# Oblivious Stochastic Composite Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 26 references that are in the map.
- First posted on arXiv 30 Jun 2023.

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

- [Learning-Rate-Free Learning by D-Adaptation](https://mlsanity.com/paper/2301.07733/) (2023)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Online Adaptive Methods, Universality and Acceleration](https://mlsanity.com/paper/1809.02864/) (2018)
- [Parameter-free Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [Scalable Semidefinite Programming](https://mlsanity.com/paper/1912.02949/) (2019)
- [Fast Stochastic Bregman Gradient Methods: Sharp Analysis and Variance Reduction](https://mlsanity.com/paper/2104.09813/) (2021)
- [Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities](https://mlsanity.com/paper/2007.08840/) (2020)
- [Complementary Composite Minimization, Small Gradients in General Norms, and Applications](https://mlsanity.com/paper/2101.11041/) (2021)
- [Anytime Online-to-Batch Conversions, Optimism, and Acceleration](https://mlsanity.com/paper/1903.00974/) (2019)
- [Optimal Algorithms for Stochastic Complementary Composite Minimization](https://mlsanity.com/paper/2211.01758/) (2022)

## Abstract (arXiv)

In stochastic convex optimization problems, most existing adaptive methods rely on prior knowledge about the diameter bound D when the smoothness or the Lipschitz constant is unknown. This often significantly affects performance as only a rough approximation of D is usually known in practice. Here, we bypass this limitation by combining mirror descent with dual averaging techniques and we show that, under oblivious step-sizes regime, our algorithms converge without any prior knowledge on the parameters of the problem. We introduce three oblivious stochastic algorithms to address different settings. The first algorithm is designed for objectives in relative scale, the second one is an accelerated version tailored for smooth objectives, whereas the last one is for relatively-smooth objectives. All three algorithms work without prior knowledge of the diameter of the feasible set, the Lipschitz constant or smoothness of the objective function. We use these results to revisit the problem of solving large-scale semidefinite programs using randomized first-order methods and stochastic smoothing. We extend our framework to relative scale and demonstrate the efficiency and robustness of our methods on large-scale semidefinite programs.