Accelerating Level-Value Adjustment for the Polyak Stepsize

The Polyak stepsize formula has been widely used for subgradient methods for convex optimization. However, calculating the stepsize requires the optimal objective value, which is generally unknown. Dynamic estimations of the optimal objective value are thus usually needed. In this paper, to guarantee convergence, a series of level values is constructed to successively estimate the optimal objective value. This is achieved by developing a decision-based procedure through a novel easy-to-solve ``Polyak Stepsize Violation Detector'' (PSVD) linear constraint satisfaction problem. Once a violation is detected, the level value is recalculated. We rigorously establish convergence for level and objective values. Through a series of empirical tests of convex functions with diverse characteristics, we illustrate the practical advantages of our approach as compared to existing methods.