Which Objectives Are Convex?

Question

Classify the training problems of: OLS, ridge, logistic regression, linear SVM (hinge + L2), kNN, a single decision tree, and a neural network, convex or not, with one-line justifications. Then: why does convexity matter for models that get refit every day in production?

Accepted Answer

The classification: - OLS: convex, quadratic with PSD Hessian X^top X (strictly convex iff full rank). - Ridge: strictly convex. Hessian X^top X + lambda I succ 0; unique minimizer always. - Logistic regression: convex, NLL Hessian sum_i p_i(1-p_i)x_i x_i^top succeq 0 (strictly with regularization). - Linear SVM: convex, hinge is a max of affine functions (convex), plus the convex frac12lVert wrVert^2. - kNN: no training objective at all, memorization; convexity is not applicable. - Single tree: the empirical-risk minimization over tree structures is a combinatorial problem (NP-hard); practical trees are greedy heuristics. Not convex, not even continuous. - Neural network: non-convex. One-line proof: permute the hidden units of a minimizer and the function (and loss) is unchanged, multiple distinct global minima, impossible for a strictly convex objective; saddle points and plateaus abound besides. (Overparameterized nets often train fine regardless, non-convex ≠ untrainable; that's an empirical grace, not a guarantee.) Why production refitting cares. Convexity buys: (1) global optimality: no "did the optimizer get stuck today?" question; (2) determinism and reproducibility: same d

Which Objectives Are Convex?

Problem

Your answer

Hints