← All setups

Smooth Convex Proximal Minimization

Descriptions may be stale. Consult the linked Lean sources.

Smooth Convex Proximal Minimization

We consider minimizing f+g over a convex set C in a real Hilbert space E, where f,g:E→R. The function f is differentiable, convex, and smooth with a hidden constant L>0, while g is convex on C. For a given proximal parameter γ>0, the oracle returns exact proximal minimizers of f over E and of g over C. A given point w1∈E satisfies ∥w1−(x⋆+γ∇f(x⋆))∥≤R for some minimizer x⋆∈C and radius R>0. For ε>0, the goal is a feasible output x¯ with (f+g)(x¯)−(f+g)(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

Write F(x)=f(x)+g(x). The optimization problem is minx∈CF(x). The norm ∥⋅∥ is induced by the inner product on E. The parameters satisfy L>0,γ>0,0<λ≤1,4γL≤λ,R>0,ε>0. The algorithm receives only E, γ, λ, and w1; the remaining parameters L, R, and ε may enter only the oracle-call budget.

Our assumptions:

Assumption 1 (Convexity and smoothness). The function f is Fréchet differentiable everywhere on E. For all x,y∈E, f(x)+⟨∇f(x),y−x⟩≤f(y),f(y)≤f(x)+⟨∇f(x),y−x⟩+L2∥y−x∥2. The set C is convex, and g is convex on C: for all x,y∈C and t∈[0,1], g((1−t)x+ty)≤(1−t)g(x)+tg(y).

Assumption 2 (Exact proximal access). For every w,v∈E, the oracle returns the respective minimizers pf(w)∈argminx∈E{f(x)+∥x−w∥22γ},pg(v)∈argminy∈C{g(y)+∥y−v∥22γ}. Both minimizers exist for every query point. Either type of query may be made anywhere in E, and both types count toward a single total oracle-call budget.

Assumption 3 (Minimizer and initial distance). There exists x⋆∈C such that F(x⋆)≤F(x)for every x∈C,∥w1−(x⋆+γ∇f(x⋆))∥≤R.

After the allotted oracle calls, the output must satisfy x¯∈C,F(x¯)−F(x⋆)≤εP-a.s.

Results

On a real Hilbert space, f is differentiable and convex with the global quadratic upper bound of parameter L>0; C is convex and g is convex on C. Exact proximal minimizers of f and of g over C are available at fixed γ. A minimizer x⋆∈C exists with ∥w1−x⋆−γ∇f(x⋆)∥≤R. Assume R,ε,γ>0, 0<λ≤1, and 4γL≤λ. The constructed fast Douglas–Rachford method guarantees yN∈C and F(yN)−F(x⋆)≤ε deterministically for its last iterate.

Fast Douglas–Rachford splitting under the DouglasRachfordSmoothConvex setup.
Result Oracle complexity Novelty Limitations
(1) AcceleratedDouglasRachfordConvex (Ours) (⋆⋆) (review) O(1+Rλγε) proximal calls. At λ=1, γ=1/(4L): O(1+LR2/ε).
(2) Fast Douglas–Rachford (Patrinos et al. 2014, Theorem 5) O(1+Rλγε) proximal calls. Special case: finite-dimensional quadratic f, closed proper g+ιC; 0<γ<1/L, λ=(1−γL)/(1+γL). (1): Scope: extends the same method’s accelerated last-iterate guarantee to nonquadratic smooth convex f. Matches the rate on the quadratic overlap; no problem-class speedup established. (1) needs 4γL≤λ; excludes (2)’s optimal γ=(2−1)/L. Tuned finite-iteration constants are worse for N≤4.

Abbr: F=f+g on C; ιC is the convex indicator of C; L is the smoothness parameter; R bounds the initial distance to x⋆+γ∇f(x⋆); γ is the proximal parameter; λ is the relaxation; N is the iteration count; ε is the objective-gap tolerance. Costs count one evaluation of each proximal map per iteration.

Patrinos, Panagiotis, Lorenzo Stella, and Alberto Bemporad. 2014. “Douglas–Rachford Splitting: Complexity Estimates and Accelerated Variants.” 53rd IEEE Conference on Decision and Control, 4234–39. https://doi.org/10.1109/CDC.2014.7040049.

Lean setup