Primal-Dual Halpern-PAGE Algorithm for Constrained Stochastic Weakly Convex Optimization

Lixin Tang, Xingyu Wang, and, Liwei Zhang · 2026

Read Primal-Dual Halpern-PAGE Algorithm for Constrained Stochastic Weakly Convex Optimization by Lixin Tang, Xingyu Wang, and, Liwei Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-25355.txt.

Description

Many learning problems are nonconvex and nonsmooth yet still structured, and adding real world constraints stated as averages makes them harder again. Lixin Tang, Xingyu Wang, and Liwei Zhang propose a solver in 2026 that handles mixed equality and inequality constraints in one loop. Older approaches nest penalty loops inside the main algorithm and demand delicate tuning. Their primal dual method, built on Halpern iteration and a variance reduced gradient estimator, needs only one simple subproblem and one projection per step.

Despite that simplicity, the authors prove the method reaches the best possible sample complexity known for this problem class, matching theoretical lower bounds. For polyhedral domains they also prove the dual variables stay stable under a standard constraint qualification. That closes a gap where earlier guarantees held only under artificial caps on the error measure used to judge solutions.

Catalog record

CREATORLixin Tang, Xingyu Wang, and, Liwei Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE84 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.25355

Browse the full library · About the Tower of Babel