Research map / Optimization / Nonconvex and smooth optimization
A Bregman Proximal Stochastic Gradient Method with Extrapolation for Nonconvex Nonsmooth Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes BPSGE, a Bregman proximal stochastic gradient method with extrapolation for nonconvex nonsmooth problems lacking global Lipschitz gradients, with convergence and O(1/eps^2) complexity analysis and experiments on NMF and matrix factorization.
Problem
Minimizing a differentiable nonconvex function without a global Lipschitz continuous gradient plus a nonconvex nonsmooth regularizer, at large scale where full gradients are costly.
Approach
Combines a Bregman proximal stochastic gradient step with inertial extrapolation (with extrapolation parameter chosen to satisfy a Bregman-distance condition), using variance-reduced gradient estimators (SGD, SAGA, SARAH) and only smooth adaptivity of the differentiable part.
Key results
- On graph regularized NMF clustering, BPSGE-SAGA reaches 89.37% on COIL20 vs 75.56% for BPG and 85.33% for BPSG-SGD (BPSGE-SAGA/SARAH variants outperform non-extrapolated counterparts).
- Theory: BPSGE needs at most O(epsilon^-2) iterations in expectation to reach an epsilon-stationary point under C = R^d and variance-reduction conditions.
- Extrapolation variants (BPGE, BPSGE) consistently outperform non-extrapolated BPG/BPSG in the reported NMF, weakly-convex MF, and sparsity-constrained NMF experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add extrapolation to BPSG-SGD (ablation) | BPSG-SGD · COIL20, PIE, COIL100, TDT2 | clustering accuracy: 85.33 -> 87.48; 84.27 -> 87.79; 76.25 -> 82.24; 77.92 -> 85.21 | Helped |
| Add extrapolation to BPSG-SARAH (ablation) | BPSG-SARAH · COIL20, PIE, COIL100, TDT2 | clustering accuracy: 85.83 -> 89.37; 87.79 -> 88.45; 82.24 -> 84.02; 85.21 -> 87.42 | Helped |
| Add extrapolation to BPSG-SAGA (ablation) | BPSG-SAGA · COIL20, PIE, COIL100, TDT2 | clustering accuracy: 87.48 -> 89.97; 88.45 -> 88.83; 82.46 -> 84.29; 85.22 -> 87.54 | Helped |
| Add extrapolation to BPG (ablation) | BPG · COIL20, PIE, COIL100, TDT2 | clustering accuracy: 75.56 -> 85.47; 77.21 -> 86.03; 73.06 -> 82.23; 68.08 -> 85.04 | Helped |
Limitations
- Global convergence and complexity analysis requires C = R^d and bounded iterates
- Experiments limited to three matrix factorization-style applications implemented in Matlab
- Extrapolation parameter condition (5) is not verified in experiments; fixed beta_k = 0.6(k-1)/(k+2) used instead
Experimental setup
Datasets: COIL20 PIE COIL100 TDT2 ORL Yale-B
Benchmarks: COIL20 PIE COIL100 TDT2 ORL Yale-B
Metrics: clustering accuracy objective value
Baselines: BPG BPSG-SGD BPSG-SAGA BPSG-SARAH BPGE
Builds on: Bregman proximal gradient (BPG) BPGE BPSG SAGA SARAH
Closest papers by meaning
- A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization (NeurIPS 2018 · similarity 0.91)
- Proximal Stochastic Methods for Nonsmooth Nonconvex Finite-Sum Optimization (NeurIPS 2016 · similarity 0.90)
- Fast Stochastic Bregman Gradient Methods: Sharp Analysis and Variance Reduction (ICML 2021 · similarity 0.89)
- Convergence Analysis of Proximal Gradient with Momentum for Nonconvex Optimization (ICML 2017 · similarity 0.88)
- Stochastic Newton Proximal Extragradient Method (NeurIPS 2024 · similarity 0.88)
- Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.