# New characterizations of Hoffman constants for systems of linear constraints

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

## Key facts

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

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

- [FERERO: A Flexible Framework for Preference-Guided Multi-Objective Learning](https://mlsanity.com/paper/2412.01773/) (2024)
- [Stability of Data-Dependent Ridge-Regularization for Inverse Problems](https://mlsanity.com/paper/2406.12289/) (2024)
- [Symmetric Matrix Completion with ReLU Sampling](https://mlsanity.com/paper/2406.05822/) (2024)
- [Interpolating Item and User Fairness in Multi-Sided Recommendations](https://mlsanity.com/paper/2306.10050/) (2023)
- [OTTER: Effortless Label Distribution Adaptation of Zero-shot Models](https://mlsanity.com/paper/2404.08461/) (2024)
- [First-order Methods for Affinely Constrained Composite Non-convex Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods](https://mlsanity.com/paper/2307.07605/) (2023)
- [On Stability in Optimistic Bilevel Optimization](https://mlsanity.com/paper/2408.13323/) (2024)
- [Trajectory-Restricted Optimization Conditions and Geometry-Aware Linear Convergence](https://mlsanity.com/paper/2604.17067/) (2026)
- [Inverse Reinforcement Learning without an Optimal Demonstrator: A Feasible Reward Set Approach](https://mlsanity.com/paper/2605.30903/) (2026)

## Abstract (arXiv)

We give a characterization of the Hoffman constant of a system of linear constraints in Rn em relative to a em reference polyhedron RsubseteqRn. The reference polyhedron R represents constraints that are easy to satisfy such as box constraints. In the special case R = Rn, we obtain a novel characterization of the classical Hoffman constant. More precisely, suppose Rsubseteq ℝn is a reference polyhedron, A∈ Rm× n, and A(R):=Ax: x∈ R. We characterize the sharpest constant H(A|R) such that for all b ∈ A(R) + Rm_+ and u∈ R [ dist(u, PA(b)cap R) ≤ H(A|R) · |(Au-b)_+|, ] where PA(b) = x∈ Rn:Ax≤ b. Our characterization is stated in terms of the largest of a canonical collection of easily computable Hoffman constants. Our characterization in turn suggests new algorithmic procedures to compute Hoffman constants.