CPBS 7620 - Lecture 5 - The Subderivative

Overview

Nicholas Dwork explains the subderivative as a generalization of the derivative for convex functions: its slope defines a global linear underestimate, and the subdifferential collects all such slopes. He applies subderivatives to iterative minimization, discusses constant and diminishing step sizes, gives a sum rule for combining a differentiable and a convex function, and shows how subgradient signs enable interval bisection.

Key takeaways

A subderivative of a convex function at x is any slope θ for which F(y) ≥ F(x) + θ(y - x) holds globally, so it generalizes the tangent slope to nonsmooth points.
For F(x) = |x|, the subdifferential at the nondifferentiable point x = 0 is [-1, 1], while at nonzero x it contains only the slope -1 or 1.
The subderivative update x = x - αg can oscillate around a minimum when α is constant; stopping after M iterations without a new best value limits this behavior.
The sequence αₖ = 1/k tends to zero but has a divergent sum, matching the stated diminishing-step conditions while potentially requiring many iterations.
For a differentiable convex F and proper convex G, the sum rule gives ∂(F + G)(x) = F'(x) + ∂G(x), yielding ∂(x² + |x|) = 2x + ∂|x|.
In one-dimensional convex minimization, the sign of a subderivative determines which half-interval can be discarded, allowing bisection to halve the search interval per iteration.

Chapters

0:00 Subderivatives and the Subdifferential of |x|

For a differentiable convex function F, the tangent line with slope F'(x) is a global underestimate: F(y) is at least F(x) + F'(x)(y - x).
A subderivative replaces F'(x) with any slope that makes the corresponding line a global underestimate, extending the derivative to convex functions that are not differentiable.
For F(x) = |x|, the subdifferential is {-1} when x < 0, {1} when x > 0, and the interval [-1, 1] at x = 0.
The subdifferential is set-valued, and containing 0 at x identifies a minimum for a convex function.

3:05 Subderivative Minimization and Step-Size Tradeoffs

The subderivative method updates x using x = x - αg, where g is a subderivative, while tracking the best function value found.
With a constant step size α, iterates can bounce around an optimum, as with |x|, so the method stops after M consecutive iterations without improving the best value.
A diminishing step-size sequence can satisfy αₖ → 0 while ∑ₖ₌₁∞ αₖ = ∞; αₖ = 1/k is one example.
Diminishing steps can converge toward a solution but may take a long time; because each iteration need not improve the function value, a fixed iteration count can replace the no-improvement stopping rule.

6:26 Subdifferential Sum Rule and Bisection for Convex Minima

For proper convex functions F and G, when F is differentiable, ∂(F + G)(x) = F'(x) + ∂G(x).
For H(x) = x² + |x|, the subdifferential is 2x + ∂|x|, combining the derivative of x² with the subdifferential of |x|.
On an interval, a positive subderivative at x shows values to the right are higher than F(x); a negative subderivative shows values to the left are higher.
This sign test lets bisection discard half the interval at each iteration, compared with golden-section search discarding about one third.

Transcript excerpt

0:00 Hi, I'm Nicholas Twork, and today we're going to discuss the subderivative. The power set of a set, denoted by a script P, takes a set as input and returns all subsets of the input. For example, if B is equal to the set 1 2 3, then the power set of B is the empty set, followed by the sets containing 1 2 and 3 individually, followed by the sets containing all pairs 1 2, 1 3, and 2 3, and then B itself, 1 2 3. Consider the function that maps a set to its power set. This is a set-valued function. Every output is a set. Let F be a function that maps the real numbers to the real numbers such that F is convex and differentiable. Then G, then G, which is a line approximating the function F locally,

0:49 equal to f of x plus f prime of x times y minus x is a global underestimate of f. What does that mean? That means that g of y is less than or equal to f of y for all y. And here's an example. F is the solid line, G is the dashed line, it's the tangent line at the solid dot, and you see that it is less than or equal to f at all locations. Now, let F be a function that maps the real numbers to the real numbers such that F is just convex. It is no longer differentiable. Then theta is a subderivative of F means that g of y equal to f of x plus theta times y minus x is a global underestimate of F. And you see the relationship here. We've replaced f prime of x when f was differentiable by theta.

1:37 So, the subderivative is a

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

Related notes

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Nicholas Dwork.