Proof of Mirror Descent Lemma Lemma 1(Mirror Descent Lemma).Let D be the Bregman divergence w.r.t.: X→R and assume to be入-strongly convex with respect to a norm‖·‖.Then, uX,the following inequality holds x)-m≤（D,ux-D(u,x-》+哭Ix股-Dx41,x Proof.fi(xi)-fi(u)<(Vfi(xt),xi-u) ≤(Vf(xt),xt-xt+1）+(7f(xt),xt+1-u) term(a) term(b) In the following,we will use the stability lemma to analyze term (a),and use the Bregman proximal inequality to analyze term(b). Advanced Optimization(Fall 2023) Lecture 7.Online Mirror Descent 11
Advanced Optimization (Fall 2023) Lecture 7. Online Mirror Descent 11 Proof of Mirror Descent Lemma Proof. term (a) term (b) In the following, we will use the stability lemma to analyze term (a), and use the Bregman proximal inequality to analyze term (b)
Proof of Mirror Descent Lemma Proof. fi(xi)-fi(u)<(Vfi(xi),xt-x+1)+(Vfi(xi),x+1-u) term (a) term(b) We introduce the following stability lemma to analyze term(a): Lemma 2(Stability Lemma).Consider the following updates: x arg minxex(g;x)+D(x,c) x'=arg minxex (g',x)+D(x,c) When the regularizer:Ris a X-strongly convex function with respect to norm,we have 入x-x‖≤g-g‖* Advanced Optimization(Fall 2023) Lecture 7.Online Mirror Descent 12
Advanced Optimization (Fall 2023) Lecture 7. Online Mirror Descent 12 Proof of Mirror Descent Lemma Proof. We introduce the following stability lemma to analyze term (a): term (a) term (b)
Stability Lemma Lemma 2 (Stability Lemma).Consider the following updates: x arg minxex(g:x)+D (x,c) x'=arg minxe (g',x)+D(x,c) When the regularizer:X→Risa入-strongly convex function with respect to norm‖.，we have λx-x‖≤lg-g* Proof.For any convex function f,we have the first-order optimality condition: f(x)≤f(y)y∈X→Vf(x)T(y-x)≥0y∈X Therefore,for x'=arg minxex {(g',x)+D(x,c)},we have g+7(x')-Vb(c),u-x)≥0 holds for Vu∈光. Advanced Optimization(Fall 2023) Lecture 7.Online Mirror Descent 13
Advanced Optimization (Fall 2023) Lecture 7. Online Mirror Descent 13 Stability Lemma Proof
Stability Lemma Lemma 2(Stability Lemma).Consider the following updates: x=arg minxex(g:x)+D (x,c) x'=arg minxex (g x)+D (x,c) When the regularizer:XR is a X-strongly convex function with respect to norm,we have 入x-x‖≤g-g*. Proof. (g'+7b(x)-7(c),u-x')≥0 holds for Vu∈X. By the first-order optimality conditions of x and x', (V(x)-7(c)+g,x'-x)≥0 (Vu(x')-Vv(c)+g;x-x)0 x'-x,g-g〉≥(7b(x)-7b(x),x-x(1) Advanced Optimization(Fall 2023) Lecture 7.Online Mirror Descent 14
Advanced Optimization (Fall 2023) Lecture 7. Online Mirror Descent 14 Stability Lemma (1) Proof
Stability Lemma Lemma 2 (Stability Lemma).Consider the following updates: x arg minxex(g:x)+D (x,c) x'=arg minxe (g',x)+D(x,c) When the regularizer:X→Risa入-strongly convex function with respect to norm‖.，we have 入x-x‖≤g-g1* Proof. Besides,by the strong convexity of we have wx刻，x-x)≥0x-心x)+分1x-X12 (Tx,X-X≥(x)-x)+2Ix-X2 Summing them up,we get ((x)-V(x),x-x)≥入x-x2 (2) Advanced Optimization(Fall 2023) Lecture 7.Online Mirror Descent 15
Advanced Optimization (Fall 2023) Lecture 7. Online Mirror Descent 15 Stability Lemma (2) Proof