0
$\begingroup$

In optimization, a proximal step is usually considered as cheap as a gradient step. I'm quite confused by this. Why are people taking this convention at all?

A typical proximal step indeed incurs a subroutine. For example, consider the Moreau–Yosida proximal step $$ x_{k+1} = \arg\min_y \{ f (y) + \frac{1}{2\eta} \| x_k - y \|_2^2 \} , $$ where $\eta$ is the step size.

I think we have to use some solver to arrive at $x_{k+1}$, isn't it? If we have to call a subroutine to solve for a single proximal step, why are we taking the convention that a proximal step is as cheap as a gradient step?

Edit 1 after @Alf's comment: If we solve the subproblem to a fixed precision, then it's no longer a proximal step, it's a proximal step with error. If we solve the subproblem to a precision depending on $k$, then we'd get an extra term depending on $k$ in the overall convergence rate. This extra term is typically of order $O (\log k)$.

Edit 2: An $O (\log k)$ term is definitely not free. For convex programs, [1] achieves a $o(1/k^2)$ convergence rate via proximal operations. However, the $o(1/k^2)$ algorithm in [1] may not be as fast as an $O(1/k^2)$ gradient algorithm for smooth convex programs, since [1] uses proximal operations...

[1] Hedy Attouch and Juan Peypouquet. The rate of convergence of nesterov’s accelerated forward-backward method is actually faster than $1/k^2$. SIAM Journal on Optimization, 26(3):1824–1834, 2016

Improve this question
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Alf
    Commented Aug 30, 2023 at 15:34
  • $\begingroup$ @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. $\endgroup$
    – T. W.
    Commented Aug 30, 2023 at 15:46
  • $\begingroup$ @Alf Please see my Edit 2 above. the cost of proximal operations is important. $\endgroup$
    – T. W.
    Commented Aug 30, 2023 at 16:34
  • $\begingroup$ 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$. $\endgroup$
    – J. Doe
    Commented Sep 16, 2023 at 16:50
  • $\begingroup$ 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. $\endgroup$
    – J. Doe
    Commented Sep 16, 2023 at 16:57

0

Reset to default

You must log in to answer this question.