Polyak Optimal-Value Step

Worked Example

Consider the objective function f(x, y) = 0.5(x² + ky²) with condition ratio k = 4, starting at (x_0, y_0) = (1, 1). The known optimal value is f^* = 0. The gradient is ∇ f(x, y) = (x, ky).

1. Calculate the objective and gradient at the starting point:
   f(1, 1) = 0.5(1² + 4 · 1²) = 2.5
   ∇ f(1, 1) = (1, 4)
2. Calculate the squared norm of the gradient:
   ‖∇ f(1, 1)‖² = 1² + 4² = 17
3. Compute the Polyak step size:
   η = (f(1, 1) - f^*)/(‖∇ f(1, 1)‖²) = (2.5 - 0)/17 ≈ 0.14705882352941177
4. Update the point using gradient descent:
   x_1 = x_0 - η · \nabla_x f(1, 1) = 1 - 0.14705882352941177 · 1 = 0.8529411764705882
   y_1 = y_0 - η · \nabla_y f(1, 1) = 1 - 0.14705882352941177 · 4 = 0.4117647058823529

Experiment

To observe the behavior of the Polyak step compared to exact line search, you can interact with the module.

1. Set the Condition ratio to 4.
2. Set the Start point to Diagonal.
3. Select the Rule as Exact line search. Notice how the step sizes differ significantly from the Polyak rule because exact line search minimizes along the gradient ray.
4. Adjust the Steps to 2 and observe the trajectory on the canvas. Switch back to Polyak and compare the steps and objective values.

Limitations

The Polyak step size relies on knowing the exact optimal value of the objective function, which is often unknown in practice. The documented optimal-value assumption cannot be silently replaced by an arbitrary mini-batch loss target, as the stochastic loss at the global optimum is not necessarily zero. Furthermore, the Polyak rule is not equivalent to an exact line search, even on a quadratic function, as it uses the optimal value rather than knowledge of the optimizer coordinates. Zero gradient stops the process before division by zero.

References

For more details on the assumptions and convergence of optimal-value steps in various models, see the paper on over-parameterization and optimization.

Primary Source: Optimal Value Step Size (Kakade et al., 2019).