An Online Adaptive Sampling Algorithm for Stochastic Difference-of-convex Optimization with Time-varying Distributions

We propose an online adaptive sampling algorithm for solving stochastic nonsmooth differenceof-convex (DC) problems under time-varying distributions. At each iteration, the algorithm relies solely on data generated from the current distribution and employs distinct adaptive sampling rates for the convex and concave components of the DC function, a novel design guided by our theoretical analysis. We show that, under proper conditions on the convergence of distributions, the algorithm converges subsequentially to DC critical points almost surely. Furthermore, the sample size requirement of our proposed algorithm matches the results achieved in the smooth case or when a measurable subgradient selector is available, both under static distributions. A key element of this analysis is the derivation of a novel O( p/n) pointwise convergence rate (modulo logarithmic factors) for the sample average approximation of subdifferential mappings, where p is the dimension of the variable and n is the sample size -a result of independent interest. Numerical experiments show that the algorithm is efficient for addressing online stochastic nonsmooth problems.