Numerical Computing and Optimization
Prerequisites: S1 linear algebra and statistics; basic algebra. Budget: 25-40 hours. Outcome: derive and check a gradient, explain convergence conditions, and report numerical limitations.
Diagnostic and calculus bridge
Solve x+y=2 and x-y=0, then explain a dot product. A derivative measures local rate of change. From f(x)=x*x, expansion gives f(x+h)-f(x)=2*x*h+h*h; dividing by h and taking h toward zero gives 2x. A partial derivative changes one coordinate while holding the others fixed. The gradient collects these partial derivatives.
For a full numerical or machine-learning concentration, study multivariable differentiation and optimization systematically. This bridge supplies only what the following experiment needs. Use the calculus and optimization sections of Mathematics for Machine Learning before proceeding if the derivation is unclear.
Worked example: step size changes convergence
Minimize f(w)=(w-3)^2. Its derivative is 2*(w-3). Gradient descent gives w_next = w - 2*alpha*(w-3). With error e=w-3, this becomes e_next=(1-2*alpha)*e.
Starting from w=0 with alpha=0.25 gives 0,1.5,2.25,2.625,... and geometric convergence to 3. With alpha=1, errors alternate sign without shrinking. With alpha=1.1, their magnitude grows. Convergence for this specific quadratic requires the absolute value of 1-2*alpha to be below one, equivalently 0<alpha<1.
This bound is not a universal learning-rate rule. Curvature, scaling, stochastic noise, and nonconvex objectives change the analysis. A decreasing training loss alone also says nothing about generalization.
Worked example: numerical cancellation
Mathematically, (a+b)+c = a+(b+c). Finite-precision arithmetic rounds intermediate values. With a=1e16,b=-1e16,c=1 in ordinary binary64 arithmetic, the first grouping gives 1 while the second can give 0 because b+c rounds back to b.
Therefore, a refactoring that reassociates sums can change results. Compare with an exact or higher-precision reference where practical. Tolerances need a scale and an error interpretation; setting a large tolerance until a test passes hides the problem.
Guided assignment
Implement the quadratic descent and log every iterate for alpha values 0.25,0.5,1,1.1. Stop by a declared gradient tolerance or iteration cap, recording which stopping condition occurred. An iteration cap means the method stopped trying, not that it converged.
Then fit y = a*x+b to points (0,1),(1,3),(2,5) using mean squared error. Derive both partial derivatives, compare them with central finite differences at several parameter values, and use gradient descent with a chosen stable step size. The exact fit is a=2,b=1. Rescale x by 100 and observe how the same step size behaves; normalize or adjust the algorithm and explain why.
Acceptance: the scalar traces match the derived recurrence; finite-difference and analytic gradients agree within justified tolerances; the line fit approaches the known answer; rescaling and cancellation failures are reported rather than omitted. Record dtype, step size, stopping rule, residual, and iteration count.
Independent transfer
Replace the scalar objective with 100*(w-3)^2. Derive the new stable step-size interval. Check: error multiplier is 1-200*alpha, requiring 0<alpha<0.01. Explain why copying the earlier 0.25 fails.
Use Linear Algebra and Its Applications for conditioning and least-squares background. Defend the distinction between small residual, stable computation, and a well-conditioned problem using the assessment contract.