WorksMathematics
Broximal Gradient Descent in General Norms: Convergence without Fejér Monotonicity
Abstract
We study Broximal Gradient Descent in a general norm for smooth optimization over a closed convex set. Each update minimizes the linear model over the intersection of the feasible set and a norm ball. Unlike the Euclidean case with suitably restricted radii, the distance to a solution can increase, even when the squared norm is strongly convex. We instead use a comparator inequality and an observable stationarity certificate. For convex objectives, prescribed radii yield value convergence, including escape when the infimum is unattained, and a last-iterate bound without a distance-bound assumption. A level-set distance bound gives an all-iteration rate with calibrated radii and an asymptotic rate with radii using no problem constant. Strong convexity and power growth give explicit faster envelopes and convergence of the iterates. Without convexity, a constrained Polyak–Łojasiewicz inequality gives linear convergence with prescribed radii. An observable radius-halving rule needs a valid smoothness constant but neither the PL modulus nor an initial gap bound; warm starting gives logarithmic total oracle complexity in inverse accuracy. The analysis separates established local-oracle ingredients from the control of level sets, radius calibration, and accuracy-based oracle counts.