Swarm-based gradient descent meets simulated annealing
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929483093639168 |
|---|---|
| author | Ding, Zhiyan Guerra, Martin Li, Qin Tadmor, Eitan |
| author_facet | Ding, Zhiyan Guerra, Martin Li, Qin Tadmor, Eitan |
| contents | We introduce a novel method for non-convex optimization, called Swarm-based Simulated Annealing (SSA), which is at the interface between the swarm-based gradient-descent (SBGD) [J. Lu et. al., ArXiv:2211.17157; E.Tadmor and A. Zenginoglu, Acta Applicandae Math., 190, 2024] and Simulated Annealing (SA) [V. Cerny, J. optimization theory and appl., 45:41-51, 1985; S.Kirkpatrick et. al., Science, 220(4598):671-680, 1983; S. Geman and C.-R. Hwang, SIAM J. Control and Optimization, 24(5):1031-1043, 1986]. Similar to SBGD, we introduce a swarm of agents, each identified with a position, ${\mathbf x}$ and mass $m$, to explore the ambient space. Similar to SA, the agents proceed in the gradient descent direction, and are subject to Brownian motion. The annealing rate, however, is dictated by a decreasing function of their mass. As a consequence, instead of the SA protocol for time-decreasing temperature, we let the swarm decide how to `cool down' agents, depending on their accumulated mass over time. The dynamics of masses is coupled with the dynamics of positions: agents at higher ground transfer (part of) their mass to those at lower ground. Consequently, resulting SSA optimizer is dynamically divided between heavier, cooler agents viewed as `leaders' and lighter, warmer agents viewed as `explorers'. Mean-field convergence analysis and benchmark optimizations demonstrate the effectiveness of the swarm-based method as a multi-dimensional global optimizer. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_18015 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Swarm-based gradient descent meets simulated annealing Ding, Zhiyan Guerra, Martin Li, Qin Tadmor, Eitan Optimization and Control Numerical Analysis 90C26, 65K10, 92D25 We introduce a novel method for non-convex optimization, called Swarm-based Simulated Annealing (SSA), which is at the interface between the swarm-based gradient-descent (SBGD) [J. Lu et. al., ArXiv:2211.17157; E.Tadmor and A. Zenginoglu, Acta Applicandae Math., 190, 2024] and Simulated Annealing (SA) [V. Cerny, J. optimization theory and appl., 45:41-51, 1985; S.Kirkpatrick et. al., Science, 220(4598):671-680, 1983; S. Geman and C.-R. Hwang, SIAM J. Control and Optimization, 24(5):1031-1043, 1986]. Similar to SBGD, we introduce a swarm of agents, each identified with a position, ${\mathbf x}$ and mass $m$, to explore the ambient space. Similar to SA, the agents proceed in the gradient descent direction, and are subject to Brownian motion. The annealing rate, however, is dictated by a decreasing function of their mass. As a consequence, instead of the SA protocol for time-decreasing temperature, we let the swarm decide how to `cool down' agents, depending on their accumulated mass over time. The dynamics of masses is coupled with the dynamics of positions: agents at higher ground transfer (part of) their mass to those at lower ground. Consequently, resulting SSA optimizer is dynamically divided between heavier, cooler agents viewed as `leaders' and lighter, warmer agents viewed as `explorers'. Mean-field convergence analysis and benchmark optimizations demonstrate the effectiveness of the swarm-based method as a multi-dimensional global optimizer. |
| title | Swarm-based gradient descent meets simulated annealing |
| topic | Optimization and Control Numerical Analysis 90C26, 65K10, 92D25 |
| url | https://arxiv.org/abs/2404.18015 |