betaFeedback

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 O(K−1/3)O(K^{-1/3}) bound without a distance-bound assumption. A level-set distance bound gives an all-iteration O(1/K)O(1/K) rate with calibrated radii and an asymptotic O(log⁡K/K)O(\log K/K) 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.

Paper details

vlnc:W_vs9npqw2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…