Questions: Convex Optimization Fundamentals

Question 1

A function f is convex if f(lambda*x + (1-lambda)*y) <= lambda*f(x) + (1-lambda)*f(y) for all x, y and lambda in [0,1]. What does this condition say geometrically?

• A. The function's graph curves downward like a dome
• B. The line segment connecting any two points on the function's graph lies on or above the graph — the function 'bowls upward' everywhere
• C. The function has exactly one minimum and no maximum
• D. The function's gradient is always positive

Answer: (B)

The convexity condition says that for any two points x and y, the function value at their weighted average (the interpolated point) is at most the weighted average of the function values. Geometrically, this means the chord between any two points on the graph lies on or above the graph itself — the function curves upward like a bowl. This 'bowl' shape is why local minima are global: you cannot have a valley within a valley in a convex function. If you take any step downhill, you are making genuine progress toward the global minimum.

Question 2

The sum of two convex functions is always convex, but the product of two convex functions is not necessarily convex.

• T. True
• F. False

Answer: True

The sum preserves convexity: if f and g are convex, then (f+g)(lambda*x + (1-lambda)*y) = f(lambda*x + (1-lambda)*y) + g(lambda*x + (1-lambda)*y) <= lambda*f(x) + (1-lambda)*f(y) + lambda*g(x) + (1-lambda)*g(y) = lambda*(f+g)(x) + (1-lambda)*(f+g)(y). The product does NOT preserve convexity in general: f(x) = x and g(x) = x are both convex, but f(x)*g(x) = x^2 is convex in 1D. However, f(x) = x^2 - 1 and g(x) = x^2 - 1 are convex, but their product x^4 - 2x^2 + 1 is not convex (it has two local minima). The preservation of convexity under sums is why regularized losses (loss + penalty) remain convex when both terms are convex.

Question 3

Strong duality (the primal and dual optimal values are equal) always holds for convex optimization problems.

• T. True
• F. False

Answer: False

Strong duality requires additional conditions beyond convexity. Weak duality (dual value <= primal value) always holds, but strong duality (equality) requires a constraint qualification. The most common is Slater's condition: there must exist a strictly feasible point (one that satisfies all inequality constraints strictly). Most well-posed ML problems satisfy Slater's condition, so strong duality holds in practice. But pathological convex problems can have a duality gap. The distinction matters because dual formulations are used in SVM optimization and in deriving the representer theorem.

Question 4

Explain why the distinction between convex and non-convex optimization is the central divide in ML optimization theory, and what guarantees convexity provides.

Model answer: Convexity guarantees three critical properties: (1) every local minimum is a global minimum, so gradient-based methods cannot get stuck in suboptimal basins; (2) first-order optimality conditions (gradient = 0) are sufficient for global optimality, making it easy to verify solutions; (3) polynomial-time algorithms with provable convergence rates exist (e.g., GD at O(1/T), accelerated GD at O(1/T^2)). Non-convex problems — including deep learning — have none of these guarantees: there can be many local minima, saddle points, and no polynomial-time algorithm is guaranteed to find the global optimum. This is why the theory for convex ML (SVMs, logistic regression, ridge regression) is mature and tight, while deep learning theory is still an active frontier. The convex/non-convex divide determines whether optimization is a solved problem or an open research question.

In practice, deep networks optimize surprisingly well despite non-convexity — understanding why is one of the major open problems in ML theory. The convex theory provides the baseline against which non-convex phenomena are measured and understood.