  We present a method to obtain the average and the typical value of the number
of critical points of the empirical risk landscape for generalized linear
estimation problems and variants. This represents a substantial extension of
previous applications of the Kac-Rice method since it allows to analyze the
critical points of high dimensional non-Gaussian random functions. Under a
technical hypothesis, we obtain a rigorous explicit variational formula for the
annealed complexity, which is the logarithm of the average number of critical
points at fixed value of the empirical risk. This result is simplified, and
extended, using the non-rigorous Kac-Rice replicated method from theoretical
physics. In this way we find an explicit variational formula for the quenched
complexity, which is generally different from its annealed counterpart, and
allows to obtain the number of critical points for typical instances up to
exponential accuracy.
