{ "cells": [ { "metadata": {}, "cell_type": "markdown", "source": [ "# Lab 3 (OPT-1) — Gradient Descent, Step Size Stability, Armijo Line Search\n", "\n", "**Course:** Mathematical Foundations of Machine and Deep Learning\n", "**Format:** 1.5h guided lab (Colab/Jupyter)\n", "**Allowed libs:** numpy, matplotlib (seaborn optional)\n", "\n", "**Content description (what we’ll do):**\n", "In this lab, you implement gradient descent (GD) from scratch and explore how the learning rate controls stability and convergence speed.\n", "You compare convex and non-convex objectives using iteration histories and visualizations.\n", "Next, you implement Armijo backtracking line search to adapt step sizes automatically and observe improved stability.\n" ], "id": "4a9068b7fdd7be0a" }, { "metadata": {}, "cell_type": "markdown", "source": [ "## Learning objectives (you should be able to...)\n", "1. Implement gradient descent in 1D and 2D and return a history of iterates.\n", "2. Explain (visually + intuitively) why too-large learning rates cause oscillation/divergence.\n", "3. Compare convex vs non-convex behavior: sensitivity to learning rate and initialization.\n", "4. Implement Armijo backtracking and interpret the step-size sequence η_k.\n", "\n", "## Minute-by-minute plan (10 / 80)\n", "**Intro (10 min)**\n", "- GD update rule + intuition (convex vs non-convex)\n", "- Step size stability\n", "- Why line search helps\n", "\n", "**Hands-on (80 min)**\n", "- Module 1 : 1D GD from scratch + learning rate sweep\n", "- Module 2 : Armijo backtracking line search (1D)\n", "- Module 3 : Incorporate Numerical Methods for ODEs\n", "- Module 4 : Stochastic Gradient Descent (SGD)\n" ], "id": "c2a67d19bf8051e6" }, { "metadata": { "ExecuteTime": { "end_time": "2026-03-18T10:31:29.232373Z", "start_time": "2026-03-18T10:31:29.158322Z" } }, "cell_type": "code", "source": [ "import numpy as np\n", "import matplotlib.pyplot as plt\n", "\n", "# (Optional) seaborn is allowed, but not required.\n", "# import seaborn as sns\n", "\n", "np.set_printoptions(precision=4, suppress=True)\n", "\n", "# For reproducibility in any random choices we might add later\n", "rng = np.random.default_rng(0)\n" ], "id": "86b3dbdeb38fa39c", "outputs": [], "execution_count": 5 }, { "metadata": { "ExecuteTime": { "end_time": "2026-03-18T10:31:29.383217Z", "start_time": "2026-03-18T10:31:29.354304Z" } }, "cell_type": "code", "source": [ "def plot_1d_function_with_path(f, xs, history, title=\"\", num_points=400):\n", " \"\"\"\n", " Plot f(x) over [min(xs), max(xs)] and overlay GD iterates.\n", " history: array-like of x_k\n", " \"\"\"\n", " x_grid = np.linspace(xs[0], xs[1], num_points)\n", " y_grid = np.array([f(x) for x in x_grid])\n", "\n", " plt.figure(figsize=(7, 4))\n", " plt.plot(x_grid, y_grid, linewidth=2)\n", " hk = np.array(history, dtype=float)\n", " plt.scatter(hk, [f(x) for x in hk], s=35)\n", " plt.plot(hk, [f(x) for x in hk], linestyle=\"--\", linewidth=1)\n", " plt.title(title)\n", " plt.xlabel(\"x\")\n", " plt.ylabel(\"f(x)\")\n", " plt.grid(True, alpha=0.3)\n", " plt.show()\n", "\n", "\n", "def plot_history(history, f, title_prefix=\"\"):\n", " \"\"\"\n", " Two plots:\n", " - x_k vs k\n", " - f(x_k) vs k\n", " \"\"\"\n", " hk = np.array(history, dtype=float)\n", " fk = np.array([f(x) for x in hk])\n", "\n", " plt.figure(figsize=(7, 3.5))\n", " plt.plot(hk, marker=\"o\")\n", " plt.title(f\"{title_prefix} x_k vs iteration\")\n", " plt.xlabel(\"k\")\n", " plt.ylabel(\"x_k\")\n", " plt.grid(True, alpha=0.3)\n", " plt.show()\n", "\n", " plt.figure(figsize=(7, 3.5))\n", " plt.plot(fk, marker=\"o\")\n", " plt.title(f\"{title_prefix} f(x_k) vs iteration\")\n", " plt.xlabel(\"k\")\n", " plt.ylabel(\"f(x_k)\")\n", " plt.grid(True, alpha=0.3)\n", " plt.show()\n", "\n", "\n", "def contour_with_trajectory(f, traj, xlim=(-5, 5), ylim=(-5, 5), levels=30, title=\"\"):\n", " \"\"\"\n", " Contour plot of f(x,y) with a trajectory overlay.\n", " traj: array-like shape (T, 2)\n", " \"\"\"\n", " traj = np.array(traj, dtype=float)\n", " xs = np.linspace(xlim[0], xlim[1], 300)\n", " ys = np.linspace(ylim[0], ylim[1], 300)\n", " X, Y = np.meshgrid(xs, ys)\n", " Z = f(X, Y)\n", "\n", " plt.figure(figsize=(6, 5))\n", " plt.contour(X, Y, Z, levels=levels)\n", " plt.plot(traj[:, 0], traj[:, 1], marker=\"o\", linewidth=2)\n", " plt.scatter(traj[0, 0], traj[0, 1], s=90, marker=\"s\", label=\"start\")\n", " plt.scatter(traj[-1, 0], traj[-1, 1], s=90, marker=\"*\", label=\"end\")\n", " plt.title(title)\n", " plt.xlabel(\"x\")\n", " plt.ylabel(\"y\")\n", " plt.legend()\n", " plt.grid(True, alpha=0.2)\n", " plt.show()\n" ], "id": "1d5416d676dfb7d0", "outputs": [], "execution_count": 6 }, { "metadata": {}, "cell_type": "markdown", "source": [ "## MODULE 1 — Intro: Gradient Descent\n", "\n", "**Update rule (GD):**\n", "$\n", "x_{k+1} = x_k - \\eta \\nabla f(x_k)\n", "$\n", "- If **f is convex**, GD tends to be well-behaved: step sizes mainly affect speed vs stability.\n", "- If **f is non-convex**, GD is sensitive to **initialization** and can get trapped in different basins/minima.\n", "\n", "**Why does too-large η diverge or oscillate?**\n", "Because you “overstep” the region where the local linear approximation is valid. You can bounce across the minimum and amplify errors.\n", "\n", "**Line search idea (Armijo):**\n", "Choose η adaptively so each step gives a **sufficient decrease** in f. This often stabilizes GD without manually tuning η.\n", "\n", "**2D view (conditioning):**\n", "For ill-conditioned quadratics (narrow valleys), gradients point mostly across the valley, so GD zig-zags instead of going straight to the minimum.\n" ], "id": "6ef8e028d307a4ab" }, { "metadata": { "ExecuteTime": { "end_time": "2026-03-18T10:31:30.472313Z", "start_time": "2026-03-18T10:31:29.984440Z" } }, "cell_type": "code", "source": [ "def f1(x): # convex\n", " return x**2\n", "\n", "def g1(x):\n", " return 2*x\n", "\n", "def f2(x): # non-convex\n", " return x**3 - 10*x**2\n", "\n", "def g2(x):\n", " return 3*x**2 - 20*x\n", "\n", "def f3(x): # non-convex\n", " return x**4 - 10*x**2 - 2*x\n", "\n", "def g3(x):\n", " return 4*x**3 - 20*x - 2\n", "\n", "\n", "# TODO Quick sanity check: plot functions in interval -3,3\n", "x = np.linspace(-3, 3, 400)\n", "\n", "plt.figure(figsize=(9, 5))\n", "\n", "plt.xlim(-3, 3)\n", "plt.axhline(0, color=\"black\", linewidth=1, alpha=0.5)\n", "plt.axvline(0, color=\"black\", linewidth=1, alpha=0.5)\n", "plt.grid(alpha=0.3)\n", "plt.legend()\n", "plt.title(\"Sanity check: f1, f2, f3 on [-3, 3]\")\n", "plt.show()\n" ], "id": "5eccb41e700df904", "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "/var/folders/rn/g1lqrdm16jvgs6h076hdgs7w0000gp/T/ipykernel_96846/1389391955.py:29: UserWarning: No artists with labels found to put in legend. Note that artists whose label start with an underscore are ignored when legend() is called with no argument.\n", " plt.legend()\n" ] }, { "data": { "text/plain": [ "
" ], "image/png": "iVBORw0KGgoAAAANSUhEUgAAAvEAAAHDCAYAAACtYkXaAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjgsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvwVt1zgAAAAlwSFlzAAAPYQAAD2EBqD+naQAALVlJREFUeJzt3Qu4lVWdP/DFHUkTFRAvKF5KZVRQCMJLapHYOJozY0PqCENGeaFUygumkDmKpRGmJGmizaSJ2pTO5DXU0UYMRU2dxPIW3hDQ8WA4AsKZ57f+/32ec+BwOYdzgLX5fJ5nP4f98u79vnuvvc/5vuv9rfW2qa2trU0AAEAx2m7oHQAAAJpGiAcAgMII8QAAUBghHgAACiPEAwBAYYR4AAAojBAPAACFEeIBAKAwQjwAABRGiAc2mAcffDC1adMm/9wYxL6MHj16vW7zlVdeydu9/PLLW/R5//SnP6XDDz88bbnllvn5f/WrX6XW8tZbb6Vjjz02bbPNNnlbkyZNarVt/eUvf0lf/vKXU8+ePfO2zjjjjFSKf/qnf8r7HLe99947beyeeuqpuv2N22233bahdwmoR4gH0jPPPJND2M4775w6d+6cdthhh/TZz342XXnllev93bnppptaNQRuKkaMGJHb9eKLL07/+q//mgYMGJAD8Pjx49MRRxyRtt566xzMbrjhhnXe1plnnpnuueeeNHbs2LyteP7Zs2ens88+O/Xr1y9tscUWabvttktHHnlkevzxx9dpW5dcckne51NOOSVv68QTT0z/+7//m0466aQcjOOgZfPNN099+/ZNV1xxRVq6dGnamHTr1i3v96WXXrrW7+3++++f26tLly5pr732St/+9rdzWzbXtddemw455JC07bbbpk6dOqVddtkljRw5Mh9Q1he/D2JfzzvvvGZvC2g9bWpra2tb8fmBjdwjjzySDjvssLTTTjvl4Bc9nK+++mp69NFH04svvpheeOGFVtv28uXL05IlS1LHjh1T27b/r0/hb/7mb9Kzzz67UqBYHyLUnnbaaemqq65ab9uM1xkh6rLLLkvf/OY3W+Q5I9RG4PvWt76V/vmf/3mlbUVb77rrrvkMyPXXX597iNdFfGaGDBmSfvazn9Uti9dy3XXXpb//+79PAwcOTDU1NenHP/5x3oe77747r98cn/zkJ1P79u3Tb3/727pl77zzTvrrv/7r9KlPfSr17t07f5bicx3788UvfjEfGG4M4n2O97wpn+2DDjoo9e/fP+2+++75APvJJ59MU6dOzQdlDz30UN33pilOPfXU9P7776d99tknbbXVVunll1/OwX7ZsmXp97//fdp+++0brB/7HL8jbr311nywD2wc2m/oHQA2rOipjd7Lxx57LHXt2rXB/82bN69Vtx0BJIIJLWv+/Pn554rtGb3hb775Zg7d0SP+iU98okW2F5+TFbd13HHH5R7j6BWv+NKXvlTXk9zcEB/b6tOnT4Nl0UsdB531nXzyyflzHQdkEydOzK+5RPUPVip22223fJA0c+bMfFDTVD/60Y9WWnbMMcfkA4N/+Zd/Seeee26z9xdYf5TTwCYuetv/6q/+aqUQFnr06NHgfvTafvrTn87L4zR8hKmrr756pcdFb2j0qEcAiV7YCOrR8xsBYXU18Yceemj69a9/nf785z/X1eHGc0XpwEc+8pF0+umnr7St1157LbVr1y5NmDBhjb3+UV4RvY+xP927d89lH42Vd0T9eJRmxGuM9yZ6jlf0+uuv51BaKUmI9aKHdEUffPBBDq0f//jH83YjSP/d3/1dft9XJU6QfuUrX8lnKP7t3/6tbnk8ZnWPC7GtKIMIZ511Vt17GGI/WzLMRllLPH/s7+TJk+vaLETvcf0AH6Jm/uCDD07PPfdck7dV+axEr3F8RirbWl2vduV1v/vuu2t8/pdeeil94QtfqCtbiXAc22lsH2655ZZ88LvjjjvmNv3MZz7Tqmes1uV1bcjnBFqXnnjYxEXgmzFjRi5hWdNguwjsEVaPPvroXNLw7//+7/nUfATkKEOpL0JNnHqPWuUo04mAG+UEEe7iORoT5R9RdhHB/Ac/+EFeFkEwbn/7t3+bpk2blntVI7RX/PznP88h8oQTTljtvsd+ROj83Oc+lwdGfvjhh+nhhx/OPbjRA1kRBx4RnON1RS33D3/4w1wSMmfOnBxCKwM5I+RVBsLGAcFdd92Vt7Fw4cK6wZZRnhAHM9OnT89lHXEQ8t5776X77rsvv9/Ro7qieEwcHMRr/eUvf5nryCsiLIbVBdc4QIgDsqiljt7wKDNZMUy3lChfqdSlxxiK4cOHr/Exc+fOzXXhTRU9+LGteF0Rnr/xjW/k5fHeV0RpVrz/UU4UB2cxWDg+31GKsjrRngcccEAuMfn617+e2/mnP/1p/pzHYM747NUX9exxFil6w+Pz+r3vfS9//n73u9+l1hCf1QjX8fric3P++efnz2YcIK+Lt99+O3/e4rP9ne98p8FnDChA1MQDm6577723tl27dvk2ePDg2rPPPrv2nnvuqV2yZMlK677//vsrLRs6dGjtrrvu2mDZzjvvHGNtah966KG6ZfPmzavt1KlT7Te+8Y26ZQ888EBeL35WHHnkkfnxK4p9inXvuuuuBsv33Xff2kMOOWS1r/H+++/Pj/3617++0v8tX7687t+xTseOHWtfeOGFumW///3v8/Irr7yybtlJJ51Uu91229UuWLCgwXN98YtfrN1yyy3r3qepU6fmx06cOHGV23355ZfzOpdddlnt0qVLa4cNG1a72Wab5de7onhfGntvVlT/OVflsccey+tcf/31tesqnue0005b43rxeWjTpk3tBRdc0OxtxeuPz0hjfv7zn+d9qdwGDBhQ+/TTT6/xOc8444y8/sMPP1y37L333qvdZZddanv37l27bNmyBp/Xvfbaq3bx4sV1615xxRV5+TPPPLPa7YwYMWKt2m9FM2bMaPC69thjjwbfmeaK72PlObfZZpvaH/7wh42uV3ndt9566zpvE2g5ymlgExc9qNETH72OMagtehWHDh2aZ6i54447Gqy72Wab1f07eiAXLFiQZ7mIUoS4X1+U2kTpREX0mO6xxx553eaIGuoYcHfjjTfWLYteyaeffjr94z/+42of+4tf/CL3msfMLCuqlH/U3079HvJ99903ffSjH63b78is8XxHHXVU/ne8B5VbvG/xPjzxxBN1241e56997Wtr3G70skY5x3/8x3+kO++8M08PuaLogd8QA35bQtSyH3/88Xlgbcxa0xpi8GWc5YgBmFET36FDh7Ro0aI1Pi7e7+jVjkGkFXH2Ikqa4v3+wx/+0GD9mMklSp0qKp/z5n621yS+S/G6oswr3rsoLVuX2Wkq4uxRvPbvf//7ebDz2rxXwMZDOQ2QBzhGCUkEyQjyUcYR5SxRDhNzRVcGEv7Xf/1XDsIR+qP0oL4IrzGQsCJCwYpiJoz/+Z//adY7HuULUbIQJT2x7ahbjkAfNckRflcn6sjjACDqnddkTfsdg0ajtOGaa67Jt8ZUBgTHduPAJUqP1iRq+iOYRbCKsQHVJMJhlBVFKVGUK7VWeU+MT4hbiM9uTEcZB6kxZ/7qxgLEGIxBgwY1WsJT+f/6pWYrfkbi8xGa+9mO2XXiu1f/YLn+dykOIisDgT//+c/n2XbiZxwsxlSa63LQE6LELJ4vXmO0zfq+VgLQPHrigTrRuxiBPsJPhOWYYzt6NSuBNOplo8c56tJj0F/0DkaNcoi6+Prq163Xty6z2kbNdQTd6JGM54kwE+GwfuBZV2va78rrjN7/eP2N3Q488MAmbzd68aOHNc6ExGDYahHhNOr044zJ7bffvl4vchRBPj4vsd2W1NKf7Xh/YsBz5dbYAO4V1w8333xzailx9mm//fZrcKYL2LjpiQcaVRnsGVMShhjEunjx4lxiU78n8oEHHmjRd3DFMpP6IgBWgkYMbowBeWtzQaoIKHExoujxXJve+NWJsqAYVBgDAtc0TWJsNwY7xsFQlHasTgyUjRKQOCiJMwtxNmRtevA3ZnHAEwdeMbA3ZnSJ0qv1KQa4hhVLvVYUg1+ff/75lZbHBasq/9+aopylfi/+ivO0ryi+h/Herul1Nef9iucGyqAnHjZxEcIb60GMWtkQ5SD1ex/rrxshIqadbEnRG726cBIzodx77735qq4xi0iUAqxJzC4T+33hhReuc+9pvA/xfFHvHjX5q5qjvbLdOHPR2MWjGttuHBRE72pMaRmvc8WzG2szxeTGJMYCxCw7MS95pfe4NcR73Nj7+ZOf/CT/rD/7UGNiBp+Ycz3KxOqXAEW5VEy9uOK89C0tZmyKtq/cKtuLsq3Grji7tq9rVTPdNFb2E68/rvDbnOcENoyyu3mAFglaUWMe0+jtueeeufwhrnYZ4SsCTAziCzHQMsptYkDnV7/61VymEFd5jDnjK731LRVoYttjxozJpT1RoxvbrIjBkTG4L3qqTznllDX2cFdqfyMUx3SRUR8d88NHQI4pJuP/mloDHFMMxsFP1FGPGjUqh67o5Y8a5d/85jf53yF6oWNu/HgtEZJiAGSEw1gnprCMOuTGLroTB0bx2KiFjqucNmWKyTWJA4oIh2+88UbdGZaY0rPyWaiUJsV0nNH2zb2iaxxkRXgfPHhwHr9Q/2quIT5vccBW/4qgMd4i5rlvqnjuKVOm5PcurkcQtfdx5iVKm+KzE9c2WJ24uFFMVRoHhDHFZJytiSkmY076OFhrzlVRW0K8L7E/URb0sY99LH834zMb41cibK84oDvOYsXZjsp1FxoT39tevXqlYcOG5aleow0ivEc7R9tfcMEF6+GVAS1BiIdNXMylHXXv0fMePY8RFKJcJkJmzEdduQhU9MjHnNmxLObHjoGCEaKjvCTmNW8psd0YTBuhIgbXRilD/RAfAxfjgCL2N4L52orni5lmrrvuunwRpAgsEYRifvCmin2IUB5za0egirAaZwUiFH33u99t0Gsf+xkXBor6/QiEsV7MghIXnVqVCGcRROO9iCB/2WWXpZZs7xioWRH7X7mgVGy3EuIrs59EjXZzRBuG6N2u38NdEQG5EuLXdVvxfsaBZwTxmPM9ypDi8xpjNxqbGaix9ozHn3POObk8K8YkxGclDnDqz9O/vsVnJA5uoqY/DpTjbEOUaI0bNy5/huvPkLO272EcUMV1EuIgNL7PUUIT5TtxTYH4blcu+gRs/NrEPJMbeicAmiJ6caP3cH1eJXNT8w//8A+5xz8OVlpbnFmJAB7tGVeVrVZxRuP+++/PZ2ziQKOxqyQ3VxwsxniKmF1qdQeITRHjPqL0JmalirMccbAfZwWAjYOeeKAo0SMZM+PE1V1pHdG3EyUZK5bAtJboFY4yjmoO8BWvvvpqPnsVZ20aG1OxLu9hXBW4pQJ8iAPlGEgObJz0xANFiPKL6BGMQX2PPfZYHuC5urm/YWMTF42qjEWIsR4xI9HGLEp0Hn300br7UWIUY2CAjYMQDxShMtAy6vVjSj6n9QHYlDV5yP1DDz2UB5nFQJgYCR8XXVmTOC27//7751Olu+++e/5jDNDUeuIo84hBmQI8AJu6Jof4mB4tLvM8efLktT4FHqP7Y4R9zFZwxhln5JHxMf0XAACwnstpoic+5mqOUeurElN2xSC0+gN4YvBNzFMcFzQBAAA2stlpYn7gFS9NPnTo0Nwjvypx2ef6l36Oi7LExVNifuXVXZIdAABKEX3pcV2QKFNv6oXlWj3Ez507N19Io764v3DhwnyRic0222ylx0yYMKHRy6MDAEA1Tj+74447lj9P/NixY/NlyitqamryjBRRX9+SF8dgw4gzKwsWLEjdunXbYJczp+Voz+oSUyDGFWjjarHRM0T5fEeri/asLu+++27aZZdd0hZbbNHkx7Z6iI95nOMy2PXF/biUeGO98CFmsWnsoh8R4IX46vgFtGTJktyWQnz5tGd1ickLOnfunLbccku/b6uE72h10Z7VqU0zysVbvRt08ODBafr06Q2W3XfffXk5AACQWj/ExxXcYqrIuIUocYl/z5kzp64UZvjw4XXrn3zyyemll15KZ599dpo9e3Y+TXvLLbekM888sxm7CwAANDnEP/7442m//fbLtxC16/HvcePG5ftvvvlmXaAPUecTU0xG73vMLx9XWozLpscMNQAAQGr9mvhDDz00T4ezKo1djTUe8+STTzZ97wAAYCO2bNmytHTp0kb/r0OHDqldu3atst2NcnYaAADYmNXW1uap1GOGmdWJiTxiopeWvtaREA8AAE1UCfA9evRIXbp0WSmkR8h///3307x58/L97bbbLrUkIR4AAJpYQlMJ8Ntss80q16tMpx5BPtZtydIaV9oBAIAmqNTARw/8mlTWWVXdfHMJ8QAA0AxrU+fe0rXwFUI8AAAURogHAIDCCPEAAFAYIR4AAAojxAMAQDMsX768RdZpDvPEAwBAE3Ts2DG1bds2vfHGG6l79+75fmMXe1qyZEmaP39+XjfWaUlCPAAANEGE8l122SW9+eabOcivaZ74nXbaKT+mJQnxAADQRNGzHuH8ww8/zFdwbUxcobV9+/atMle8EA8AAM0Q4bxDhw75tr4Z2AoAAIUR4gEAoDBCPAAAFEaIBwCAwgjxAABQGCEeAAAKI8QDAEBhhHgAACiMEA8AAIUR4gEAoDBCPAAAFEaIBwCAwgjxAABQGCEeAAAKI8QDAEBhhHgAACiMEA8AAIUR4gEAoDBCPAAAFEaIBwCAwgjxAABQGCEeAAAKI8QDAEBhhHgAACiMEA8AAIUR4gEAoDBCPAAAFEaIBwCAwgjxAABQGCEeAAAKI8QDAEBhhHgAACiMEA8AAIUR4gEAoDBCPAAAFEaIBwCAwgjxAABQGCEeAAAKI8QDAEBhhHgAACiMEA8AAIUR4gEAoDBCPAAAFEaIBwCAwgjxAABQGCEeAAAKI8QDAEBhhHgAACiMEA8AAIUR4gEAoDBCPAAAFEaIBwCATSHET548OfXu3Tt17tw5DRo0KM2cOXO160+aNCntscceabPNNku9evVKZ555Zvrggw+au88AALBJa3KInzZtWhozZkwaP358euKJJ1Lfvn3T0KFD07x58xpd/6abbkrnnntuXv+5555L1113XX6O8847ryX2HwAANjlNDvETJ05Mo0aNSiNHjkx9+vRJU6ZMSV26dElTp05tdP1HHnkkHXjggen444/PvfeHH354Ou6449bYew8AADSufWqCJUuWpFmzZqWxY8fWLWvbtm0aMmRImjFjRqOPOeCAA9LPfvazHNoHDhyYXnrppXTnnXemE088cZXbWbx4cb5VLFy4MP9cvnx5vlG2aMPa2lptWSW0Z/W2p9+31cF3tLpoz+qyfB1ybZNC/IIFC9KyZcvStttu22B53J89e3ajj4ke+HjcQQcdlP8wfPjhh+nkk09ebTnNhAkT0oUXXrjS8vnz5+cDCcr/wNbU1OTPQxwEUjbtWV3i93WMWYqfHTp02NC7QwvwHa0u2rO61NTUrJ8Q3xwPPvhguuSSS9KPfvSjPAj2hRdeSKeffnq66KKL0gUXXNDoY6KnP+ru6/fEx4DY7t27p65du7b2LrMefgG1adMmt6cQXz7tWV2WLl2aJy3o1q1b6tGjx4beHVqA72h10Z7VpWPHjusnxMcv9Xbt2qW33nqrwfK437Nnz0YfE0E9Sme+/OUv5/v77LNPWrRoUfrKV76SvvWtbzUa4jp16pRvK4p1hb7qECFee1YP7Vk94nupPauPNq0u2rN6rEuubdvUo4X+/fun6dOnNzgijPuDBw9u9DHvv//+SjsYBwIhyikAAIBWLqeJMpcRI0akAQMG5IGqMQd89KzHbDVh+PDhaYcddsh17eGoo47KM9rst99+deU00TsfyythHgAAaMUQP2zYsDzAdNy4cWnu3LmpX79+6e67764b7DpnzpwGPe/nn39+Pu0TP19//fVcBx0B/uKLL27qpgEAgOYObB09enS+rWoga33t27fPF3qKGwAAsO7M7wcAAIUR4gEAoDBCPAAAFEaIBwCAwgjxAABQGCEeAAAKI8QDAEBhhHgAACiMEA8AAIUR4gEAoDBCPAAAFEaIBwCAwgjxAABQGCEeAAAKI8QDAEBhhHgAACiMEA8AAIUR4gEAoDBCPAAAFEaIBwCAwgjxAABQGCEeAAAKI8QDAEBhhHgAACiMEA8AAIUR4gEAoDBCPAAAFEaIBwCAwgjxAABQGCEeAAAKI8QDAEBhhHgAACiMEA8AAIUR4gEAoDBCPAAAFEaIBwCAwgjxAABQGCEeAAAKI8QDAEBhhHgAACiMEA8AAIUR4gEAoDBCPAAAFEaIBwCAwgjxAABQGCEeAAAKI8QDAEBhhHgAACiMEA8AAIUR4gEAoDBCPAAAFEaIBwCAwgjxAABQGCEeAAAKI8QDAEBhhHgAACiMEA8AAIUR4gEAoDBCPAAAFEaIBwCAwgjxAABQGCEeAAAKI8QDAEBhhHgAACiMEA8AAIUR4gEAYFMI8ZMnT069e/dOnTt3ToMGDUozZ85c7frvvvtuOu2009J2222XOnXqlD7+8Y+nO++8s7n7DAAAm7T2TX3AtGnT0pgxY9KUKVNygJ80aVIaOnRoev7551OPHj1WWn/JkiXps5/9bP6/2267Le2www7pz3/+c+ratWtLvQYAANikNDnET5w4MY0aNSqNHDky348w/+tf/zpNnTo1nXvuuSutH8vfeeed9Mgjj6QOHTrkZdGLDwAArIcQH73qs2bNSmPHjq1b1rZt2zRkyJA0Y8aMRh9zxx13pMGDB+dymttvvz117949HX/88emcc85J7dq1a/QxixcvzreKhQsX5p/Lly/PN8oWbVhbW6stq4T2rN729Pu2OviOVhftWV2Wr0OubVKIX7BgQVq2bFnadtttGyyP+7Nnz270MS+99FK6//770wknnJDr4F944YV06qmnpqVLl6bx48c3+pgJEyakCy+8cKXl8+fPzwcSlP+BrampyUEhDgIpm/asLvF7/oMPPsg/K2dPKZvvaHXRntWlpqZm/ZXTNOfDFvXw11xzTe5579+/f3r99dfTZZddtsoQHz39UXdfvye+V69euRdfLX354jPRpk2b3J5CfPm0Z3WJDpaYtKBbt26NjnOiPL6j1UV7VpeOHTuunxAfv9QjiL/11lsNlsf9nj17NvqYmJEmenPql87stddeae7cublXvbGdjxls4raiCHxCX3WIEK89q4f2rB7xvdSe1UebVhftWT3WJdc26ZERuKMnffr06Q2OCON+1L035sADD8wlNPVrfv74xz/mcL8uRx8AALCpanL8jzKXa6+9Nv30pz9Nzz33XDrllFPSokWL6marGT58eIOBr/H/MTvN6aefnsN7zGRzySWX5IGuAADAeqiJHzZsWB5gOm7cuFwS069fv3T33XfXDXadM2dOg1MDUct+zz33pDPPPDPtu+++eZ74CPQxOw0AALCeBraOHj063xrz4IMPrrQsSm0effTR5mwKAABYgfn9AACgMEI8AAAURogHAIDCCPEAAFAYIR4AAAojxAMAQGGEeAAAKIwQDwAAhRHiAQCgMEI8AAAURogHAIDCCPEAAFAYIR4AAAojxAMAQGGEeAAAKIwQDwAAhRHiAQCgMEI8AAAURogHAIDCCPEAAFAYIR4AAAojxAMAQGGEeAAAKIwQDwAAhRHiAQCgMEI8AAAURogHAIDCCPEAAFAYIR4AAAojxAMAQGGEeAAAKIwQDwAAhRHiAQCgMEI8AAAURogHAIDCCPEAAFAYIR4AAAojxAMAQGGEeAAAKIwQDwAAhRHiAQCgMEI8AAAURogHAIDCCPEAAFAYIR4AAAojxAMAQGGEeAAAKIwQDwAAhRHiAQCgMEI8AAAURogHAIDCCPEAAFAYIR4AAAojxAMAQGGEeAAAKIwQDwAAhRHiAQCgMEI8AAAURogHAIDCCPEAAFAYIR4AAAojxAMAQGGEeAAAKIwQDwAAhRHiAQCgMEI8AABsCiF+8uTJqXfv3qlz585p0KBBaebMmWv1uJtvvjm1adMmHXPMMc3ZLAAA0JwQP23atDRmzJg0fvz49MQTT6S+ffumoUOHpnnz5q32ca+88kr65je/mQ4++GBvPAAArM8QP3HixDRq1Kg0cuTI1KdPnzRlypTUpUuXNHXq1FU+ZtmyZemEE05IF154Ydp11101GAAArIP2TVl5yZIladasWWns2LF1y9q2bZuGDBmSZsyYscrHfec730k9evRIJ510Unr44YfXuJ3FixfnW8XChQvzz+XLl+cbZYs2rK2t1ZZVQntWb3v6fVsdfEeri/asLsvXIdc2KcQvWLAg96pvu+22DZbH/dmzZzf6mN/+9rfpuuuuS0899dRab2fChAm5135F8+fPzwcSlP+BrampyUEhDgIpm/asLvF7/oMPPsg/O3TosKF3hxbgO1pdtGd1qampWT8hvqnee++9dOKJJ6Zrr702devWba0fFz39UXdfvye+V69eqXv37qlr166ttLesz19AMcA52lOIL5/2rC5Lly7NkxbE7+w4g0r5fEeri/asLh07dlw/IT5+qbdr1y699dZbDZbH/Z49e660/osvvpgHtB511FErnTZo3759ev7559Nuu+220uM6deqUbyuKwCf0VYcI8dqzemjP6hHfS+1ZfbRpddGe1WNdcm3bph4t9O/fP02fPr1BKI/7gwcPXmn9PffcMz3zzDO5lKZyO/roo9Nhhx2W/x296wAAQCuX00SZy4gRI9KAAQPSwIED06RJk9KiRYvybDVh+PDhaYcddsh17XFKdu+9927w+Eo5zIrLAQCAVgrxw4YNywNMx40bl+bOnZv69euX7r777rrBrnPmzFHyAgAArahZA1tHjx6db4158MEHV/vYG264oTmbBAAA/j/z+wEAQGGEeAAAKIwQDwAAhRHiAQCgMEI8AAAURogHAIDCCPEAAFAYIR4AAAojxAMAQGGEeAAAKIwQDwAAhRHiAQCgMEI8AAAURogHAIDCCPEAAFAYIR4AAAojxAMAQGGEeAAAKIwQDwAAhRHiAQCgMEI8AAAURogHAIDCCPEAAFAYIR4AAAojxAMAQGGEeAAAKIwQDwAAhRHiAQCgMEI8AAAURogHAIDCCPEAAFAYIR4AAAojxAMAQGGEeAAAKIwQDwAAhRHiAQCgMEI8AAAURogHAIDCCPEAAFAYIR4AAAojxAMAQGGEeAAAKIwQDwAAhRHiAQCgMEI8AAAURogHAIDCCPEAAFAYIR4AAAojxAMAQGGEeAAAKIwQDwAAhRHiAQCgMEI8AAAURogHAIDCCPEAAFAYIR4AAAojxAMAQGGEeAAAKIwQDwAAhRHiAQCgMEI8AAAURogHAIDCCPEAAFAYIR4AAAojxAMAQGGEeAAA2BRC/OTJk1Pv3r1T586d06BBg9LMmTNXue61116bDj744LTVVlvl25AhQ1a7PgAA0MIhftq0aWnMmDFp/Pjx6Yknnkh9+/ZNQ4cOTfPmzWt0/QcffDAdd9xx6YEHHkgzZsxIvXr1Socffnh6/fXXm7ppAACgOSF+4sSJadSoUWnkyJGpT58+acqUKalLly5p6tSpja5/4403plNPPTX169cv7bnnnuknP/lJWr58eZo+fboGAACAZmjflJWXLFmSZs2alcaOHVu3rG3btrlEJnrZ18b777+fli5dmrbeeutVrrN48eJ8q1i4cGH+GeE/bpQt2rC2tlZbVgntWb3t6fdtdfAdrS7as7osX4dc26QQv2DBgrRs2bK07bbbNlge92fPnr1Wz3HOOeek7bffPgf/VZkwYUK68MILV1o+f/78fCBB+R/YmpqaHBTiIJCyac/qEr/nP/jgg/yzQ4cOG3p3aAG+o9VFe1aXmpqa9RPi19Wll16abr755lwnH4NiVyV6+qPuvn5PfNTSd+/ePXXt2nU97S2t+QuoTZs2uT2F+PJpz+oSZ0rj93O3bt1Sjx49NvTu0AJ8R6uL9qwuHTt2XD8hPn6pt2vXLr311lsNlsf9nj17rvaxl19+eQ7xv/nNb9K+++672nU7deqUbyuKwCf0VYcI8dqzemjP6hHfS+1ZfbRpddGe1WNdcm3bph4t9O/fv8Gg1Mog1cGDB6/ycd/73vfSRRddlO6+++40YMCAZu8sAADQjHKaKHMZMWJEDuMDBw5MkyZNSosWLcqz1YThw4enHXbYIde1h+9+97tp3Lhx6aabbspzy8+dOzcv33zzzfMNAABo5RA/bNiwPMA0gnkE8pg6MnrYK4Nd58yZ0+DUwNVXX50Hox577LENnifmmf/2t7/d1M0DAMAmr1kDW0ePHp1vjYlBq/W98sorm/ybDAAALcn8fgAAUBghHgAACiPEAwBAYYR4AAAojBAPAACFEeIBAKAwQjwAABRGiAcAgMII8QAAUBghHgAACiPEAwBAYYR4AAAojBAPAACFEeIBAKAwQjwAABRGiAcAgMII8QAAUBghHgAACiPEAwBAYYR4AAAojBAPAACFEeIBAKAwQjwAABRGiAcAgMII8QAAUBghHgAACiPEAwBAYYR4AAAojBAPAACFEeIBAKAwQjwAABRGiAcAgMII8QAAUBghHgAACiPEAwBAYYR4AAAojBAPAACFEeIBAKAwQjwAABRGiAcAgMII8QAAUBghHgAACiPEAwBAYYR4AAAojBAPAACFEeIBAKAwQjwAABRGiAcAgMII8QAAUBghHgAACiPEAwBAYYR4AAAojBAPAACFEeIBAKAwQjwAABRGiAcAgMII8QAAUBghHgAACiPEAwBAYYR4AAAojBAPAACFEeIBAKAwQjwAABRGiAcAgMII8QAAUBghHgAANoUQP3ny5NS7d+/UuXPnNGjQoDRz5szVrn/rrbemPffcM6+/zz77pDvvvLO5+wsAAJu8Jof4adOmpTFjxqTx48enJ554IvXt2zcNHTo0zZs3r9H1H3nkkXTcccelk046KT355JPpmGOOybdnn312k3/zAQBgvYT4iRMnplGjRqWRI0emPn36pClTpqQuXbqkqVOnNrr+FVdckY444oh01llnpb322itddNFFaf/9909XXXVVs3YYAAA2de2bsvKSJUvSrFmz0tixY+uWtW3bNg0ZMiTNmDGj0cfE8ui5ry967n/1q1+tcjuLFy/Ot4qampr8849//GP66Ec/2pRdZiO0fPny9M477+RbfH4om/asLnPnzs3fzT/96U/pvffe29C7QwvwHa0u2rO6LFy4MP+sra1t3RC/YMGCtGzZsrTttts2WB73Z8+evco/CI2tH8tXZcKECenCCy9caXnU3wPQ+q6//npvM8B68vbbb6ctt9yy9UL8+hI9/fV7799999208847pzlz5jT5BbJxHnX26tUrvfrqq86sVAHtWV20Z/XRptVFe1aXmpqatNNOO6Wtt966yY9tUojv1q1bateuXXrrrbcaLI/7PXv2bPQxsbwp64dOnTrl24oiwCunqR7RltqzemjP6qI9q482rS7as7o0p7y4SY/o2LFj6t+/f5o+fXqD2qy4P3jw4EYfE8vrrx/uu+++Va4PAAC0cDlNlLmMGDEiDRgwIA0cODBNmjQpLVq0KM9WE4YPH5522GGHXNceTj/99HTIIYek73//++nII49MN998c3r88cfTNddc09RNAwAAzQnxw4YNS/Pnz0/jxo3Lg1P79euX7r777rrBq1G3Xv+UwAEHHJBuuummdP7556fzzjsvfexjH8sz0+y9995rvc0orYl56RsrsaE82rO6aM/qoj2rjzatLtqzunRah4zbprY5c9oAAAAbjEm6AQCgMEI8AAAURogHAIDCCPEAAFCY4kL80Ucfna9s1blz57TddtulE088Mb3xxhsberdohldeeSWddNJJaZdddkmbbbZZ2m233fII7SVLlng/C3XxxRfnGam6dOmSunbtuqF3h2aYPHly6t27d/4dO2jQoDRz5kzvY6EeeuihdNRRR6Xtt98+tWnTJs8MR7li6u5PfOITaYsttkg9evRIxxxzTHr++ec39G7RTFdffXXad9996y7aFddPuuuuu6o7xB922GHplltuyR/cX/ziF+nFF19Mxx577IbeLZph9uzZ+WJhP/7xj9N///d/px/84AdpypQpeSpSyhQHYF/4whfSKaecsqF3hWaYNm1avhZIHEw/8cQTqW/fvmno0KFp3rx53s8CxTVcog3jwIzy/ed//mc67bTT0qOPPpovmrl06dJ0+OGH53amPDvuuGO69NJL06xZs/L1kz796U+nz3/+8zkPbTJTTN5xxx35aHTx4sWpQ4cOG3p3WEeXXXZZPjp96aWXvJcFu+GGG9IZZ5yR3n333Q29KzRB9LxHT99VV12V78dBdq9evdLXvva1dO6553ovCxY98b/85S/z30uqQ1yzJ3rkI9x/6lOf2tC7QwvYeuutcw6KKoWq7Imv75133kk33nhjPn0vwFeHmpqa/CEG1v9ZlOgRGjJkSN2yuHBf3J8xY4bmgI3w72XwN7N8y5YtSzfffHM+qxJlNWuryBB/zjnnpI985CNpm222yVeIvf322zf0LtECXnjhhXTllVemr371q95PWM8WLFiQ/5BUrr5dEffj6tzAxiPOksXZzgMPPDDtvffeG3p3aKZnnnkmbb755vlqrSeffHI+W9anT5+yQnycpo1Tfau7Rf10xVlnnZWefPLJdO+996Z27dql4cOHp8KrgqpKU9szvP766+mII47I9dSjRo3aYPtOy7QnAK0nauOfffbZ3HtLufbYY4/01FNPpd/97nd5LNmIESPSH/7wh7Jq4qOu6+23317tOrvuumvq2LHjSstfe+21XLP5yCOPNOkUBBtPe8bsQoceemj65Cc/mWup4xQ+G4/mfD/VxJdZThOzCt12220N6qbjj0qMbXDGs2xq4qvH6NGj8/cxZh+K2d2oHlG+GDP1xYQfa6N92gh0794935p7SinEwFY2Dk1pz+iBjxmH+vfvn66//noBfiO0Lt9PyhEHYfE9nD59el2Ij9+vcT9CA7BhRZ9rDDKPkosHH3xQgK9C8Tu3KXl2owjxaytONzz22GPpoIMOSltttVWeXvKCCy7IRy164csTAT564Hfeeed0+eWX5x7fip49e27QfaN5YoxKDDiPn1FfHacJw+67757r/ti4xfSS0fM+YMCANHDgwDRp0qQ80GrkyJEbetdohr/85S95rFHFyy+/nL+TMRAyrrdCeSU0N910U+6Fj7niK2NVttxyy3ytFcoyduzY9LnPfS5/F997773ctnFwds8996z9k9QW5Omnn6497LDDarfeeuvaTp061fbu3bv25JNPrn3ttdc29K7RDNdff32UcjV6o0wjRoxotD0feOCBDb1rrKUrr7yydqeddqrt2LFj7cCBA2sfffRR712h4nvX2PcxvqeUZ1V/L+NvKeX50pe+VLvzzjvn37Xdu3ev/cxnPlN77733Nuk5NoqaeAAAYO0ZQQgAAIUR4gEAoDBCPAAAFEaIBwCAwgjxAABQGCEeAAAKI8QDAEBhhHgAACiMEA8AAIUR4gEAoDBCPAAAFEaIBwCAVJb/A418glQhoaKTAAAAAElFTkSuQmCC" }, "metadata": {}, "output_type": "display_data", "jetTransient": { "display_id": null } } ], "execution_count": 7 }, { "metadata": {}, "cell_type": "markdown", "source": [ "### MODULE 1 — Task 1: Implement GD update (1D)\n", "\n", "We implement GD that stores all iterates `x_k` in a list called `history`.\n", "This will let us plot both the path on the function and iteration curves.\n", "Keep it simple: fixed learning rate, fixed number of iterations.\n", "\n", "**What do you observe?** (after running later)\n", "- With small η: slow but stable movement.\n", "- With a good η: faster convergence.\n", "- With too-large η: oscillation or divergence.\n", "\n", "**Expected takeaway:** Step size is a stability–speed tradeoff, and the “safe” range depends on the function curvature.\n" ], "id": "4604766f3f77408" }, { "metadata": { "ExecuteTime": { "end_time": "2026-03-18T10:31:30.632865Z", "start_time": "2026-03-18T10:31:30.517059Z" } }, "cell_type": "code", "source": [ "def gradient_descent(start, lr, iters, grad):\n", " \"\"\"\n", " Fixed-step gradient descent in 1D.\n", " Returns:\n", " history: list of x_k values (length iters+1)\n", " \"\"\"\n", " x = float(start)\n", " history = [x]\n", "\n", " for k in range(iters):\n", " pass\n", " # TODO: implement the GD update x <- x - lr * grad(x)\n", " # Append new point to history\n", "\n", " return history\n", "\n", "\n", "# Quick smoke test\n", "h_test = gradient_descent(start=5.0, lr=0.1, iters=10, grad=g1)\n", "print(\"last iterate:\", h_test[-1])\n" ], "id": "188a13477b262f9e", "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "last iterate: 5.0\n" ] } ], "execution_count": 8 }, { "metadata": {}, "cell_type": "markdown", "source": [ "### MODULE 1 — Task 2: Plot f1(x)=x^2 with iterates for different learning rates\n", "\n", "We’ll try 2–3 learning rates:\n", "- **small** (slow but stable),\n", "- **good** (fast, stable),\n", "- **too large** (oscillates / diverges).\n", "\n", "Use the same start and iterations so comparisons are fair.\n", "\n", "**What do you observe?**\n", "- Do iterates move monotonically toward 0?\n", "- Does the path “bounce” across the minimum?\n", "\n", "**Expected takeaway:** On a simple convex quadratic, GD behavior is easy to see: too-large η causes bouncing and may not decrease f.\n" ], "id": "62ac0a602f383703" }, { "metadata": { "ExecuteTime": { "end_time": "2026-03-18T10:31:30.971254Z", "start_time": "2026-03-18T10:31:30.958882Z" } }, "cell_type": "code", "source": [ "start = 6.0\n", "iters = 20\n", "lrs = [0.05, 0.3, 1.1] # small / good / too large (for x^2, lr>1 typically unstable)\n", "\n", "xs_plot = (-8, 8)\n", "\n", "for lr in lrs:\n", " pass\n", " # TODO: run experiment and plot f1(x) with iterates for lr\n", "\n" ], "id": "8248fd7dfad52490", "outputs": [], "execution_count": 9 }, { "metadata": {}, "cell_type": "markdown", "source": [ "### MODULE 1 — Task 3: Plot iteration histories (x_k and f(x_k))\n", "\n", "Iteration plots are a debugging superpower:\n", "- `x_k vs k` shows oscillations or slow drift.\n", "- `f(x_k) vs k` shows whether we actually decrease the objective.\n", "\n", "**What do you observe?**\n", "- Which lr decreases f fastest?\n", "- For the unstable lr, does f explode?\n", "\n", "**Expected takeaway:** Always plot `f(x_k)` when diagnosing optimization: the path might “look okay” but f might not decrease.\n" ], "id": "68c7490acafc933b" }, { "metadata": { "ExecuteTime": { "end_time": "2026-03-18T10:31:31.379677Z", "start_time": "2026-03-18T10:31:31.367407Z" } }, "cell_type": "code", "source": [ "for lr in lrs:\n", " pass\n", " # TODO: run experiment and plot history for f1(x) with iterates for lr\n", "\n" ], "id": "2397f94229d9f2b6", "outputs": [], "execution_count": 10 }, { "metadata": {}, "cell_type": "markdown", "source": [ "### MODULE 1 — Task 4: Non-convex sensitivity (f2 or f3)\n", "\n", "Non-convex objectives can have:\n", "- multiple critical points (minima, maxima, saddles),\n", "- basins of attraction that depend on start,\n", "- more fragile stability ranges for η.\n", "\n", "We will run GD on a non-convex function and compare:\n", "1) different learning rates, and\n", "2) different starting points.\n", "\n", "**What do you observe?**\n", "- Do you end up in different places for different starts?\n", "- Does the “good” lr for convex f1 still look good here?\n", "\n", "**Expected takeaway:** Non-convex GD is more sensitive: initialization + step size can change the outcome dramatically.\n" ], "id": "35fbd5d3685fc44d" }, { "metadata": { "ExecuteTime": { "end_time": "2026-03-18T10:31:31.818914Z", "start_time": "2026-03-18T10:31:31.806331Z" } }, "cell_type": "code", "source": [ "# Choose non-convex function: f2 or f3 make two ore more experiments (you can examinate other functions)\n", "f_nc, g_nc, name = f3, g3, \"f3(x)=x^4 - 10x^2 - 2x\"\n", "#TODO Create experiments with different starts, lrs, and iters then plot_1d_function_with_path\n", "\n" ], "id": "6960fad6d11690f3", "outputs": [], "execution_count": 11 }, { "metadata": {}, "cell_type": "markdown", "source": [ "### MODULE 1 — Quick reflection (30–60 seconds)\n", "\n", "**What do you observe?**\n", "- On f1, what is the “too large” lr signature in `x_k` and `f(x_k)`?\n", "- On f3, do two different starts converge to different regions/minima?\n", "\n", "**Expected takeaway:** Always connect *plots* (trajectory + f(x_k)) to *diagnosis* (stable/unstable, slow/fast, basin dependence).\n" ], "id": "ba70c343d166f89c" }, { "metadata": {}, "cell_type": "markdown", "source": [ "## MODULE 2 — Armijo backtracking line search (20 min)\n", "\n", "Goal: instead of picking a fixed η by hand, we choose η adaptively each step.\n", "\n", "**Armijo condition (informal):** choose η so that\n", "$\n", "f(x - \\eta g) \\le f(x) - c \\eta \\|g\\|^2\n", "$\n", "In 1D, $\\|g\\|^2$ is just $g^2$.\n", "If the condition fails, shrink $η ← β η$ and try again (backtracking).\n", "\n", "We will:\n", "1) implement `armijo_backtracking(...)` (1D),\n", "2) implement GD that uses it, and\n", "3) compare fixed-lr vs Armijo on a non-convex function.\n" ], "id": "4a65bb0f88ee343a" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### MODULE 2 — Task 1: Implement Armijo backtracking (1D)\n", "\n", "We’ll implement a function that returns a step size η.\n", "Inputs:\n", "- f: objective\n", "- x: current point\n", "- g: gradient at x (a scalar in 1D)\n", "- eta0: initial trial step size\n", "- c: Armijo parameter (small, like 1e-4)\n", "- beta: shrink factor (e.g., 0.5)\n", "- max_steps: stop after some shrink attempts\n", "\n", "**What do you observe?** (later)\n", "- When gradients are large or curvature is harsh, η shrinks.\n", "- When things are smooth, η can stay near eta0.\n", "\n", "**Expected takeaway:** Line search automates stability: “if decrease is not sufficient, reduce step”.\n" ], "id": "d098972d6d33876c" }, { "metadata": { "ExecuteTime": { "end_time": "2026-03-18T10:31:33.195773Z", "start_time": "2026-03-18T10:31:33.136007Z" } }, "cell_type": "code", "source": [ "def armijo_backtracking(f, x, g, eta0=1.0, c=1e-4, beta=0.5, max_steps=25):\n", " \"\"\"\n", " 1D Armijo backtracking.\n", " Returns:\n", " eta: accepted step size\n", " steps: number of backtracking reductions performed\n", " \"\"\"\n", " eta = float(eta0)\n", " fx = float(f(x))\n", "\n", " # In 1D, directional step is x_new = x - eta * g\n", " # Armijo sufficient decrease: f(x_new) <= f(x) - c * eta * (g^2)\n", "\n", " steps = 0\n", " for j in range(max_steps):\n", " x_new = x - eta * g\n", " # TODO: implement the Armijo condition check\n", " # TODO: backtracking update eta *= beta if condition fails\n", "\n", "\n", " return eta, steps # return the final (small) eta if max_steps reached\n", "\n", "\n", "# Smoke test on f1 at x=10\n", "eta, steps = armijo_backtracking(f2, x=10.0, g=g1(10.0), eta0=1.0)\n", "print(\"eta:\", eta, \"backtracking steps:\", steps)\n" ], "id": "11d06fc8b0a65fc8", "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "eta: 1.0 backtracking steps: 0\n" ] } ], "execution_count": 12 }, { "metadata": {}, "cell_type": "markdown", "source": [ "### MODULE 2 — Task 2: GD with Armijo (track η_k)\n", "\n", "We implement GD that calls Armijo each iteration and stores:\n", "- `history`: x_k\n", "- `eta_history`: η_k\n", "\n", "This allows us to visualize:\n", "- path on f(x),\n", "- f(x_k) vs k,\n", "- η_k vs k.\n", "\n", "**What do you observe?**\n", "- Does η shrink early then stabilize?\n", "- Does Armijo prevent divergence compared to a fixed lr?\n", "\n", "**Expected takeaway:** Adaptive step sizes can make GD robust when fixed lr is hard to tune.\n" ], "id": "b7d49a7ec5dab158" }, { "metadata": { "ExecuteTime": { "end_time": "2026-03-18T10:31:34.104209Z", "start_time": "2026-03-18T10:31:34.050448Z" } }, "cell_type": "code", "source": [ "def gd_with_armijo(start, iters, f, grad, eta0=1.0, c=1e-4, beta=0.5, max_steps=25):\n", " x = float(start)\n", " history = [x]\n", " eta_history = []\n", "\n", " for k in range(iters):\n", " g = float(grad(x))\n", " # TODO: GD update using the Armijo-chosen eta add new point to history.\n", "\n", "\n", " return history, eta_history\n", "\n", "\n", "# Smoke test\n", "hA, eA = gd_with_armijo(start=6.0, iters=20, f=f1, grad=g1, eta0=1.0)\n", "print(\"last x:\", hA[-1], \"eta first/last:\", eA[0], eA[-1])\n" ], "id": "1b7abf347369289e", "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "last x: 6.0 eta first/last: 1.0 1.0\n" ] } ], "execution_count": 13 }, { "metadata": {}, "cell_type": "markdown", "source": [ "### MODULE 2 — Task 3: Compare fixed-lr GD vs Armijo on a non-convex objective\n", "\n", "We’ll use the same start point for a fair comparison.\n", "You should see that:\n", "- fixed lr might be too aggressive (blow up) or too small (slow),\n", "- Armijo adapts η_k to maintain sufficient decrease.\n", "\n", "We’ll plot:\n", "1) f(x) with iterates\n", "2) f(x_k) vs k\n", "3) η_k vs k (Armijo only)\n", "\n", "**What do you observe?**\n", "- Does Armijo reduce large steps in steep regions?\n", "- Compared to fixed lr, is the objective curve more stable?\n", "\n", "**Expected takeaway:** Armijo often “saves” you from instability with minimal manual tuning.\n" ], "id": "a5a2ed3b698e523b" }, { "metadata": { "ExecuteTime": { "end_time": "2026-03-18T10:31:35.225252Z", "start_time": "2026-03-18T10:31:35.119705Z" } }, "cell_type": "code", "source": [ "# Choose a non-convex function for comparison\n", "f_cmp, g_cmp, name = f2, g2, \"f2(x)=x^3 - 10x^2\"\n", "start = 17.1\n", "iters = 50\n", "xs_plot = (-2, 12)\n", "\n", "# Fixed learning rates to compare\n", "fixed_lrs = []\n", "\n", "# Run fixed-lr GD\n", "hist_fixed = {}\n", "\n", "\n", "# Run Armijo GD\n", "\n", "\n", "# Plot function + paths\n", "\n", "\n", "\n", "# Plot objective histories\n", "\n", "\n", "# Plot eta_k\n", "plt.figure(figsize=(7, 3.5))\n", "plt.plot(eta_hist, marker=\"o\")\n", "plt.title(f\"{name} | Armijo step sizes η_k\")\n", "plt.xlabel(\"k\")\n", "plt.ylabel(\"η_k\")\n", "plt.grid(True, alpha=0.3)\n", "plt.show()\n" ], "id": "31dc54c67c126807", "outputs": [ { "ename": "NameError", "evalue": "name 'eta_hist' is not defined", "output_type": "error", "traceback": [ "\u001B[31m---------------------------------------------------------------------------\u001B[39m", "\u001B[31mNameError\u001B[39m Traceback (most recent call last)", "\u001B[36mCell\u001B[39m\u001B[36m \u001B[39m\u001B[32mIn[14]\u001B[39m\u001B[32m, line 26\u001B[39m\n\u001B[32m 14\u001B[39m \u001B[38;5;66;03m# Run Armijo GD\u001B[39;00m\n\u001B[32m 15\u001B[39m \n\u001B[32m 16\u001B[39m \n\u001B[32m (...)\u001B[39m\u001B[32m 23\u001B[39m \n\u001B[32m 24\u001B[39m \u001B[38;5;66;03m# Plot eta_k\u001B[39;00m\n\u001B[32m 25\u001B[39m plt.figure(figsize=(\u001B[32m7\u001B[39m, \u001B[32m3.5\u001B[39m))\n\u001B[32m---> \u001B[39m\u001B[32m26\u001B[39m plt.plot(\u001B[43meta_hist\u001B[49m, marker=\u001B[33m\"\u001B[39m\u001B[33mo\u001B[39m\u001B[33m\"\u001B[39m)\n\u001B[32m 27\u001B[39m plt.title(\u001B[33mf\u001B[39m\u001B[33m\"\u001B[39m\u001B[38;5;132;01m{\u001B[39;00mname\u001B[38;5;132;01m}\u001B[39;00m\u001B[33m | Armijo step sizes η_k\u001B[39m\u001B[33m\"\u001B[39m)\n\u001B[32m 28\u001B[39m plt.xlabel(\u001B[33m\"\u001B[39m\u001B[33mk\u001B[39m\u001B[33m\"\u001B[39m)\n", "\u001B[31mNameError\u001B[39m: name 'eta_hist' is not defined" ] }, { "data": { "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data", "jetTransient": { "display_id": null } } ], "execution_count": 14 }, { "metadata": {}, "cell_type": "markdown", "source": [ "### MODULE 2 — Discussion\n", "\n", "**What do you observe?**\n", "- When does η_k shrink the most? (early iterations? near steep regions?)\n", "- Does Armijo produce smoother f(x_k) decrease than fixed lr?\n", "- Did fixed lr ever increase f(x_k) or diverge?\n", "\n", "**Expected takeaway:**\n", "Armijo is a practical “auto-tuner” that enforces sufficient decrease. It can be slower per-iteration (extra function calls),\n", "but it reduces the risk of catastrophic step sizes when the landscape changes.\n" ], "id": "65a92586e1e8b949" }, { "metadata": {}, "cell_type": "markdown", "source": [ "## MODULE 3 — Incorporate Numerical Methods for ODEs\n", "\n", "We now add **momentum-based gradient descent**:\n", "\n", "$$\n", "v_{t+1} = \\gamma v_t - \\eta \\nabla f(x_t), \\qquad x_{t+1} = x_t + v_{t+1}\n", "$$\n", "\n", "where:\n", "- $\\eta$ is the learning rate,\n", "- $\\gamma \\in [0,1)$ is the momentum coefficient,\n", "- $v_t$ stores a running velocity.\n", "We now add **momentum-based gradient descent**:\n", "\n", "$$\n", "v_{t+1} = \\gamma v_t - \\eta \\nabla f(x_t), \\qquad x_{t+1} = x_t + v_{t+1}\n", "$$\n", "\n", "where:\n", "- $\\eta$ is the learning rate,\n", "- $\\gamma \\in [0,1)$ is the momentum coefficient,\n", "- $v_t$ stores a running velocity.\n", "\n", "This is closely related to the damped second-order ODE\n", "$$\n", "\\ddot{x} + c\\dot{x} + \\nabla f(x) = 0.\n", "$$\n", "If we introduce velocity $v = \\dot{x}$, then\n", "$$\n", "\\dot{x} = v, \\qquad \\dot{v} = -c v - \\nabla f(x).\n", "$$\n", "A forward-Euler style discretization with step size $h$ gives\n", "$$\n", "v_{k+1} \\approx (1 - h c) v_k - h\\nabla f(x_k), \\qquad x_{k+1} \\approx x_k + v_{k+1},\n", "$$\n", "so the discrete momentum parameter behaves like $\\gamma \\approx 1 - h c$.\n", "\n", "**What should you observe?**\n", "- Momentum can accelerate progress in shallow regions.\n", "- It may also overshoot and oscillate near minima.\n", "- Compared with plain GD, it behaves more like a particle with inertia and damping." ], "id": "3a22a07610790ea2" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### MODULE 3 — Task 4: Incorporate Numerical Methods for ODEs\n", "\n", "\n" ], "id": "378aef97bd6d04dd" }, { "metadata": {}, "cell_type": "code", "outputs": [], "execution_count": null, "source": [ "def momentum_gradient_descent(start, lr, gamma, iters, grad):\n", " \"\"\"\n", " 1D momentum GD inspired by the Euler discretization of a damped ODE.\n", " Returns:\n", " history: x_k values\n", " velocity_history: v_k values\n", " \"\"\"\n", " x = float(start)\n", " v = 0.0\n", " history = [x]\n", " velocity_history = [v]\n", "\n", " for k in range(iters):\n", " # TODO implement momentum update\n", " pass\n", "\n", " return history, velocity_history\n", "\n", "\n", "# Quick smoke test\n", "h_mom, v_mom = momentum_gradient_descent(start=6.0, lr=0.1, gamma=0.8, iters=10, grad=g1)\n", "print(\"last x:\", h_mom[-1], \"last velocity:\", v_mom[-1])\n" ], "id": "19b5dc7e5be7cc6e" }, { "metadata": { "ExecuteTime": { "end_time": "2026-03-18T08:41:27.858462Z", "start_time": "2026-03-18T08:41:27.756440Z" } }, "cell_type": "code", "source": [ "# Compare plain GD and momentum GD on the same non-convex objective\n", "f_ode, g_ode, name_ode = f2, g2, \"f2(x)=x^3 - 10x^2\"\n", "start = 17.1\n", "iters = 35\n", "xs_plot = (-2, 18)\n", "\n", "lr_plain = 0.01\n", "lr_momentum = 0.01\n", "gamma = 0.85\n", "\n", "\n", "# Run GD and Momentum\n", "\n", "\n", "# Plot function + paths\n", "\n", "\n", "\n", "# Plot objective histories\n", "\n", "\n", "#Polot momentum velocity\n", "\n", "\n", "print(\"plain GD last x:\", hist_plain[-1], \"last f(x):\", f_ode(hist_plain[-1]))\n", "print(\"momentum GD last x:\", hist_momentum[-1], \"last f(x):\", f_ode(hist_momentum[-1]))\n" ], "id": "d7ca4f94674f5db4", "outputs": [ { "ename": "NameError", "evalue": "name 'f2' is not defined", "output_type": "error", "traceback": [ "\u001B[31m---------------------------------------------------------------------------\u001B[39m", "\u001B[31mNameError\u001B[39m Traceback (most recent call last)", "\u001B[36mCell\u001B[39m\u001B[36m \u001B[39m\u001B[32mIn[4]\u001B[39m\u001B[32m, line 2\u001B[39m\n\u001B[32m 1\u001B[39m \u001B[38;5;66;03m# Compare plain GD and momentum GD on the same non-convex objective\u001B[39;00m\n\u001B[32m----> \u001B[39m\u001B[32m2\u001B[39m f_ode, g_ode, name_ode = \u001B[43mf2\u001B[49m, g2, \u001B[33m\"\u001B[39m\u001B[33mf2(x)=x^3 - 10x^2\u001B[39m\u001B[33m\"\u001B[39m\n\u001B[32m 3\u001B[39m start = \u001B[32m17.1\u001B[39m\n\u001B[32m 4\u001B[39m iters = \u001B[32m35\u001B[39m\n", "\u001B[31mNameError\u001B[39m: name 'f2' is not defined" ] } ], "execution_count": 4 }, { "metadata": {}, "cell_type": "markdown", "source": "## MODULE 4 — Stochastic Gradient Descent (SGD)\n", "id": "m4_sgd_intro" }, { "metadata": {}, "cell_type": "code", "outputs": [], "execution_count": null, "source": "# TODO prepare full SGD experiemntes based on the previous experiments", "id": "m4_sgd_module" }, { "metadata": {}, "cell_type": "code", "outputs": [], "execution_count": null, "source": "", "id": "6f1143464d356257" }, { "metadata": {}, "cell_type": "markdown", "source": "TO BE CONTINUED IN NEXT LAB", "id": "141943c423461abf" }, { "metadata": {}, "cell_type": "code", "outputs": [], "execution_count": null, "source": "", "id": "456fb741f0735f67" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3" } }, "nbformat": 4, "nbformat_minor": 5 }