Fix a proper closed convex penalty r r r with non-singleton domain in its original Euclidean dimension. Work at L = 1 L=1 L = 1 , with q = μ r ≥ 0 q=\mu_r\ge0 q = μ r ≥ 0 , 0 < h < 2 0<h<2 0 < h < 2 , N ≥ 1 N\ge1 N ≥ 1 , b = 1 + h q b=1+hq b = 1 + h q and η = h / b \eta=h/b η = h / b . Let ϕ \phi ϕ be a quadratic or positive-threshold Huber matching function and let t 0 , … , t N t_0,\ldots,t_N t 0 , … , t N be its quadratic-penalty PGD matching trajectory. Set
D = ϕ ( t 0 ) + q 2 t 0 2 − ϕ ( t N ) − q 2 t N 2 > 0 , σ = ∣ t N − 1 − t N ∣ h , σ 2 D = K N ( h , q ) . D=\phi(t_0)+\tfrac q2t_0^2-\phi(t_N)-\tfrac q2t_N^2>0,
\qquad \sigma=\frac{|t_{N-1}-t_N|}{h},
\qquad \frac{\sigma^2}{D}=K_N(h,q). D = ϕ ( t 0 ) + 2 q t 0 2 − ϕ ( t N ) − 2 q t N 2 > 0 , σ = h ∣ t N − 1 − t N ∣ , D σ 2 = K N ( h , q ) .
Choose M ≥ max i ≤ N ∣ t i ∣ M\ge\max_{i\le N}|t_i| M ≥ max i ≤ N ∣ t i ∣ . Put p 0 = r − q 2 ∥ ⋅ ∥ 2 p_0=r-\tfrac q2\|\cdot\|^2 p 0 = r − 2 q ∥ ⋅ ∥ 2 . For a center c j c_j c j , a subgradient s j ∈ ∂ p 0 ( c j ) s_j\in\partial p_0(c_j) s j ∈ ∂ p 0 ( c j ) , a unit vector v j v_j v j and a positive scale δ j \delta_j δ j , assume the segment c j + δ j [ − M , M ] v j c_j+\delta_j[-M,M]v_j c j + δ j [ − M , M ] v j is feasible and define the finite support-gap bound
Q j ( z ) = p 0 ( c j + δ j z ) − p 0 ( c j ) − δ j ⟨ s j , z ⟩ δ j 2 , ε j = sup ∣ t ∣ ≤ M Q j ( t v j ) < ∞ . Q_j(z)=\frac{p_0(c_j+\delta_jz)-p_0(c_j)-\delta_j\langle s_j,z\rangle}{\delta_j^2},
\qquad \varepsilon_j=\sup_{|t|\le M}Q_j(tv_j)<\infty. Q j ( z ) = δ j 2 p 0 ( c j + δ j z ) − p 0 ( c j ) − δ j ⟨ s j , z ⟩ , ε j = ∣ t ∣ ≤ M sup Q j ( t v j ) < ∞.
Run the actual PGD method with unchanged penalty r r r , step h h h , initial state x 0 j = c j + δ j t 0 v j x_0^j=c_j+\delta_jt_0v_j x 0 j = c j + δ j t 0 v j , and smooth function
f j ( x ) = δ j 2 ϕ ( ⟨ v j , x − c j ⟩ δ j ) − ⟨ s j + q c j , x ⟩ . f_j(x)=\delta_j^2\phi\!\left(\frac{\langle v_j,x-c_j\rangle}{\delta_j}\right)
-\langle s_j+qc_j,x\rangle. f j ( x ) = δ j 2 ϕ ( δ j ⟨ v j , x − c j ⟩ ) − ⟨ s j + q c j , x ⟩ .
Define
e ˉ j = N 2 η ε j , ω j = 2 e ˉ j h , E j = ( 1 + q ) ( M e ˉ j + e ˉ j 2 2 ) + ε j + e ˉ j 2 2 η b 2 . \bar e_j=N\sqrt{2\eta\varepsilon_j},\qquad
\omega_j=\frac{2\bar e_j}{h},\qquad
\mathcal E_j=(1+q)\left(M\bar e_j+\frac{\bar e_j^2}{2}\right)
+\varepsilon_j+\frac{\bar e_j^2}{2\eta b^2}. e ˉ j = N 2 η ε j , ω j = h 2 e ˉ j , E j = ( 1 + q ) ( M e ˉ j + 2 e ˉ j 2 ) + ε j + 2 η b 2 e ˉ j 2 .
For F j = f j + r F_j=f_j+r F j = f j + r , the scaled observations
D j = F j ( x 0 j ) − F j ( x N j ) δ j 2 , σ j = ∥ x N − 1 j − x N j ∥ h δ j D_j=\frac{F_j(x_0^j)-F_j(x_N^j)}{\delta_j^2},
\qquad \sigma_j=\frac{\|x_{N-1}^j-x_N^j\|}{h\delta_j} D j = δ j 2 F j ( x 0 j ) − F j ( x N j ) , σ j = h δ j ∥ x N − 1 j − x N j ∥
satisfy
∣ D j − D ∣ ≤ E j , ∣ σ j − σ ∣ ≤ ω j . |D_j-D|\le\mathcal E_j,\qquad |\sigma_j-\sigma|\le\omega_j. ∣ D j − D ∣ ≤ E j , ∣ σ j − σ ∣ ≤ ω j .
If E j < D \mathcal E_j<D E j < D , then D j > 0 D_j>0 D j > 0 and
( σ − ω j ) + 2 D + E j ≤ σ j 2 D j ≤ ( σ + ω j ) 2 D − E j . \frac{(\sigma-\omega_j)_+^2}{D+\mathcal E_j}
\le\frac{\sigma_j^2}{D_j}
\le\frac{(\sigma+\omega_j)^2}{D-\mathcal E_j}. D + E j ( σ − ω j ) + 2 ≤ D j σ j 2 ≤ D − E j ( σ + ω j ) 2 .
With r , h , q , N , M r,h,q,N,M r , h , q , N , M and the scalar matching instance fixed, any such sequence with ε j → 0 \varepsilon_j\to0 ε j → 0 satisfies
σ j 2 D j − σ 2 D = O ( ε j ) . \frac{\sigma_j^2}{D_j}-\frac{\sigma^2}{D}
=O(\sqrt{\varepsilon_j}). D j σ j 2 − D σ 2 = O ( ε j ) .
These are finite error bounds for the fixed-penalty sharpness construction; they quantify the observed ratio as well as its limiting value.
Related results. Fixed-penalty exact curve · Optimal constant stepsizes