Speaker
Description
The Rotosolve algorithm leverages explicit knowledge about the objective function to perform exact minimisation along one coordinate at a time. Recently, we established its convergence, and derived explicit rates which match those of gradient-based methods. However, since Rotosolve uses additional information about the objective function, it is expected to outperform generic gradient-based optimisers. Empirical studies indeed demonstrate its superior performance. Further, the variance in the performance of Rotosolve across multiple experiments was inexplicably found to be higher than gradient-based methods. In this extended abstract, we address these discrepancies between theory and practice.
1. We first argue that the establishment of better convergence rates for Rotosolve requires the consideration of a stronger measure of performance than first-order stationarity, and introduce the notion of coordinate-wise second-order stationarity.
2. We consider the convergence of Rotosolve and gradient-based methods in the noise-free case. While the latter are guaranteed to converge only to first-order stationary points, Rotosolve converges to coordinate-wise second-order stationary points, yielding a quadratic acceleration over gradient-based methods. We further show that even in the absence of noise, Rotosolve has a higher variance than its gradient-based counterparts.
3. Under an additive noise model, we establish conditions under which Rotosolve retains its noise-free iteration complexity. Since these assumptions are not guaranteed to hold in practice, we are motivated to consider a relative-error noise model instead, and modify Rotosolve accordingly. Owing to space constraints, discussion on the relative noise model, the modified algorithm, and its analysis are deferred to an extended version of this paper.
| Topic | Theoretical foundations of quantum learning |
|---|---|
| Additional Topic | Hybrid quantum-classical approaches for learning and optimization |