The supporting inequality in part 2(a) bounds below by an affine function plus a positive squared Euclidean norm, making it a coercive function. Its continuity gives a global minimizer , which is unique by strict convexity. Let , and . Here is the block size, so its role differs from the number of component functions in Question 2. Use randomized block coordinate descent with uniformly sampled blocks of size , independently at each update. Sampling uniformly from a fixed partition into equal-sized blocks gives the same calculation, since each coordinate has inclusion probability .
Let be a common upper bound on the block Lipschitz constants. Part (c) permits . With step size , part (a) gives
Summing squared partial derivatives according to their inclusion probabilities,
For a strongly convex function, part 2(a) also yields the strong convexity gradient inequality
Indeed, substitute into the supporting inequality and complete the square in : the expression is at least for every .
Combining the last three estimates gives a contraction in conditional expectation:
By the tower property and repeated application,
An optimization epoch counts coordinate partial derivative evaluations: it comprises block updates or one full gradient update. With sampling with replacement, an optimization epoch is this work measure; it need not visit every coordinate. Consequently the block method needs
to bring the expected objective function gap below , for , up to integer rounding.
For the steepest descent method, use a global Lipschitz gradient constant . Part (c) with the full block permits . The descent lemma with step size , together with the strong convexity gradient inequality, gives
An exact line search along the negative gradient does at least as well in objective function decrease per update. Ignoring its additional work, the resulting epoch complexity is
The common coordinate-based guarantees favour blocks by a factor in epochs. In fact, with the conservative constants and , both methods have the same guaranteed contraction per update, while a block update uses only coordinate partial derivatives.
This compares the bounds justified by the given constants. For a particular objective function, sharper constants give the comparison against ; an actual speedup of is not universal. Computing a block coordinate gradient also need not cost exactly of a full gradient evaluation. The epoch complexity comparison assumes that coordinate partial derivative counts are a useful measure of work, and does not itself establish a wall-clock comparison.
For , with a convex function having an -Lipschitz gradient and a proper convex function with a well-defined proximal operator, the proximal gradient method with step size satisfies the displayed bound whenever a global minimizer exists. The one-step subgradient inequality and descent lemma give
The objective function values are nonincreasing. A telescoping sum over , followed by comparison of the last error with the arithmetic mean of the errors, proves the result. The bound controls the last objective function error without requiring a strongly convex function or a unique minimizer.
Target: convex-optimization.bigb, under Proximal gradient method.
Smooth maximum Created 2026-09-28 Updated 2026-10-25
Composing the log-sum-exp function with finitely many affine functions gives a differentiable approximation to their pointwise maximum. Increasing the inverse-temperature parameter reduces the uniform approximation error while increasing the Lipschitz gradient constant.
A residual accuracy level in a bound for stochastic gradient descent with a fixed step size and nonvanishing gradient noise. For a convex function with an -Lipschitz gradient, step size and conditional total variance at most , typical bounds have floors for averaged squared gradient norms, for averaged gradient norms, and for the best expected objective function gap. Such floors are upper bounds depending on the analysis and assumptions, rather than claims that these exact values are attained or that every last iterate converges.
Target: gradient-descent.bigb, under Stochastic gradient descent.