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.
翻译:我们提出了一个方法,以获得经验风险全线估计问题和变体的经验风险场景关键点数的平均值和典型值,这大大扩展了Kac-Rice方法以前的应用,因为它能够分析高维非Gausian随机功能的关键点。在技术假设下,我们获得了一个严格明确的肛交复杂度变异公式,即以经验风险固定价值计算的平均关键点数的对数。这一结果使用理论物理学的非硬性Kac-Rice复制法加以简化和扩展。我们通过这种方法找到了一个明确的被解密复杂性变式公式,该公式通常不同于其同源的对应方,并且能够获得典型情况达到指数精确度的临界点数。