Research map / Optimization / Nonconvex and smooth optimization
Revisiting Frank-Wolfe for Structured Nonconvex Optimization
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 DC-FW, a projection-free method that applies Frank-Wolfe to subproblems of the DC Algorithm for difference-of-convex nonconvex problems, with decomposition-dependent variants (CGS-like and proximal point) for smooth nonconvex optimization.
Problem
Projection-free (Frank-Wolfe) optimization of nonconvex functions written as difference of two convex functions over a convex compact set, aiming for first-order stationarity with few gradient and linear minimization oracle calls.
Approach
Combine the DC Algorithm (linearize the concave part) with Frank-Wolfe as the inner subproblem solver; different DC decompositions of the same smooth objective yield distinct algorithms, e.g., a nonconvex conditional gradient sliding variant reusing gradients (O(1/eps) gradient calls) and an inexact proximal point variant.
Key results
- On 134 QAPLIB instances, DC-FW beat FW in 73 cases, lost in 43, and tied in 18, with average assignment error 0.0085 vs 0.0112 for FW.
- The gradient-efficient DC-FW variant achieves O(1/eps) gradient complexity and O(1/eps^2) LMO complexity for smooth nonconvex minimization, improving from O(1/eps^2) gradient calls of standard FW-based methods.
- On partially observed embedding alignment, DC-FW called the subgradient oracle 88 times versus 10^4 for FW-K and FW-M, and recovers 93.11% of the full-observation Procrustes alignment quality with 10% of target entries observed.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DC-FW instead of FW | QAP relax-and-round · QAPLIB (134 datasets) | average assignment error: 0.0112 -> 0.0085 | Helped |
| Use DC-FW instead of FW | QAP relax-and-round · QAPLIB (134 datasets) | assignment error across datasets: 73 out of 134 datasets; 18 cases equal; 43 datasets | Mixed |
| Use DC-FW for the partially observed embedding alignment problem | embedding alignment with spectral-norm constraint and negative nuclear-norm regularization · Partially observed embedding alignment (10% observed) | alignment quality relative to fully observed baseline: 93.11% | Helped |
| Use DC-FW instead of FW-K | partially observed embedding alignment · Partially observed embedding alignment | FW gap convergence | Helped |
| Reuse the subgradient across outer iterations with DC-FW instead of computing it every iteration | partially observed embedding alignment · Partially observed embedding alignment (10^4 iterations) | subgradient oracle calls: 10^4 -> 88 | Helped |
| Use DC-FW instead of FW-M | partially observed embedding alignment · Partially observed embedding alignment | iteration convergence rate | No clear effect |
| Increase the parameter bound c | FW neural-network training · CIFAR-10 and CIFAR-100 | convergence speed | Hurt |
| Increase the parameter bound c | DC-FW neural-network training · CIFAR-10 and CIFAR-100 | performance as c varies | No clear effect |
| Use DC-FW with L = 10 instead of FW | neural-network classification training · CIFAR-10 and CIFAR-100 | training and validation performance | Helped |
| Use the reported DC-FW variants instead of non-convex CGS or FW | QAP · QAP datasets | assignment error: 68.70 cases [66.17, 71.23] vs CGS; 46.40 cases [43.76, 49.04] in the reverse comparison | Helped |
Surprising findings
- Under strongly convex domains, DC-FW improves LMO complexity to O(1/eps^{3/2}) versus O(1/eps^2) for standard FW.
- The PGM gap treats minima, saddles and maxima similarly, while the PPM-based DC gap distinguishes them.
Limitations
- Analysis is deterministic; stochastic settings are left to future work.
- Practical gains depend on the adaptive inner-loop tolerance heuristic and decomposition choice, which lack theory.
- Oracles evaluated with full SVDs on a single CPU core; large-scale inexact oracles not benchmarked.
Experimental setup
Datasets: QAPLIB FastText English and French 300-d embeddings CIFAR-10 CIFAR-100
Benchmarks: QAPLIB FastText word embedding alignment CIFAR-10 CIFAR-100
Metrics: assignment error FW gap number of SVD / LMO calls wall clock time top-1 accuracy cross-entropy loss alignment quality relative to Procrustes
Baselines: Frank-Wolfe (FW) FW-K (DC FW of Khamaru-style subgradient FW) FW-M (FW with backtracking line search for DC) Non-convex CGS relax-and-round FW
Builds on: DC Algorithm (DCA) Frank-Wolfe algorithm Conditional Gradient Sliding
Closest papers by meaning
- Fast Frank–Wolfe Algorithms with Adaptive Bregman Step-Size for Weakly Convex Functions (ICLR 2026 · similarity 0.91)
- Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets (AAAI 2019 · similarity 0.90)
- A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates (ICML 2017 · similarity 0.90)
- Frank-Wolfe Beyond 1/t Convergence (NeurIPS 2026 · similarity 0.88)
- Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features (ICML 2024 · similarity 0.88)
- Zeroth-Order Methods for Constrained Nonconvex Nonsmooth Stochastic Optimization (ICML 2024 · 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.