FastPart: Over-Parameterized Stochastic Gradient Descent for Sparse optimisation on Measures
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911137459601408 |
|---|---|
| author | De Castro, Yohann Gadat, Sébastien Marteau, Clément |
| author_facet | De Castro, Yohann Gadat, Sébastien Marteau, Clément |
| contents | 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: $\mathrm{(i)}$ The total variation norms of the solution measures along the descent trajectory remain bounded, ensuring stability and preventing undesirable divergence; $\mathrm{(ii)}$ We establish a global convergence guarantee with a convergence rate of ${O}(\log(K)/\sqrt{K})$ over $K$ iterations, showcasing the efficiency and effectiveness of our algorithm, $\mathrm{(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_05993 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | FastPart: Over-Parameterized Stochastic Gradient Descent for Sparse optimisation on Measures De Castro, Yohann Gadat, Sébastien Marteau, Clément Optimization and Control Machine Learning 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: $\mathrm{(i)}$ The total variation norms of the solution measures along the descent trajectory remain bounded, ensuring stability and preventing undesirable divergence; $\mathrm{(ii)}$ We establish a global convergence guarantee with a convergence rate of ${O}(\log(K)/\sqrt{K})$ over $K$ iterations, showcasing the efficiency and effectiveness of our algorithm, $\mathrm{(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. |
| title | FastPart: Over-Parameterized Stochastic Gradient Descent for Sparse optimisation on Measures |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2312.05993 |