Baillon–Haddad theorem 2026-10-06
On the whole Euclidean space, an -Lipschitz gradient of a convex function is -cocoercive. Subtract the supporting affine function at one point, apply the descent lemma to a gradient step at the other point, then interchange the points and add. The conclusion needs convexity but no second derivative.
For a continuously differentiable convex function on with coordinate Lipschitz continuity constants , its block coordinate gradient is Lipschitz continuous along each corresponding coordinate subspace, with constant at most .
To prove this without assuming a Hessian matrix, put . Sum the coordinate derivative bound by Bregman divergence over the block, then repeat with interchanged and average:If is supported in the block, the dot product uses only . The Cauchy-Schwarz inequality and cancellation of its Euclidean norm give the result, including the zero case separately. Taking the full block supplies a global Lipschitz gradient constant .
Target: convex-optimization.bigb, under Coordinate descent. Descent lemma Created 2026-10-06 Updated 2026-10-25
Suppose is a differentiable function on an open convex set and has an -Lipschitz gradient there, in the Euclidean norm. For , the descent lemma statesA bounded continuous Hessian matrix gives one sufficient route to this estimate.[ref]
For a short proof, put . The fundamental theorem of calculus along the line segment givesThe Cauchy-Schwarz inequality and the Lipschitz gradient bound make the integrand at most ; its integral is . This proof needs no assumption that is a convex function.
For the gradient descent update , provided , substitution yieldsFor and , this ensures strict decrease whenever the gradient is nonzero. At it guarantees only nonincrease; the quadratic example has a nonshrinking alternating component at this endpoint. At the guaranteed decrease is . A bound valid only on cannot justify a step leaving .
If a fixed admissible step size is used forever, every iterate stays in , and has a finite lower bound, summing this inequality shows , hence . That conclusion alone gives neither convergence of the iterates nor a global minimum. For example, the smooth polynomial has and : gradient descent started at zero never moves, although . On , , so the Lipschitz gradient hypothesis holds on this domain. Convex functions and strongly convex functions provide additional structure; the exact quadratic convergence result above uses a positive-definite matrix.
Implicit nonsmooth block in alternating proximal-gradient iteration Created 2026-10-06 Updated 2026-11-05
Let be convex with an -Lipschitz gradient, , and let be a proper lower semicontinuous convex function. For , takeThe proper closed convex assumption on ensures that the implicit section has a well-defined proximal operator.
For two mixed points with difference , write for the gradient difference of and for the difference of the selected subgradients of . Inputs differ by and outputs by . Monotonicity of a convex subdifferential gives , while cocoercivity gives . Expanding these squared norms provesfor . Thus the combined update is firmly nonexpansive. Its fixed points are the minimizers of ; if one exists, the Browder convergence theorem for averaged operators gives norm convergence in finite dimensions.
Lipschitz gradient Created 2026-09-24 Updated 2026-10-18
A differentiable function has a -Lipschitz gradient on a set if its gradient satisfies Lipschitz continuity there:All norms here are the Euclidean norm. The constant limits how fast the gradient changes; it is not a bound on the magnitude of the gradient. For , the gradient is the linear map . Its operator norm is , so works globally and is sharp by taking . The gradient itself is unbounded on the whole Euclidean space.
If has a continuous Hessian matrix on an open convex set and throughout , integrate that linear map along the line segment from to :The operator norm bound proves the displayed Lipschitz continuity. Convexity of the domain keeps the entire line segment inside it. Bounding the Hessian matrix only at the endpoints is insufficient.
Fix with nonempty subdifferential for a convex function . If and , monotonicity of a convex subdifferential gives for any fixed . HenceThe Cauchy-Schwarz inequality proves the bound uniformly for . If has an -Lipschitz gradient, this makes the remainder in the proximal gradient mapping descent bound at most . Thus the big O notation is justified despite the dependence of the proximal gradient mapping on .
Target: convex-optimization.bigb, under Coordinate descent. Nesterov accelerated gradient method Created 2026-09-28 Updated 2026-11-05
For a differentiable convex function on a Euclidean space with -Lipschitz gradient, , one form of the Nesterov accelerated gradient method usesstarting with . The first extrapolation is zero. Each later step uses the previous displacement to form an extrapolated point , then evaluates the gradient there.[ref]
Proximal Algorithms by Neal Parikh and Stephen Boyd. section4.3, extrapolation weight k/(k+3) and accelerated convergence, printed p152, smooth specialization
If a global minimizer exists with , the objective error is . Reaching error therefore takes iterations. The parameter schedule and convex smoothness hypotheses are part of that guarantee.
The same extrapolation can be combined with a proximal gradient method step to handle an additional nonsmooth convex term.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 325 1 iv Solution Created 2026-10-03 Updated 2026-10-14
For the Euclidean norm, rotational symmetry and minimizing the radial objective give the radial soft thresholding formulaIndeed, if , an optimal is a nonnegative scalar multiple of ; minimizing over gives . The gradient of a Moreau envelope is consequentlyAt this is , and the two expressions agree when . The Moreau envelope of the Euclidean norm itself isThus a quadratic core replaces the nondifferentiable tip while the outer gradient remains the normalized radial direction. The Euclidean norm has an unbounded effective domain, unlike the earlier bounded-domain hypothesis; the preceding argument explicitly shows that this restriction is unnecessary here.
The absolute value and its Moreau envelope with tau equal to one, together with the continuous clipped gradient replacing the jump at the origin
. Details. For convex optimization, this Moreau–Yosida regularisation permits gradient descent and other methods for functions with a Lipschitz gradient, using a gradient Lipschitz constant . It approximates the norm uniformly: . Smaller improves approximation but makes the permitted gradient steps smaller. Minimizing alone preserves the minimizers and minimum value of ; replacing one term in a larger objective can shift the minimizer, so the smoothing parameter controls that approximation error.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 325 2 iv Solution Created 2026-10-03 Updated 2026-10-06
Here -smooth means that is differentiable on the entire Euclidean space and has an -Lipschitz gradient, with . Together with convexity, this implies -cocoercivity:First, integration of the Lipschitz gradient along a line segment proves the descent lemma:Indeed, subtract the linear term and integrate for ; its absolute value is at most .
Fix and define . This is a convex function, has the same Lipschitz gradient constant, and , so is a global minimizer. Put . The descent lemma at with givesThereforeInterchange and add the inequalities. The function values cancel, leaving the asserted cocoercivity. This is a proof of the Baillon–Haddad theorem without assuming a second derivative. Convexity is essential: has a -Lipschitz gradient but its gradient is not cocoercive.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 325 2 vi Solution Created 2026-10-03 Updated 2026-10-06
Set . Completing the square in the -minimization givesThus, with , the steps in terms of the proximal map of areThe factor comes from the squared residual without a prefactor. The proximal map can equivalently be denoted . Since is a finite convex function, it is continuous, and the quadratic makes the proximal minimizer unique.
A general convex may be nondifferentiable, so this last example need not satisfy the full -smooth hypothesis of the preceding part. The formulas nevertheless remain well-defined: only the derivative is used explicitly. If has an -Lipschitz gradient, one may take in the smooth proof, where is the operator norm.
There is also a useful nonsmooth extension. Put , whose Lipschitz gradient constant is . For two updates, retain the mixed-point differences above, let , and let be the difference of the two selected subgradients of at . The input difference is and the output difference is . Monotonicity of gives . The same norm expansion now yieldsFor , discard the nonpositive term and use . The result is the firmly nonexpansive mapping inequality for the full residual . Fixed points satisfy and , exactly the subgradient optimality condition for the convex objective. Thus the stated algorithm also converges for nonsmooth under this sufficient step bound, provided a minimizer exists; this extension uses monotonicity, not an unavailable gradient of .
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 325 2 v Solution Created 2026-10-03 Updated 2026-10-06
Assume , as is necessary for convergence to a minimizer. The printed hypotheses alone omit this condition: in scalar is convex with an -Lipschitz gradient for any prescribed , but has no minimizer, and the update sends to .
Under existence, define the full update . The proximal -step is uniquely defined by strong convexity of its quadratic term and satisfiesThe partial subdifferential in this equation belongs to the scalar function ; differentiating a subdifferential itself would not define the printed proximal minimization.
We prove directly that the alternating proximal-gradient operator is averaged. For two inputs and , setThe input difference is , the output difference is , and the difference of the two update residuals is . Exact expansion givesThe first inequality uses cocoercivity at the mixed points . Therefore is -averaged for the requested . In particular, the endpoint is covered: is firmly nonexpansive, not merely nonexpansive.
A fixed point has and , so the two optimality equations give and . Conversely, at a minimizer both gradients vanish and neither step moves. By convexity,The assumed existence of a minimizer supplies a fixed point. The Browder convergence theorem for averaged operators now givesNo uniqueness of the minimizer is needed. The same estimate even proves averagedness for in this smooth setting, but the requested interval already suffices. The existence condition and the use of the gradient at are both essential to the proof as presented.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 340 5 c Solution Created 2026-10-03 Updated 2026-10-05
For a differentiable convex function with -Lipschitz gradient and a proper lower-semicontinuous convex function , the proximal gradient method isThe proximal operator is . To obtain an explicit iteration for discrete isotropic total variation, let with the printed zero boundary differences andThe dual is minimization of over , and the primal minimizer is . Here must be the exact adjoint operator of these differences. For example,with the analogous formula in for ; for both operators are zero. Equivalently use in the backward-difference expression, ignoring unused edge components.
The gradient of the dual objective is , with Lipschitz constant . Taking to be the indicator functional of a constraint set makes its proximal operator the Euclidean projection onto a convex set. Thus a valid explicit algorithm isThe bound follows by summing over grid differences. Finite-dimensional proximal gradient method convergence gives a dual minimizer and convergence of the recovered to the unique primal minimizer. Projection is pointwise in the dual; applying pointwise soft thresholding directly to would not compute the primal TV proximal operator.
Past exam of the mathematics course of the University of Cambridge 2022 ib Paper 1 7H Solution Created 2026-09-23 Updated 2026-09-25
Starting from , gradient descent repeatedly computes the gradient and updatesstopping when the gradient norm, step, or objective decrease is sufficiently small.
The Hessian bounds say that is -strongly convex and has -smooth gradient. With ,Thus the iteration count isconvergence becomes slower linearly with the condition number .
Past exam of the mathematics course of the University of Cambridge 2023 iii Paper 339 1 d Solution 2026-09-28
Define the softmax weightsThey obey and . The gradient is their weighted mean,Differentiating once more gives the covariance-form Hessian matrixFor every unit vector ,where . The Hessian is a covariance matrix, so it is positive semidefinite; the displayed upper bound also gives in the Loewner order. Consequently has a Lipschitz gradient with
Past exam of the mathematics course of the University of Cambridge 2023 iii Paper 339 1 e Solution 2026-09-28
Chooseso the smooth maximum error is at most and the Lipschitz gradient constant isSuppose a minimizer of lies within distance of the starting point. The Nesterov accelerated gradient method can find such thatiniterations. If minimizes , then the smoothing inequalities implyThis improves the nonsmooth subgradient method dependence from to .
A Lipschitz gradient with constant gives the descent lemmaFor , this upper bound is at most whenever . Since is a descent direction, the right side is positive. Thus the Armijo condition holds throughoutAt it holds by equality. If the gradient Lipschitz constant can be taken as zero, the objective is affine and every positive step along a descent direction passes this sufficient-decrease test.
A line search chooses a positive step size giving useful decrease along the chosen direction. Fix and a trial step . The Armijo condition isThe backtracking line search tests and takes the first accepted value. A Lipschitz gradient has with a constant independent of .
Integrating the gradient along a segment gives the descent lemmaFor , every satisfies the Armijo condition. Thus backtracking terminates. If the trial step is accepted, ; otherwise the immediately preceding step failed, so it exceeded . ConsequentlyThe same global Lipschitz constant and fixed search parameters make independent of . If , the zero direction passes the first test. If , the gradient is constant and the first test passes, so take .
Choose , fixed , , and repeat for every : compute , choose by the backtracking line search in part (b) with , and set . At a stationary point keep the sequence constant.
Assume has a globally Lipschitz gradient and is bounded below on its initial sublevel set . Then the steepest descent method satisfies . Indeed, the Armijo condition and the uniform lower step bound giveThe objective values decrease and stay in the stated sublevel set. Summing the inequality and using its lower bound yieldswhich proves the limit. Every cluster point is a stationary point by continuity of the gradient. If the initial sublevel set is compact, cluster points exist. This global convergence result guarantees stationarity from arbitrary initial points under these assumptions; it does not, for a general nonconvex objective, guarantee convergence of the whole iterate sequence or a global minimum.
Past exam of the optimisation for data science course of the University of Oxford 2023 1 d Solution 2026-10-25
Fix , and write and . The supplied subgradient relation gives with . The evaluation point in is , whereas is a subgradient at the new point .
Apply the subgradient inequality at , with comparison point :The descent lemma for the -Lipschitz gradient of givesAdding these estimates proves the stronger, explicit inequalityIn particular, the objective function decreases for whenever the proximal gradient mapping is nonzero.
To justify the requested big O notation, we must check that , which depends on , stays bounded. Suppose is nonempty, and choose a fixed in this subdifferential. This holds for a finite-valued convex function on , including both norms in parts (a) and (b). By monotonicity of a convex subdifferential,Substituting and , and then using the Cauchy-Schwarz inequality, yieldsThus , uniformly in . This local boundedness of the proximal gradient mapping makes the remainder at most , soNo differentiability of is needed. If an proper extended-real function is allowed as the regularization term, the subdifferential condition at is a qualification for this uniform remainder; the preceding explicit descent inequality remains the useful statement whenever its quantities are finite.
Past exam of the optimisation for data science course of the University of Oxford 2023 2 f Solution 2026-10-25
The printed distance needs a square. The native PDF, paper page 3, prints in the final bound, but the general conclusion from (5) contains . We first prove the corrected statement and then show that the printed version can fail.
Take the expectation in (5), use the tower property, and sum over . The squared Euclidean distances form a telescoping sum:Discard the final nonnegative squared Euclidean distance. The smallest of numbers is at most their arithmetic mean, soThis is an bound above the stochastic gradient noise floor for the best expected objective function value. By Jensen's inequality, it also bounds for the averaged iterate , because is a convex function.
To test the printed version, take one component function, , with , and . This convex quadratic function has , hence it has a -Lipschitz gradient. The stochastic gradient descent update is deterministic, its conditional variance is zero, and the assumed positive bound is valid. At , the new iterate is , soThus the printed inequality is false under its stated assumptions. The squared Euclidean distance in the corrected bound resolves the defect.
