Pointwise Lipschitz Continuous Graph Algorithms via Proximal Gradient Analysis

In many real-world applications, it is prohibitively expensive to drastically change the solution to a problem after a small perturbation in the environment. Therefore, the stability of an algorithm is a very desirable property. In this paper, we study the class of pointwise Lipschitz continuous alg...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-07
Main Authors: Liu, Quanquan C, Velegkas, Grigoris, Yoshida, Yuichi, Zhou, Felix
Format: Article
Language:English
Subjects:
Algorithms
Graph theory
Integer programming
Lower bounds
Matching
Perturbation
Stability analysis
Tightness
Trajectory analysis
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In many real-world applications, it is prohibitively expensive to drastically change the solution to a problem after a small perturbation in the environment. Therefore, the stability of an algorithm is a very desirable property. In this paper, we study the class of pointwise Lipschitz continuous algorithms as introduced in the recent work of Kumabe and Yoshida [FOCS'23]. The Lipschitz constant of an algorithm, intuitively, bounds the ratio of the changes in its output (measured in \(\ell_1\) distance) over the \(\ell_1\) perturbations of the weights of the underlying graph. In this work, we give a general and simple framework for bounding the Lipschitz constant of algorithms measured through the unweighted \(\ell_1\) distance of their outputs. Our approach consists of three main steps. First, we consider a natural continuous relaxation of the underlying graph problem by adding a smooth and strongly convex regularizer to the objective function. Then, we give upper bounds on the \(\ell_1\) distance of the optimal solutions of the convex programs, under small perturbations of the weights, via a stability analysis of the trajectory of the proximal gradient method. Finally, we present new problem-specific rounding techniques to obtain integral solutions to several graph problems that approximately maintain the stability guarantees of the fractional solutions. We apply our framework to a number of problems including minimum \(s\)-\(t\) cut, densest subgraph, maximum \(b\)-matching, and packing integer programs. To complement our algorithms, we show the tightness of our results for certain problems by establishing tight lower bounds.
ISSN:2331-8422