Second, we solve Newton systems inexactly and randomly via the sketch-and-project method. This method was initially proposed by [1]} for solving general linear systems. We refer to that work for other equivalent interpretations of the method and for specific matrix-free examples (e.g., randomized Kaczmarz method). [2]}, [3]}, [4]} solved Newton systems exactly. [5]} solved Newton systems inexactly but deterministically (via conjugate gradient (CG) and minimum residual (MINRES) methods). In addition, we perform a fixed number of iterations of the solver, so that the per-iteration computational cost does not blow-up. In contrast, [5]} gradually vanished the approximation error. On the other hand, we should mention that [5]} is more adaptive than AI-StoSQP; the residual of their solver is controlled by either KKT residual or feasibility residual, both of which are computed from the iterates (although converge to zero), while our iteration budget \(\tau \)  is given and fixed.
