  In this paper, we deal with algorithms to solve the finite-sum problems
related to fitting over-parametrized models, that typically satisfy the
interpolation condition. In particular, we focus on approaches based on
stochastic line searches and employing general search directions. We define
conditions on the sequence of search directions that guarantee finite
termination and bounds for the backtracking procedure. Moreover, we shed light
on the additional property of directions needed to prove fast (linear)
convergence of the general class of algorithms when applied to PL functions in
the interpolation regime. From the point of view of algorithms design, the
proposed analysis identifies safeguarding conditions that could be employed in
relevant algorithmic framework. In particular, it could be of interest to
integrate stochastic line searches within momentum, conjugate gradient or
adaptive preconditioning methods.
