Snake: A Stochastic Proximal Gradient Algorithm for Regularized Problems Over Large Graphs

DOI10.1109/TAC.2019.2890888zbMATH Open1482.90156WikidataQ128686398 ScholiaQ128686398MaRDI QIDQ5223690FDOQ5223690

Authors: Adil Salim, Pascal Bianchi, W. Hachem 

Publication date: 18 July 2019

Published in: IEEE Transactions on Automatic Control (Search for Journal in Brave)

Abstract: A regularized optimization problem over a large unstructured graph is studied, where the regularization term is tied to the graph geometry. Typical regularization examples include the total variation and the Laplacian regularizations over the graph. When applying the proximal gradient algorithm to solve this problem, there exist quite affordable methods to implement the proximity operator (backward step) in the special case where the graph is a simple path without loops. In this paper, an algorithm, referred to as "Snake", is proposed to solve such regularized problems over general graphs, by taking benefit of these fast methods. The algorithm consists in properly selecting random simple paths in the graph and performing the proximal gradient algorithm over these simple paths. This algorithm is an instance of a new general stochastic proximal gradient algorithm, whose convergence is proven. Applications to trend filtering and graph inpainting are provided among others. Numerical experiments are conducted over large graphs.

Full work available at URL: https://arxiv.org/abs/1712.07027

Recommendations

• Graph-dependent implicit regularisation for distributed stochastic subgradient descent
• Proximal gradient methods for general smooth graph total variation model in unsupervised learning
• Stochastic Proximal Gradient Consensus Over Random Networks
• Proximal Regularization for the Saddle Point Gradient Dynamics
• Stochastic proximal gradient method FOR \(\ell_1\) regularized optimization over a sphere
• SnapVX: a network-based convex optimization solver
• A proximal stochastic gradient method with progressive variance reduction
• Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs
• Convergences of regularized algorithms and stochastic gradient methods with random projections

Mathematics Subject Classification ID

Convex programming (90C25) Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Cited In (5)

• New nonasymptotic convergence rates of stochastic proximal point algorithm for stochastic convex optimization
• Sub-linear convergence of a stochastic proximal iteration method in Hilbert space
• Sublinear convergence of a tamed stochastic gradient descent method in Hilbert space
• Dualize, split, randomize: toward fast nonsmooth optimization algorithms
• Stochastic proximal splitting algorithm for composite minimization

This page was built for publication: Snake: A Stochastic Proximal Gradient Algorithm for Regularized Problems Over Large Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5223690)