Non-Smooth, Non-Finite, and Non-Convex Optimization(Mark Schmidt)

《Non-Smooth, Non-Finite, and Non-Convex Optimization(Mark Schmidt)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、LooseEndsNon-SmoothNon-FiniteNon-ConvexNon-Smooth,Non-Finite,andNon-ConvexOptimizationDeepLearningSummerSchoolMarkSchmidtUniversityofBritishColumbiaAugust2015LooseEndsNon-SmoothNon-FiniteNon-ConvexComplex-StepDerivativeUsingcomplexnumbertocomputedirec

2、tionalderivatives:Theusualnite-dierenceapproximationofderivative:0f(x+h)f(x)f(x):hHasO(h2)errorfromTaylorexpansion,f(x+h)=f(x)+hf0(x)+O(h2);Buthcan'tbetoosmall:cancellationinf(x+h)f(x).LooseEndsNon-SmoothNon-FiniteNon-ConvexComplex-StepDerivative

3、Usingcomplexnumbertocomputedirectionalderivatives:Theusualnite-dierenceapproximationofderivative:0f(x+h)f(x)f(x):hHasO(h2)errorfromTaylorexpansion,f(x+h)=f(x)+hf0(x)+O(h2);Buthcan'tbetoosmall:cancellationinf(x+h)f(x).Foranalyticfunctions,thecompl

4、ex-stepderivativeuses:f(x+ih)=f(x)+ihf0(x)+O(h2);thatalsogivesfunctionandderivativetoaccuracyO(h2):2imag(f(x+ih))02real(f(x+ih))=f(x)+O(h);=f(x)+O(h);hLooseEndsNon-SmoothNon-FiniteNon-ConvexComplex-StepDerivativeUsingcomplexnumbertocomputedirectionald

5、erivatives:Theusualnite-dierenceapproximationofderivative:0f(x+h)f(x)f(x):hHasO(h2)errorfromTaylorexpansion,f(x+h)=f(x)+hf0(x)+O(h2);Buthcan'tbetoosmall:cancellationinf(x+h)f(x).Foranalyticfunctions,thecomplex-stepderivativeuses:f(x+ih)=f(x)+ihf0

6、(x)+O(h2);thatalsogivesfunctionandderivativetoaccuracyO(h2):2imag(f(x+ih))02real(f(x+ih))=f(x)+O(h);=f(x)+O(h);hbutnocancellationsousetinyh(e.g.,10150inminFunc).FirstappearanceisapparentlySquire&Trapp[1998].LooseEndsNon-SmoothNon-FiniteNon-ConvexSub

7、gradients"ofNon-ConvexfunctionsSub-gradientdoffunctionfatxhasf(y)f(x)+dT(yx);forallyandx.Sub-gradientsalwaysexistforreasonableconvexfunctions.LooseEndsNon-SmoothNon-FiniteNon-ConvexSubgradients"ofNon-ConvexfunctionsSub-gradientdoffunctionfatxhasf(y

8、)f(x)+dT(yx);forallyandx.Sub-gradientsalwaysexistforreasonableconvexfunctions.Clarkesubgradientorgeneralizedgradientdoffatxf(y)f(x)+dT(yx)kyxk2;forsome>0andallynearx[Clarke,1975].Existforreasonablenon-convexfunctions.LooseEndsNon-Smoot