The complexity of gradient descent: CLS = PPAD∩PLS
We study search problems that can be solved by performing Gradient Descent on a bounded convex polytopal domain and show that this class is equal to the intersection of two well-known classes: PPAD and PLS. As our main underlying technical contribution, we show that computing a Karush-Kuhn-Tucker (K...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Sprog: | English |
| Udgivet: |
Association for Computing Machinery
2022
|