Timeline for How expensive is a proximal operation?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 5 at 21:57 | comment | added | Damaru | The prox operator is clearly not as cheap, I don't know in which community you have seen this but it is not like that. That being said, specifically for convex smooth functions you can implement an inexact accelerated proximal point method in a way that the total complexity of the method is like nesterov's accelerated GD, by using only 5 iterations of gradient descent on the prox subproblem arxiv.org/abs/1911.11271 And there are other more general reductions that do not incur more than a constant penalty for randomized algorithms arxiv.org/pdf/2206.08627.pdf | |
| Sep 17, 2023 at 5:03 | comment | added | T. W. | @J.Doe Thanks. That's an important case where the proximal operation is cheap. But there are other important cases where the proximal step can be very expensive. Let $g$ be a function that is 0 within a convex set $C$ and $\infty$ outside of it. We can pick a crazy convex set $C$ so that projection onto $C$ is very expensive. Based on what I learned from the literature (by reputable researchers in good venues), the convergence rate is in a lot of cases measured by how many proximal steps are needed, and the complexity of the proximal step is not discussed... That's weird... | |
| Sep 16, 2023 at 16:57 | comment | added | J. Doe | Adding to @Alf comment, if $f$ is $C^1$ with Lipschitz-continuous gradients (or more generally weakly-convex) then it is known that for $\eta$ small enough, the minimization problem in the prox operator will be convex. Thus, we can solve a sequence of convex operators (which can be easier than to solve a non-convex one), which might be interesting from a theoretical/practical point. Doesn't mean that the proximal step will be cheap though. | |
| Sep 16, 2023 at 16:50 | comment | added | J. Doe | The proximal operator is definitely not considered to be cheap. However, for some functions it can be solved in a close form. Typically in a ML scenario you regularize problem to solve a new optimization problem : $\min f +g$. If $\textrm{prox}_g$ is easily computed (e.g. $g = || \cdot||_1$), then you can solve it by applying a gradient step on $f$ and a proximal step on $g$. In this case, it is as cheap as just using gradient descent on $f$. | |
| Aug 31, 2023 at 2:34 | history | edited | T. W. | CC BY-SA 4.0 |
added 27 characters in body
|
| Aug 30, 2023 at 16:41 | history | edited | T. W. | CC BY-SA 4.0 |
deleted 6 characters in body
|
| Aug 30, 2023 at 16:34 | comment | added | T. W. | @Alf Please see my Edit 2 above. the cost of proximal operations is important. | |
| Aug 30, 2023 at 16:33 | history | edited | T. W. | CC BY-SA 4.0 |
added 474 characters in body
|
| Aug 30, 2023 at 15:55 | history | edited | T. W. | CC BY-SA 4.0 |
added 345 characters in body
|
| Aug 30, 2023 at 15:46 | comment | added | T. W. | @Alf. If you solve it to a fixed precision, then it's no longer a proximal step, it's a proximal step with error. If you solve it to a precision depending on $k$, then you'd get an extra $\log k$ term in the convergence rate. | |
| Aug 30, 2023 at 15:34 | comment | added | Alf | It is important to note that for $\eta$ small and $f$ convex and smooth, the objective in the inner minimization problem is smooth and strongly convex (with condition number nearly $1$ when $\eta$ is large enough), so a minimizer can be found very cheaply. Depending on the overall application, it can therefore make sense to think of this inner loop as basically free. | |
| Aug 30, 2023 at 15:18 | history | asked | T. W. | CC BY-SA 4.0 |