Curiosities and counterexamples in smooth convex optimization

Jérôme Bolte, Edouard Pauwels

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

Abstract

Counterexamples to some old-standing optimization problems in the smooth\nconvex coercive setting are provided. We show that block-coordinate, steepest\ndescent with exact search or Bregman descent methods do not generally converge.\nOther failures of various desirable features are established: directional\nconvergence of Cauchy's gradient curves, convergence of Newton's flow, finite\nlength of Tikhonov path, convergence of central paths, or smooth\nKurdyka-Lojasiewicz inequality. All examples are planar. These examples are\nbased on general smooth convex interpolation results. Given a decreasing\nsequence of positively curved C k convex compact sets in the plane, we provide\na level set interpolation of a C k smooth convex function where k $\\ge$ 2 is\narbitrary. If the intersection is reduced to one point our interpolant has\npositive definite Hessian, otherwise it is positive definite out of the\nsolution set. Furthermore , given a sequence of decreasing polygons we provide\nan interpolant agreeing with the vertices and whose gradients coincide with\nprescribed normals.\n
BibTeX
@article{bolte2020curiosities,
  author = {Jérôme Bolte and Edouard Pauwels},
  title = {{Curiosities and counterexamples in smooth convex optimization}},
  journal = {Math. Program.},
  year = {2020},
}
Figure