math.OCApr 8, 2026

Continuous-Time Dynamics of the Difference-of-Convex Algorithm

Authors: Yi-Shuai Niu

Organizations: Beijing Institute of Mathematical Sciences and Applications (BIMSA), Beijing, China

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We study the continuous-time structure of the difference-of-convex algorithm (DCA) for smooth DC decompositions with a strongly convex component. In dual coordinates, classical DCA is exactly the full-step explicit Euler discretization of a nonlinear autonomous system. This viewpoint motivates a damped DCA scheme, which is also a Bregman-regularized DCA variant, and whose vanishing-step limit yields a Hessian-Riemannian gradient flow generated by the convex part of the decomposition. For the damped scheme we prove monotone descent, asymptotic criticality, Kurdyka-Lojasiewicz convergence under boundedness, and a global linear rate under a metric DC-PL inequality. For the limiting flow we establish an exact energy identity, asymptotic criticality of bounded trajectories, explicit global rates under metric relative error bounds, finite-length and single-point convergence under a Kurdyka-Lojasiewicz hypothesis, and local exponential convergence near nondegenerate local minima. The analysis also reveals a global-local tradeoff: the half-relaxed scheme gives the best provable global guarantee in our framework, while the full-step scheme is locally fastest near a nondegenerate minimum. Finally, we show that different DC decompositions of the same objective induce different continuous dynamics through the metric generated by the convex component, providing a geometric criterion for decomposition quality and linking DCA with Bregman geometry.

More in this topic

Nonconvex Optimization

Nonconvex optimization develops methods for problems whose objectives or constraints can have multiple local optima, saddle points, or nonsmooth structure.

See all 145 papers

Explore similar work

CardsList
May 22, 2026

RA-DCA: A Randomized Active-Set DCA for Directional Stationarity in Max-Structured DC Programs

We study nonsmooth difference-of-convex programs whose subtracted convex term is a finite maximum of smooth convex functions. In this setting, standard DCA iterations may converge to critical points that are not directionally stationary, whereas exact active-vertex screening can be expensive when active sets are large or combinatorial. We propose RA-DCA, a vertex-first randomized active-set DCA that projects active gradients onto sampled directions, checks a sampled vertex residual, and uses a small linear program only as a low-residual convex-combination fallback. The method preserves the descent structure of DCA and reduces the randomized screening layer to matrix multiplications. Under the stated regularity, numerical active-set consistency, and random-embedding assumptions, every accumulation point generated by the safeguarded method is directionally stationary with probability one. MATLAB experiments first test the theorem on degenerate max-affine, max-quadratic, and sparse support-function models, where the safeguard avoids nonstationary critical points and closely tracks a full active-vertex scan. Block top-k tests then show that the same screening idea remains useful when exact aggregate enumeration is combinatorial. Trimmed-regression, complementarity, and QUBO diagnostics separate cases where active-set selection helps from cases dominated by multistart search, the DC split, or other problem-specific features.

Yi-Shuai Niu

Beijing Institute of Mathematical Sciences and Applications (BIMSA), Beijing, China

Nonconvex Optimization
AskPDF
Jun 15, 2026

Accelerated Convex Optimization via Hamiltonian Dynamics with Deterministic Integration Time

We develop Hamiltonian dynamics-based algorithms for smooth convex optimization that achieve accelerated rates of convergence. By exploiting contraction of averaged Hamiltonian flow trajectories rather than requiring contraction at trajectory endpoints, we show that Hamiltonian dynamics-based optimization methods admit deterministic and accelerated convergence guarantees, extending prior work that is limited to quadratic objectives or holds only in expectation. We analyze an idealized continuous-time algorithm and derive practical discrete-time implementations with optimal first-order complexity, thereby establishing Hamiltonian dynamics as a useful algorithmic primitive for deterministic accelerated convex optimization.

Xiuyuan Wang, Vishwak Srinivasan, Qiang Fu +3

Department of Computer Science, Yale University · Department of EECS, Massachusetts Institute of Technology

Hamiltonian Dynamics
AskPDF
Oct 20, 2025

Stochastic Difference-of-Convex Optimization with Momentum

We study the online stochastic difference-of-convex (DC) program min⁡x∈RnF(x)=G(x)−H(x)+r1(x)−r2(x)\min_{x \in R^n} F(x) = G(x) - H(x) + r_1(x) - r_2(x), which covers sparse learning with nonconvex penalties, robust regression with smooth robust losses, and non-negative positive--unlabeled learning. We propose momentum-based DCA (MDCA), which combines a damped DCA step with a momentum estimator for ∇H\nabla H and uses a constant per-iteration batch size. With exact solutions of the convex subproblems, MDCA with Polyak momentum uses O(ε−4)\mathcal{O}( ε^{-4}) stochastic gradients of HH to reach εε-stationarity, and momentum-based variance reduction (MVR) uses O(ε−3)\mathcal{O}(ε^{-3}) under averaged smoothness, with a single O(ε−1)\mathcal O(ε^{-1}) warm-up batch in place of the periodic large batches of DCA-PAGE, whose εε-dependence it matches. We also introduce a single-loop variant (S-MDCA) that replaces the subproblem solve by one stochastic prox-gradient step; for every fixed smoothing parameter γγ for which the separately smoothed surrogate FγF_γ is bounded below, it reaches εε-stationarity of FγF_γ in O(ε−4)\mathcal{O}(ε^{-4}) iterations, which does not by itself imply stationarity of FF. A variance--drift trade-off lemma describes how the momentum parameter trades estimator variance against iterate-drift bias in steady-state upper bounds. Guarantees are given for two criteria: the critical-distance measure, and a DCA fixed-point residual that requires no smoothness of r2r_2 and vanishes exactly at DC-critical points; both give the same εε-dependence. Experiments on two LIBSVM classification datasets illustrate the methods' behaviour.

El Mahdi Chayti, Martin Jaggi

Machine Learning and Optimization Laboratory (MLO), EPFL

Nonconvex OptimizationNonconvex Stochastic OptimizationStochastic Optimization ConvergenceMomentum Methods
AskPDF