31:T4fb,# First-Order Stochastic Optimization This visualization is a brief summary of stochastic gradient descent algorithms. Here, we consider to optimize an objective function ${tex `f: \mathcal X \rightarrow \mathbb{R}_+`} ${tex.block ` \mathbf x^\star \leftarrow \argmin_{\mathbf x \in \mathcal X} f(\mathbf x), `} where we assume that ${tex `f`} is differentiable; it is also nonconvex and has no analytical solution. This kind of functions is often solved using an iterative procedure that utilizes the gradients of ${tex `f`}, gradually finding better a solution. More specially, the procedure is the following form ${tex.block ` \mathbf x_{t+1} \leftarrow \mathbf x_{t} - \gamma \phi(\nabla f(\mathbf x_t)), ` } where ${tex `\gamma \in \reals_+`} is a learning rate and ${tex `\phi(\cdot)`} is a function producing an update for improving the solution.

**Acknowledgement**: The content and implementation details of this work is based on [Goodfellow et al. (2016)'s Chapter 8](https://www.deeplearningbook.org) and [Ruder (2016)](https://ruder.io/optimizing-gradient-descent/). The visualization is primarily inspired by [Louis (2016)](http://louistiao.me/notes/visualizing-and-animating-optimization-algorithms-with-matplotlib/).

32:T42c,class Adam { constructor(lr, init, func) { this.lr = lr this.cache = [init] this.current = init this.func = func this.r = mathjs.matrix([0, 0]) this.s = mathjs.matrix([0, 0]) this.rho1 = 0.9 this.rho2 = 0.999 } update(currentEpoch) { const grad = mathjs.matrix( clipGradient(this.func.grad(this.current)) ) this.s = mathjs.add( mathjs.multiply(this.rho1, this.s), mathjs.multiply(1-this.rho1, grad) ) this.r = mathjs.add( mathjs.multiply(this.rho2, this.r), mathjs.multiply(1-this.rho2, mathjs.dotPow(grad, 2)) ) const sh = mathjs.divide( this.s, 1 - Math.pow(this.rho1, currentEpoch+1) ) const rh = mathjs.divide( this.r, 1 - Math.pow(this.rho2, currentEpoch+1) ) const update = mathjs.dotDivide( sh, mathjs.add(mathjs.dotPow(rh, -0.5), 1e-10), ) this.current = mathjs.subtract( this.current, mathjs.multiply(this.lr, update) )._data this.cache.push(this.current) } }33:Te8e,chart = { const svg = d3.create("svg") .attr("viewBox", [0, 0, width + 28, height]) .style("display", "block") .style("margin", "0 -90px") .style("padding-right", "200px") .style("width", width + 200) .style("height", height) const optimizers = [ new SGD(lr, start_at, func), new SGDwithMomentum(lr, start_at, func), new SGDwithNesterovMomentum(lr, start_at, func), new AdaGrad(lr, start_at, func), new RMSProp(lr, start_at, func), new Adam(lr, start_at, func), ] svg.append("g") .attr("fill", "none") .attr("stroke", "#000") .attr("stroke-opacity", 0.1) .selectAll("path") .data(contours) .join("path") .attr("fill", d => color(d.value)) .attr("d", d3.geoPath()); const localOptimalSymbol = d3.symbol().type(d3.symbolStar).size(20) svg.append("g") .selectAll("path") .data(func.optimal) .join("path") .attr("d", d => { if(d.global) { return d3.symbol().type(d3.symbolStar).size(20)() } else { return d3.symbol().type(d3.symbolCross).size(20)() } }) .attr("opacity", 0.3) .attr("transform", d => `translate(${x(d.p[0])},${y(d.p[1])})`) const paths = svg.append("g") const makers = optimizers.map( (o, i) => { return svg.append("circle") .attr("cx", x(start_at[0])) .attr("cy", y(start_at[1])) .attr("r", 3) .attr("fill", legendColors[i]) }) // legend const textLegend = svg.selectAll("labels") .data(optimizers) .enter() .append("text") .attr("x", width + 55) .attr("y", (d, i) => 50 + i*20) // 100 is where the first dot appears. 25 is the distance between dots .style("alignment-baseline", "middle") .style("font-size", "12px") .text(d => d.constructor.name) textLegend.on("mouseover", function(evt, d) { const e = textLegend.nodes(); const i = e.indexOf(this); makers.forEach( (m, j) => { if (i != j) { makers[j].style("opacity", 0.1) svg.selectAll(`.trajectory.${optimizers[j].constructor.name}`).style("visibility", "hidden") } }) }) textLegend.on("mouseout", function(evt, d) { makers.forEach(m => m.style("opacity", 1)) svg.selectAll(`.trajectory`).style("visibility", "visible") }) svg.selectAll("dots") .data(optimizers) .enter() .append("circle") .attr("cx", width + 45) .attr("cy", (d,i) => 50 + i*20) // 100 is where the first dot appears. 25 is the distance between dots .attr("r", 3) .style("fill", (d, i) => legendColors[i]) svg.append("g").call(xAxis) svg.append("g").call(yAxis) return { svg: svg, node: svg.node(), optimizers: optimizers, tick: (tick) => { optimizers.forEach((opt, i) => { const condition = opt.cache[tick+1] === undefined if (condition) { opt.update(tick) paths.append("line")//making a line for legend .attr("class", `trajectory ${opt.constructor.name}`) .attr("stroke", legendColors[i]) .attr("x1", x(opt.cache[tick][0])) .attr("x2", x(opt.current[0])) .attr("y1", y(opt.cache[tick][1])) .attr("y2", y(opt.current[1])) .attr("opacity", opacityScale(tick)) } let current = opt.cache[tick] makers[i] .attr("cx", x(current[0])) .attr("cy", y(current[1])) }) if(tick == epochs-1) { textLegend.text((d, i) => `${d.constructor.name} at ${d.func.forward(d.current).toFixed(4)}`) } } } }34:[] 2f:{"title":"First-Order Stochastic Optimization","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":518,"value":"viewof functionName = Inputs.select([\n \"Ellipsoid\",\n \"Himmelblau\",\n \"Beale\",\n], {label: \"Objective Function\", value: \"Himmelblau\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1224,"value":"md`\n${tex.block `f(x_1, x_2) = ${func.describe()}`}\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":250,"value":"legend({color, title: \"Value\", tickFormat: \",\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":407,"value":"chart.node","pinned":false,"hidden":false,"mode":"ojs"},{"id":1420,"value":"md`\n

\nWe display the global minimum of the function using ★; and if local minimas also exists, we display them using ✚. ${ shouldClipGradient ? `We also clip each gradient coordiate to have magnitude as most ${gradientClippingThreshold}.`: `` }\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":945,"value":"viewof restart = Inputs.button(\"Restart\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":387,"value":"viewof epoch = { \n func;\n chart;\n lr;\n start_at;\n return Scrubber(Array.from({length: epochs}, (_, i) => i), {loop: false})\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":389,"value":"viewof epochs = slider({\n min: 10, \n max: 300, \n step: 10, \n value: 200, \n description: \"Numbef of Epochs\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1349,"value":"viewof lr = slider({\n min: 0.0001, \n max: 0.01, \n step: 0.00001, \n value: 0.001, \n // format: \".5\",\n precision: 4,\n description: md`Learning rate ${tex `\\gamma`}`\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1525,"value":"viewof shouldClipGradient = Inputs.toggle({\n label: md`Clip Gradient`,\n value: true\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1410,"value":"❧","pinned":false,"hidden":false,"mode":"md"},{"id":1282,"value":"# Appendix","pinned":false,"hidden":false,"mode":"md"},{"id":383,"value":"{\n // this cell control each epoch's elapsed.\n chart.tick(epoch)\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1305,"value":"## Optimization Variables and Functions","pinned":false,"hidden":false,"mode":"md"},{"id":346,"value":"start_at = { \n restart;\n return [\n sampleInRange(func.boundary.x),\n sampleInRange(func.boundary.y),\n ]\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":788,"value":"lrScheduler = (l, epoch) => {\n if (epoch < epochs * 0.5) {\n return l \n } else {\n return l * 0.1**Math.floor((epoch - epochs * 0.5) / 10)\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":938,"value":"sampleInRange = (r) => {\n return Math.random() * [r[1] - r[0]] + r[0]\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1513,"value":"gradientClippingThreshold = func.boundary.x[1] / 2","pinned":false,"hidden":false,"mode":"ojs"},{"id":1468,"value":"clipGradient = (grad) => {\n if(!shouldClipGradient) {\n return grad\n }\n const threshold = gradientClippingThreshold\n return grad.map(g => Math.abs(g) > threshold ? threshold * g / Math.abs(g) : g)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1319,"value":"### Optimizers","pinned":false,"hidden":false,"mode":"md"},{"id":558,"value":"class SGD {\n constructor(lr, init, func) {\n this.lr = lr \n this.cache = [init]\n this.current = init \n this.func = func\n }\n update(currentEpoch) {\n const grad = clipGradient(this.func.grad(this.current))\n this.current = [\n this.current[0] - this.lr * grad[0],\n this.current[1] - this.lr * grad[1],\n ]\n \n this.cache.push(this.current)\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":672,"value":"class SGDwithMomentum {\n constructor(lr, init, func) {\n this.lr = lr \n this.cache = [init]\n this.current = init\n this.func = func\n this.velocity = mathjs.matrix([0, 0])\n\n this.alpha = 0.5\n }\n update(currentEpoch) {\n const grad = mathjs.matrix(clipGradient(this.func.grad(this.current)))\n\n this.velocity = mathjs.subtract(\n mathjs.multiply(this.velocity, this.alpha),\n mathjs.multiply(grad, this.lr)\n )\n\n this.current = mathjs.add(this.velocity, this.current)._data\n \n this.cache.push(this.current)\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":755,"value":"class SGDwithNesterovMomentum {\n constructor(lr, init, func) {\n this.lr = lr \n this.cache = [init]\n this.current = init\n this.func = func\n this.velocity = mathjs.matrix([0, 0])\n\n this.alpha = 0.5\n }\n update(currentEpoch) {\n \n const grad = mathjs.matrix(clipGradient(\n this.func.grad(\n mathjs.add(\n mathjs.multiply(this.velocity, this.alpha),\n this.current\n )._data\n )\n ))\n\n this.velocity = mathjs.subtract(\n mathjs.multiply(this.velocity, this.alpha),\n mathjs.multiply(grad, this.lr)\n )\n\n this.current = mathjs.add(this.velocity, this.current)._data\n \n this.cache.push(this.current)\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":841,"value":"class AdaGrad {\n constructor(lr, init, func) {\n this.lr = lr \n this.cache = [init]\n this.current = init\n this.func = func\n this.r = mathjs.matrix([0, 0])\n\n }\n update(currentEpoch) {\n \n const grad = mathjs.matrix(clipGradient(this.func.grad(this.current)))\n\n this.r = mathjs.add(this.r, mathjs.dotPow(grad, 2))\n\n const update = mathjs.dotDivide(\n grad,\n mathjs.add(mathjs.dotPow(this.r, -0.5), 1e-10),\n )\n\n this.current = mathjs.subtract(\n this.current, mathjs.multiply(this.lr, update)\n )._data\n\n this.cache.push(this.current)\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":885,"value":"class RMSProp {\n constructor(lr, init, func) {\n this.lr = lr \n this.cache = [init]\n this.current = init\n this.func = func\n this.r = mathjs.matrix([0, 0])\n \n this.rho = 0.9\n\n }\n update(currentEpoch) {\n \n const grad = mathjs.matrix(clipGradient(this.func.grad(this.current)))\n\n this.r = mathjs.add(\n mathjs.multiply(this.rho, this.r), \n mathjs.multiply(1-this.rho, mathjs.dotPow(grad, 2))\n )\n\n const update = mathjs.dotDivide(\n grad,\n mathjs.add(mathjs.dotPow(this.r, -0.5), 1e-10),\n )\n\n this.current = mathjs.subtract(\n this.current, mathjs.multiply(this.lr, update)\n )._data\n\n this.cache.push(this.current)\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":893,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":1337,"value":"### Objective Functions","pinned":false,"hidden":false,"mode":"md"},{"id":523,"value":"func = {\n if(functionName == \"Beale\") {\n return new Beale()\n } else if(functionName == \"Ellipsoid\") {\n return new Ellipsoid() \n } else if(functionName == \"Himmelblau\") {\n return new Himmelblau() \n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":581,"value":"class Ellipsoid{\n constructor() {\n this.optimal = [\n { global: true, p: [0, 0]}\n ]\n this.boundary = {\n x: [-5, 5],\n y: [-5, 5]\n }\n }\n forward(p) {\n const x = p[0]\n const y = p[1]\n return x** 2 + 10 *y ** 2\n }\n grad(p) {\n const x = p[0]\n const y = p[1]\n return [\n 2 * x,\n 20 * y\n ]\n } \n describe() {\n return `x_1^2 + 10 x_2^2`\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":508,"value":"class Beale {\n constructor() {\n this.optimal = [\n {global: true, p: [3, 0.5]}\n ]\n this.boundary = {\n x: [-5, 5],\n y: [-5, 5]\n }\n }\n forward(p) {\n const x = p[0]\n const y = p[1]\n return (1.5 - x + x*y)** 2 + (2.25 - x + x*y**2)**2 + (2.625 - x + x* y**3)**2\n }\n grad(p) {\n const x = p[0]\n const y = p[1]\n const firstTerm = (1.5 - x + x*y)\n const secondTerm = (2.25 - x + x*y**2)\n const thirdTerm = (2.625 - x + x*y**3)\n return [\n 2 * firstTerm * (-1 + y) + 2*secondTerm * (-1 + y ** 2) + 2*thirdTerm*(-1 + y**3),\n 2 * firstTerm * x + 2*secondTerm* (x*(2*y)) + 2*thirdTerm*(3*x*y**2)\n ]\n }\n describe() {\n return `(1.5 - x_1 + x_1 x_2)^2 + (2.25 - x_1 + x_1 x_2^2)^2 + (2.265 - x_1 + x_1 x_2^3)^2`\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":921,"value":"class Himmelblau {\n // ref: https://en.wikipedia.org/wiki/Himmelblau%27s_function\n constructor() {\n this.optimal = [\n { global: false, p: [3.0, 2.0]}, \n { global: false, p: [-2.805118, 3.131312]}, \n { global: false, p: [-3.779310, -3.283186]},\n { global: false, p: [3.584428, -1.848126]},\n { global: true, p: [-0.270848, -0.923039]},\n ]\n \n this.boundary = {\n x: [-6, 6],\n y: [-6, 6]\n }\n }\n forward(p) {\n const x = p[0]\n const y = p[1]\n\n return (x**2 + y - 11)**2 + (x + y**2 - 7)**2\n }\n grad(p) {\n const x = p[0]\n const y = p[1]\n\n const firstTerm = (x**2 + y - 11)\n const secondTerm = (x + y**2 - 7)\n\n return [\n 2*firstTerm*(2*x) + 2*secondTerm,\n 2*firstTerm + 2*secondTerm*(2*y)\n ]\n }\n describe() {\n return `(x_1^2 + x_2 - 11)^2 + (x_1+x_2-7)^2`\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1287,"value":"## Plotting Variables and Functions","pinned":false,"hidden":false,"mode":"md"},{"id":36,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":175,"value":"color = d3.scaleSequential(d3.extent(contours, (d) => d.value), d3.interpolatePuBuGn)","pinned":true,"hidden":false,"mode":"ojs"},{"id":12,"value":"grid = {\n const q = 4; // The level of detail, e.g., sample every 4 pixels in x and y.\n const x0 = -q / 2, x1 = width + 28 + q;\n const y0 = -q / 2, y1 = height + q;\n const n = Math.ceil((x1 - x0) / q);\n const m = Math.ceil((y1 - y0) / q);\n const grid = new Array(n * m);\n for (let j = 0; j < m; ++j) {\n for (let i = 0; i < n; ++i) {\n grid[j * n + i] = func.forward([x.invert(i * q + x0), y.invert(j * q + y0)]);\n }\n }\n grid.x = -q;\n grid.y = -q;\n grid.k = q;\n grid.n = n;\n grid.m = m;\n return grid;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":152,"value":"// Converts from grid coordinates (indexes) to screen coordinates (pixels).\ntransform = ({type, value, coordinates}) => {\n return {type, value, coordinates: coordinates.map(rings => {\n return rings.map(points => {\n return points.map(([x, y]) => ([\n grid.x + grid.k * x,\n grid.y + grid.k * y\n ]));\n });\n })};\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":31,"value":"contours = d3.contours()\n .size([grid.n, grid.m])\n .thresholds(100)(grid)\n .map(transform)","pinned":true,"hidden":false,"mode":"ojs"},{"id":18,"value":"x = d3.scaleLinear(func.boundary.x, [0, width + 28])","pinned":true,"hidden":false,"mode":"ojs"},{"id":729,"value":"opacityScale = d3.scaleLinear([0, epochs*0.8], [0.1, 1])","pinned":true,"hidden":false,"mode":"ojs"},{"id":20,"value":"y = d3.scaleLinear(func.boundary.y, [height, 0])","pinned":true,"hidden":false,"mode":"ojs"},{"id":54,"value":"xAxis = g => g\n .attr(\"transform\", `translate(0,${height})`)\n .call(d3.axisTop(x).ticks(width / height * 10))\n .call(g => g.select(\".domain\").remove())\n .call(g => g.selectAll(\".tick\").filter(d => x.domain().includes(d)).remove())","pinned":true,"hidden":false,"mode":"ojs"},{"id":1011,"value":"legendColors = d3.schemeCategory10","pinned":true,"hidden":false,"mode":"ojs"},{"id":49,"value":"yAxis = g => g\n .attr(\"transform\", \"translate(-1,0)\")\n .call(d3.axisRight(y))\n .call(g => g.select(\".domain\").remove())\n .call(g => g.selectAll(\".tick\").filter(d => y.domain().includes(d)).remove())","pinned":true,"hidden":false,"mode":"ojs"},{"id":9,"value":"height = 400","pinned":true,"hidden":false,"mode":"ojs"},{"id":268,"value":"width = 400","pinned":true,"hidden":false,"mode":"ojs"},{"id":1309,"value":"## Dependencies","pinned":false,"hidden":false,"mode":"md"},{"id":15,"value":"d3 = require(\"d3@6\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":385,"value":"import {Scrubber} from \"@mbostock/scrubber\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":248,"value":"import {legend} from \"@d3/color-legend\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":673,"value":"mathjs = require('https://unpkg.com/mathjs@6.6.0/dist/math.min.js')","pinned":true,"hidden":false,"mode":"ojs"},{"id":1351,"value":"import {slider,checkbox} from \"@jashkenas/inputs\"","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}