# Trajectory-Restricted Optimization Conditions and Geometry-Aware Linear Convergence

arXiv: https://arxiv.org/abs/2604.17067 · HTML: https://mlsanity.com/paper/2604.17067/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 66 references that are in the map.
- First posted on arXiv 18 Apr 2026.

## Builds on (most cited first, 17 of 17)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Error bounds, quadratic growth, and linear convergence of proximal methods](https://mlsanity.com/paper/1602.06661/) (2016)
- [From error bounds to the complexity of first-order descent methods for convex functions](https://mlsanity.com/paper/1510.08234/) (2015)
- [Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection](https://mlsanity.com/paper/1506.00552/) (2015)
- [A Unified Approach to Error Bounds for Structured Convex Optimization Problems](https://mlsanity.com/paper/1512.03518/) (2015)
- [The Training Process of Many Deep Networks Explores the Same Low-Dimensional Manifold](https://mlsanity.com/paper/2305.01604/) (2023)
- [Active manifolds, stratifications, and convergence to local minima in nonsmooth optimization](https://mlsanity.com/paper/2108.11832/) (2021)
- [Forward-backward quasi-Newton methods for nonsmooth optimization problems](https://mlsanity.com/paper/1604.08096/) (2016)
- [New characterizations of Hoffman constants for systems of linear constraints](https://mlsanity.com/paper/1905.02894/) (2019)
- ["Active-set complexity" of proximal gradient: How long does it take to find the sparsity pattern?](https://mlsanity.com/paper/1712.03577/) (2017)
- [Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods](https://mlsanity.com/paper/2312.16775/) (2023)
- [Path Length Bounds for Gradient Descent and Flow](https://mlsanity.com/paper/1908.01089/) (2019)
- [Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria](https://mlsanity.com/paper/1610.03446/) (2016)
- [Gradient Properties of Hard Thresholding Operator](https://mlsanity.com/paper/2209.08247/) (2022)
- [The restricted strong convexity revisited: Analysis of equivalence to error bound and quadratic growth](https://mlsanity.com/paper/1511.01635/) (2015)
- [An easily computable upper bound on the Hoffman constant for homogeneous inequality systems](https://mlsanity.com/paper/2302.02193/) (2023)

## Abstract (arXiv)

Linear convergence of first-order methods is typically characterized by global optimization conditions whose constants reflect worst-case geometry of the ambient space. In high-dimensional or structured problems, these global constants can be arbitrarily conservative and fail to capture the geometry actually encountered by optimization trajectories. In this paper, we develop a trajectory-restricted framework for linear convergence based on localized geometric regularity. We introduce restricted variants of the Polyak--Lojasiewicz inequality, error bound, and quadratic growth conditions that are required to hold only on subsets of the domain. We show that classical convergence guarantees extend under these localized conditions, and in key cases, we develop new arguments that yield explicit relationships between the corresponding constants. The resulting rates are governed by geometric quantities associated with the regions traversed by the algorithm. For polyhedral composite problems, we prove that convergence is controlled by restricted Hoffman constants corresponding to the active polyhedral faces visited along the trajectory. Once the iterates enter a well-conditioned face, the effective condition number improves accordingly. Our work provides a geometric quantification for fast local convergence after active-set or manifold identification and more broadly suggests that linear convergence is fundamentally governed by the geometry of the subsets explored by the algorithm, rather than by worst-case global conditioning.