Optimization of Inf-Convolution Regularized Nonconvex Composite Problems
Emanuel Laude Tao Wu Daniel Cremers







Optimization of Inf-Convolution Regularized Nonconvex Composite Problems






Laude, Wu, Cremers

[

Optimization of Inf-Convolution Regularized
 Nonconvex Composite Problems

 Emanuel Laude Tao Wu Daniel Cremers 
Department of Informatics, Technical University of Munich, Germany 
]



In this work, we consider nonconvex composite problems that involve inf-convolution with a Legendre function, which gives rise to an anisotropic generalization of the proximal mapping and Moreau-envelope. In a convex setting such problems can be solved via alternating minimization of a splitting formulation, where the consensus constraint is penalized with a Legendre function. In contrast, for nonconvex models it is in general unclear that this approach yields stationary points to the infimal convolution problem. To this end we analytically investigate local regularity properties of the Moreau-envelope function under prox-regularity, which allows us to establish the equivalence between stationary points of the splitting model and the original inf-convolution model.
We apply our theory to characterize stationary points of the penalty objective, which is minimized by the elastic averaging SGD (EASGD) method for distributed training. Numerically, we demonstrate the practical relevance of the proposed approach on the important task of distributed training of deep neural networks.




§ INTRODUCTION

In this work, we are interested in optimizing nonconvex composite models which involve infimal convolutions with Legendre functions:

    u∈^nminimize       f(Au) + g(u).

Here both f:^m →:=∪{+∞,-∞} and g:^n → are extended real-valued, proper[A function f:^m → is called proper if f(z̅)<∞ for some z̅∈^m and f(z)>-∞ for all z∈^m.]
and lower semi-continuous (lsc) functions which are possibly nonconvex and nonsmooth, and A ∈^m × n is a coupling matrix. Let f:={z∈^m: f(z) <∞} denote the domain of f. By f we denote the infimal convolution of a function f with some Legendre function ϕ: ^m →; see Definition <ref>.
The infimal convolution of f with a potential ϕ and scaling parameter λ is defined as 

    f(v)=inf_z ∈^m f(z) + 1/λϕ(v-z).

We shall refer to f as the ϕ-envelope of f, and the corresponding  map

    f(v)=_z ∈^m f(z) + 1/λϕ(v-z),

as the ϕ-proximal mapping of f at v. 

Note that for ϕ=1/2·^2 they specialize to the classical Moreau-envelope and proximal mapping <cit.>. 

Under suitable assumptions that guarantee that the inf is attained when finite, f yields a regularized variant of f in the sense that the epigraph of f is obtained via the Minkowski sum of the epigraphs of the individual functions f and ϕ <cit.>. 
For convex proper lsc f and Lipschitz differentiable[A function is called Lipschitz differentiable if it is differentiable and its gradient is Lipschitz continuous.] ϕ, f is a Lipschitz differentiable approximation to f.
In contrast, when f is nonconvex and nonsmooth, f remains nonsmooth and nonconvex in general which renders the optimization of (<ref>) challenging.

Inf-convolution models are well grounded in machine learning and signal processing. A variety of convex and nonconvex loss functions and regularizers can be written as an infimal convolution. There, the potential ϕ is chosen in accordance with the underlying noise prior, e.g., quadratic for Gaussian.

In addition, benefits of inf-convolution regularization (with quadratic ϕ) have been observed empirically in neural network training in recent works <cit.>. 



 §.§ Motivation

To compute a stationary point of (<ref>), we resort to a splitting model

    u∈^n,  z ∈^mminimize 
    F(u, z):= f(z) + 1/λϕ(Au - z) + g(u),

where the violation of the constraint Au = z is penalized with ϕ. From Equation (<ref>) it can be seen that model (<ref>) is equivalent to model (<ref>) in terms of global optima but in general not in terms of stationary points[A stationary point (u̅, z̅) of (<ref>) is a point that satisfies the necessary first order optimality condition 0∈∂ F(u̅, z̅), cf. Fermat's rule generalized <cit.>. 

When (u̅, z̅) ∈ F is feasible and ϕ is continuously differentiable on ϕ open, 0∈∂ F(u̅, z̅) is implied by (<ref>)–(<ref>) via <cit.>.
].
The splitting formulation (<ref>) is amenable to alternating optimization, which, under mild assumptions, converges subsequentially to a stationarity point (u̅, z̅) of F, satisfying the following conditions (assuming ϕ is open): Au̅-z̅∈ϕ, u̅∈ g, z̅∈ f, and


    0    ∈∂ g(u̅) + 1λ A^⊤∇ϕ(Au̅-z̅), 
    
    0    ∈∂ f(z̅) - 1λ∇ϕ(Au̅-z̅).


Here ∂ denotes the (limiting) subdifferential of a function, cf. Definition <ref>.

Meanwhile, in order for u̅ to qualify as
a stationary point of the original problem (<ref>) it must  satisfy

    0 ∈∂ ( f ∘ A + g)(u̅).

When f is smooth around A u̅ and u̅∈ g, the stationarity condition (<ref>) simplifies to 

    0 ∈ A^⊤∇ f(Au̅) + ∂ g(u̅),
 
via <cit.>.

It is important to realize that conditions (<ref>)–(<ref>) do not imply (<ref>) or (<ref>) in general when f is nonconvex.
This stands in stark contrast to the convex setting, where the stationarity condition (<ref>) (for quadratic ϕ=1/2·^2) can be guaranteed via the well known gradient formula for the Moreau-envelope <cit.>: 

    ∇ e_λ^·^2/2 f(v) = 1/λ (v - P_λ^·^2/2 f (v)).

To this end, note that (<ref>) resembles the necessary (and in the convex setting also sufficient) optimality condition of the ϕ-proximal mapping z̅= (Au̅).
For this reason, a main focus of this work is to derive sufficient conditions that guarantee the translation of stationarity in the more general nonconvex setting for (nonquadratic) ϕ, which ultimately boils down to the following implication:

    (<ref>) ⇒ 1λ∇ϕ(Au̅-z̅) =∇ f (A u̅).

In this sense, the implication in (<ref>) is a generalization of the gradient formula (<ref>) for the the ϕ-envelope. 



 §.§ Contributions

Our contributions are summarized as follows:


  * We consider an anisotropic generalization of the proximal mapping and Moreau-envelope <cit.> induced by a Legendre function in the nonconvex setting. More precisely we establish local regularity properties of the envelope function and proximal mapping under prox-regularity, including a generalization of the well known gradient formula for the Moreau-envelope. The translation of stationarity is a consequence of this theory.

  * We apply our theory to characterize stationary points of the model that is minimized by the elastic averaging SGD (EASGD) <cit.> method for distributed training with anisotropic (i.e., non-quadratic) penalty functions. There, our theory can be invoked to obtain a robust measure of stationarity via the gradient of the Moreau-envelope. 

  * Numerically, we apply our algorithm to distributed training of deep neural networks and showcase merits of anisotropic inf-convolution potentials over standard quadratic in this context.





§ RELATED WORK

Proximal mappings and Moreau-envelopes date back to the seminal papers of Moreau <cit.>.

<cit.> consider an anisotropic generalization of the proximal mapping which is obtained by replacing the quadratic penalty with a Legendre function and study its properties in a convex setting. <cit.> relates the anisotropic proximal mapping to the Bregman proximal mapping (introduced in <cit.> and investigated in <cit.>) via a generalization of Moreau's decomposition <cit.>, which holds for convex functions. The Bregman prox and the anisotropic prox are different generalizations of the classical prox with complementary properties.

In the convex setting the Moreau-envelope has strong regularity properties such as Lipschitz differentiability. In the nonconvex setting the Moreau-envelope is nonsmooth in general. In <cit.> the concept of prox-regular functions is introduced, which allows the authors to (locally) recover some of the properties known from the convex setting: These include the (local) single-valuedness of the prox and (local) Lipschitz differentiability of the envelope.

In <cit.>, prox-regularity is used to establish a local convergence result for alternating and averaged projections methods.
Similar to this work but specialized to quadratic ϕ, in <cit.>, prox-regularity is utilized to show a translation of stationarity for the model (<ref>) which is computationally resolved by multiblock ADMM.

More recently, in <cit.> the gradient of the Moreau-envelope has been used as a stationarity measure in stochastic optimization methods.

Inf-convolution regularization has recently been utilized in neural network training <cit.>:
In <cit.> the authors have considered the consensus training of deep neural networks by optimizing a relaxed consensus model of the form (<ref>) with quadratic ϕ. Similar algorithms were later connected to partial differential equations <cit.>. 



§ ANISOTROPIC PROXIMAL MAPPING

In this section, we introduce the notion of Legendre functions that gives rise to an anisotropic generalization of the proximal mapping and Moreau-envelope investigated in the convex setting by <cit.>. We establish a sufficient condition for the well-definedness of the anisotropic prox (denoted as ϕ-prox) and envelope (denoted as ϕ-envelope) in the nonconvex setting, based on a generalized notion of prox-boundedness <cit.>.

A proper convex lsc Legendre function is defined below according to <cit.>. Here ∂ϕ reduces to the classical convex subdifferential.
 
The proper convex lsc function ϕ:^m → is


  (i) essentially smooth, if the interior of the domain of ϕ is nonempty, i.e. ϕ≠∅, and ϕ is differentiable on ϕ such that ∇ϕ(w^ν)→∞ whenever w^ν→ w ∈ϕ;

  (ii) essentially strictly convex, if ϕ is strictly convex on every convex subset of ∂ϕ:={w ∈^m : ∂ϕ(w) ≠∅};

  (iii) Legendre, if ϕ is both essentially smooth and essentially strictly convex.


Let ϕ^* denote the convex conjugate of ϕ. Then, Legendre functions have the following essential properties:
 
Let ϕ:^m → be proper lsc convex and Legendre. Then ϕ has the following properties:


  (i) ∂ϕ = ϕ, <cit.>. 

  (ii) ∇ϕ: ϕ→ϕ^* is bijective with inverse ∇ϕ^*: ϕ^* →ϕ with both ∇ϕ and ∇ϕ^* continuous on ϕ resp. ϕ^*, <cit.>.



Overall we will make the following (additional) assumptions on ϕ:


  (A1) ϕ:^m → is proper lsc convex and Legendre.

  (A2)  ϕ is open.

  (A3)  ϕ is twice continuously differentiable on ϕ with positive definite Hessian, i.e., ∇^2 ϕ(w) ≻ 0 for any w ∈ϕ.

  (A4)  ϕ is super-coercive, i.e., ϕ(w)/w→∞ whenever w→∞.

  (A5)  ϕ(0) = 0 and ∇ϕ(0) = 0.

(A2) ensures that ϕ(w^ν) →∞, whenever w^ν→ w ∈ϕ. In particular this allows us to utilize alternating gradient descent steps as updates in our algorithm, cf. Section <ref>. (A3) implies that ϕ is “locally” strongly convex and Lipschitz differentiable in the sense of <cit.>: For any compact and convex K ⊂∂ϕ, there are constants μ,γ>0 such that for any w_1, w_2 ∈ K:

    ϕ(w_1) ≥ϕ(w_2) + ⟨∇ϕ(w_2), w_1 -w_2 ⟩ + μ/2w_1-w_2^2, 
       ∇ϕ(w_1) - ∇ϕ(w_2) ≤γw_1-w_2.

Such functions are known under the term very strictly convex <cit.> which lie “strictly between the class of strongly convex and the class of strictly convex functions”, <cit.>.
(A4) is required later on in Section <ref> to show the translation of stationarity.
(A5) is technically not required in our theory. However, it naturally leads to a smoothing which under prox-regularity preserves stationarity (see Corollary <ref>).

Examples for such ϕ include the scaled quadratic ϕ(w)=w^⊤ Q w (with matrix Q symmetric positive definite) or a log-barrier function ϕ(w)= -log(1- w^2). Further examples are provided in Section <ref>.


It is important to realize that for nonconvex f the well-definedness of the ϕ-proximal mapping and envelope requires additional assumptions: More precisely, we shall guarantee that f is proper and f(v) ≠∅ for any v ∈ f.
In addition, this condition allows us to extract a continuity property for the ϕ-proximal mapping and envelope which is extensively needed later on to prove the desired translation of stationarity in Section <ref>:

We say f:^m → is ϕ-prox-bounded if there exists λ > 0 such that for any v̅∈^m there exists ϵ > 0 and a constant β > -∞ such that

    f(v) ≥β

for any v with v-v̅≤ϵ. The supremum of the set of all such λ is the threshold λ_f of the ϕ-prox-boundedness.

When f is bounded from below it is ϕ-prox-bounded with threshold λ_f = ∞. 
Notably, in the classical case (when ϕ is quadratic) the definition can be made minimalistic, cf. <cit.>: It suffices to assume the existence of some v̅∈^m so that f(v̅) > -∞.


Overall we summarize below the properties of ϕ-prox and envelope under ϕ-prox-boundedness that shall be used along our course in the next section.
 
Let f:^m → be proper lsc and ϕ-prox-bounded with threshold λ_f>0. Then for any λ∈ (0,λ_f), f and f have the following properties:


  (i) f(v) ≠∅ is compact for all v ∈ f= f + ϕ, whereas f(v) =∅ for v ∉ f.

  (ii) The ϕ-envelope f is continuous relative to f.

  (iii) For any sequence v^ν→v̅ contained in f and z^ν∈ f(v^ν) we have {z^ν}_ν∈ is bounded and all its cluster points z̅ lie in f(v̅).





§ TRANSLATION OF STATIONARITY
 
In this section we prove the translation of stationarity, see (<ref>), under prox-regularity: We emphasize that it is a major concern of the splitting approach in the nonconvex setting to justify whether solving the splitting model (<ref>) guarantees solving the original model (<ref>), both in terms of stationarity. 

To this end we recall the definitions of the regular and the limiting subdifferential according to <cit.>.
 
Let f:^m→ and z̅∈ f be given. For y∈^m, we say 


  (i) y is a regular subgradient of f at z̅, written y ∈∂ f(z̅), if

    lim inf_z →z̅
     z ≠z̅f(z)-f(z̅)- yz-z̅/z-z̅≥ 0.

We refer to the set ∂ f(z̅) as the regular subdifferential of f at z̅.

  (ii) y is a (limiting) subgradient of f at y, written y ∈∂ f(z̅), if there exist z^ν→z̅ with f(z^ν) → f(z̅) and y^ν∈∂ f(z^ν) with y^ν→ y.
We refer to the set ∂ f(z̅) as the (limiting) subdifferential of f at z̅.


We remark that for f convex, both the regular and the limiting subdifferential coincide with the classical convex subdifferential, <cit.>.

Next, we define prox-regularity of functions, according to <cit.>:

Assume f:^m→ is lsc and finite at z̅∈^m. We say f is prox-regular at z̅ for y̅∈∂ f(z̅) if there exist ϵ>0 and r≥ 0 such that for all z'-z̅<ϵ

    f(z') ≥ f(z)+yz'-z-r/2z'-z^2,

whenever z-z̅<ϵ, f(z)-f(z̅)<ϵ, y∈∂ f(z), y-y̅<ϵ. When this holds for all y̅∈∂ f(z̅), f is said to be prox-regular at z̅.

Prox-regularity is a local property in nature. Examples for (everywhere) prox-regular functions include: (i) proper, (weakly) convex, lsc functions; (ii) 𝒞^2-functions; and (iii) indicator functions of 𝒞^2-manifolds <cit.>. For further examples we refer to <cit.>.

Based on prox-regularity and ϕ-prox-boundedness, we now extend <cit.> to f and f in our context (see Theorem <ref>) and eventually derive the translation of stationarity as desired (see Corollary <ref>).
As a key ingredient in the proof of Theorem <ref> we may invoke the generalized implicit function theorem <cit.> <cit.> to assert f is locally a single-valued, Lipschitz map. 

 
Let f:^m→ proper lsc and ϕ-prox-bounded with threshold λ_f. Let v̅∈z̅+ϕ. Then for any λ∈ (0,λ_f) sufficiently small and f finite and prox-regular at z̅ for y̅∈∂ f(z̅) with 

    y̅ =1/λ∇ϕ(v̅-z̅)

the following statements hold true:


  (i) f is a singled-valued, Lipschitz 
 map near v̅ such that 
z̅= f(v̅) and 

    f(v) 
       = (I + ∇ϕ^* ∘λ T)^-1(v),

where T is the f-attentive ϵ-localization of ∂ f near (z̅,y̅), i.e. the set-valued mapping T:^m ⇉^m defined by T(z):={y ∈∂ f(z) : y -y̅< ϵ}
if z - z̅ < ϵ and f(z)<f(z̅)+ϵ, and T(z):=∅ otherwise.

  (ii) f is Lipschitz differentiable around v̅ with 

    ∇ f(v)=1/λ∇ϕ(v-z).




We provide a short proof sketch for part (i). For a detailed proof of part (i) and part (ii) we refer to the supplements.

(i) Using the definition of prox-regularity, the assumptions in the theorem and the continuity property of the prox from Lemma <ref> (which holds under ϕ-prox-boundedness) it can be proven that for some λ∈ (0, λ_f) sufficiently small for any ξ sufficiently near 0 we have
ξ∈ T(z)-1/λ∇ϕ(v̅-z),
for some z near z̅. Furthermore, using the definition of prox-regularity and Assumption (A3), it can be shown that T-1/λ∇ϕ(v̅-·) is strongly monotone.

This implies that ξ↦(T-1/λ∇ϕ(v̅-·))^-1(ξ) is a single-valued, Lipschitz map in a neighborhood of 0 such that (T-1/λ∇ϕ(v̅-·))^-1(0)=z̅. 
Invoking the generalized implicit function theorem 
<cit.>, we assert that v↦ f(v)=(T-1/λ∇ϕ(v-·))^-1(0) is a single-valued, Lipschitz map in a neighborhood of v̅ 
such that z̅= f(v̅).


As an immediate consequence of the above theorem, the implication in (<ref>) holds true and the translation of stationarity is attained under prox-regularity.

 
Let (u̅,z̅) be a stationary point for the splitting model (<ref>) satisfying Au̅-z̅∈ϕ, u̅∈ g, z̅∈ f and conditions (<ref>)–(<ref>). Let f:^m→ be ϕ-prox-bounded with threshold λ_f and prox-regular at z̅ for y̅:=1/λ∇ϕ(Au̅-z̅). Then, for λ∈ (0, λ_f) sufficiently small, the stationarity condition (<ref>) is fulfilled, i.e., u̅ is a stationary point for the inf-convolution model (<ref>).


Invoking Theorem <ref> with (z̅,1/λ∇ϕ(Au̅-z̅)) and λ∈ (0, λ_f) sufficiently small, we obtain A^⊤∇ f(Au̅)=1/λA^⊤∇ϕ(Au̅-z̅). In combination with (<ref>), this yields 
0 ∈ A^⊤∇ f(Au̅) + ∂ g(u̅).
Since f is continuously differentiable around A u̅ and u̅∈ g, this implies (<ref>) due to <cit.>.




§ APPLICATION TO DISTRIBUTED TRAINING
 
In this section, we present a stochastic alternating minimization scheme (Algorithm <ref>) tailored to distributed empirical risk minimization in (<ref>).
As an interesting special case, we consider scenarios where all workers have access to the entire training set and the method specializes to elastic averaging SGD (EASGD) <cit.>. 


 §.§ Inexact Alternating Minimization

For the optimization of the splitting problem (<ref>) one typically resorts to alternating minimization where the variables u and z are updated as:


    u^t+1∈_u∈^n g(u)+ 1/λϕ(Au-z^t), 
    
    z^t+1∈_z∈^m 1/λϕ(Au^t+1-z) + f(z).


Such a scheme is known as the Gauss-Seidel or block coordinate descent method and has been investigated in a general setting by, e.g., <cit.>.

In our case we regard alternating minimization as a generic scheme where the subproblems (in particular the z-update) may be solved approximately (e.g., by replacing the function with a surrogate) as long as convergence to a stationary point of the splitting problem can be guaranteed. Then, the translation of stationarity from Corollary <ref> applies under prox-regularity.

For instance, the vanilla Gauss-Seidel method can be extended with a proximal regularization as in <cit.>. When ϕ is Lipschitz differentiable, the coupling term ϕ(Au-z) can be replaced by a proximal linearization in z (resp. u) at z^t (resp. u^t), so that the updates become proximal gradient steps on F as in proximal alternating linearized minimization (PALM) <cit.>.

Alternating minimization can also incorporate stochastic gradient updates, as described in the next subsection.



 §.§ Stochastic Alternating Minimization for Distributed Training
 
In distributed learning, a set of M workers collaborates on the training of a model parameterized by consensus weights u. To this end, with access to a prescribed subset (indexed by ℐ_j) of the full training set (indexed by ℐ), each individual worker trains its local copy z_j of the model parameters u under a (relaxed) consensus constraint u=z_j. As a consequence, all workers can update their copies in parallel.

In terms of the model (<ref>), this is formulated as follows. For the remainder of this section let f:^nM→ with 

    f(z)=∑_j=1^M f_j(z_j)

be a separable sum of (regularized) continuously differentiable empirical risks f_j:^n→, each assigned to worker j.
More specifically each f_j is defined as

    f_j(z_j)=  1/|ℐ_j|∑_i∈ℐ_jℓ(h_i, H(x_i; z_j)) + R(z_j),

for training pairs (x_i, h_i)_i ∈ℐ_j, some prediction function H(·;z) parameterized by weights z, a loss function ℓ(·,·) and a regularizer R. Furthermore, let g:=0 and A:=[I, ⋯, I]^⊤∈^(nM) × n, and set the Legendre penalty as

    ϕ(w):= ∑_j=1^M (w_j)

which is separable over the copies w_j. Overall model (<ref>) then reads:

    min_u, (z_j)_j=1^M ∈^n F(u,z)=∑_j=1^M f_j(z_j) + 1/λ(u - z_j),

where (u - z_j) loosely enforces the consensus constraint u = z_j.

The stochastic instance of the alternating minimization scheme is formulated in Algorithm <ref> below. Notably, Algorithm <ref> specializes to EASGD <cit.> in the isotropic case, i.e. when ϕ is quadratic and all workers have access to the entire training set ℐ, i.e. ℐ_j= ℐ.




To obtain an unbiased estimate of the gradient ∇_z F(u^t+1, z^t) of F(u^t+1, ·)= f + 1/λϕ(A u^t+1 - ·) at z^t, worker j samples a uniformly random minibatch ℬ_j^t from ℐ_j, and computes the standard stochastic gradient, 

    δ_j^t =1/|ℬ_j^t|∑_i∈ℬ_j^t∇ (ℓ(h_i, H(x_i; ·)))(z_j^t).

Then we may define Δ(z^t; ξ^t):=(Δ_j(z_j^t; ξ_j^t))_j=1^M for

    Δ_j(z_j^t; ξ_j^t) = δ_j^t + ∇ R(z_j^t) - 1/λ∇ϕ(u^t - z_j^t).


The u-update in Algorithm <ref> combines the current model parameters z_j^t of the workers into a consensus model u^t+1. Notably, for the isotropic case and the particular choice τ=1/M, the consensus update reduces to the arithmetic mean of the copies z_j^t.

As a main difference to EASGD, for general ϕ the u-update can be regarded as a more general form of averaging. For instance, for the non-admissible choice ϕ=·_1, it is well known that minimization of F w.r.t. u yields the (componentwise) median.

A convergence proof for the stochastic method is beyond the scope of the paper. Instead we focus on the characterization of the stationary points (u̅, z̅), that the algorithm attempts to find.

Invoking the translation of stationarity reveals that the solution u̅ is stationary w.r.t. the sum of ϕ-envelopes ∑_j=1^M e_λ^f_j.
If furthermore all workers can sample from the entire training set ℐ, i.e., ℐ_j= ℐ and therefore all f_j = f̂ are equal, perfect consensus u̅ = z̅_j holds at stationary points for some finite penalty parameter 1/λ>0, which translates to a stationary point of the unregularized problem min_u f̂(u) satisfying 0∈∂f̂(u̅).
This is not trivial as the workers may follow different paths to different stationary points if not coupled tightly (due to stochasticity).
In addition, our theory shows that the ϕ-envelope is Lipschitz differentiable at u̅ and ∇f̂(u̅) = 0, implying that whenever u^ν→u̅ it holds that ∇f̂(u^ν)→ 0. The gradient norm of the ϕ-envelope may thus serve as a measure of stationarity, more robust compared to (0,∂f̂(u^ν))→ 0, see <cit.>.
All of these properties are formally stated in the following corollary. 

 
Let (u̅,z̅) be a stationary point for the splitting model (<ref>) satisfying u̅-z̅_j ∈ and conditions (<ref>)–(<ref>). If f:^m→ is prox-regular at z̅ for y̅ = 1/λ∇ϕ(Au̅ - z̅) and ϕ-prox-bounded with threshold λ_f, then for λ∈ (0, λ_f) sufficiently small, u̅ is a stationary point of ∑_j=1^M e_λ^f_j, i.e., ∑_j=1^M e_λ^f_j is Lipschitz differentiable around u̅ and

    ∑_j=1^M ∇ e_λ^f_j(u̅) = 0.

If in addition ℐ_j = ℐ for all 1≤ j ≤ M and therefore f_j = f̂ the stationarity condition reduces to

    0 = ∇ e_λ^f̂(u̅),


and it holds that,
u̅=z̅_j for all j and 0 ∈∂f̂(u̅).


The first part of the corollary follows directly from Corollary <ref> and the special structure of A,f,g and ϕ.
For the second part we invoke Theorem <ref> (i) and obtain that for some λ > 0, sufficiently small P_λ^f̂ is single-valued at u̅ and that
z̅_j = P_λ^f̂(u̅),
showing that all z̅_j's are equal.
From (<ref>) it follows that

    0 = A^⊤∇ϕ(A u̅ - z̅)  = M ∇(u̅ - P_λ^f̂(u̅)).

By Assumptions (A1), (A5) and Lemma <ref> we have ∇(w) = 0 if and only if w = 0, and therefore u̅ = z̅_j and y̅_j = 0. From (<ref>) we know 0 ∈∂f̂(z̅_j) = ∂f̂(u̅).





§ NUMERICAL EXPERIMENTS
 

In the experiments we consider the stochastic distributed training of a deep neural network with Algorithm <ref> where all workers have access to the entire training set, i.e. ℐ_j= ℐ for all j in terms of the model (<ref>).
More precisely, we report comparisons of different choices of potentials.
We manually set  as

    (w_j):=∑_l=1^L (w_jl/η),

where η is a scaling parameter (in addition to λ), and l indexes the (learnable) layers.
The different choices of  are summarized in Table <ref>.

Since both the log- and tan-potentials have bounded domains, we incorporate a line search in our algorithm to ensure that the iterates stay feasible. Note that cubic does not satisfy Assumption (A3) as its Hessian is 0 at 0. Yet we include it in our numerical evaluation.

We apply a variant of our Algorithm <ref> with constant step size, that in addition incorporates Nesterov momentum <cit.> in the SGD updates of the z_j. Note that for ϕ := 1/2·^2 this algorithm specializes to the synchronous EASGD, resp. mEASGD <cit.>. 

We report results of the training of a classifier on the MNIST dataset resorting to the standard LeNet-5 CNN architecture <cit.> given as

Conv_20, 5, 1 → ReLU → Pool_2,2 → Conv_50, 5, 1 → ReLU → Pool_2,2  → FC → Softmax


In Table <ref> we compare different potentials . To this end we perform a grid search over different learning rates σ=τ∈{0.001, 0.005}, momentum parameters κ∈{0.9, 0.99}, and different scalings of the potentials λ∈{0.1, 0.05, 0.025, 0.01, 0.005, 0.0025}, η∈{0.5, 1, 2}. We set the number of workers to 4, the batch size to 20 and the regularization parameter ν=10^-4. We run the algorithm for 30,000 iterations, so that each worker completes 10 epochs.
For each potential we report the best performances over all scalings and configurations in Table <ref>.

In terms of training loss, the tan- and log-potentials seem slightly superior, while the non-separable variants yield slightly better performance than the separable ones. The cubic potential performs worst in terms of training loss.
All potentials consistently yield 0% training error after 10 epochs (for each worker).

Notably, we observe that the cubic potential performs better, in terms of low test error, than all other potentials. This is even true for a whole range of scalings. 

In Figure <ref>, 
we show convergence plots for a representative configuration of our Algorithm <ref> for 4 and 8 workers respectively. In addition, we show a comparison to plain SGD with Nesterov momentum (mSGD). The different EASGD variants “see” 4 to 8 times more training examples than mSGD within one iteration. As a result the distributed method is stable at much higher learning rates and requires fewer iterations than mSGD to achieve low objective value.




§ CONCLUSION

In this work we have considered an anisotropic generalization of the proximal mapping and Moreau-envelope. We derived a gradient formula for the Moreau-envelope in the nonconvex setting based on prox-regularity. This allows us to equivalently (in terms of stationary points) reformulate the problem as a splitting problem which is amenable to (stochastic) alternating minimization. As an application of our theory we characterize stationary points of the penalty objective that is optimized by the elastic averaging SGD method. There, our theory can be used to obtain a robust measure of stationarity. Through numerical validations we demonstrated the relevance of our theory and algorithm on the important task of consensus training of deep neural networks.




 §.§ Acknowledgement

The work was supported by the DFG Research Grant “Splitting Methods for 3D Reconstruction and SLAM". 



plain





§ PROOFS



 §.§ Proof of Lemma <ref>

In parametric minimization problems, such as encountered in the definitions of ϕ-prox and ϕ-envelope, a sufficient condition for the continuity of the  map is given by uniform level boundedness <cit.> of the map h:(z,v) ↦ f(z)+ 1/λϕ(v-z).

We say a function h:^m ×^m → with values h(z,v) is level-bounded in z locally uniformly in v if for each v̅∈^m and α∈ there is a neighborhood V of v̅ along with a bounded set X ⊂^m such that 

    {z : h(z,v) ≤α}⊂ X
 for all v ∈ V.

In the next lemma we establish the uniform level boundedness of the map h:(z,v, ξ) ↦ f(z)+ 1/λϕ(v-z)- ⟨ξ, z ⟩ from ϕ-prox-boundedness so that <cit.> can be invoked to assert the continuity of ϕ-prox and ϕ-envelope. The Lemma is stated in a more general form including an additional linear term ⟨ξ, z ⟩, which is needed later on in the proof of Theorem <ref>, see Section <ref>.
 
Let f:^m → be proper lsc and ϕ-prox-bounded with threshold λ_f>0. Then for any λ∈ (0,λ_f), the function h:^m ×^m×^m →, defined via

    h(z,ξ, v):=f(z)+ 1/λϕ(v-z) - ⟨ξ, z ⟩,

is level-bounded in z locally uniformly in (ξ,v).


We assume the contrary: More precisely let λ∈ (0,λ_f) and assume that h is not level-bounded in z locally uniformly in v. On the one hand, this means that there exist v̅,ξ̅∈^m, α∈ and sequences v^ν→v̅, ξ^ν→ξ̅ and z^ν, z^ν→∞ such that

    f(z^ν)+ 1/λϕ(v^ν-z^ν) - ⟨ξ^ν, z^ν⟩≤α.

On the other hand, we know that

    f(z^ν)+ 1/λ'ϕ(v^ν-z^ν) ≥β,

for some λ' > λ, with λ' ∈ (0,λ_f) and ν sufficiently large. Summing the inequalities yields:

    (1/λ - 1/λ')  ϕ(v^ν-z^ν)- ⟨ξ^ν, z^ν⟩≤α -β.

Due to the super-coercivity of ϕ, for ν→∞ this yields ∞≤α -β, a contradiction.


Now we are ready to prove Lemma <ref> invoking <cit.>:

Let f:^m → be proper lsc and ϕ-prox-bounded with threshold λ_f>0. Then for any λ∈ (0,λ_f), f and f have the following properties:


  (i) f(v) ≠∅ is compact for all v ∈ f= f + ϕ, whereas f(v) =∅ for v ∉ f.

  (ii) The ϕ-envelope f is continuous relative to f.

  (iii) For any sequence v^ν→v̅ contained in f and z^ν∈ f(v^ν) we have {z^ν}_ν∈ is bounded and all its cluster points z̅ lie in f(v̅).



Obviously it holds for the domain that f= f + ϕ. In view of Lemma <ref> (with ξ=0) we assert that h:(z,v) ↦ f(z)+ 1/λϕ(v-z) is level-bounded in z locally uniformly in v. Then we may invoke <cit.> to assert that f(v) ≠∅ is compact for any v∈ f whereas f(v) =∅ for v ∉ f and in addition for any v̅∈ f and any sequence z^ν∈ f(v^ν) with v^ν→v̅ contained in f, that {z^ν}_ν∈ is bounded. Furthermore, as ϕ is continuous relative to its domain, we know for some z̅∈ f(v̅) that h(z̅, ·) is continuous relative to z̅ + ϕ containing v̅. Through <cit.> all cluster points of the sequence z^ν∈ f(v^ν) lie in f(v̅) and f(v^ν) → f(v̅) and therefore f is continuous at v̅ relative to f. Since this holds for all v̅∈ f, f is continuous relative to f.




 §.§ Proof of Theorem <ref>
 
In order to prove the desired statement we need the following intermediate result. For the sake of notational convenience recall the notion of Bregman distances as a short-hand notation for ϕ(w')- ϕ(w)-∇ϕ(w)w'-w:
 
The ϕ-induced Bregman distance B_ϕ : ^m ×^m → is defined by

    B_ϕ(w',w) =  ϕ(w')- ϕ(w)-∇ϕ(w)w'-w   if w ∈ (ϕ)
    
    +∞   otherwise.


 
Let f:^m→ proper lsc and ϕ-prox-bounded with threshold λ_f. In addition assume that f is finite and prox-regular at z̅ for y̅∈∂ f(z̅) such that the subgradient inequality (<ref>) is satisfied by constants r>0 and ϵ>0 and let v̅∈z̅+ϕ. Then the following inequality holds for all z∈^m and r_1≥max{r,λ_f^-1} sufficiently large:

    f(z)≥ f(z̅)+y̅z-z̅ - r_1B_ϕ(v̅-·)(z,z̅).



By prox-regularity of f we know there exist r>0 and ϵ>0 such that the subgradient inequality

    f(z) ≥ f(z̅)+y̅z-z̅-r/2z-z̅^2,

holds for z-z̅ < ϵ. By Assumption (A3) and <cit.> we have that 
 
   B_ϕ(v̅ - ·)(z,z̅) = ϕ(v̅-z) - ϕ(v̅-z̅) +∇ϕ(v̅-z̅)z-z̅≥μ/2z-z̅^2,

for some μ>0. Summing (<ref>) and (<ref>) yields (<ref>), which holds for any z with z-z̅<ϵ and r_1 ≥r/μ.
To show the assertion we prove that (<ref>) also holds for any z with z-z̅≥ϵ for r_1≥max{r/μ,λ_f^-1} sufficiently large. By ϕ-prox-boundedness it holds for λ∈ (0,λ_f) and v̅∈ f that +∞> f(v̅)>-∞. We have

    f(z)≥ f(v̅)-1/λϕ(v̅-z),

showing, that the desired inequality (<ref>) is implied by

    f(v̅)-1/λϕ(v̅-z) ≥ f(z̅)+y̅z-z̅ -r_1B_ϕ(v̅ - ·)(z,z̅),

which is equivalent to

    (r_1-λ^-1) B_ϕ(v̅ - ·)(z,z̅) ≥ f(z̅)- f(v̅)+y̅z-z̅+1/λϕ(v̅-z̅) -1/λ∇ϕ(v̅ - z̅)z-z̅,

and (using Cauchy-Schwarz) implied by

    (r_1-λ^-1) B_ϕ(v̅ - ·)(z,z̅)/z-z̅≥f(z̅)- f(v̅) + 1/λϕ(v̅-z̅)/z-z̅+y̅-λ^-1∇ϕ(v̅ - z̅).

Due to the super-coercivity of ϕ (<ref>) holds for z with z-z̅≥γ for some γ>0 sufficiently large. To make (<ref>) also hold for z with ϵ≤z-z̅<γ we can choose r_1>max{r, λ_f^-1} sufficiently large as B_ϕ(v̅ - ·)(z,z̅) is bounded away from zero, due to the strict convexity of ϕ(v̅ - ·). 


Throughout the proof we work with graphical localizations of set-valued mappings F, which are constructed graphically by intersecting the graph of F with some neighborhood of some reference point (z̅, y̅) ∈ F:

For F:^m ⇉^n and a pair (z̅, y̅) ∈ F, a graphical localization of F at z̅ for y̅ is a set-valued mapping T such that

    T = (U × V)∩ F

for some neighborhoods U of z̅ and V of y̅, so that

    T(z) := 
    F(z) ∩ V    if z ∈ U, 
    ∅   otherwise.



In the proof of Theorem <ref>, we shall invoke the following generalized implicit function theorem specialized from <cit.>, originally due to Robinson <cit.> for analyzing the solutions of parametric variational inequalities.
 
Consider a function G:^m×^m→^m and a set-valued map T:^m⇉^m with (v̅,z̅)∈ G and 
0∈ G(v̅,z̅)+T(z̅), and suppose that 

    _v(G;(v̅,z̅)):= lim sup_v,v'→v̅
     z→z̅
     v≠ v'G(v,z)-G(v',z)/v-v'≤γ<∞.

Let H:^m→^m be a strict estimator of G w.r.t. z uniformly in v at (v̅,z̅) with constant μ, i.e.,

    _z(e;(v̅,z̅))≤μ<∞  for  e(v,z)=G(v,z)-H(z).

Suppose that (H+T)^-1 has a Lipschitz continuous single-valued localization around 0 for z̅ with modulus κ and κμ<1. Then the solution mapping 

    S: v∈^m↦{z∈^m: 0∈ G(v,z)+T(z)}

has a Lipschitz continuous single-valued localization around v̅ for z̅ with modulus κγ/1-κμ.



We are now ready to prove the desired statement Theorem <ref>:

Let f:^m→ proper lsc and ϕ-prox-bounded with threshold λ_f. Let v̅∈z̅+ϕ. Then for any λ∈ (0,λ_f) sufficiently small and f finite and prox-regular at z̅ for y̅∈∂ f(z̅) with 

    y̅ =1/λ∇ϕ(v̅-z̅)

the following statements hold true:


  (i) f is a singled-valued, Lipschitz 
 map near v̅ such that 
z̅= f(v̅) and 

    f(v) 
       = (I + ∇ϕ^* ∘λ T)^-1(v),

where T is the f-attentive ϵ-localization of ∂ f near (z̅,y̅), i.e.
the set-valued mapping T:^m ⇉^m defined by T(z):={y ∈∂ f(z) : y -y̅< ϵ}
if z - z̅ < ϵ and f(z)<f(z̅)+ϵ, and T(z):=∅ otherwise.

  (ii) f is Lipschitz differentiable around v̅ with 

    ∇ f(v)=1/λ∇ϕ(v-z).





(i) Due to the prox-regularity at z̅ for y̅ with constants ϵ>0 and r>0 and the ϕ-prox-boundedness of f with threshold λ_f we can invoke Lemma <ref> to assert that for some λ∈ (0,min{λ_f,r^-1}) sufficiently small the following inequality holds globally for all z≠z̅:

    f(z)+ 1/λϕ(v̅-z)> f(z̅)+ 1/λϕ(v̅-z̅)+y̅z-z̅ - 1/λ∇ϕ(v̅-z̅)z-z̅.

By assumption y̅=1/λ∇ϕ(v̅-z̅) showing that

    f(z')+1/λϕ(v̅-z')>f(z̅)+1/λϕ(v̅-z̅),

for any z'≠z̅.
Therefore we can assert f(v̅) = z̅.

Due to the ϕ-prox-boundedness of f and the coercivity of ϕ we can invoke Lemma <ref> to assert that h(z,v):=f(z) + 1/λϕ(v-z) is level-bounded in z locally uniformly in v. By Lemma <ref> it follows that f(v) ≠∅ for any v∈ f. Furthermore, we assert, that for any sequence z^ν∈ f(v^ν), v^ν→v̅ we have {z^ν} is bounded and all its cluster points lie in f(v̅) = z̅, meaning z^ν→z̅ and f(v^ν) → (v̅). In addition, we have f(z^ν) → f(z̅) as f(v^ν) = f(z^ν) + 1/λϕ(v^ν - z^ν) → f(v̅)=f(z̅) + 1/λϕ(v̅-z̅).
Overall this shows, that for any v, sufficiently near v̅ we have z∈ f(v), z-z̅ < ϵ, |f(z) - f(z̅)| < ϵ and 1/λ∇ϕ(v-z) -y̅ <ϵ, due to the continuity of ∇ϕ on a neighborhood of v̅-z̅. 
From applying Fermat's rule <cit.> to f(v) we obtain

    1/λ∇ϕ(v-z) ∈∂ f(z),

and we can assert that 1/λ∇ϕ(v-z) ∈ T(z) via the arguments above. This shows that

    ∅≠ f(v) ⊂(T-1/λ∇ϕ(v-·))^-1(0),

where ∂ f is replaced by T.
It is straightforward to verify, using the fact (∇ϕ)^-1=∇ϕ^* from Lemma <ref>, that 

(T-1/λ∇ϕ(v-·))^-1(0) = (I + ∇ϕ^* ∘λT)^-1(v) .


We proceed showing that (I + ∇ϕ^* ∘λ T)^-1 is a single-valued Lipschitz map in a neighborhood of v̅. Via the inclusion above this means that f=(I + ∇ϕ^* ∘λ T)^-1 on this neighborhood.

To this end, consider the function h:^m ×^m ×^m → defined via h(v, ξ, z):=f(z)+1/λϕ(v-z)-⟨ξ,z ⟩. In view of Lemma <ref> we assert that h(v, ξ, z) is level-bounded in z locally uniformly in (v, ξ). Through <cit.> we know that for any sequence ξ^ν→ 0 with inf_z∈^m h(v̅,ξ^ν,z) < ∞ there is z^ν∈_z∈^m h(v̅, ξ^ν, z) ≠∅ with z^ν→z̅=_z∈^m h(v̅, 0, z)= f(v̅) and inf_z∈^m h(v̅, ξ^ν, z) →inf_z∈^m h(v̅, 0, z) =  f(v̅).

From applying Fermat's rule <cit.> to the minimization problem above we know that ξ^ν + 1/λ∇ϕ(v̅-z^ν) ∈∂ f(z^ν) and for ν sufficiently large we have that ξ^ν + 1/λ∇ϕ(v̅-z^ν) - y̅≤ϵ due to the continuity of ∇ϕ on a neighborhood of v̅-z̅. In addition, we have f(z^ν) → f(z̅) as inf_z∈^m h(v̅, ξ^ν, z) = f(z^ν) + 1/λϕ(v̅ - z^ν) -⟨ξ^ν, z^ν⟩→ f(v̅)=f(z̅) + 1/λϕ(v̅-z̅). Overall this means that for any ξ sufficiently near 0 we have:

    ξ∈ T(z)-1/λ∇ϕ(v̅-z),

for some z near z̅, and ∂ f is interchangeable with T.

Now pick any (z^1,y^1),(z^2,y^2) ∈ T. Then it follows from (<ref>) that

f(z^2)    ≥f(z^1)+y^1z^2-z^1 -r/2z^2-z^1^2, 

f(z^1)    ≥f(z^2)+y^2z^1-z^2 -r/2z^1-z^2^2,

and furthermore, due to Assumption (A3) and <cit.> we have that 
 
   B_ϕ(v̅ - ·)(z^2,z^1) = ϕ(v̅-z^2) - ϕ(v̅-z^1) +∇ϕ(v̅-z^1)z^2-z^1≥μ/2z^2-z^1^2. 
for some μ>0. Then we have

ϕ(v̅-z^2)    ≥ϕ(v̅-z^1)-∇ϕ(v̅-z^1)z^2-z^1 +μ/2z^2-z^1^2, 

ϕ(v̅-z^1)    ≥ϕ(v̅-z^2)-∇ϕ(v̅-z^2)z^1-z^2 +μ/2z^1-z^2^2. 

Summing the four inequalities yields for ξ^1:=y^1-1/λ∇ϕ(v̅-z^1) and ξ^2:=y^2-1/λ∇ϕ(v̅-z^2):

z^1-z^2ξ^1-ξ^2 ≥(μλ-r)z^1-z^2^2,

Consequently, the map T-1/λ∇ϕ(v̅-·) is (μλ-r)-strongly monotone. 

Define H(z):=-1/λ∇ϕ(v̅-z), G(v,z):=-1/λ∇ϕ(v-z) and e(v,z):=G(v,z)-H(z). Then the above argument implies that ξ↦(T+H)^-1(ξ) is a single-valued, (μλ-r)^-1-Lipschitz map in a neighbourhood of 0 such that 0 ∈ T(z̅)+G(v̅,z̅). Due to Assumption (A3) and <cit.> ∇ϕ is Lipschitz on a neighbourhood of v̅-z̅∈ϕ and we may conclude that _v(G;(v̅,z̅)) and _z(e;(v̅,z̅)) are finite. This implies that H is a strict estimator of G w.r.t. z uniformly in v at (v̅,z̅) ∈ G.
Invoking 
Theorem <ref>, we assert that v↦{z∈^m: 0∈ G(v,z)+T(z)} has a single-valued, Lipschitz localization around v̅ for z̅.
Since z̅= f(v̅) is single-valued at v̅ and for any v near v̅ and z ∈ f(v) it holds that z is near z̅, we may conclude that f(v)={z∈^m: 0∈ G(v,z)+T(z)} is single-valued and Lipschitz on a neighborhood of v̅.

(ii) Let (z,v), (z',v') be sufficiently close to (z̅,v̅) with z= f(v), z'= f(v'). 
Then, by Fermat's rule <cit.> it holds y∈∂ f(z) such that y=1/λ∇ϕ(v-z). Furthermore, by assumption the subgradient inequality (<ref>) holds true at (z,y) ∈ T. This means in particular that y is a proximal subgradient <cit.> of f at z.
In view of <cit.>, we assert y∈∂̂f(z). 
Thus (and using the differentiability of ϕ on ϕ) one can derive

    f(v')- f(v)     =f(z')-f(z)+1/λϕ(v'-z')-1/λϕ(v-z)
       ≥yz'-z +o(z'-z) +1/λ∇ϕ(v-z)(v'-v)-(z'-z) +o((v'-v)-(z'-z)).

Using the conclusion from (i) that v↦ z is a Lipschitz map near v̅ there is some α such that

    z'-z≤αv'-v.

This shows that o((v'-v)-(z'-z)) + o(z'-z) = o(v'-v) and we get from (<ref>) that

    f(v')- f(v)- 1/λ∇ϕ(v-z)v'-v≥ o(v'-v).

On the other hand, we have

f(v') =inf_z” f(z”) + 1/λϕ(v' - z”) ≤f(z) + 1/λϕ(v' - z).

Due to the differentiability of ϕ, we have

   ϕ(v'-z) = ϕ(v-z)+ ∇ϕ(v-z)v'-v+ o(v'-v).

This yields

f(v')-f(v)    ≤f(z) + 1/λϕ(v'-z) - f(z) - 1/λϕ(v-z) 

   =1/λ∇ϕ(v-z)v'-v + o(v'-v). 

Combining (<ref>) and (<ref>), we conclude that f is differentiable at v and 1/λ∇ϕ(v-z) = ∇ f(v). Since furthermore ∇ϕ is Lipschitz around v̅ -z̅ it holds that ∇ f is the composition of two locally Lipschitz maps and therefore Lipschitz around v̅.




