Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness

What the math gives to ML

The paper gives a sharp finite-sum complexity law showing that the useful restart schedule for PAGE depends qualitatively on whether the PL condition number is below or above the square-root sample-size threshold. This is transferable as a condition-number-aware variance-reduced optimizer schedule: use frequent exact refreshes and short inner phases for well-conditioned problems, but retain the longer square-root-scaled PAGE regime for ill-conditioned problems. The dense weak-hiding construction also supplies a principled adversarial benchmark in which individual component gradients reveal little while their exact average preserves the optimization signal.