Research map / Optimization / Nonconvex and smooth optimization
ADMM for Nonconvex Optimization under Minimal Continuity Assumption
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 IPDS-ADMM, a proximal linearized ADMM with increasing penalty and decreasing Moreau-envelope smoothing, requiring continuity in only one block, and proves O(eps^-3) oracle complexity to an eps-critical point for nonconvex multi-block composite problems.
Problem
Multi-block nonconvex nonsmooth composite optimization with linear coupling constraints, where existing nonconvex ADMM methods require at least one block to be smooth; the paper also addresses relaxation stepsizes when the linear operator is bijective or surjective.
Approach
Combines an increasing penalty schedule beta^t = beta^0(1+xi t^p) with a decreasing Moreau-envelope smoothing mu^t ∝ 1/beta^t applied only to the last (convex, Lipschitz) block, inside a proximal linearized cyclic ADMM; uses over-relaxation (sigma in [1,2)) for bijective A_n and under-relaxation (sigma in (0,1)) for surjective A_n, with a novel potential function for analysis.
Key results
- IPDS-ADMM achieves an oracle complexity of O(eps^-3) to an eps-critical point, improving RADMM's O(eps^-4) for this class.
- In sparse PCA experiments on 8 datasets (rho=100), IPDS-ADMM consistently attains the lowest objective values versus SubGrad, SPGM and RADMM.
- Parameter choice p=1/3 gives the optimal trade-off between terms and yields T^{-1/3} average criticality rate.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the increasing-penalty and decreasing-smoothing strategy | ADMM for nonconvex composite optimization · epsilon-critical point | iteration complexity: \mathcal{O}(\epsilon^{-4}) to \mathcal{O}(\epsilon^{-3}) | Helped |
| Use IPDS-ADMM instead of SubGrad, SPGM, or RADMM | Sparse PCA · Sparse PCA | objective value | Helped |
Limitations
- Requires continuity/Lipschitz condition only on last block and convexity of h_n, restricting the class.
- Experiments limited to sparse PCA with a single algorithmic setup and MATLAB CPU implementation.
- Parameter choices depend on condition number kappa, which must be known or estimated.
Experimental setup
Datasets: randn synthetic data mnist TDT2 sector
Benchmarks: sparse PCA objective on randn, mnist, TDT2, sector datasets
Metrics: objective value vs. running time
Baselines: Subgradient method Smoothing Proximal Gradient Method (SPGM) RADMM
Builds on: ADMM Riemannian ADMM (RADMM) smoothing proximal gradient method
Closest papers by meaning
- A proximal ADMM for multiblock problems with block anti-upper triangular constraints (ICML 2026 · similarity 0.91)
- Linearized Alternating Direction Method with Penalization for Nonconvex and Nonsmooth Optimization (AAAI 2016 · similarity 0.91)
- Faster Stochastic Alternating Direction Method of Multipliers for Nonconvex Optimization (ICML 2019 · similarity 0.90)
- Optimizing ADMM and Over-Relaxed ADMM Parameters for Linear Quadratic Problems (AAAI 2024 · similarity 0.87)
- Adaptive Riemannian ADMM for Nonsmooth Optimization: Optimal Complexity without Smoothing (NeurIPS 2025 · similarity 0.86)
- ADMM for Structured Fractional Minimization (ICLR 2025 · similarity 0.86)
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.