  Stochastic First-Order (SFO) methods have been a cornerstone in addressing a
broad spectrum of modern machine learning (ML) challenges. However, their
efficacy is increasingly questioned, especially in large-scale applications
where empirical evidence indicates potential performance limitations. In
response, this paper proposes an innovative method specifically designed for
kernel support vector machines (SVMs). This method not only achieves faster
convergence per iteration but also exhibits enhanced scalability when compared
to conventional SFO techniques. Diverging from traditional sample average
approximation strategies that typically frame kernel SVM as an 'all-in-one'
Quadratic Program (QP), our approach adopts adaptive sampling. This strategy
incrementally refines approximation accuracy on an 'as-needed' basis.
Crucially, this approach also inspires a decomposition-based algorithm,
effectively decomposing parameter selection from error estimation, with the
latter being independently determined for each data point. To exploit the
quadratic nature of the kernel matrix, we introduce a stochastic conjugate
subgradient method. This method preserves many benefits of first-order
approaches while adeptly handling both nonlinearity and non-smooth aspects of
the SVM problem. Thus, it extends beyond the capabilities of standard SFO
algorithms for non-smooth convex optimization. The convergence rate of this
novel method is thoroughly analyzed within this paper. Our experimental results
demonstrate that the proposed algorithm not only maintains but potentially
exceeds the scalability of SFO methods. Moreover, it significantly enhances
both speed and accuracy of the optimization process.
