A Structured Proximal Stochastic Variance Reduced Zeroth-order Algorithm
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915365465882624 |
|---|---|
| author | Rando, Marco Traoré, Cheik Molinari, Cesare Rosasco, Lorenzo Villa, Silvia |
| author_facet | Rando, Marco Traoré, Cheik Molinari, Cesare Rosasco, Lorenzo Villa, Silvia |
| contents | Minimizing finite sums of functions is a central problem in optimization, arising in numerous practical applications. Such problems are commonly addressed using first-order optimization methods. However, these procedures cannot be used in settings where gradient information is unavailable. Finite-difference methods provide an alternative by approximating gradients through function evaluations along a set of directions. For finite-sum minimization problems, it was shown that incorporating variance-reduction techniques into finite-difference methods can improve convergence rates. Additionally, recent studies showed that imposing structure on the directions (e.g., orthogonality) enhances performance. However, the impact of structured directions on variance-reduced finite-difference methods remains unexplored. In this work, we close this gap by proposing a structured variance-reduced finite-difference algorithm for non-smooth finite-sum minimization. We analyze the proposed method, establishing convergence rates for non-convex functions and those satisfying the Polyak-Łojasiewicz condition. Our results show that our algorithm achieves state-of-the-art convergence rates while incurring lower per-iteration costs. Finally, numerical experiments highlight the strong practical performance of our method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_23758 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Structured Proximal Stochastic Variance Reduced Zeroth-order Algorithm Rando, Marco Traoré, Cheik Molinari, Cesare Rosasco, Lorenzo Villa, Silvia Optimization and Control 90C56 (Primary) 90C15, 90C25, 90C30 (Secondary) G.1.6 Minimizing finite sums of functions is a central problem in optimization, arising in numerous practical applications. Such problems are commonly addressed using first-order optimization methods. However, these procedures cannot be used in settings where gradient information is unavailable. Finite-difference methods provide an alternative by approximating gradients through function evaluations along a set of directions. For finite-sum minimization problems, it was shown that incorporating variance-reduction techniques into finite-difference methods can improve convergence rates. Additionally, recent studies showed that imposing structure on the directions (e.g., orthogonality) enhances performance. However, the impact of structured directions on variance-reduced finite-difference methods remains unexplored. In this work, we close this gap by proposing a structured variance-reduced finite-difference algorithm for non-smooth finite-sum minimization. We analyze the proposed method, establishing convergence rates for non-convex functions and those satisfying the Polyak-Łojasiewicz condition. Our results show that our algorithm achieves state-of-the-art convergence rates while incurring lower per-iteration costs. Finally, numerical experiments highlight the strong practical performance of our method. |
| title | A Structured Proximal Stochastic Variance Reduced Zeroth-order Algorithm |
| topic | Optimization and Control 90C56 (Primary) 90C15, 90C25, 90C30 (Secondary) G.1.6 |
| url | https://arxiv.org/abs/2506.23758 |