Return to Question

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, 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

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

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. In [1], a $o(1/k^2)$ convergence rate is achieved via proximal operations. However, the $o(1/k^2)$ algorithm in [1] is actually not as fast as an $O(1/k^2)$ gradient algorithms, 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

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, 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

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 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)$.

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. In [1], a $o(1/k^2)$ convergence rate is achieved via proximal operations. However, the $o(1/k^2)$ algorithm in [1] is actually not as fast as an $O(1/k^2)$ gradient algorithms, 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