Convex Optimization & Gradient Descent

Convergence guarantees, learning rate, momentum, Adam

You are training L2-regularized logistic regression. You are minimizing L(w) = Σ log(1 + exp(-y_i w^T x_i)) + λ‖w‖². This function is convex — every local minimum is the global minimum, gradient descent is guaranteed to converge, and convergence rates are provable. Now train a 5-layer neural network instead. L(w) is non-convex, has countless saddle points and local minima of varying quality, and has no convergence guarantee. The mathematical gulf between these two problems is the difference between a well-posed optimization problem and one that works empirically.

A convex set C: for any x, y in C and t ∈ [0,1], the point tx + (1-t)y is also in C. The line segment between any two points stays inside the set. A convex function satisfies f(tx + (1-t)y) ≤ tf(x) + (1-t)f(y) — the function lies below the chord connecting any two points. First-order condition: f is convex if and only if f(y) ≥ f(x) + ∇f(x)^T(y-x) for all x, y. The tangent plane is a global lower bound on the function. This is why gradient information is sufficient for global optimization of convex problems.

What convexity buys: every local minimum is also the global minimum — no need to worry about getting trapped in a worse optimum (note: this does not mean the global minimum is unique; only strict convexity gives that) — gradient descent convergence guaranteed with appropriate step size, and theoretical convergence rates: O(1/t) for gradient descent, O(1/t²) for Nesterov acceleration. If the function is strongly convex (its curvature is bounded below by some m > 0 everywhere, not merely ≥ 0), gradient descent does better still, converging geometrically — the error shrinks by a constant factor each step — rather than the slower O(1/t) that plain convexity alone guarantees. Convexity of the objective and constraints also makes strong duality plausible — the dual problem's optimal value matching the primal's — but that additionally requires a constraint qualification such as Slater's condition; convexity alone does not guarantee it.

Where that dual problem comes from: for a constrained problem min f(x) subject to g(x)=0, form the Lagrangian L(x,λ) = f(x) + λg(x). The constrained optimum satisfies stationarity, ∇ₓL = ∇f(x) + λ∇g(x) = 0, together with primal feasibility, g(x) = 0 — two conditions that pin down both x* and λ* at once. Geometrically this says ∇f is parallel to ∇g at the optimum: if it weren't, you could still move along the constraint surface g=0 and decrease f further. λ* also has a sensitivity interpretation — relax the constraint from g(x)=0 to g(x)=ε and the optimal value of f shifts by approximately −λ*ε, so λ* measures how hard the constraint is binding.

SVMs, logistic regression, lasso, ridge — all convex. Neural networks: not convex. But empirically, modern overparameterized networks rarely get trapped in bad local minima. In overparameterized regimes where the number of parameters exceeds the number of training examples, loss surfaces have many saddle points but almost all local minima are approximately globally optimal.

NOT this. Non-convex optimization is not practically hopeless. Modern neural network training is non-convex optimization that works reliably in practice because of a structural property of overparameterized loss surfaces: most critical points are saddle points, not local minima, and most local minima have similar loss values to the global minimum. The theory of why gradient descent on non-convex neural networks generalizes well is still being developed — but empirically, the non-convexity is not the obstacle it appears to be in theory.

Key points

• Verify whether your objective is convex before choosing an optimizer. For convex problems, SGD with a decaying learning rate is provably convergent to the global minimum. For non-convex problems, convergence is only guaranteed to a stationary point — a point where the gradient is zero, which could be a saddle point. This determines whether you should trust a single run or require multiple restarts.
• Trap: using gradient descent on an ill-conditioned convex problem without checking convergence. A function can be convex but have a condition number κ = λ_max/λ_min that is extremely large — meaning the loss surface is a narrow, elongated valley. Gradient descent zigzags across the valley rather than descending efficiently. The convergence rate is (κ-1)/(κ+1) per step. Use Adam or L-BFGS for ill-conditioned convex problems, not vanilla gradient descent.
• Diagnostic: if optimization is converging slowly on a problem you believe is convex, compute the condition number of the Hessian at your current point. If κ > 1000, the problem is ill-conditioned — standardize your features or add regularization. For logistic regression, feature scaling directly improves the condition number of the Hessian and can reduce the number of gradient steps needed by an order of magnitude.

Recap

• Convex function lies below its chords; first-order: f(y) ≥ f(x) + ∇f(x)ᵀ(y−x) — tangent is a global lower bound.
• Convexity buys every local min being global (not necessarily unique) and guaranteed GD convergence, with provable rates; strong duality also needs a constraint qualification like Slater's, not convexity alone.
• Strongly convex → gradient descent converges geometrically; merely convex → only O(1/t).
• Lagrangian L(x,λ)=f(x)+λg(x): stationarity ∇f+λ∇g=0 plus feasibility g(x)=0 pin the optimum; λ measures sensitivity (Δf*≈−λε).
• Rates: O(1/t) for gradient descent, O(1/t²) for Nesterov acceleration.
• SVM / logistic / lasso / ridge are convex; neural nets are not — but overparam nets rarely hit bad local minima.
• Non-convex isn't hopeless: most critical points are saddles, and most local minima ≈ global in loss.
• Ill-conditioning, not non-convexity, is the real slowdown: GD zigzags at rate (κ−1)/(κ+1); standardise features.
• Slow on a convex problem? Compute the Hessian condition number — κ > 1000 means rescale or use Adam/L-BFGS.

Check your understanding