CS Paper Radar

Difference-of-Convex Regularization for Graph Learning by Differentiable Programming

Liping Tao, Chee Wei Tan

cs.LG math.OC ·submitted 2026-08-13 03:10 UTC · v2

Abstract

Laplacian-regularized minimization is fundamental in signal processing and machine learning, but explicit construction of the dense graph Laplacian pseudoinverse can be computationally expensive. To address this issue, we consider the setting where the graph Laplacian is given and propose a Difference-of-Convex Regularizer (DCR) graph learning framework that learns a reusable approximation of the pseudoinverse action through regularized Maximum Likelihood Estimation (MLE) and shrinkage-regularized Convex--Concave Procedure (CCCP) iterations. For Laplacian-Regularized Nonnegative Least Squares (LR-NNLS), dual and Karush-Kuhn-Tucker (KKT) analysis motivates separating graph-dependent pseudoinverse learning from instance-specific optimization. The learned pseudoinverse is embedded into a differentiable primal optimization procedure as a graph-aware preconditioner for nonnegative reconstruction and can be reused across LR-NNLS instances sharing the same graph. We establish stability and fixed-point existence guarantees for the proposed pseudoinverse-learning iteration. Experiments across different graph topologies and scales demonstrate near-reference accuracy, competitive time-to-moderate-accuracy behavior, and effective cross-instance reuse across independently generated problem instances sharing the same graph.

Closest papers

Nearest neighbours by meaning across the whole index.

Riemannian Difference-of-Convex Optimization for K-Means Clustering

cs.LG math.OC ·2026-09-28 ·Meng Xu, Bo Jiang, Hanfu Zhang, Ya-Feng Liu, Anthony Man-Cho So
similarity 0.69
Abstract · 5 pages

K-means is a widely adopted clustering approach in signal processing and machine learning. In this paper, we study K-means clustering through a cardinality-constrained formulation on a compact embedded submanifold. We replace the cardinality constraint with a difference-of-convex (DC) penalty and establish a global error bound to prove that the penalized and constrained formulations share the same global minimizers whenever the penalty parameter exceeds a finite threshold. To solve the resulting nonsmooth Riemannian DC problem, we reformulate it as a minimax problem and propose RADA-DC, a Riemannian alternating descent ascent method combining dual regularization with DC linearization. Under standard assumptions and suitable parameter choices, RADA-DC finds an $ε$-Riemannian critical point within $O(ε^{-3})$ iterations. We conduct experiments on synthetic and real-world datasets to demonstrate that the proposed method outperforms the tested baselines, including K-means++, in solution quality at competitive computational cost when the number of clusters is large.

0.13

Graph Learning with Spectral Connectivity Priors for Scarce Data

cs.LG eess.SP ·2026-09-23 ·Mingxiao Liu, Bahar Oveisgharan, Bingyan Zou, Gene Cheung, H. Vicky Zhao +1 more
similarity 0.68
Abstract · 5 pages, 1 figure. Submitted to IEEE ICASSP 2027

Learning a sparse graph from scarce data is practically important but challenging. Motivated by the desirable combination of local sparsity and strong global connectivity exhibited by expander-like graphs, we propose spectral connectivity-regularized graph learning (SCoGL), a framework that incorporates a family of Laplacian spectral priors to explicitly promote global connectivity. Specifically, SCoGL augments a combinatorial-Laplacian-constrained graphical lasso (GLASSO) objective over a target adjacency matrix $\mathbf{W}$ with a general connectivity prior computed from Laplacian eigenvalues. We derive gradients for several representative connectivity priors and develop a projected gradient descent (PGD) algorithm with Armijo backtracking to efficiently optimize $\mathbf{W}$. Experiments show that the proposed SCoGL variants improve graph recovery and enhance downstream tasks such as graph signal denoising when signal observations are scarce.

0.24

Learning Variable Metrics for Convergent Proximal Splitting Algorithms

eess.IV ·2026-10-15 ·Yodai Suzuki, Shunsuke Ono
similarity 0.66
Abstract

We propose learned variable metric (LVM), a framework that learns metrics of proximal splitting algorithms adapted to each problem instance, coordinate, and iteration with a convergence guarantee. Proximal splitting algorithms can solve a wide variety of convex optimization problems but often require many iterations to converge. Choosing a suitable metric is an effective remedy, and variable metric theory naturally extends convergence guarantees to metrics that vary over the iterations. Learning is a promising way to design such adaptive metrics beyond the reach of manual design, but a naive implementation leads to (i) an expensive evaluation of a network at every iteration and (ii) difficulty in satisfying the conditions that the theory imposes on the whole infinite sequence of metrics. To resolve these difficulties, we first train a neural network to generate a few representative metrics once per problem instance, and then obtain the metric of every iteration by combining them with basis functions of the normalized iteration index. We present LVM for the proximal gradient method with a quadratic term and the primal-dual hybrid gradient method, and prove their convergence under a mild spectral condition, which is ensured by a rescaling of the representative metrics. In experiments on deblurring and inpainting, LVM reduces the number of iterations to reach a target accuracy in most tested settings compared with several baselines, and the computation time at high accuracies.

0.16

Explaining f-Divergence-Based Regularization via Local Curvature and Sharpness-Aware Minimization

cs.LG cs.IT ·2026-09-08 ·Nour Jamoussi, Marios Kountouris
publishedbenchmark similarity 0.65
Abstract · Published at 5th Conference on Lifelong Learning Agents (CoLLAs), 2026

Divergence-based regularization and Sharpness-Aware Minimization (SAM) are two prominent approaches for improving generalization in deep learning, both motivated by robustness to perturbations. However, their relationship has remained largely unexplored. Building on classical second-order expansions of $f$-divergences, we show that the two methods are locally consistent under parameter-space perturbations: both induce curvature-sensitive penalties, with divergence regularization yielding a Fisher-weighted quadratic form and SAM penalizing sharpness through the dominant Hessian eigenvalue. For negative log-likelihood objectives with exponential-family output distributions, this correspondence becomes especially transparent, since the Fisher and Gauss-Newton matrices coincide. We further show that the same local geometric perspective extends to input-space perturbations, where divergence-based regularization is defined through transformations of the input. In this setting, the regularizer induces a pullback quadratic form on the input space, providing a more general perturbation framework than standard SAM while preserving the same local sensitivity interpretation. To validate the analysis empirically, we use the asymmetric $α$-skew Jensen-Shannon divergence (JSD) family as a controlled testbed. Its local curvature coefficient scales as $α(1-α)$ and is maximized at the symmetric point $α=\tfrac12$, which recovers the standard JSD. Loss-landscape visualizations in the input-perturbation regime show that stronger induced curvature penalization is associated with flatter local minima. Experiments on four benchmark datasets further demonstrate that both accuracy and negative log-likelihood are consistently best near this regime of maximal curvature penalization.

0.57

Nonnegative DAG Learning via Concomitant Estimation

eess.SP stat.ML ·2026-09-28 ·Madeline Navarro, Gonzalo Mateos, Samuel Rey
similarity 0.64
Abstract

We study the problem of learning directed acyclic graphs (DAGs) with nonnegative edge weights from observational data. We propose the Nonnegative and Concomitant (NoCo) DAG estimator, which jointly recovers the weighted graph structure and the exogenous noise variances in the linear structural equation model for the observations. Different from prior art, this noise-adaptive formulation blends a smoothed concomitant lasso criterion with a simpler log-determinant acyclicity constraint that exploits nonnegativity and yields a more benign optimization landscape. Specifically, nonnegative weights allow us to impose acyclicity directly on the adjacency matrix without elementwise squaring of its entries, thus avoiding the well-documented degeneracy of the Karush-Kuhn-Tucker conditions. Computationally, we develop a method of multipliers' algorithm that accommodates both homoscedastic and heteroscedastic noise profiles. Within each iteration, we use block successive convex approximation to minimize the augmented Lagrangian, alternating between proximal gradient steps for the adjacency matrix and closed-form updates for the noise scales. Simulated experiments demonstrate NoCo's improved structural and edge-weight recovery relative to competing methods in a variety of settings, highlighting the benefits of exploiting nonnegativity along with noise adaptivity.

0.42

Fast Graph Laplacian Estimation using Effective Resistance

eess.SP cs.LG ·2026-09-20 ·Christoffer Kjellson, Claudio Altafini, Emma Tegling
published similarity 0.64
Abstract

Inferring network topology from noisy node observations is a central problem in graph signal processing. In this paper, we consider Laplacian-constrained graph estimation for Gaussian Markov random fields, focusing on the underdetermined regime in which the number of samples is smaller than the number of graph nodes. Existing approaches often formulate the problem as a sparsity-regularized maximum-likelihood estimation problem. While effective, such methods typically require iterative optimization and are often computationally demanding, particularly under Laplacian constraints. Instead, we propose a non-iterative estimator of graph Laplacians that uses effective resistance for regularization, and evaluate the method using a simple sparsification procedure. Experiments show that with some trade-off in edge and weight recovery on the considered dataset, computational cost for moderately sized graphs can be substantially reduced.

0.29

Right Bregman proximal gradient with application to Poisson inverse problems *

eess.IV math.OC ·2026-10-05 ·Thibaut Modrzyk, Elie Bretin, Voichita Maxim
theorycode/data similarity 0.64
Abstract

We introduce a novel Bregman proximal algorithm for convex composite optimization by applying the standard Bregman proximal gradient (BPG) method to a mirror-coordinate reparameterization of the objective. In primal variables, the resulting algorithm alternates between a preconditioned gradient step followed by a right Bregman proximal update. Our analysis relies on relative smoothness holding in the mirror coordinates instead of primal coordinates. Under this condition, we prove monotonic decrease of the objective in the general convex setting. We then specialize the method to Poisson inverse problems using weighted negative entropy as the potential. The resulting scheme recovers the classical Richardson-Lucy multiplicative updates and extends them to general convex regularizers. Building on a recent convergence analysis of multiplicative updates, we establish a sublinear convergence rate in function values for the Poisson setting. Finally, we demonstrate the performance of the regularized algorithm on several imaging inverse problems with Poisson-distributed observations. The code is publicly available at https://github.com/Tmodrzyk/MU-Bregman.

0.30

Controlled Block Proximal Linearized Method for Nonconvex and Nonsmooth Optimization

cs.LG math.OC ·2026-10-25 ·Weifeng Yang
theory similarity 0.63
Abstract

We consider multiblock nonconvex and nonsmooth optimization without assuming bounded iterates or coercivity of the original objective. We propose the Controlled Block Proximal Linearized (CBPL) method, which incorporates a control potential into block updates while retaining the original objective, variables, and constraints. Under explicit control design conditions and the KL property, the control yields boundedness, finite length, whole-sequence convergence of the original variables, and convergence of objective values. At the limit, one limiting subgradient of the original objective vanishes on all effective comparison directions. We apply CBPL to graph-regularized nonnegative matrix factorization (NMF), CP decomposition, and independent-core matrix tri-factorization (NMTF) with $\ell_0$ norm sparsity constraints. We characterize their reconstruction-preserving scale degeneracies, proving that scale criticality is equivalent to graph collapse and that full criticality forces such collapse. Explicit controls provide compact sublevel sets and a uniform positive lower bound on graph action, including with an independent Tucker core, while retaining genuine reconstruction-changing directions. Each block admits an explicit projection and a computable safe step parameter. For ordinary NMF and CP models, whole-sequence convergence to a full critical point follows. Experiments with direct safe updates demonstrate convergence, sustained graph action, and controlled factor and core scales.

0.15