Timeline for Direct (first-order ?) algorithm to minimize $u(x) := \|x-a\|_C + r\|x\|_p$
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 4, 2022 at 17:58 | comment | added | dohmatob | This problem is structured. All the implicit gradients (aka prox operators) can be computed in closed-form; etc. Subgradient algorithms are not worth the try even for $d=1$ (my problems will typiclaly have large $d$). As for the stepsizes, yes those "oracle" choices (as proposed in Chambolle and Pock 20XY) are enough to get ergodic convergence, but are likely to be suboptimal for this problem. Another issue with PD algorithms is the sense in which convergence is implied. Very indirect. | |
| Sep 4, 2022 at 17:38 | comment | added | cheyp | I know, but again if your dimension is 5 and you need to solve it with $\varepsilon=0.1$, it may be worth of a try. For primal-dual methods, you are right that you need two parameters. But if you know the norm of matrix $K$, then you can always take primal and dual steps equal, like $\alpha = \beta = \frac{1}{\|K\|}$. So it is also not that difficult. | |
| Sep 4, 2022 at 16:30 | comment | added | dohmatob | Well, subgradient-methods are possibly one of the worst things to do here. For example, they'll typically have a convergence rate of $O(1/\sqrt{t})$, where as a simple PD scheme can ensure $O(1/t)$ in an ergodic sense... | |
| Sep 4, 2022 at 9:51 | comment | added | cheyp | There is always the subgradient method for such problems. It satisfies all the properties you mentioned (the term "efficient" is not very informative without specifying the dimensions or the required accuracy). | |
| Sep 3, 2022 at 14:58 | history | asked | dohmatob | CC BY-SA 4.0 |