video<\/a> I posted on the section today.<\/p>\n\n\n\nThe setting was minimizing a quadratic approximation to the loss function of a neural network: $$ E(\\ww) \\approx E(\\ww_0) + (\\ww – \\ww_0)^T \\bb + {1 \\over 2} (\\ww – \\ww_0)^T \\HH (\\ww – \\ww_0).$$ <\/p>\n\n\n\n
The parameter vector $\\ww$ represents all $W$ weights in the networks. <\/p>\n\n\n\n
Bishop’s first point was that we need $O(W^2)$ independent pieces of information to determine this function, and hence to find its minimum: $W$ in $\\bb$, and $W(W+1)\/2$ for $\\HH$. So far so good.<\/p>\n\n\n\n
Now, one way we can get those pieces of information is function evaluation, evaluating the loss at a given point. Each such evaluation gives us one piece of information, so performing $O(W^2)$ evaluations gives us all the information we need to determine the loss function, and hence its minimum. <\/p>\n\n\n\n
How much does gathering this information cost? Each function evaluation costs a feedforward pass through the network, so $O(W)$ operations. The total cost of this approach is then $O(W^2)$ evaluations $\\times O(W)$ operations per evaluation, yielding $O(W^3)$ total operations.<\/p>\n\n\n\n
What if we used gradients instead? Each evaluation of $\\nabla E(\\ww)$ gives us $W$ pieces of information: the gradient of the loss relative to each of the $W$ weights. So, we should need $O(W)$ such operations to get $O(W^2)$ pieces of information. How much does this cost? <\/p>\n\n\n\n
One might think that if one function evaluation cost $O(W)$, then, since the gradient is $W$ such functions, it would cost $O(W^2)$ to compute the gradient. But, it turns out that it we use backpropagation, the gradient evaluation also costs $O(W)$ operations, the same as a single function evaluation! We’re therefore getting $W$-times more information, or the same information at $1\/W$ the cost! <\/p>\n\n\n\n
The total cost of getting $O(W^2)$ pieces of information then becomes $O(W) $ evaluations $\\times O(W) $ operations per evaluation, yielding $O(W^2)$ total operations, a factor of $W$ less than function evaluation! And in the modern setting where deep nets can have billions of parameters, a factor of $W$ difference is enormous!<\/p>\n\n\n\nMethod<\/strong><\/td>Info \/ Eval<\/strong><\/td># Evals<\/strong><\/td>Cost \/ Eval <\/strong><\/td>Total Cost<\/strong><\/td><\/tr>Function Evaluation<\/td> 1<\/td> $W^2$<\/td> $W$<\/td> $W^3$<\/td><\/tr> Gradient Evaluation<\/td> $W$<\/td> $W$<\/td> $W$<\/td> $W^2$<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\nI’m now excited to find out how backpropagation can be so efficient…<\/p>\n\n\n\n
$$\\blacksquare$$<\/p>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
When we think about learning the parameters of a neural network, we naturally think of gradient descent, because what else can we really do? It turns out that there is something else we can do, namely function evaluation, but that gradient descent, at least in a neural network setting, can be enormously more efficient. I […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[150,1],"tags":[],"class_list":["post-8710","post","type-post","status-publish","format-standard","hentry","category-bishop","category-blog"],"acf":[],"_links":{"self":[{"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/posts\/8710","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/comments?post=8710"}],"version-history":[{"count":10,"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/posts\/8710\/revisions"}],"predecessor-version":[{"id":8720,"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/posts\/8710\/revisions\/8720"}],"wp:attachment":[{"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/media?parent=8710"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/categories?post=8710"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sinatootoonian.com\/index.php\/wp-json\/wp\/v2\/tags?post=8710"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}