Research map / Optimization / Nonconvex and smooth optimization

The Multi-Block DC Function Class: Theory, Algorithms, and Applications

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Adaptive first-order convex methods · 0 citations (OpenAlex)

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.

Introduces the multi-block difference-of-convex (BDC) function class, shows it is exponentially more compact than DC for monomials, gives explicit BDC decompositions for deep ReLU networks with MSE/CE losses, and proposes proximal BDC algorithms with non-asymptotic convergence under generalized smoothness and stochastic gradients.

Problem

Standard difference-of-convex (DC) decompositions of nonconvex objectives are hard to find, often exponentially large, and non-constructive, which limits DC-based optimization for block-structured models such as deep networks and factorizations.

Approach

Relax the global DC requirement to a per-block DC decomposition (convex in each block with others fixed), show this class is strictly larger than DC and can be exponentially more compact, and derive constructive BDC forms (including layer-wise ReLU networks) with a block-wise proximal DCA that converges to Clarke-stationary points.

Key results

• For monomials, the minimum DC atom count grows as prod(b_i+1) while a BDC decomposition of theta1 theta2 theta3^2 theta4^4 uses 4 atoms vs at least 30 for DC.
• SBDC achieves test loss and accuracy comparable to SGD on Boston Housing regression and CIFAR10/FashionMNIST classification (10 Monte Carlo runs).
• For sparse dictionary learning with the l1-lq regularizer, BDCA converges faster and attains a lower objective than joint gradient descent on synthetic data.

Surprising findings

• Proximal BDC updates consistently reduce overfitting while achieving comparable test error to SGD in the neural network experiments.

Limitations

• Convergence analysis assumes boundedness of g_i along the trajectory, ensured indirectly by bounding h_i at update points.
• Generalized-smoothness analysis applies only to unconstrained BDC problems.
• Neural network experiments are a simple proof-of-concept ReLU network and do not compare with state-of-the-art training pipelines.

Experimental setup

Datasets: CIFAR10 FashionMNIST Boston Housing California Housing BSDS500 synthetic data

Benchmarks: CIFAR10 FashionMNIST Boston Housing BSDS500 synthetic sparse dictionary data

Metrics: test loss test accuracy reconstruction error proportion of zeros in codes Clarke stationarity residual

Baselines: SGD gradient descent l1 regularizer

Builds on: difference-of-convex algorithm (DCA) Waring rank (r,l)-smoothness alternating DC algorithm

Closest papers by meaning

• Discrete and Continuous Difference of Submodular Minimization (ICML 2025 · similarity 0.87)
• Coordinate Descent Methods for DC Minimization: Optimality Conditions and Global Convergence (AAAI 2023 · similarity 0.86)
• Deep Submodular Functions: Definitions and Learning (NeurIPS 2016 · similarity 0.86)
• Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergence (ICML 2019 · similarity 0.85)
• Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses (NeurIPS 2026 · similarity 0.85)
• Revisiting Frank-Wolfe for Structured Nonconvex Optimization (NeurIPS 2025 · similarity 0.85)