Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability / 6 / c / iv

At $d=10^6$, gradient descent remains a plausible large-scale choice; dense Newton method and full-memory BFGS are generally impractical. A dense $d\times d$ double-precision matrix alone contains $10^{12}$ entries, about $8$ TB. Dense factorization also has order $10^{18}$ arithmetic work. Full BFGS avoids factorization but retains quadratic storage and update work, so it does not solve that scaling problem.

Gradient descent uses linear working storage in $d$, though the cost of reading the data and evaluating the gradient is still $O(nd)$ for dense $A$. Sparsity or streaming can be important. Limited-memory BFGS, a distinct limited-memory variant, stores only a fixed number $m$ of recent update pairs and uses $O(md)$ storage and update work, making it a realistic alternative to full BFGS.^[ref]

The available Hessian matrix factorization also permits a matrix-free Hessian-vector product:It costs $O(nd)$ for dense data without forming $H$. A suitable iterative, safeguarded Newton method can exploit this structure, so the conclusion rules out the dense implementation rather than every possible second-order algorithm.

These methods seek a local solution and require convergence checks appropriate to nonconvex optimization. The formula does not even ensure a finite minimizer exists: with one positive coefficient and nonzero $\mathbf{a}$, the positive exponential loss approaches zero along an unbounded direction without attaining it. Dimension alone cannot supply a convergence guarantee.