Minimizing a Convex Quadratic: Closed Form and Iterative Optimization Algorithms

The machine learning round centered on a single question: optimizing a quadratic function, with the discussion built around optimization algorithms and the reasoning behind them. The exact function was not reported, so take the general convex quadratic $f(x) = \frac{1}{2} x^\top A x - b^\top x$, where $x \in \mathbb{R}^d$ and $A$ is symmetric positive definite, which includes the one-variable case $f(x) = \frac{1}{2} a x^2 - b x$ with $a > 0$. Find the minimizer, first in closed form and then with iterative optimization algorithms. For each algorithm you propose, give its update rule, explain how to choose its step size, and say whether it converges on this function, how fast, and what one iteration costs. ```hint Start from the gradient Write the gradient and the equation the minimizer must satisfy, then ask what solving that equation directly costs when $d$ is large. ``` ```hint Look along the eigenvectors For an iterative method, write how the error changes in one step, then follow each eigenvector of $A$ separately. ``` ### Constraints and Clarifications - Not reported: the exact function, its dimension, and whether $x$ is constrained. The statement above is the standard unconstrained form; ask before assuming otherwise. ### Clarifying Questions - Is $x$ a scalar or a vector, and roughly how large is $d$? - Is $A$ known to be positive definite, or could the function be flat or unbounded below in some direction? - Can we form and factor $A$, or can we only multiply vectors by it, or only observe noisy gradients? - Are there constraints on $x$, such as bounds or a maximum norm? ### What a Strong Answer Covers - The gradient, the optimality condition and the closed-form minimizer, and what positive definiteness guarantees - Gradient descent on this function: the error recursion, which step sizes converge, the best fixed step, and the rate in terms of the eigenvalues of $A$ - At least one faster method, with its cost per iteration and why it helps on this function - What changes when $A$ is singular, indefinite or badly conditioned, or when only noisy gradients are available - The connection to machine learning: least-squares regression as a quadratic, and why conditioning matters in training ### Follow-up Questions - Gradient descent zig-zags down a long, narrow valley. Explain why, and what you would change. - Only stochastic mini-batch gradients are available. How do the step-size choice and the convergence behavior change? - Why does Newton's method reach the minimizer of this function in one step, and why is it rarely applied directly to large neural networks? - Add the constraint $\lVert x \rVert \le r$. How do you find the minimizer now?