Research map / Learning theory and algorithms / Sample complexity

Pointwise Lipschitz Continuous Graph Algorithms

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Private and query-efficient algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces proximal gradient trajectory analysis (PGTA) to bound pointwise Lipschitz constants of regularized LP relaxations, yielding optimal-Lipschitz minimum S-T cut and improved bipartite b-matching algorithms, plus the first dynamic min S-T cut with non-trivial recourse.

Problem

Stability of graph algorithms: outputs of min S-T cut and b-matching should change little (in expected symmetric difference) under small edge-weight perturbations, while maintaining approximation quality.

Approach

Analyze the stability of proximal gradient iterates for strongly convex regularized LP relaxations, which allows weighted (non-identical across perturbed instances) regularizers and yields linear-in-perturbation bounds, unlike prior first-order-condition analyses restricted to unweighted regularizers.

Key results

• Min vertex S-T cut algorithm with (1+O(1/sqrt n), O(lambda_2))-approximation and pointwise Lipschitz constant O(n/lambda_2), matched by an Omega(n/lambda_2) lower bound for (O(1), lambda_2)-approximations.
• Bipartite matching: 2(1+eps)-approximation with pointwise Lipschitz constant O(sqrt(m)/(eps w_min)), versus prior O(eps^-1 n^{3/2} log(m)/OPT).
• First dynamic min S-T cut algorithm with expected recourse O(n/lambda_2) and (1+O(1/sqrt n), O(lambda_2)) approximation.

Surprising findings

• Unweighted-regularizer analyses incur an inherent Omega(Lambda n) additive error barrier, which weighted regularizers via PGTA avoid.

Limitations

• Lipschitz constants depend on input-specific quantities such as lambda_2 and can be large for poorly connected graphs.
• Pointwise Lipschitz constant is defined in expectation and does not translate directly to differential privacy guarantees.
• Bipartite b-matching approximation degrades by factor (1-1/e); general-graph extension costs a factor 2 in approximation.

Experimental setup

Metrics: pointwise Lipschitz constant approximation ratio additive error expected recourse

Baselines: kumabe2022lipschitz bipartite matching algorithm varma2021average sensitivity min s-t cut algorithm

Builds on: kumabe2022lipschitz pointwise Lipschitz framework hardt2016train stability of first-order methods threshold rounding exponential mechanism

Closest papers by meaning

• Efficiently Computing Local Lipschitz Constants of Neural Networks via Bound Propagation (NeurIPS 2022 · similarity 0.84)
• A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data (ICLR 2023 · similarity 0.84)
• ECLipsE: Efficient Compositional Lipschitz Constant Estimation for Deep Neural Networks (NeurIPS 2024 · similarity 0.83)
• Some Fundamental Aspects about Lipschitz Continuity of Neural Networks (ICLR 2024 · similarity 0.83)
• Incremental Topological Ordering and Cycle Detection with Predictions (ICML 2024 · similarity 0.83)
• Graph Alignment via Birkhoff Relaxation (NeurIPS 2025 · similarity 0.82)