{"id":22,"date":"2018-02-26T00:43:54","date_gmt":"2018-02-26T00:43:54","guid":{"rendered":"http:\/\/wordpress.cs.vt.edu\/optml\/?p=22"},"modified":"2018-03-10T01:17:38","modified_gmt":"2018-03-10T01:17:38","slug":"22","status":"publish","type":"post","link":"https:\/\/wordpress.cs.vt.edu\/optml\/2018\/02\/26\/22\/","title":{"rendered":"Subgradient Method and Stochastic Gradient Descent"},"content":{"rendered":"

Subgradient Method<\/h2>\n

Subgradient method is the basic optimization algorithm for convex\u00a0 nondifferentiable functions. First, let’s see what a subgradient is. A subgradient is a generalization of the gradient for nondifferentiable functions. For simplicity, let’s elaborate it in a one-dimensional space. The gradient of a function at a certain point is the slope of the tangent line at that point.<\/p>\n

\"\"
Fig. 1: Gradient of a function.<\/figcaption><\/figure>\n

However, for nondifferentiable functions, there is no unique gradient at nondifferentiable points. Instead, there are subgradients \"g\" which satisfy the following condition:<\/span><\/p>\n

\"f(y)\geq for all y.<\/span><\/p>\n

All vectors \"g\"<\/span> that satisfy this condition are called subgradients of the function J at point x.<\/p>\n

\"\"
Fig. 2: Slopes of both blue and red line are the subgradients of the nondifferentiable function in the breaking point.<\/figcaption><\/figure>\n
<\/div>\n

In Fig. 2, you can see that slopes of both blue and red lines are subgradients of the function at\u00a0\"x=1\"<\/span>.<\/p>\n

Now assume that our goal is to minimize the cost function \"f(x)\" . The update algorithm is simply<\/p>\n\"x^{(k+1)}=x^{(k)}-\alpha_k\n

where \"\alpha_k\" is subgradient of\u00a0\"f(x)\" at point \"x^{(k)}\".<\/p>\n

However, the subgradient direction is not always a descent direction (can you think of an example?), so we have to keep track of the smallest objective function value that we have reached so far(i.e. iteration \"k\"):<\/p>\n\"f^k_{best}=\min\n

 <\/p>\n

The proof of convergence for this algorithm depends on three conditions:<\/p>\n