Auto increase gamma

[aplavin]

Currently, the step size gamma parameter can only decrease, eg at

ProximalAlgorithms.jl/src/algorithms/fast_forward_backward.jl

Line 92 in dc0342c

gamma, state.g_z = backtrack_stepsize!(

However, sometimes larger step sizes can be performed at some point during iteration.
I tried doing state.gamma *= 1.02 in the iteration loop, and seem to get ~2x faster convergence on some problems.
Gamma vs iterations plot looks like this:

Does this modification make sense in general? For some algorithms?
Should it be included into the package implementation itself?

[lostella]

@aplavin I think this makes sense to include as an option pretty much anywhere that backtracking routine is adopted. Backtracking is used to make sure gamma is small enough wrt the local geometry of the objective, to guarantee some sufficient decrease condition hence convergence: as long as it runs at every iteration, having it start from the previous gamma or something larger will not make a difference for convergence (rates).

Do you want to open a PR?

It would have an associated coefficient in the algorithm (your 1.02) to allow configuration: just like the backtracking coefficient, I’m not sure there’s some a priori optimal setting for this. Too large an increase will trigger backtracking more often, which has a cost.

For a proximal gradient iteration with fully adaptive stepsize, and no backtracking logic, you can check out this paper https://arxiv.org/abs/2301.04431 with associated code https://github.com/pylat/adaptive-proximal-algorithms. We found this to often outperform Nesterov extrapolation, and requires no setting, although it doesn’t come with the same convergence rate guarantees. (Haven’t found the time to include this in ProximalAlgorithms.)

[aplavin]

Thanks for confirming that the modification makes sense! I'm not closely familiar with proximal algorithms, just saw this trick used somewhere.Also I noticed some algorithms (eg PANOC) do a state reset when gamma changes. Would this modification play well with those?However I didn't find any of the other algorithms to perform better than the accelerated gradient (FastForwardBackward) in cursory testing on my problems.Definitely looking forward for trying the new algorithm you linked!Message ID: ***@***.***>

[aldma]

For algorithms using some sort of extrapolation (e.g. PANOC and PANOCplus), the state reset after changing gamma is due to the underlying quasi-Newton approximation of the fixed-point operator, which depends on gamma. The rationale is that, whenever gamma changes, the operator changes as well, so we reset the memory and restart with the approximation scheme.

A increase_gamma factor has been included with #91 / #92 to increase the stepsize in some algorithms.

The adaptive schemes mentioned above by @lostella should be included as well with a dedicated PR (work in progress).