Proximal gradient method

proximal_gradient_method(M, f, g, grad_g, p=rand(M); prox_nonsmooth=missing, kwargs...)
proximal_gradient_method(M, mpgo::ManifoldProximalGradientObjective, p=rand(M); kwargs...)
proximal_gradient_method!(M, f, g, grad_g, p; prox_nonsmooth=missing, kwargs...)
proximal_gradient_method!(M, mpgo::ManifoldProximalGradientObjective, p; kwargs...)

Perform the proximal gradient method as introduced in [BJJP25b] and [BJJP25a]. See also [FHS+21] for a similar approach.

Given the minimization problem

\[\operatorname*{arg\,min}_{p∈\mathcal{M}} f(p), \quad \text{ where } \quad f(p) = g(p) + h(p).\]

This method performs the (intrinsic) proximal gradient method algorithm.

Let $λ_k ≥ 0$ be a sequence of (proximal) parameters, initialize $p^{(0)} = p$, and $k=0$.

Then perform as long as the stopping criterion is not fulfilled

\[p^{(k+1)} = \operatorname{prox}_{λ_k h}\Bigl( \operatorname{retr}_{a^{(k)}}\bigl(-λ_k \operatorname{grad} g(a^{(k)})\bigr) \Bigr),\]

where $a^{(k)}=p^{(k)}$ by default, but it allows to introduce some acceleration before computing the gradient step.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
• f: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v (the total cost function $f = g + h$)
• g: the smooth part of the cost function
• grad_g: a gradient (M,p) -> X or (M, X, p) -> X of the smooth part $g$ of the problem
• p::P: a point on the manifold $\mathcal{M}$

Keyword arguments

• acceleration=(pr, st, k) -> (copyto!(get_manifold(pr), st.a, st.p); st): a function (problem, state, k) -> state to compute an acceleration, that is performed before the gradient step - the default is to copy the current point to the acceleration point, i.e. no acceleration is performed
• callbacks::D = Dict{Symbol,Function}(): provided callback functions given either as a single function (symbol, problem, state, k) called in every hook or as a (vector of) pairs :hook => function, which are processed by process_callbacks_arg. As key you can either pass single symbol or an array of symbols to indicate a callback should be added in multiple places
• evaluation::AbstractEvaluationType=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating their result (AllocatingEvaluation) or whether they modify their input argument to return the result therein (InplaceEvaluation). Since usually the first argument is the manifold, the modified argument is the second.
• inverse_retraction_method::AbstractInverseRetractionMethod=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• cost_nonsmooth = missing: the (possibly) nonsmooth part $h$ of $f$ as a function (M, p) -> v, used together with subgradient_nonsmooth to build the default sub_problem
• prox_nonsmooth = missing: a proximal map (M,λ,p) -> q or (M, q, λ, p) -> q for the (possibly) nonsmooth part $h$ of $f$
• subgradient_nonsmooth = missing: a subgradient (M, p) -> X of the (possibly) nonsmooth part $h$ of $f$, used together with cost_nonsmooth to build the default sub_problem
• stepsize::Stepsize=default_stepsize(M,ProximalGradientMethodState): a functor inheriting from Stepsize to determine a step size that by default uses a ProximalGradientMethodBacktracking.
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stopping_criterion::StoppingCriterion=StopWhenGradientMappingNormLess(1.0e-7)|StopAfterIteration(5000)|StopWhenChangeLess(1.0e-9): a functor indicating that the stopping criterion is fulfilled
• sub_problem::Union{AbstractManoptProblem, F, Missing} = missing: specify a problem for a solver or a closed form solution function, which can be allocating or in-place. Alternatively pass missing to take the proximal map from the ManifoldProximalGradientObjective
• sub_state::Union{AbstractManoptSolverState,AbstractEvaluationType} =AllocatingEvaluation(): a state to specify the sub solver to use. For a closed form solution, this indicates the type of function. If the objective does not provide a proximal map, a SubGradientMethodState is used instead. This field is ignored, if the sub_problem is missing.
• X::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$ to specify the representation of a tangent vector

If you activate tutorial mode (cf. is_tutorial_mode), this solver provides additional debug warnings.

All other keyword arguments are passed to decorate_state! for state decorators or decorate_objective! for objective decorators, respectively.

Output

The obtained approximate minimizer $p^*$. To obtain the whole final state of the solver, see get_solver_return for details, especially the return_state= keyword.

proximal_gradient_method(M, f, g, grad_g, p=rand(M); prox_nonsmooth=missing, kwargs...)
proximal_gradient_method(M, mpgo::ManifoldProximalGradientObjective, p=rand(M); kwargs...)
proximal_gradient_method!(M, f, g, grad_g, p; prox_nonsmooth=missing, kwargs...)
proximal_gradient_method!(M, mpgo::ManifoldProximalGradientObjective, p; kwargs...)

Perform the proximal gradient method as introduced in [BJJP25b] and [BJJP25a]. See also [FHS+21] for a similar approach.

Given the minimization problem

\[\operatorname*{arg\,min}_{p∈\mathcal{M}} f(p), \quad \text{ where } \quad f(p) = g(p) + h(p).\]

This method performs the (intrinsic) proximal gradient method algorithm.

Let $λ_k ≥ 0$ be a sequence of (proximal) parameters, initialize $p^{(0)} = p$, and $k=0$.

Then perform as long as the stopping criterion is not fulfilled

\[p^{(k+1)} = \operatorname{prox}_{λ_k h}\Bigl( \operatorname{retr}_{a^{(k)}}\bigl(-λ_k \operatorname{grad} g(a^{(k)})\bigr) \Bigr),\]

where $a^{(k)}=p^{(k)}$ by default, but it allows to introduce some acceleration before computing the gradient step.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
• f: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v (the total cost function $f = g + h$)
• g: the smooth part of the cost function
• grad_g: a gradient (M,p) -> X or (M, X, p) -> X of the smooth part $g$ of the problem
• p::P: a point on the manifold $\mathcal{M}$

Keyword arguments

• acceleration=(pr, st, k) -> (copyto!(get_manifold(pr), st.a, st.p); st): a function (problem, state, k) -> state to compute an acceleration, that is performed before the gradient step - the default is to copy the current point to the acceleration point, i.e. no acceleration is performed
• callbacks::D = Dict{Symbol,Function}(): provided callback functions given either as a single function (symbol, problem, state, k) called in every hook or as a (vector of) pairs :hook => function, which are processed by process_callbacks_arg. As key you can either pass single symbol or an array of symbols to indicate a callback should be added in multiple places
• evaluation::AbstractEvaluationType=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating their result (AllocatingEvaluation) or whether they modify their input argument to return the result therein (InplaceEvaluation). Since usually the first argument is the manifold, the modified argument is the second.
• inverse_retraction_method::AbstractInverseRetractionMethod=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• cost_nonsmooth = missing: the (possibly) nonsmooth part $h$ of $f$ as a function (M, p) -> v, used together with subgradient_nonsmooth to build the default sub_problem
• prox_nonsmooth = missing: a proximal map (M,λ,p) -> q or (M, q, λ, p) -> q for the (possibly) nonsmooth part $h$ of $f$
• subgradient_nonsmooth = missing: a subgradient (M, p) -> X of the (possibly) nonsmooth part $h$ of $f$, used together with cost_nonsmooth to build the default sub_problem
• stepsize::Stepsize=default_stepsize(M,ProximalGradientMethodState): a functor inheriting from Stepsize to determine a step size that by default uses a ProximalGradientMethodBacktracking.
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stopping_criterion::StoppingCriterion=StopWhenGradientMappingNormLess(1.0e-7)|StopAfterIteration(5000)|StopWhenChangeLess(1.0e-9): a functor indicating that the stopping criterion is fulfilled
• sub_problem::Union{AbstractManoptProblem, F, Missing} = missing: specify a problem for a solver or a closed form solution function, which can be allocating or in-place. Alternatively pass missing to take the proximal map from the ManifoldProximalGradientObjective
• sub_state::Union{AbstractManoptSolverState,AbstractEvaluationType} =AllocatingEvaluation(): a state to specify the sub solver to use. For a closed form solution, this indicates the type of function. If the objective does not provide a proximal map, a SubGradientMethodState is used instead. This field is ignored, if the sub_problem is missing.
• X::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$ to specify the representation of a tangent vector

If you activate tutorial mode (cf. is_tutorial_mode), this solver provides additional debug warnings.

All other keyword arguments are passed to decorate_state! for state decorators or decorate_objective! for objective decorators, respectively.

Output

The obtained approximate minimizer $p^*$. To obtain the whole final state of the solver, see get_solver_return for details, especially the return_state= keyword.

ProximalGradientMethodAcceleration{P, T, F}

Compute an acceleration step

\[a^{(k)} = \operatorname{retr}_{p^{(k)}}\bigl( -β_k\operatorname{retr}^{-1}_{p^{(k)}}(p) \bigr)\]

where $p^{(k)}$ is the current iterate from the ProximalGradientMethodState's field p and the result is stored in state.a. The field p in this struct stores the last iterate.

The inverse retraction is taken from this struct's inverse_retraction_method, the retraction from the state.

Fields

• p - the last iterate
• β - acceleration parameter function k -> β_k
• inverse_retraction_method - method for inverse retraction
• X - tangent vector for computations

Constructor

ProximalGradientMethodAcceleration(M::AbstractManifold; kwargs...)

Generate the acceleration functor for a given manifold M.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$

Keyword arguments

• β = k -> (k-1)/(k+2) - acceleration parameter function k -> β_k
• inverse_retraction_method - method for inverse retraction
• p - initial point
• X - initial tangent vector

ProximalGradientMethodState <: AbstractManoptSolverState

State for the proximal_gradient_method solver.

Fields

• callbacks::D: provided callback functions given as a dictionary with symbols as keys
• inverse_retraction_method::AbstractInverseRetractionMethod: an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• a - point after acceleration step
• p::P: a point on the manifold $\mathcal{M}$ storing the current iterate
• q - the point the last proximal gradient step started from, that is $a^{(k)}$, which is the previous iterate without acceleration
• retraction_method::AbstractRetractionMethod: a retraction $\operatorname{retr}$ to use, see the section on retractions
• X - tangent vector for storing gradient
• stop::StoppingCriterion: a functor indicating that the stopping criterion is fulfilled
• acceleration - a function (problem, state, k) -> state to compute an acceleration before the gradient step
• stepsize - a Stepsize object to compute the stepsize
• last_stepsize - stores the last computed stepsize
• sub_problem::Union{AbstractManoptProblem, F}: specify a problem for a solver or a closed form solution function, which can be allocating or in-place. Alternatively pass missing to take the proximal map from the ManifoldProximalGradientObjective
• sub_state::Union{AbstractManoptSolverState,AbstractEvaluationType}: a state to specify the sub solver to use. For a closed form solution, this indicates the type of function. This field is ignored, if the sub_problem is missing.

Constructor

ProximalGradientMethodState(M::AbstractManifold; kwargs...)

Generate the state for a given manifold M with initial iterate p.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$

Keyword arguments

• stepsize=default_stepsize(M, ProximalGradientMethodState)
• callbacks::D = Dict{Symbol,Function}(): provided callback functions given as a dictionary with symbols as keys
• inverse_retraction_method::AbstractInverseRetractionMethod=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• p::P =rand(M): a point on the manifold $\mathcal{M}$ to specify the initial value
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• acceleration=(pr, st, k) -> (copyto!(get_manifold(pr), st.a, st.p); st) by default no acceleration is performed
• stopping_criterion::StoppingCriterion=StopWhenGradientMappingNormLess(1.0e-2)|StopAfterIteration(5000)|StopWhenChangeLess(1.0e-9): a functor indicating that the stopping criterion is fulfilled
• sub_problem::Union{AbstractManoptProblem, F} = missing: specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
• sub_state::Union{AbstractManoptSolverState,AbstractEvaluationType} = missing: a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.
• X::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$ to specify the representation of a tangent vector

ProximalGradientNonsmoothSubgradient{F, R, P} <: AbstractManifoldFunction

Stores a subgradient of the nonsmooth part $h$ of the proximal gradient objective $f = g + h$, as well as the stepsize parameter $λ ∈ ℝ$.

This struct is also a functor (M, q) -> X that computes a subgradient in allocating fashion. This is primarily used for computing a subgradient of the cost function $h(q) + \frac{1}{2λ}\mathrm{d}^2(q, p)$ that defines proximal map in the proximal gradient method. This reads

\[ ∂h(q) - \frac{1}{λ}\log_q p\]

and $p$ is the proximity point where the proximal map is evaluated, i.e. the argument $p$ of the proximal map $\operatorname{prox}_{λ h} (p)$.

Fields

• X::F - the subgradient of the nonsmooth part of the total objective, i.e. the part of the objective whose proximal map is sought
• λ::R - the stepsize parameter for the proximal map
• proximity_point::P - point where the proximal map is evaluated, i.e. the argument of the proximal map that we want to solve for

Constructor

ProximalGradientNonsmoothSubgradient(X, λ, proximity_point)

ProximalGradientNonsmoothCost{F, R, P} <: AbstractManifoldFunction

Stores the nonsmooth part $h$ of the proximal gradient objective $f = g + h$, as well as the stepsize parameter $λ ∈ ℝ$.

This struct is also a functor (M, q) -> v that can be used as a cost function within a solver, primarily for solving the proximal map subproblem formulation in the proximal gradient method, which reads

\[ \operatorname{prox}_{λ h}(p) = \operatorname*{arg\,min}_{q ∈ \mathcal{M}} h(q) + \frac{1}{2λ}\mathrm{d}^2(q, p)\]

Hence, the function reads

\[ (M, q) ↦ h(q) + \frac{1}{2λ} \mathrm{d}^2(q, p)\]

and p is the proximity point where the proximal map is evaluated, i.e. the argument p of the proximal map $\operatorname{prox}_{λ h}$.

Fields

• cost::F - the nonsmooth part $h$ of the proximal gradient objective, i.e. the part of the objective whose proximal map is sought
• λ::R - the stepsize parameter for the proximal map
• proximity_point::P - point where the proximal map is evaluated, i.e. the argument $p$ of the proximal map $\operatorname{prox}_{λ h} (p)$ that we want to solve for

Constructor

ProximalGradientNonsmoothCost(cost, λ, proximity_point)

ProximalGradientMethodBacktracking(; kwargs...)
ProximalGradientMethodBacktracking(M::AbstractManifold; kwargs...)

Compute a stepsize for the proximal gradient method using a backtracking line search.

For the nonconvex case, the condition is:

\[f(p) - f(T_{λ}(p)) ≥ γλ\lVert G_{λ}(p) \rVert^2\]

where $G_{λ}(p) = -(1/λ)\log_p(T_{λ}(p))$ is the gradient mapping.

For the convex case, the condition is:

\[g(T_{λ}(p)) ≤ g(p) + ⟨\operatorname{grad} g(p), \log_p T_{λ}(p)⟩ + \frac{ζ_δ}{2λ} \mathrm{d}^2(p, T_{λ}(p))\]

Returns a stepsize λ that satisfies the specified condition.

ProximalGradientMethodBacktrackingStepsize <: Stepsize

A functor for backtracking line search in proximal gradient methods.

Fields

• initial_stepsize::T - initial step size guess
• sufficient_decrease::T - sufficient decrease parameter (default: 0.5)
• contraction_factor::T - step size reduction factor (default: 0.5)
• strategy::Symbol - :nonconvex or :convex (default: :nonconvex)
• candidate_point::P - a working point used during backtracking, it stores the result of the proximal step
• gradient_point::P - a working point used during backtracking, it stores the result of the gradient step
• last_stepsize::T - the last computed stepsize
• stop_when_stepsize_less::T - the smallest stepsize before the search stops
• warm_start_factor::T - factor to scale the last stepsize with for the next initial guess (:convex strategy)
• k_max::T - an upper bound on the sectional curvature of the manifold
• δ::T - tolerance parameter for the radius restriction used when k_max > 0

Constructor

ProximalGradientMethodBacktrackingStepsize(M::AbstractManifold; kwargs...)

Keyword arguments

• initial_stepsize=1.0: initial stepsize to try
• stop_when_stepsize_less=1e-8: smallest stepsize when to stop (the first one below this bound is returned)
• sufficient_decrease=0.5: sufficient decrease parameter
• contraction_factor=0.5: step size reduction factor
• strategy=:nonconvex: backtracking strategy, either :convex or :nonconvex
• warm_start_factor=1.0: factor to scale the last stepsize with to obtain the initial guess of the next search, only used by the :convex strategy
• k_max=0.0: an upper bound to the sectional curvatures of the manifold; if positive, candidate steps are restricted to a curvature-dependent radius (applies to both strategies)
• δ=1e-2: parameter for backtracking in case k_max > 0

get_cost_smooth(M::AbstractManifold, objective, p)

Helper function to extract the smooth part g of a proximal gradient objective at the point p.

default_stepsize(M::AbstractManifold, ::Type{<:ProximalGradientMethodState})

Returns the default proximal stepsize, which is a nonconvex backtracking strategy.