Research map / Optimization / Nonconvex and smooth optimization
ADMM for Structured Fractional Minimization
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 FADMM, the first ADMM for structured nonsmooth fractional minimization, with Dinkelbach (FADMM-D) and quadratic-transform (FADMM-Q) variants, proving O(1/eps^3) iteration complexity to epsilon-critical points.
Problem
Nonconvex nonsmooth fractional minimization of the form u(x)/d(x) where u is a differentiable function plus a simple nonconvex nonsmooth term, a concave nonsmooth term and a convex nonsmooth term composed with a linear operator, and d is weakly convex (or has weakly convex square root). Existing sub
Approach
Reformulate with a new splitting variable and Nesterov-smoothed convex term, then apply ADMM with linearized proximal (MM) subproblems, using Dinkelbach's parametric update or a quadratic transform for the ratio; a novel Lyapunov function gives convergence and complexity.
Key results
- FADMM-D and FADMM-Q reach the lowest objective values among SPM, SPGM, and FSA on sparse FDA across the eight datasets for rho in {10, 1000}.
- FADMM converges to an epsilon-critical point with oracle complexity O(1/epsilon^3) (p=1/3).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FADMM-D instead of SPM | Sparse FDA · Sparse FDA | objective value after 20 seconds | Helped |
| Use FADMM-Q instead of SPM | Sparse FDA · Sparse FDA | objective value after 20 seconds | Helped |
| Use FADMM-D instead of SPGM-D | Sparse FDA · Sparse FDA | objective value after 20 seconds | Helped |
| Use FADMM-Q instead of SPGM-Q | Sparse FDA · Sparse FDA | objective value after 20 seconds | Helped |
| Use FADMM-D instead of FSA | Sparse FDA · Sparse FDA | objective value after 20 seconds | Helped |
| Use FADMM-Q instead of FSA | Sparse FDA · Sparse FDA | objective value after 20 seconds | Helped |
| Use variable-smoothing SPGM-D instead of SPM | Sparse FDA · Sparse FDA | objective value after 20 seconds | Helped |
| Use variable-smoothing SPGM-Q instead of SPM | Sparse FDA · Sparse FDA | objective value after 20 seconds | Helped |
| Remove the dual-variable updates and smoothing by fixing z=0 and mu=0 (ablation) | FADMM-D · Sparse FDA | objective value after 20 seconds | Hurt |
| Remove the dual-variable updates and smoothing by fixing z=0 and mu=0 (ablation) | FADMM-Q · Sparse FDA | objective value after 20 seconds | Hurt |
Limitations
- Experiments are limited to sparse FDA in the main text; other applications are only in appendix.
- Convergence requires boundedness and lower bounds on d(x) and F(x) (Assumptions on d and F>0).
Experimental setup
Datasets: madelon TDT2 mnist mushroom gisette randn synthetic
Benchmarks: sparse FDA objective on 8 datasets
Metrics: objective value after fixed wall-clock time (20 s)
Baselines: SPM SPGM FSA
Builds on: ADMM Dinkelbach's parametric algorithm quadratic transform algorithm Nesterov smoothing
Closest papers by meaning
- Coordinate Descent Methods for Fractional Minimization (ICML 2023 · similarity 0.90)
- ADMM for Nonconvex Optimization under Minimal Continuity Assumption (ICLR 2025 · similarity 0.86)
- Adaptive Relaxed ADMM: Convergence Theory and Practical Implementation (CVPR 2017 · similarity 0.86)
- Revisiting Frank-Wolfe for Structured Nonconvex Optimization (NeurIPS 2025 · similarity 0.85)
- Decentralized Gradient-Free Methods for Stochastic Non-smooth Non-convex Optimization (AAAI 2024 · similarity 0.84)
- Efficient Continual Finite-Sum Minimization (ICLR 2024 · similarity 0.84)
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.