Adrian S. Lewis

The classical Euclidean subgradient algorithm extends, via tangent constructions and exponential maps, to geodesically convex optimization on manifolds. General complexity analysis for manifolds with an upper curvature bound of zero, as developed by Zhang and Sra in 2016 [Zhang H, Sra S (2016) First-order methods for geodesically convex optimization. Feldman V, Rakhlin A, Shamir O, eds. Proc. 29th Conf. Learn. Theory, vol. 49 (PMLR, New York), 1617–1638] depends unavoidably on an additional lower curvature bound. We present a fresh approach to subgradient-type methods, suitable for objectives with “horospherically convex” level sets. Our method avoids both tangential constructions in its description and lower curvature bounds in its complexity analysis. Furthermore, it applies beyond manifolds to general geodesic metric spaces with curvature nonpositive but possibly unbounded below. As applications in such spaces, which include CAT(0) cubical complexes such as the Billera–Holmes–Vogtmann space of phylogenetic trees, we consider previously inaccessible problems such as recognizing weighted Fréchet means and computing minimal enclosing balls. Funding: A. Goodwin was supported by the NSERC Postgraduate Fellowship [Grant PGSD-587671-2024]. A. S. Lewis was supported in part by the National Science Foundation [Grant DMS-2405685]. G. López-Acedo was supported in part by Dirección General de Enseñanza Superior e Investigación Científica (DGES) [Grants PID2023-148294NB-I00, PID-2024-156594NB, and CEX2024-00151-M]. A. Nicolae was supported in part by the Ministry of Research, Innovation and Digitization (CNCS/CCCDI – UEFISCDI) [Grant PN-III-P1-1.1-TE-2019-1306] within PNCDI III.

Variational analysis presents a unified theory encompassing in particular both smoothness and convexity. In a Euclidean space, convex sets and smooth manifolds both have straightforward local geometry. However, in the most basic hybrid case of feasible regions consisting of pre-images of convex sets under maps that are once (but not necessarily twice) continuously differentiable, the geometry is less transparent. We define a new approximate convexity property, that holds both for such feasible regions and also for all prox-regular sets. This new property requires that nearby points can always be joined by smooth feasible paths that are almost straight. In particular, in the terminology of real algebraic geometry, such feasible regions are locally normally embedded in the Euclidean space.

We study the impact of nonconvexity on the complexity of nonsmooth optimization, emphasizing objectives such as piecewise linear functions, which may not be weakly convex. We focus on a dimension-independent analysis, slightly modifying a 2020 black-box algorithm of Zhang-Lin-Jegelka-Sra-Jadbabaie that approximates an ϵ-stationary point of any directionally differentiable Lipschitz objective using [ ] calls to a specialized subgradient oracle and a randomized line search. Seeking by contrast a deterministic method, we present a simple black-box version that achieves [ ] for any difference-of-convex objective and [ ] for the weakly convex case. Our complexity bound depends on a natural nonconvexity modulus that is related, intriguingly, to the negative part of directional second derivatives of the objective, understood in the distributional sense. Funding: This work was supported by the National Science Foundation [Grant DMS-2006990].

Differentiable structure ensures that many of the basics of classical convex analysis extend naturally from Euclidean space to Riemannian manifolds. Without such structure, however, extensions are more challenging. Nonetheless, in Alexandrov spaces with curvature bounded above (but possibly positive), we develop several basic building blocks. We define subgradients via projection and the normal cone, prove their existence, and relate them to the classical affine minorant property. Then, in what amounts to a simple calculus or duality result, we develop a necessary optimality condition for minimizing the sum of two convex functions.