Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent
<|reference_start|>Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent: Optimization techniques in deep learning are predominantly led by first-order gradient methodologies, such as SGD. However, neural network training can greatly benefit from the rapid convergence characteristics of second-order optimization. Newton's GD stands out in this category, by rescaling the gradient using the inverse Hessian. Nevertheless, one of its major bottlenecks is matrix inversion, which is notably time-consuming in $O(N^3)$ time with weak scalability.   Matrix inversion can be translated into solving a series of linear equations. Given that quantum linear solver algorithms (QLSAs), leveraging the principles of quantum superposition and entanglement, can operate within a $\text{polylog}(N)$ time frame, they present a promising approach with exponential acceleration. Specifically, one of the most recent QLSAs demonstrates a complexity scaling of $O(d\cdot\kappa \log(N\cdot\kappa/\epsilon))$, depending on: {size~$N$, condition number~$\kappa$, error tolerance~$\epsilon$, quantum oracle sparsity~$d$} of the matrix. However, this also implies that their potential exponential advantage may be hindered by certain properties (i.e. $\kappa$ and $d$).   We propose Q-Newton, a hybrid quantum-classical scheduler for accelerating neural network training with Newton's GD. Q-Newton utilizes a streamlined scheduling module that coordinates between quantum and classical linear solvers, by estimating & reducing $\kappa$ and constructing $d$ for the quantum solver.   Our evaluation showcases the potential for Q-Newton to significantly reduce the total training time compared to commonly used optimizers like SGD. We hypothesize a future scenario where the gate time of quantum machines is reduced, possibly realized by attoseconds physics. Our evaluation establishes an ambitious and promising target for the evolution of quantum computing.<|reference_end|>
@article{li2024hybrid,
    title={Hybrid Quantum-Classical Scheduling for Accelerating Neural Network
  Training with Newton's Gradient Descent},
    author={Pingzhi Li, Junyu Liu, Hanrui Wang, Tianlong Chen},
    journal={arXiv preprint arXiv:2405.00252},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.00252},
    primaryClass={quant-ph cs.AI cs.LG}
}