Timeline for How does the number of function calls in BFGS scale with the dimensionality of space?
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Jan 11, 2022 at 16:33 | history | suggested | Tyberius | CC BY-SA 4.0 |
replaced [scaling] with [complexity
|
| Jan 11, 2022 at 15:51 | review | Suggested edits | |||
| S Jan 11, 2022 at 16:33 | |||||
| Apr 18, 2021 at 20:08 | vote | accept | Kvothe | ||
| Apr 16, 2021 at 6:01 | history | tweeted | twitter.com/StackSciComp/status/1382937231300685825 | ||
| Apr 15, 2021 at 9:04 | comment | added | Kvothe | @Beni, agreed there are definitely functions for which the scaling is constant. I am more interested in whether the behaviour of "linear scaling at worst" is somewhat generic. So counter examples for that would be really appreciated. Then I can check how convoluted that example is. An obvious example of terrible scaling is when you actively make the extra dimensions more and more terrible functions for BFGS. For example x^2 is clearly going to be solved easily. If you add something much more complicated in the new dimension the behaviour is going to be much worse. | |
| Apr 15, 2021 at 8:57 | comment | added | Beni Bogosel | @Kvothe: Maybe I should formulate my ideas in an answer. What I want to say is that you cannot really give a general answer if you don't specify how your function behaves with respect to the dimension. You can build examples for which even the Gradient Descent takes roughly the same number of iterations to converge regardless of the dimension, just because the conditioning of the function does not deteriorate with the dimension. | |
| Apr 15, 2021 at 8:05 | history | edited | Kvothe | CC BY-SA 4.0 |
added 255 characters in body
|
| Apr 15, 2021 at 8:02 | comment | added | Kvothe | @Beni, Also what do you mean about the Rosenbrock's function becoming more ill-conditioned. Does that not give additional evidence in favor of the scaling behaviour being generic. The Rosenbrock function shows linear scaling for a large range of dimensions. You also say it is both well-conditioned (for a low dimensionality) and ill-conditioned (for a large dimensionality). Both show linear scaling so it seems that the ill-conditioning itself is not that much of a problem then. Do you agree? | |
| Apr 15, 2021 at 8:00 | comment | added | Kvothe | @Beni, if you have a counter example to this scaling that would be much appreciated as well. I understand that the conditioning number has to do with how much the function changes under a small change. I don't know whether there is an easy or useful answer for this. BFGS should be scale invariant after a sufficient number of steps so what does small even mean exactly, I guess with respect to the space I actually want the BFGS to explore. Anyway I am happy to add more data on the type of functions I have in mind if requested. I saw I did not add any information on continuity so I will add that. | |
| Apr 15, 2021 at 7:56 | comment | added | Kvothe | @Beni, I disagree a bit. The question is explicitly about whether there is some kind of generic estimate and I think that kind of question is extremely important to have on this stackexchange. For my problem I don't have a specific function in mind but a class of (very complicated and expensive so I cannot give an example) functions. If the answer really is that no prediction of any use can be made than that is a very useful answer as well. Based on the answer by Infinity77 I do not think this is the case. It seems that generically the scaling is not terrible. cont'd ... | |
| Apr 14, 2021 at 21:06 | comment | added | Beni Bogosel | I would say that your question is too general and a complete answer cannot be given without further information regarding your objective function. The examples given in the answer of @Infinity77 are really nice, but keep in mind that Rosenbrock's function becomes more ill conditioned as the dimension increases. As the previous comment says, the conditioning of the problem is critical. Theoretically, if the condition number of the Hessian does not deteriorate when the dimension increases, the number of iterations should not increase too much. Taking a look at the quadratic case might help. | |
| Apr 13, 2021 at 12:48 | history | edited | Kvothe | CC BY-SA 4.0 |
added 94 characters in body
|
| Apr 13, 2021 at 10:34 | answer | added | Infinity77 | timeline score: 11 | |
| Apr 12, 2021 at 17:56 | comment | added | Brian Borchers | The conditioning of the problem is a critical factor that needs to be taken into account. | |
| Apr 12, 2021 at 15:41 | review | First posts | |||
| Apr 12, 2021 at 16:47 | |||||
| Apr 12, 2021 at 15:38 | history | asked | Kvothe | CC BY-SA 4.0 |