Non-Euclidean dual gradient ascent for entropically regularized linear and semidefinite programming
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915365864341504 |
|---|---|
| author | Cai, Yuhang Lindsey, Michael |
| author_facet | Cai, Yuhang Lindsey, Michael |
| contents | We present an optimization framework that exhibits dimension-independent convergence on a broad class of semidefinite programs (SDPs). Our approach first regularizes the primal problem with the von Neumann entropy, then solve the regularized problem using dual gradient ascent with respect to a problem-adapted norm. In particular, we show that the dual gradient norm converges to zero at a rate independent of the ambient dimension and, via rounding arguments, construct primal-feasible solutions in certain special cases. We also derive explicit convergence rates for the objective. In order to achieve optimal computational scaling, we must accommodate the use of stochastic gradients constructed via randomized trace estimators. Throughout we illustrate the generality of our framework via three important special cases -- the Goemans-Williamson SDP relaxation of the Max-Cut problem, the optimal transport linear program, and several SDP relaxations of the permutation synchronization problem. Numerical experiments confirm that our methods achieve dimension-independent convergence in practice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_09711 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Non-Euclidean dual gradient ascent for entropically regularized linear and semidefinite programming Cai, Yuhang Lindsey, Michael Optimization and Control Numerical Analysis We present an optimization framework that exhibits dimension-independent convergence on a broad class of semidefinite programs (SDPs). Our approach first regularizes the primal problem with the von Neumann entropy, then solve the regularized problem using dual gradient ascent with respect to a problem-adapted norm. In particular, we show that the dual gradient norm converges to zero at a rate independent of the ambient dimension and, via rounding arguments, construct primal-feasible solutions in certain special cases. We also derive explicit convergence rates for the objective. In order to achieve optimal computational scaling, we must accommodate the use of stochastic gradients constructed via randomized trace estimators. Throughout we illustrate the generality of our framework via three important special cases -- the Goemans-Williamson SDP relaxation of the Max-Cut problem, the optimal transport linear program, and several SDP relaxations of the permutation synchronization problem. Numerical experiments confirm that our methods achieve dimension-independent convergence in practice. |
| title | Non-Euclidean dual gradient ascent for entropically regularized linear and semidefinite programming |
| topic | Optimization and Control Numerical Analysis |
| url | https://arxiv.org/abs/2506.09711 |