Convex Functions
Convexity of a learning problem has two requirements.
Why Convexity Matters
Convexity gives an optimization problem a useful geometric structure. Instead of needing to understand every possible shape of a function, we can study how its graph behaves between selected pairs of points. This structure leads to an important optimization consequence: for a convex function, finding a local minimum is enough to identify a global minimum.
The word any matters. Convexity is not established by checking one convenient pair of points. The defining comparison applies to every selected pair of inputs.
The Graph and the Chord
The geometric definition of convexity compares two points on the graph of a function with the line segment joining their function values. Choose two inputs and look at the corresponding points on the graph. Then examine the segment connecting those two function values. The function is convex when the required comparison holds for every selected pair of inputs.
Checking the Definition with Two Points
Use two selected inputs, p and q, to organize a convexity check without relying on a single visual sample.
Select: Choose two inputs p and q and locate their corresponding function values on the graph.
Join: Form the line segment joining those two function values.
Compare: Compare the graph between p and q with that line segment according to the convexity condition.
Repeat: Because the condition applies to every selected pair, repeat the reasoning for arbitrary pairs rather than treating one successful pair as proof.
A valid convexity argument must address the graph-to-segment comparison for arbitrary selected pairs of inputs.
The Epigraph Region
The epigraph of a function is the set of points on the graph and all points above the graph. It changes the viewpoint from looking only at the curve to looking at the entire region supported by that curve and everything above it.
The epigraph is useful because it turns a property of the graph into a property of a region. When studying convexity, the shape of this region provides another geometric way to reason about the function. The essential membership rule is simple: a point belongs to the epigraph if it is on the graph or above it.
Generated illustration: imagine drawing a function's graph on a coordinate plane and then shading every point directly above the graph. The graph itself is included in the shaded region, so the shaded region represents the epigraph rather than only the area strictly above the graph.
Subgradients at a Point
A subgradient of a convex function f at a point w is one member of the subdifferential set at w. The subdifferential is written as ∂f(w).
The set ∂f(w) contains all subgradients of f at w. A subgradient is therefore an individual element, while the subdifferential is the complete set of such elements at the point w.
When a problem asks you to calculate a subgradient, the task begins with a convex function f and a point w. The immediate goal is not necessarily to describe the entire set ∂f(w). It is to identify an element of that set. This distinction matters because finding one valid member can be enough for many practical uses.
Differentiability and Singleton Sets
The simplest subgradient construction occurs when f is differentiable at w. In that situation, the subdifferential set contains exactly one element. That element is the gradient of f at w, written as ∇f(w). Therefore, when differentiability is known, the gradient supplies the subgradient to use.
Using Differentiability
Suppose f is known to be differentiable at the selected point w. What must be identified to obtain a subgradient at w?
Recognize the condition: The relevant condition is that f is differentiable at w.
Identify the set structure: Differentiability makes ∂f(w) a singleton, so the set has one element.
Name the element: That single element is the gradient ∇f(w).
The gradient ∇f(w) is the subgradient to use, and there is no need to search through multiple members of ∂f(w).
One Useful Subgradient
Many practical uses require only one element of ∂f(w), not every element. This is why a construction method is valuable: it gives a reliable way to obtain one valid subgradient at the point of interest. Calculating the entire subdifferential can be unnecessary when the downstream task only needs a single member.
The source material also identifies pointwise maximum functions as a second situation with a subgradient construction method. The role of that method is practical: starting from the pointwise maximum structure, it helps produce one member of the subdifferential set. The central lesson is the output, not an obligation to calculate every possible subgradient.
Local and Global Minima
A local minimum is defined using a neighborhood around a point. It means that the point has the minimum behavior being considered within that surrounding neighborhood. A global minimum is the minimum over the entire domain being considered.
For convex functions, every local minimum is also a global minimum. The reason is the same geometric structure introduced earlier: convexity controls how the function behaves between points. A point cannot be lowest only in a small neighborhood while a lower value exists elsewhere without conflicting with the convexity property.
Interpreting a Local Minimum
A point is identified as a local minimum of a convex function. What conclusion follows?
Start locally: The given point is lowest according to the comparison within a neighborhood around it.
Use convexity: The function has the global structure required by convexity, so its behavior between points is constrained.
Extend the conclusion: For a convex function, the local minimum property extends beyond the neighborhood.
The point is a global minimum of the convex function.
Common Reasoning Errors
Treating one successful pair of points as proof of convexity.
The convexity condition applies to every selected pair of inputs.
Fix:
Use the pair as an illustration, then reason about arbitrary pairs.Using subgradient and subdifferential as if they meant the same thing.
A subgradient is one member, while ∂f(w) contains all subgradients at w.
Fix:
Use subgradient for one element and subdifferential for the set.Assuming that every subdifferential must contain many elements.
Differentiability makes ∂f(w) a singleton containing ∇f(w).
Fix:
When differentiability at w is known, use the gradient as the single subgradient.Assuming that a practical calculation must list every subgradient.
For many practical uses, one member is sufficient.
Fix:
Match the calculation to the task and construct one useful member when that is all the task requires.Confusing a local minimum with a global minimum without using convexity.
The local-to-global conclusion is guaranteed here because the function is convex.
Fix:
State the convexity condition before extending a local minimum conclusion to the whole function.
Check Your Understanding
A convex function f is considered at a point w. Explain the difference between a subgradient and the subdifferential set. Then state what ∂f(w) becomes if f is differentiable at w, and explain why finding one subgradient may be enough for a practical task.
Hints
- Describe the subgradient as one member rather than as the whole collection.
- Use the differentiability condition to identify the unique member.
- Connect one-member construction to the fact that many practical uses do not require every member.
Describe a geometric convexity check using two arbitrary inputs. Include the graph, the line segment joining the two function values, and the reason one pair alone is not enough. Finally, explain what the epigraph contains and why a local minimum of a convex function is also global.
Hints
- Start with two points on the graph.
- Compare the graph between them with the joining line segment.
- The epigraph includes the graph and all points above it.
- Use convexity when moving from a neighborhood-based minimum to a whole-domain conclusion.
Key Takeaways
- Convexity is defined geometrically by comparing the graph between two points with the line segment joining their function values, and the condition must hold for every selected pair.
- The epigraph is the set of points on the graph together with all points above it.
- A subgradient is one member of the subdifferential set ∂f(w), which contains all subgradients at w.
- If f is differentiable at w, ∂f(w) is a singleton containing the gradient ∇f(w).
- For many practical uses, one constructed subgradient is sufficient, and every local minimum of a convex function is also a global minimum.
Key Takeaways
- Convexity describes how a function's graph relates to line segments between function values for every pair of selected inputs.
- The epigraph contains the graph and every point above it.
- The subdifferential ∂f(w) is the set of all subgradients at w; a subgradient is one member of that set.
- Differentiability reduces the subdifferential to the single gradient ∇f(w), and many practical tasks need only one subgradient.
- Convexity guarantees that every local minimum is also a global minimum.