Pointwise Lipschitz Continuous Graph Algorithms via Proximal Gradient Analysis
<|reference_start|>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 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.<|reference_end|>
@article{liu2024pointwise,
    title={Pointwise Lipschitz Continuous Graph Algorithms via Proximal Gradient
  Analysis},
    author={Quanquan C. Liu, Grigoris Velegkas, Yuichi Yoshida, Felix Zhou},
    journal={arXiv preprint arXiv:2405.08938},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.08938},
    primaryClass={cs.DS}
}