Trajectory-Restricted Optimization Conditions and Geometry-Aware Linear Convergence

• URL: http://arxiv.org/abs/2604.17067v1
• Date: Sat, 18 Apr 2026 17:02:06 GMT
• Title: Trajectory-Restricted Optimization Conditions and Geometry-Aware Linear Convergence
• Abstract summary: We develop a trajectory-restricted framework for linear convergence based on localized geometric regularity.<n>We show that classical convergence guarantees extend under these localized conditions.<n>Our work provides a geometric quantification for fast local convergence after active-set or manifold identification.
• Score: 0.764671395172401
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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--Łojasiewicz 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.

Related papers

• Yau's Affine Normal Descent: Algorithmic Framework and Convergence Analysis [0.30222726571099656]
  Yau's Affine Normal Descent (YAND) is a geometric framework for smooth unconstrained optimization.<n>We show that affinenormal directions are robust under affine scalings, remaining insensitive to arbitrarily ill-conditioned transformations.
  arXiv  Detail & Related papers  (2026-03-30T13:55:11Z)
• Non-Euclidean Broximal Point Method: A Blueprint for Geometry-Aware Optimization [55.002497070656624]
  Broximal Point Method (BPM) offers an idealized optimization framework based on iteratively minimizing the objective function over norm balls centered at the current iterate.<n>It enjoys striking global convergence guarantees, converging linearly and in a finite number of steps for proper, closed and convex functions.<n>In this note, we ask whether the convergence theory of BPM can be extended to this more general, non-Euclidean setting.
  arXiv  Detail & Related papers  (2025-10-01T12:32:52Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  This paper establishes new convergence results for textitgeodesic strongly monotone games.<n>Our key result shows that RGD attains last-iterate linear convergence in a textitgeometry-agnostic fashion.<n>Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
  We show that Adam converges to $epsilon$-stationary points with $O(epsilon-4)$ gradient complexity under far more realistic conditions. We also propose a variance-reduced version of Adam with an accelerated gradient complexity of $O(epsilon-3)$.
  arXiv  Detail & Related papers  (2023-04-27T06:27:37Z)
• The rate of convergence of Bregman proximal methods: Local geometry vs. regularity vs. sharpness [29.642830843568525]
  We show that the convergence rate of a given method depends sharply on its associated Legendre exponent.<n>In particular, we show that boundary solutions exhibit a stark separation between methods with a zero and non-zero Legendre exponent.
  arXiv  Detail & Related papers  (2022-11-15T10:49:04Z)
• Geometry and convergence of natural policy gradient methods [0.0]
  We study the convergence of several natural policy gradient (NPG) methods in infinite-horizon discounted Markov decision processes with regular policy parametrizations. For a variety of NPGs and reward functions we show that the trajectories in state-action space are solutions of gradient flows with respect to Hessian geometries.
  arXiv  Detail & Related papers  (2022-11-03T19:16:15Z)
• On Asymptotic Linear Convergence of Projected Gradient Descent for Constrained Least Squares [22.851500417035947]
  This manuscript presents a unified framework for the analysis of projected gradient descent in the context of constrained least squares. We present a recipe for the convergence analysis of PGD and demonstrate it via a beginning-to-end application of the recipe on four fundamental problems.
  arXiv  Detail & Related papers  (2021-12-22T09:49:51Z)
• Proximal Gradient Descent-Ascent: Variable Convergence under K{\L} Geometry [49.65455534654459]
  The finite descent-ascent parameters (GDA) has been widely applied to solve minimax optimization problems. This paper fills such a gap by studying the convergence of the KL-Lized geometry.
  arXiv  Detail & Related papers  (2021-02-09T05:35:53Z)
• Curvature-Dependant Global Convergence Rates for Optimization on Manifolds of Bounded Geometry [6.85316573653194]
  We give curvature-dependant convergence rates for weakly convex functions defined on a manifold of 1-bounded geometry. We compute these bounds explicitly for some manifold commonly used in the optimization literature. We present self-contained proofs of fully general bounds on the norm of the differential of the exponential map.
  arXiv  Detail & Related papers  (2020-08-06T08:30:35Z)
• The Convergence Indicator: Improved and completely characterized parameter bounds for actual convergence of Particle Swarm Optimization [68.8204255655161]
  We introduce a new convergence indicator that can be used to calculate whether the particles will finally converge to a single point or diverge. Using this convergence indicator we provide the actual bounds completely characterizing parameter regions that lead to a converging swarm.
  arXiv  Detail & Related papers  (2020-06-06T19:08:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.