Distributed Averaging Methods for Randomized Second Order Optimization

Understand

We consider distributed optimization problems where forming the Hessian is computationally challenging and communication is a significant bottleneck.

• We develop unbiased parameter averaging methods for randomized second order optimization that employ sampling and sketching of the Hessian.
• Existing works do not take the bias of the estimators into consideration, which limits their application to massively parallel computation.
• We provide closed-form formulas for regularization parameters and step sizes that provably minimize the bias for sketched Newton directions.