Symplectic Discretization Approach for Developing New Proximal Point Algorithm
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913570905653248 |
|---|---|
| author | Yuan, Ya-xiang Zhang, Yi |
| author_facet | Yuan, Ya-xiang Zhang, Yi |
| contents | The rapid advancements in high-dimensional statistics and machine learning have increased the use of first-order methods. Many of these methods can be regarded as instances of the proximal point algorithm. Given the importance of the proximal point algorithm, there has been growing interest in developing its accelerated variants. However, some existing accelerated proximal point algorithms exhibit oscillatory behavior, which can impede their numerical convergence rate. In this paper, we first introduce an ODE system and demonstrate its \( o(1/t^2) \) convergence rate and weak convergence property. Next, we apply the Symplectic Euler Method to discretize the ODE and obtain a new accelerated proximal point algorithm, which we call the Symplectic Proximal Point Algorithm. The reason for using the Symplectic Euler Method is its ability to preserve the geometric structure of the ODEs. Theoretically, we demonstrate that the Symplectic Proximal Point Algorithm achieves an \( o(1/k^2) \) convergence rate and that the sequences generated by our method converge weakly to the solution set. Practically, our numerical experiments illustrate that the Symplectic Proximal Point Algorithm significantly reduces oscillatory behavior, leading to improved long-time behavior and faster numerical convergence rate. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_03986 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Symplectic Discretization Approach for Developing New Proximal Point Algorithm Yuan, Ya-xiang Zhang, Yi Optimization and Control 47J20, 47H05, 65K15, 65Y20, 90C25, 90C52 The rapid advancements in high-dimensional statistics and machine learning have increased the use of first-order methods. Many of these methods can be regarded as instances of the proximal point algorithm. Given the importance of the proximal point algorithm, there has been growing interest in developing its accelerated variants. However, some existing accelerated proximal point algorithms exhibit oscillatory behavior, which can impede their numerical convergence rate. In this paper, we first introduce an ODE system and demonstrate its \( o(1/t^2) \) convergence rate and weak convergence property. Next, we apply the Symplectic Euler Method to discretize the ODE and obtain a new accelerated proximal point algorithm, which we call the Symplectic Proximal Point Algorithm. The reason for using the Symplectic Euler Method is its ability to preserve the geometric structure of the ODEs. Theoretically, we demonstrate that the Symplectic Proximal Point Algorithm achieves an \( o(1/k^2) \) convergence rate and that the sequences generated by our method converge weakly to the solution set. Practically, our numerical experiments illustrate that the Symplectic Proximal Point Algorithm significantly reduces oscillatory behavior, leading to improved long-time behavior and faster numerical convergence rate. |
| title | Symplectic Discretization Approach for Developing New Proximal Point Algorithm |
| topic | Optimization and Control 47J20, 47H05, 65K15, 65Y20, 90C25, 90C52 |
| url | https://arxiv.org/abs/2308.03986 |