  We prove non asymptotic linear convergence rates for the constrained Anderson
acceleration extrapolation scheme. These guarantees come from new upper bounds
on the constrained Chebyshev problem, which consists in minimizing the maximum
absolute value of a polynomial on a bounded real interval with $l_1$
constraints on its coefficients vector. Constrained Anderson Acceleration has a
numerical cost comparable to that of the original scheme.
