Are Convex Optimization Curves Convex?
This addresses a fundamental issue in optimization theory for researchers and practitioners, providing insights into stopping criteria and curve behavior, though it is incremental as it builds on known step size conditions.
The paper investigates whether optimization curves from gradient descent on smooth convex functions are convex, finding that convexity depends on step size, with provable convexity in some regimes and non-convexity in others.
In this paper, we study when we might expect the optimization curve induced by gradient descent to be \emph{convex} -- precluding, for example, an initial plateau followed by a sharp decrease, making it difficult to decide when optimization should stop. Although such undesirable behavior can certainly occur when optimizing general functions, might it also occur in the benign and well-studied case of smooth convex functions? As far as we know, this question has not been tackled in previous work. We show, perhaps surprisingly, that the answer crucially depends on the choice of the step size. In particular, for the range of step sizes which are known to result in monotonic convergence to an optimal value, we characterize a regime where the optimization curve will be provably convex, and a regime where the curve can be non-convex. We also extend our results to gradient flow, and to the closely-related but different question of whether the gradient norm decreases monotonically.