论文标题
通过光谱密度估计的平均案例加速度
Average-case Acceleration Through Spectral Density Estimation
论文作者
论文摘要
我们开发了一个框架，用于对随机二次问题的平均分析分析，并得出在此分析下最佳的算法。如果在Hessian的特征值分布的模型下，这产生了一类新的方法，可以实现加速。我们为统一，Marchenko-Pastur和指数分布开发明确的算法。这些方法是基于动量的算法，与经典的加速方法（如Nesterov加速和Polyak动量）相比，可以估算其超参数，而无需了解Hessian的最小奇异值。通过关于二次和逻辑回归问题的经验基准，我们确定了所提出的方法改善经典（最坏）加速方法的制度。
We develop a framework for the average-case analysis of random quadratic problems and derive algorithms that are optimal under this analysis. This yields a new class of methods that achieve acceleration given a model of the Hessian's eigenvalue distribution. We develop explicit algorithms for the uniform, Marchenko-Pastur, and exponential distributions. These methods are momentum-based algorithms, whose hyper-parameters can be estimated without knowledge of the Hessian's smallest singular value, in contrast with classical accelerated methods like Nesterov acceleration and Polyak momentum. Through empirical benchmarks on quadratic and logistic regression problems, we identify regimes in which the the proposed methods improve over classical (worst-case) accelerated methods.
