# Block stochastic gradient iteration for convex and nonconvex optimization

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Aug 2014.

## Built on by (most cited first, 22 of 22)

- [On the Versatile Uses of Partial Distance Correlation in Deep Learning](https://mlsanity.com/paper/2207.09684/) (2022)
- [Block Policy Mirror Descent](https://mlsanity.com/paper/2201.05756/) (2022)
- [Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization](https://mlsanity.com/paper/2212.05088/) (2022)
- [Federated Semi-Supervised Learning with Class Distribution Mismatch](https://mlsanity.com/paper/2111.00010/) (2021)
- [Fast and Structured Block-Term Tensor Decomposition For Hyperspectral Unmixing](https://mlsanity.com/paper/2205.03798/) (2022)
- [Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds](https://mlsanity.com/paper/2306.12498/) (2023)
- [Audio Embeddings as Teachers for Music Classification](https://mlsanity.com/paper/2306.17424/) (2023)
- [Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization](https://mlsanity.com/paper/2303.16279/) (2023)
- [Stochastic Block-ADMM for Training Deep Networks](https://mlsanity.com/paper/2105.00339/) (2021)
- [MULTIPAR: Supervised Irregular Tensor Factorization with Multi-task Learning](https://mlsanity.com/paper/2208.00993/) (2022)
- [Convergence of the Stochastic Heavy Ball Method With Approximate Gradients and/or Block Updating](https://mlsanity.com/paper/2303.16241/) (2023)
- [MISA: Memory-Efficient LLMs Optimization with Module-wise Importance Sampling](https://mlsanity.com/paper/2511.00056/) (2025)
- [Attentive Gaussian processes for probabilistic time-series generation](https://mlsanity.com/paper/2102.05208/) (2021)
- [Bayesian Federated Model Compression for Communication and Computation Efficiency](https://mlsanity.com/paper/2404.07532/) (2024)
- [Addressing Finite-Horizon MDPs via Low-Rank Tensor Value Approximation](https://mlsanity.com/paper/2501.10598/) (2025)
- [Online non-parametric change-point detection for heterogeneous data streams observed over graph nodes](https://mlsanity.com/paper/2110.10518/) (2021)
- [Convergence of Batch Updating Methods with Approximate Gradients and/or Noisy Measurements: Theory and Computational Results](https://mlsanity.com/paper/2209.05372/) (2022)
- [Online Learning Under A Separable Stochastic Approximation Framework](https://mlsanity.com/paper/2305.07484/) (2023)
- [ATE-SG: Alternate Through the Epochs Stochastic Gradient for Multi-Task Neural Networks](https://mlsanity.com/paper/2312.16340/) (2023)
- [Scalable Random Feature Latent Variable Models](https://mlsanity.com/paper/2410.17700/) (2024)
- [Neighbor-Sampling Based Momentum Stochastic Methods for Training Graph Neural Networks](https://mlsanity.com/paper/2508.00267/) (2025)
- [Demystifying Pipeline Parallelism: First Theory for PipeDream](https://mlsanity.com/paper/2606.03498/) (2026)

## Abstract (arXiv)

The stochastic gradient (SG) method can minimize an objective function composed of a large number of differentiable functions, or solve a stochastic optimization problem, to a moderate accuracy. The block coordinate descent/update (BCD) method, on the other hand, handles problems with multiple blocks of variables by updating them one at a time; when the blocks of variables are easier to update individually than together, BCD has a lower per-iteration cost. This paper introduces a method that combines the features of SG and BCD for problems with many components in the objective and with multiple (blocks of) variables. Specifically, a block stochastic gradient (BSG) method is proposed for solving both convex and nonconvex programs. At each iteration, BSG approximates the gradient of the differentiable part of the objective by randomly sampling a small set of data or sampling a few functions from the sum term in the objective, and then, using those samples, it updates all the blocks of variables in either a deterministic or a randomly shuffled order. Its convergence for both convex and nonconvex cases are established in different senses. In the convex case, the proposed method has the same order of convergence rate as the SG method. In the nonconvex case, its convergence is established in terms of the expected violation of a first-order optimality condition. The proposed method was numerically tested on problems including stochastic least squares and logistic regression, which are convex, as well as low-rank tensor recovery and bilinear logistic regression, which are nonconvex.