← All setups

Accelerated Douglas Rachford Convex — Smooth Convex Proximal Minimization

Descriptions may be stale. Consult the linked Lean sources.

Smooth Convex Proximal Minimization · Lean proof

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.

Proved result

2⋅⌈2⋅R2lam⋅γ⋅ε⌉+

OracleTemplate.Convergence LongTails.Setups.DouglasRachfordSmoothConvex.spec OracleTemplate.DouglasRachford.budget

Relevant previous results

  • Panagiotis Patrinos, Lorenzo Stella, Alberto Bemporad. Douglas-Rachford Splitting: Complexity Estimates and Accelerated Variants. 2014 (CDC publication; September 2014 preprint v2 used). Complexity: O(1+R(1+γL)/(γ(1−γL)ε)) exact proximal-oracle calls using fast Douglas–Rachford, counting both proximal evaluations per iteration, for objective gap ≤ε; 0<γL<1.