# Semi-Stochastic Coordinate Descent

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Dec 2014.

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

- [Communication-Efficient Hierarchical Federated Learning for IoT Heterogeneous Systems with Imbalanced Data](https://mlsanity.com/paper/2107.06548/) (2021)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [To Talk or to Work: Delay Efficient Federated Learning over Mobile Edge Devices](https://mlsanity.com/paper/2111.00637/) (2021)
- [Hierarchical Federated Learning for Social Network with Mobility](https://mlsanity.com/paper/2509.14938/) (2025)
- [A stochastic gradient descent algorithm with random search directions](https://mlsanity.com/paper/2503.19942/) (2025)

## Abstract (arXiv)

We propose a novel stochastic gradient method---semi-stochastic coordinate descent (S2CD)---for the problem of minimizing a strongly convex function represented as the average of a large number of smooth convex functions: f(x)=tfrac1nsumi fi(x). Our method first performs a deterministic step (computation of the gradient of f at the starting point), followed by a large number of stochastic steps. The process is repeated a few times, with the last stochastic iterate becoming the new starting point where the deterministic step is taken. The novelty of our method is in how the stochastic steps are performed. In each such step, we pick a random function fi and a random coordinate j---both using nonuniform distributions---and update a single coordinate of the decision vector only, based on the computation of the jth partial derivative of fi at two different points. Each random step of the method constitutes an unbiased estimate of the gradient of f and moreover, the squared norm of the steps goes to zero in expectation, meaning that the stochastic estimate of the gradient progressively improves. The complexity of the method is the sum of two terms: O(nlog(1/ε)) evaluations of gradients nabla fi and O(hatkappalog(1/ε)) evaluations of partial derivatives nablaj fi, where hatkappa is a novel condition number.