TL;DR
This paper provides a collection of counterexamples to fundamental questions in smooth convex optimization, demonstrating that several standard algorithms and theoretical properties do not hold as generally assumed. The authors construct novel smooth convex functions and sequences of sets to show that methods like gradient descent, block coordinate descent, and Newton's flow may fail to converge, and that certain desirable properties like the Kurdyka-Łojasiewicz inequality may not hold.
What Problem Does This Paper Address?
Convex optimization is a cornerstone of many fields, and a significant amount of research has focused on developing algorithms with guaranteed convergence properties and understanding the theoretical underpinnings of these methods. While many positive results exist, there are still fundamental questions about the behavior of optimization algorithms and the properties of convex functions, even in the relatively simple setting of smooth, coercive functions. For instance, does steepest descent with exact line search always converge? Does Newton's flow converge? Do central paths converge? This paper aims to answer these questions by providing counterexamples, showing that the convergence and desirable properties we often assume are not universally guaranteed.
Methods
The authors' approach relies on constructing specific smooth convex functions and sequences of convex sets. A key tool is a general $C^k$ interpolation theorem for positively curved convex sets. This theorem allows them to build a smooth convex function whose sublevel sets are a given sequence of convex sets, and importantly, whose Hessian is positive definite outside the solution set. They also develop a discrete approximate interpolation result for sequences of polygons, enabling the construction of smooth convex functions that interpolate vertices with prescribed normals. These constructions are achieved through techniques like parametrization, Minkowski summation, Bernstein approximation, and convex analysis.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Ubiquitous Failure of Convergence: The paper demonstrates that several seemingly robust optimization algorithms, including gradient descent with exact line search, block coordinate descent, and Newton's flow, can fail to converge even for smooth convex functions. This highlights the importance of carefully analyzing algorithm behavior beyond simple cases.
- Breakdown of Theoretical Properties: The authors show that fundamental theoretical properties, such as the Kurdyka-Łojasiewicz inequality and the finite length of Tikhonov regularization paths, do not hold universally for smooth convex functions. This challenges assumptions that might have been implicitly made in prior work.
- The Power of Construction: The paper's strength lies in its constructive approach. By carefully crafting specific mathematical objects (smooth functions and sets), the authors provide concrete counterexamples, moving beyond abstract arguments.
- Curvature as a Key Factor: The paper suggests that oscillations in curvature can be a primary cause for the observed pathological behaviors, underscoring the subtle role of geometric properties in optimization.
Key Results
The paper presents nine counterexamples, categorized into structural, algorithmic, and continuous-time ODE counterexamples. These include:
- A $C^k$ convex function that does not satisfy the Kurdyka-Łojasiewicz inequality.
- A $C^k$ convex function whose Tikhonov regularization path has infinite length.
- A $C^k$ convex function for which block coordinate descent and gradient descent with exact line search do not converge.
- A $C^k$ convex function for which Newton's flow does not converge.
- A $C^k$ convex function where gradient curves at infinity do not converge directionally.
- A $C^k$ convex function for which Bregman descent may not converge.
- A $C^k$ convex function for which central paths of Legendre barriers may not converge.
- A $C^k$ convex function for which Hessian Riemannian gradient dynamics may not converge.
Limitations and Future Work
The authors acknowledge that their results are primarily for functions in $\mathbb{R}^2$. They suggest that generalizing these counterexamples to higher dimensions might be a delicate question. The paper also opens up avenues for further research by posing questions about the behavior of dual methods and exploring more general nonconvex cases. The extensive list of references also points to related areas of research that could benefit from these findings.
Summary updated