Timeline for Does gradient descent always converge to an optimum?
Current License: CC BY-SA 4.0
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 30, 2021 at 10:31 | comment | added | Tuyen | Maybe you can mention a specific result in Nemirovski or whatever book/paper you like, and we can check whether the assumptions are practical or cliche. Considering my paper: one part is published online in Applied Mathematics and Optimization, another part is accepted in Minimax Theory and its Applications. | |
| Mar 30, 2021 at 10:25 | comment | added | Dole | With regards to Nemirovski I am talking about the general convergence theorem. But yes, it only shows convergence to the set of critical points, and not to a particular point. Have you tried getting the paper published? | |
| Mar 30, 2021 at 10:05 | history | edited | Tuyen | CC BY-SA 4.0 |
added 529 characters in body
|
| Mar 30, 2021 at 9:57 | comment | added | Tuyen | Also, relevant to the second link (by Nemirovski?) it may be worthy to mention the difference between flow methods (which have good theoretical guarantee, but may be not practical - i.e. difficult to use for explicit optimization problems) and the discrete methods (which are practical, but may not have good theoretical guarantees.) For example, take the gradient flow: dx/dt= -\nabla f(x(t)). It has many good theoretical guarantee. However, it discretisation cannot be as simple as x_{n+1}=x_n-\nabla f(x_n), you need to add a learning rate \delta into. | |
| Mar 30, 2021 at 9:52 | comment | added | Tuyen | For the second link (by Nemirovski?), the assumption is C^{1,1}_L, which is the popular assumption in the literature. On the other hand, you then need to make sure that the learning rate is bounded by 1/L, and hence need to get a good estimate of L. Is estimate L practically possible and desirable, for example for Deep Neural Networks? Also, even for C^{1,1}_L, I don't think you get global convergence to 1 Single point, except you add more assumptions such as strongly convex (which is cliche in many research papers). | |
| Mar 30, 2021 at 9:43 | comment | added | Tuyen | Theorem 2 in the first link (by Bharath K. Sriperumbudur?) basically talks about what I mentioned before: every cluster point of the sequence is a critical point. This is, as I wrote, easier (or easy, depending on the assumptions you make). | |
| Mar 30, 2021 at 9:41 | comment | added | Tuyen | I see. However, the assumptions in the theorems you mentioned are very strong. Take for example, the statement of Theorem 1 in the first link you mentioned. For example, it is assumed that the sequence constructed is contained in a compact set. And also there is the 2 part of the assumption. Both are very technical. What general class of cost functions and optimization algorithms that these assumptions are satisfied? Are they practical? The results mentioned in my answer are under very general assumptions. | |
| Mar 30, 2021 at 9:15 | comment | added | Dole | I am talking about the global convergence theorem. It is given in Zangwill (1969) "Nonlinear programming: A unified approach", and improved in Meyer (1976) "Sufficient conditions for the convergence of monotonic mathematical programming algorithms". See theorem 1 and 2 of this paper direct.mit.edu/neco/article/24/6/1391/7776/…. The convergence of gradient descent is given here www2.isye.gatech.edu/~nemirovs/Lect_OptII.pdf (see the convergence chapter). | |
| Mar 30, 2021 at 8:33 | history | edited | Tuyen | CC BY-SA 4.0 |
added 442 characters in body
|
| Mar 30, 2021 at 6:04 | comment | added | Tuyen | By the way, which paper/book of Zangwill (1969) you are talking about? Which precise theorem/lemma/proposition etc which confirms your claim? | |
| Mar 30, 2021 at 6:03 | comment | added | Tuyen | I think you are confused between convergence to a Single Limit point (which is what I am talking here) and that any Cluster Point of the sequence is a stationary point/critical point (as usually in the literature). Even page 5 of the slides you linked to mentioned this issue, and writes that it is very difficult for the first point, while the second point is easy. | |
| Mar 28, 2021 at 23:46 | comment | added | Dole | Are you aware that back tracking gradient descent has been proven to converge without the countability condition due to Zangwill (1969). Further, the convergence can be proved by mean value theorem as given by web.mit.edu/6.252/www/LectureNotes/6_252%20Lecture04.pdf. | |
| S Aug 5, 2020 at 7:30 | history | suggested | Zephyr | CC BY-SA 4.0 |
Corrected links quote
|
| Aug 5, 2020 at 7:00 | review | Suggested edits | |||
| S Aug 5, 2020 at 7:30 | |||||
| Apr 8, 2019 at 3:45 | history | edited | Tuyen | CC BY-SA 4.0 |
added 278 characters in body
|
| Apr 5, 2019 at 19:25 | history | edited | Tuyen | CC BY-SA 4.0 |
added 600 characters in body
|
| Nov 6, 2018 at 2:24 | history | edited | Tuyen | CC BY-SA 4.0 |
added 360 characters in body
|
| Nov 6, 2018 at 2:18 | history | edited | Tuyen | CC BY-SA 4.0 |
added 360 characters in body
|
| Nov 6, 2018 at 2:08 | history | edited | Tuyen | CC BY-SA 4.0 |
added 144 characters in body
|
| Nov 3, 2018 at 19:35 | history | edited | Tuyen | CC BY-SA 4.0 |
added 530 characters in body
|
| Nov 3, 2018 at 1:02 | history | edited | Stephen Rauch♦ | CC BY-SA 4.0 |
Minor formatting
|
| Nov 3, 2018 at 1:00 | review | Late answers | |||
| Nov 3, 2018 at 1:02 | |||||
| Nov 3, 2018 at 0:45 | review | First posts | |||
| Nov 3, 2018 at 1:02 | |||||
| Nov 3, 2018 at 0:41 | history | answered | Tuyen | CC BY-SA 4.0 |