{"ID":2870783,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.11657","arxiv_id":"2509.11657","title":"Improved Rates for Stochastic Variance-Reduced Difference-of-Convex Algorithms","abstract":"In this work, we propose and analyze DCA-PAGE, a novel algorithm that integrates the difference-of-convex algorithm (DCA) with the ProbAbilistic Gradient Estimator (PAGE) to solve structured nonsmooth difference-of-convex programs. In the finite-sum setting, our method achieves a gradient computation complexity of $O(N + N^{1/2}\\varepsilon^{-2})$ with sample size $N$, surpassing the previous best-known complexity of $O(N + N^{2/3}\\varepsilon^{-2})$ for stochastic variance-reduced (SVR) DCA methods. Furthermore, DCA-PAGE readily extends to online settings with a similar optimal gradient computation complexity $O(b + b^{1/2}\\varepsilon^{-2})$ with batch size $b$, a significant advantage over existing SVR DCA approaches that only work for the finite-sum setting. We further refine our analysis with a gap function, which enables us to obtain comparable convergence guarantees under milder assumptions.","short_abstract":"In this work, we propose and analyze DCA-PAGE, a novel algorithm that integrates the difference-of-convex algorithm (DCA) with the ProbAbilistic Gradient Estimator (PAGE) to solve structured nonsmooth difference-of-convex programs. In the finite-sum setting, our method achieves a gradient computation complexity of $O(N...","url_abs":"https://arxiv.org/abs/2509.11657","url_pdf":"https://arxiv.org/pdf/2509.11657v1","authors":"[\"Anh Duc Nguyen\",\"Alp Yurtsever\",\"Suvrit Sra\",\"Kim-Chuan Toh\"]","published":"2025-09-15T07:52:31Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}