# FastPart: Over-Parameterized Stochastic Gradient Descent for Sparse optimisation on Measures

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 35 references that are in the map.
- First posted on arXiv 10 Dec 2023.

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

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Sparse Optimization on Measures with Over-parameterized Gradient Descent](https://mlsanity.com/paper/1907.10300/) (2019)
- [On Representer Theorems and Convex Regularization](https://mlsanity.com/paper/1806.09810/) (2018)
- [Exact Support Recovery for Sparse Spikes Deconvolution](https://mlsanity.com/paper/1306.6909/) (2013)
- [Homeomorphic-Invariance of EM: Non-Asymptotic Convergence in KL Divergence for Exponential Families via Mirror Descent](https://mlsanity.com/paper/2011.01170/) (2020)
- [The Sliding Frank-Wolfe Algorithm and its Application to Super-Resolution Microscopy](https://mlsanity.com/paper/1811.06416/) (2018)
- [Gradient Descent on Infinitely Wide Neural Networks: Global Convergence and Generalization](https://mlsanity.com/paper/2110.08084/) (2021)
- [Sketching for Large-Scale Learning of Mixture Models](https://mlsanity.com/paper/1606.02838/) (2016)
- [Support detection in super-resolution](https://mlsanity.com/paper/1302.3921/) (2013)
- [Asymptotic linear convergence of fully-corrective generalized conditional gradient methods](https://mlsanity.com/paper/2110.06756/) (2021)

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

- [Fenchel-Young Duality Gaps: Certified Early Stopping for Regularized Inverse Problems](https://mlsanity.com/paper/2609.17629/) (2026)
- [Effective regions and kernels in continuous sparse regularisation, with application to sketched mixtures](https://mlsanity.com/paper/2507.08444/) (2025)
- [Riemannian Gradient Descent for Gaussian Mixture Models with unknown diagonal covariances](https://mlsanity.com/paper/2609.30220/) (2026)

## Abstract (arXiv)

This paper presents a novel algorithm that leverages Stochastic Gradient Descent strategies in conjunction with Random Features to augment the scalability of Conic Particle Gradient Descent (CPGD) specifically tailored for solving sparse optimization problems on measures. By formulating the CPGD steps within a variational framework, we provide rigorous mathematical proofs demonstrating the following key findings: (i) The total variation norms of the solution measures along the descent trajectory remain bounded, ensuring stability and preventing undesirable divergence; (ii) We establish a global convergence guarantee with a convergence rate of O(log(K)/√K) over K iterations, showcasing the efficiency and effectiveness of our algorithm, (iii) Additionally, we analyse and establish local control over the first-order condition discrepancy, contributing to a deeper understanding of the algorithm's behaviour and reliability in practical applications.