LOCAL MINIMA ESCAPE TRANSIENTS BY STOCHASTIC GRADIENT DESCENT ALGORITHMS IN BLIND ADAPTIVE EQUALIZERS

Many adaptive algorithms perform stochastic gradient descent on perfor mance surfaces that are not guaranteed to be unimodal. In some example s, it is possible to show that not only is there more than one station ary point on this performance surface, but also that there is at least one incorrect local minimum. In the past, many authors have noted the existence of these incorrect stable equilibria, and noted that transi tions between the regions of attraction of these local equilibria are possible. However, very little work has been done to determine the esc ape times, beyond observing that if the valleys surrounding these unde sirable equilibria are very small and shallow, the escape time should not be too large. In this paper, we begin with a general discussion of the escape behaviour of adaptive algorithms, and follow this with an analysis, using diffusion approximations and large deviations theory, of the escape behaviour of the Godard class of blind equalizers. From this analysis, we obtain asymptotic estimates for the expected value o f the escape time when leaving the region of attraction of local equil ibria. Some observations are made also on the trajectories followed du ring such escapes. The basis for the computation of escape time estima tes is the connection between large deviations and optimal control the ory. For this interesting class of adaptive estimation problems, posse ssing multiple equilibria, the construction and solution of the optima l control problem is approximated, and shown to yield reasonable quant ifications.