A stochastic Remes algorithm (Q1091725)

The linear Tchebycheff approximation \(\sum a_ kh_ k\) for a regression function f by a Haar system \(h_ 0,h_ 1,...,h_ N\) is estimated by a stochastic Remes algorithm. This procedure is related to the usual Newton-type Remes algorithm as the Kiefer-Wolfowitz method of stochastic approximation is related to the classical Newton method. Only estimates for the first derivatives of f are used. Under suitable conditions the estimates for the alternant, for the coefficients \(a_ k\) and the minimal error \(\lambda\) all converge almost surely to the true values, when the number n of iterations tends to infinity. There is also convergence in distribution, which is formulated as an invariance principle. Under usual conditions on the noise the order of convergence is \(O(n^{-1/4})\) for the alternant (even \(O(n^{-1/3})\) if f is in \(C^ 3)\), and \(O(n^{-})\) for the coefficients and the minimal error.