# Faster p-norm minimizing flows, via smoothed q-norm problems

arXiv: https://arxiv.org/abs/1910.10571 · HTML: https://mlsanity.com/paper/1910.10571/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2019.

## Built on by (most cited first, 4 of 4)

- [Complementary Composite Minimization, Small Gradients in General Norms, and Applications](https://mlsanity.com/paper/2101.11041/) (2021)
- [Optimal Excess Risk Bounds for Empirical Risk Minimization on p-Norm Linear Regression](https://mlsanity.com/paper/2310.12437/) (2023)
- [ℓ2-norm Flow Diffusion in Near-Linear Time](https://mlsanity.com/paper/2105.14629/) (2021)
- [Sharper Bounds for ℓp Sensitivity Sampling](https://mlsanity.com/paper/2306.00732/) (2023)

## Abstract (arXiv)

We present faster high-accuracy algorithms for computing ℓp-norm minimizing flows. On a graph with m edges, our algorithm can compute a (1+1/poly(m))-approximate unweighted ℓp-norm minimizing flow with pm^1+frac1p-1+o(1) operations, for any p ≥ 2, giving the best bound for all pgtrsim 5.24. Combined with the algorithm from the work of Adil et al. (SODA '19), we can now compute such flows for any 2≤ p≤ mo(1) in time at most O(m1.24). In comparison, the previous best running time was Omega(m1.33) for large constant p. For p~δ-1log m, our algorithm computes a (1+δ)-approximate maximum flow on undirected graphs using m1+o(1)δ-1 operations, matching the current best bound, albeit only for unit-capacity graphs. We also give an algorithm for solving general ℓp-norm regression problems for large p. Our algorithm makes pm^frac13+o(1)log2(1/varepsilon) calls to a linear solver. This gives the first high-accuracy algorithm for computing weighted ℓp-norm minimizing flows that runs in time o(m1.5) for some p=mOmega(1). Our key technical contribution is to show that smoothed ℓp-norm problems introduced by Adil et al., are interreducible for different values of p. No such reduction is known for standard ℓp-norm problems.