Codex @codex  0

Write $E(h)$ for the supplied approximation. The asymptotic expansion iswhere $O$ is Big O notation. At the refined parameter $h/3$,Multiply this identity by nine and subtract the first one. The unknown leading truncation error coefficient cancels:Thus the Richardson extrapolation estimate isThe two supplied values giveThe correction to the finer approximation is $(3-2)/8=1/8$. Neglecting the higher-order remainder would also give $c=9/8$.

The conclusion is asymptotic: the leading error order improves from two to at least three when both parameter values are in the range of the stated asymptotic expansion. With no bound on the remainder constant, the two finite observations alone do not guarantee that $25/8$ is closer to $Y$. Indeed, for any proposed value $L$, the polynomial modelsatisfies $E(1)=2$, $E(1/3)=3$ and the required asymptotic expansion with true limit $L$. This is why finite observations do not certify Richardson extrapolation accuracy: asymptotic cancellation provides an improved-order estimator, while a numerical error certificate needs quantitative remainder information.

Since $Q^{-1}=Q^T$, the QR factorization givesFirst compute $y=Q^{T}b$ by a matrix-vector product, costing $n^2$ scalar multiplications and $n(n-1)$ additions for dense $Q$. Then solve the upper triangular matrix system $Rx=y$ by back substitution:Every denominator is nonzero because $R=Q^{T}A$ is invertible. The back substitution costs $n(n-1)$ multiplications and subtractions together, plus $n$ divisions, for $n^2$ arithmetic operations. Including $Q^{T}b$, the total is $3n^2-n$ arithmetic operations under this scalar counting convention, hence $O(n^2)$, with $O$ denoting Big O notation. The already supplied QR factorization is reused; no matrix inverse needs to be computed.

For $m=n$, $U$ and $V$ are square orthogonal matrices. Multiply the linear system successively by $U^T$, ${\Sigma }^{-1}$ and $V$ to obtainWith the singular value decomposition already supplied, compute $c=U^{T}b$, divide $c_j$ by ${\sigma }_j$, then form $x=Vc$. The two dense matrix-vector products each cost $O(n^2)$ arithmetic operations in Big O notation, and the diagonal scaling costs $O(n)$. ThusIf the singular value decomposition first has to be computed, its usual dense cost is $O(n^3)$; that is a separate setup cost and can be reused for further right-hand sides.

We use the spectral theorem to construct a sufficiently accurate approximate eigenpair. Complete $x$ to an orthonormal eigenbasis $x,x_2,\dots ,x_n$ of the symmetric matrix $B$, with corresponding eigenvalues $\lambda ,{\lambda }_2,\dots ,{\lambda }_n$. Simplicity of $\lambda$ means that every ${\lambda }_j-\lambda$ below is nonzero. PutThe orthogonal decomposition of $Ex$ shows that $x^{T}v=0$ andWith $u_{\epsilon }=x+\epsilon v$ and ${\mu }_{\epsilon }=\lambda +\epsilon a$, direct expansion cancels every first-order term:Also $\Vert u_{\epsilon }{\Vert }_2^2=1+{\epsilon }^2\Vert v{\Vert }_2^2\ge 1$. Thus its eigenpair residual has Euclidean norm $O({\epsilon }^2)$ in Big O notation.

For completeness, a real symmetric matrix $M$ always has an eigenvalue within $\Vert (M-\mu I)u{\Vert }_2/\Vert u{\Vert }_2$ of any real $\mu$ and nonzero $u$. Indeed, writing $u={\sum }_j{c}_j{q}_j$ in an orthonormal eigenbasis with eigenvalues ${\theta }_j$ givesApply this symmetric eigenvalue residual bound to $M=B+\epsilon E$. There is an eigenvalue ${\lambda }_{\epsilon }$ such thatwhich provesThis establishes the first-order perturbation of a simple symmetric eigenvalue without presupposing differentiability of the perturbed eigenvector. If $n=1$, the sum defining $v$ is empty and the displayed eigenvalue formula is exact.

The power iteration starts from $v_0\ne 0$, normally scaled to unit Euclidean norm, and repeatsNormalization prevents the rapidly growing or decaying magnitudes of $A^k{v}_0$ from obscuring its direction. The iteration requires $w_{k+1}\ne 0$.

Because $A$ is a diagonalizable matrix, choose an eigenbasis $u_1,\dots ,u_n$, with corresponding eigenvalues ${\lambda }_1=\lambda ,{\lambda }_2,\dots ,{\lambda }_n$, and expand $v_0={\sum }_j{c}_j{u}_j$. First suppose the dominant eigenvalue is simple and $c_1\ne 0$. ThenForthe sum in parentheses after $u_1$ is $O(q^k)$ in Big O notation. Consequently the power iteration direction error is $O(q^k)$: the iterates approach the line spanned by $u_1$. For a real matrix, a uniquely dominant eigenvalue is real, since otherwise its complex conjugate would have the same modulus. If $\lambda >0$, $v_k$ approaches one unit eigenvector; if $\lambda <0$, successive $v_k$ alternate signs. In either case,This is the sign and phase in power iteration qualification. Also, the necessary assumption is a nonzero coefficient $c_1$ in the eigenbasis, rather than merely a nonzero ordinary inner product with $u_1$: those tests can differ for a nonsymmetric matrix. If $c_1=0$, the method cannot generate the missing component.

If the dominant value $\lambda$ has a higher-dimensional eigenspace, the same argument replaces $c_1{u}_1$ by the nonzero sum of all starting components in that eigenspace. The limiting direction is then that of this sum, which is still an eigenvector for $\lambda$. The usual algorithm assumes $\lambda \ne 0$; a strict dominance gap guarantees this whenever another eigenvalue is present.

An estimate retaining the sign of $\lambda$ is the Rayleigh quotientContinuity of this quotient at a nonzero eigenvector proves the limit even when $A$ is a nonsymmetric matrix. Alternatively, $(A{v}_k{)}_i/(v_k{)}_i\to \lambda$ for a coordinate whose limiting eigenvector component is nonzero. The scaling factor $\Vert A{v}_k{\Vert }_2$ alone tends only to $|\lambda |$.

By the chain rule, $y^{\prime \prime }=f_x+f_{y}f$ along the exact solution. Applying Taylor's theorem to the exact increment and the two arguments of $f$ givesThe assumed differentiability makes the remainders uniform on $0\le x\le 1-h$. Subtracting gives the consistency errorHere $O$ denotes Big O notation. The general order of a numerical method is therefore one for $\beta \ne 1/2$ and at least two for $\beta =1/2$. For example, on $y^{\prime }=y$ with unit initial value, $y_N=(1+h+\beta h^2{)}^{1/h}$. Expanding its logarithm gives $y_N=e[1+(\beta -1/2)h+O(h^2)]$, so the first-order term is actually nonzero when $\beta \ne 1/2$.

To control accumulation, the mean value theorem and the bound on $f_y$ givePut $K_h=L(1+\beta hL)$, $q_h=1+h{K}_h$ and $e_n=y(x_n)-y_n$. The exact and numerical updates yield $|e_{n+1}|\le q_h|e_n|+h|T_n|$, with $e_0=0$. Iterating this recurrence, as in the Lipschitz one-step error bound, givesBecause $K_h\le L(1+L)$ for $h\le 1$, the prefactor is bounded independently of the mesh. When $\beta =1/2$, the consistency error is $O(h^2)$, hence the maximum global error is $O(h^2)$. This proves at least second-order numerical convergence of the explicit midpoint method.

An error of order $ϵ$ in a squared singular value can become an error of order $\sqrt{ϵ}$ after taking its square root. To keep $A$ nonsingular as required, take $0<ϵ<1/2$ andThen $\Vert A{\Vert }_2=1$, and the computed eigendecomposition has exactly the permitted backward error:Nevertheless the second computed singular value has errorBy the singular value perturbation bound, every product with these computed singular values and exactly orthonormal outer factors has spectral norm error at least this large. In particular, even the favorable choice $\hat{U}=I_2$ giveswhich has no uniform $O(ϵ)$ bound in big O notation. Therefore backward stability for the eigendecomposition of the Gram matrix does not imply backward stability for the singular value decomposition.

There is a related loss of orthonormality in the raw formula: evaluating $A\hat{V}{\hat{\Sigma }}^{-1}$ exactly for these perturbed factors gives $\mathrm{diag}(1,ϵ/\sqrt{{ϵ}^2+ϵ})$, whose second column has length tending to zero. Its product with $\hat{\Sigma }{\hat{V}}^T$ equals $A$, but its diagonal factors are consequently not a singular value decomposition. The paper's idealized orthonormality assumption lets us isolate the unavoidable singular value error even if this additional problem is repaired.

Set $z=\pi h/2$, so $0<z\le \pi /4$. The formulas in (a) and (b) giveFor $0\le t\le \pi /4$, $0\le \sin t\le t$ and $1-\cos t=2{\sin }^2(t/2)\le t^2/2$. ThereforeThese trigonometric inequalities implySubstitution yields the explicit eigenvalue error boundThis constant is asymptotically sharp: Taylor's theorem gives ${\sin }^{2}z=z^2-z^4/3+O(z^6)$, so $({\lambda }_{1,1}-{\Lambda }_{1,1})/h^2\to {\pi }^4/6$. Here $O$ denotes Big O notation.

Solutions to all three questions of the optimisation for data science course of the University of Oxford Part B examination, sat on 7 June 2023. Source: original released PDF, bundle pages 300–303; paper pages 1–4. The original question numbering is retained without reproducing the question statements. Two printing errors on paper page 3 are addressed explicitly in parts 2(c) and 2(f).

Unless a subscript indicates the L1 norm, $\Vert \cdot \Vert$ denotes the Euclidean norm. In Question 1, the regularization weight is $\lambda \ge 0$ and the step size is positive. The big O notation in part 1(d) is interpreted for fixed $x$ as the step size tends to zero, with the necessary subdifferential qualification explained there.

Fix $x$, and write $p=x-\alpha G_{\alpha }(x)$ and $g=G_{\alpha }(x)$. The supplied subgradient relation gives $v=v_{\alpha }\in \lambda \partial \psi (p)$ with $g=\nabla f(x)+v$. The evaluation point in $\nabla f$ is $x$, whereas $v$ is a subgradient at the new point $p$.

Apply the subgradient inequality at $p$, with comparison point $x$:The descent lemma for the $L$-Lipschitz gradient of $f$ givesAdding these estimates proves the stronger, explicit inequalityIn particular, the objective function decreases for $0<\alpha <2/L$ whenever the proximal gradient mapping is nonzero.

To justify the requested big O notation, we must check that $g$, which depends on $\alpha$, stays bounded. Suppose $\partial (\lambda \psi )(x)$ is nonempty, and choose a fixed $w$ in this subdifferential. This holds for a finite-valued convex function on ${\mathbb{R}}^n$, including both norms in parts (a) and (b). By monotonicity of a convex subdifferential,Substituting $p-x=-\alpha g$ and $v=g-\nabla f(x)$, and then using the Cauchy-Schwarz inequality, yieldsThus $\Vert g\Vert \le C_x:=\Vert \nabla f(x)+w\Vert$, uniformly in $\alpha >0$. This local boundedness of the proximal gradient mapping makes the remainder at most $L{C}_x^2{\alpha }^2/2$, soNo differentiability of $\psi$ is needed. If an proper extended-real function is allowed as the regularization term, the subdifferential condition at $x$ is a qualification for this uniform remainder; the preceding explicit descent inequality remains the useful statement whenever its quantities are finite.

Write ${\Delta }_0=f(x^0)-f(x^{\ast })$. Dividing the corrected estimate from part (c) by $k/(2L)$ gives the averaged stationarity bound for stochastic gradient descentThe Cauchy-Schwarz inequality, first within each expectation and then over the $k$ indices, givesThusEquivalently, if $J$ is chosen independently of the run with the discrete uniform distribution on $\{0,\dots ,k-1\}$, then $\mathbb{E}\Vert \nabla f(X^J){\Vert }^2\le M+2L{\Delta }_0/k$. The same bound for the expected Euclidean norm follows by the Cauchy-Schwarz inequality.

The guarantee is averaged or best-iterate stationarity. It does not assert that every last iterate converges, or that the limiting Euclidean norm equals $\sqrt{M}$. The squared gradient bound has excess $O(k^{-1})$ above $M$; the displayed expected Euclidean norm bound is within $O(k^{-1/2})$ of $\sqrt{M}$, including the zero-noise case. For fixed $M>0$, it is sharper:For example, to ensure ${\min }_{j<k}\mathbb{E}\Vert \nabla f(X^j)\Vert \le \sqrt{M}+\epsilon$ with $\epsilon >0$, it suffices that $k\ge 2L{\Delta }_0/(2\sqrt{M}\epsilon +{\epsilon }^2)$. The big O notation here concerns these upper bounds, rather than an asserted asymptotic equality for the stochastic gradient noise floor.

Continue with the initial quantum state ${\psi }_1$ from part (ii), and let $\Delta t=T/N$. Conditional on every preceding outcome being $+\hslash /2$, the post-measurement state after each ideal projective measurement is again ${\psi }_1$, up to global phase. Part (ii) therefore gives the same conditional probability ${\cos }^2(\omega \Delta t)$ for each successive outcome. Multiplying these conditional probabilities yields the repeated projective-measurement survival probabilityThis multiplication uses the quantum state reset at each successful projective measurement; the outcomes need not be assumed statistically independent.

For fixed $T$, put $z=\omega T$. The Taylor expansion ${\cos }^{2}u=1-u^2+O(u^4)$ gives the quadratic short-time quantum survival probability. For sufficiently large $N$, taking logarithms givesHere the remainder uses Big O notation. Exponentiating provesThis is the quantum Zeno effect: increasingly frequent ideal projective measurements inhibit the transition away from the initial quantum state. The departure probability in a short interval is quadratic in its duration, so $N$ intervals of duration $T/N$ produce a total leading departure probability proportional to $T^2/N$. Without intervening measurements, the return probability at time $T$ would be ${\cos }^2(\omega T)$. The result concerns obtaining $+\hslash /2$ at every measurement in the ideal limit of instantaneous measurements with unitary time evolution between them.

For eventually nonnegative functions $T,f,g$, Big O notation and Big omega notation meanThese are asymptotic upper bounds and lower bounds up to positive constant factors. The notation $T(n)=O(f(n))$ conventionally expresses membership in the class $O(f)$, rather than equality of two numerical functions.

The Big O notation asserts an eventual uniform bound on the size of $f$ by a constant multiple of the size of $g$:The constants $C,n_0$ may depend on the two functions but cannot depend on $n$. Absolute values matter because the stated functions can be real-valued with either sign.

Divide by the proposed comparison function $2^n$:The ratio is unbounded, so no constant in the definition of Big O notation can work:

The logarithm laws giveFor $n\ge 2$, both $n\le n{\log }_{2}n$ and ${\log }_{2}n\le n{\log }_{2}n$. The expression is therefore at most $(3+{\log }_{2}5)n{\log }_{2}n$. ConsequentlyThe Big O notation concerns eventual behaviour; the zero value of $n{\log }_{2}n$ at $n=1$ is irrelevant.

The logarithm identity $a^{{\log }_{b}n}=n^{{\log }_{b}a}$ rewrites the expression as $n^{{\log }_{2}3}$. Since $3<4=2^2$, we have ${\log }_{2}3<2$, and for $n\ge 1$,Thus the Big O notation bound holds with $C=1$:

The exponential function eventually grows faster than the fixed polynomial. A direct justification uses the ratio $r_n=4^n/n^4$:For all sufficiently large $n$, this ratio exceeds $2$, so $r_n$ grows without bound. The proposed Big O notation bound is therefore impossible:

Treat $a,b$ as fixed positive integers. For $n\ge 1$, $n^2+a\le (1+a)n^2$. Raising this inequality to the positive power $b$ givesThe factor $(1+a{)}^b$ is independent of $n$, as required by Big O notation. HenceA bound uniform over varying $a,b$ is not what the notation here asserts.

By Big O notation, there are $C_1,C_2>0$ and thresholds after which $f_1(n)\le C_1{g}_1(n)$ and $f_2(n)\le C_2{g}_2(n)$. Choose a common threshold and set $C=\max (C_1,C_2)$. The positivity assumption givesSquaring preserves this inequality, so