Norm-Constrained Flows and Sign-Based Optimization: Theory and Algorithms

Abstract

Sign Gradient Descent (SignGD) uses only the coordinate-wise sign of the gradient. We study this method through norm-constrained continuous-time dynamics: at each point, the velocity is chosen to minimize the directional derivative over a unit norm ball. This recovers the sign flow for the ${\ell }_{\infty }$ constraint, normalized gradient flow for ${\ell }_2$, and greedy coordinate directions for ${\ell }_1$. We formulate the resulting dynamics as a set-valued differential inclusion, prove existence of solutions, and derive an exact energy identity. This identity also gives finite-time convergence under a Polyak-Lojasiewicz inequality expressed in the dual norm. We then connect the canonical set-valued flow with classical Filippov regularization of discontinuous selectors, which gives a precise description of crossing and sliding near switching sets. Motivated by this behavior, we introduce two face-aware SignGD variants, one-hit freeze and two-hit sliding-track. Both methods modify the usual sign direction by damping selected coordinates when a crossing or persistent switching is detected. We derive descent certificates for these damped sign directions and introduce a safeguard that preserves a global linear convergence rate under ${\ell }_{\infty }$-smoothness and a Polyak-Lojasiewicz inequality. For the ${\ell }_1$ flow, we also introduce convex-combination updates on active faces and prove a corresponding linear convergence guarantee. Finally, we analyze mass-aware face restrictions and an inertial SignGD method with restart. Numerical experiments illustrate the certified step rules, the face-aware variants, and the inertial scheme.