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

Thank you for your careful reading and valuable feedback. We address your comments as follows:

1. There are some other machine learning problems with a nonsmooth DC structure. It is well known that piece-wise linear functions are DC. In order to guarantee both robustness and continuity, they could serve as the surrogate loss functions for binary classification. A direct example is calculating AUROC (area under ROC curve) of a predictive function $h(\cdot,w)$:

$AUROC(h(\cdot,w)) = Pr(h(x_+,w) > h(x_-,w)) = E_{x_+ \sim P_+, x_- \sim P_-} [\mathbb{1}(h(x_+,w) > h(x_-,w))],$

where $P_+$ is the distribution of positive examples, $P_-$ is the distribution of negative examples, and $h(x,w) : \mathcal{X} \to \mathbb{R}$ is a predictive function parameterized by a vector $w \in \mathbb{R}^d$. $\mathbb{1}(\cdot)$ is an indicator function of a predicate.

Let $\ell(w; x, x') = \ell(h(x',w) - h(x,w))$ denote a pairwise surrogate loss for a positive-negative pair $(x, x')$ to approximate $\mathbb{1}(\cdot)$. If $h(x,\cdot)$ and the surrogate loss $\ell(\cdot~; x, x')$ are both piecewise linear, the minimization problem with regard to $w$ can be formulated as a stochastic DC problem.

For the time-varying data distribution, section 6 provides an example of time-varying multi-variable normal distributions that satisfy the assumption. Since the Wasserstein-1 distance of some common distributions is easy to calculate or control, it is not hard to construct examples of time-varying exponential or uniform distributions that satisfy the assumption. We will add some examples in the final version of the paper. A simple but direct real-world example is problems with finite outliers or finite times of distribution shifts (due to the change of environment).

2. Establishing non-asymptotic rates remains an interesting but challenging problem. The derivation of Theorems 3.5.(ii) and 3.6.(iii) in [1] suggests that proving strict non-asymptotic rates still requires a smoothness assumption on either $g$ or $h$, even in the deterministic setting. Without such assumptions, obtaining non-asymptotic guarantees becomes significantly more difficult. This challenge persists unless a relaxed convergence criterion, such as nearly $\epsilon$-critical points, is considered.

[1] Hoai An Le Thi, Van Ngai Huynh, Tao Pham Dinh, and Hoang Phuc Hau Luu. Stochastic difference-of-convex-functions algorithms for nonconvex programming. SIAM Journal on Optimization, 32(3):2263–2293, 2022.

3. We sincerely appreciate your meticulous attention to detail. We agree that saying "$\rho$-strongly complex" is better. For the typos in lines 209 and 708, we will carefully revise them and ensure accuracy in the final version. We will also add a conclusion section. For reference, the definitions of $f_t$, $g_t$, and $h_t$ can be found in line 243 (left).

Thank you again for your valuable feedback. Your insights are greatly appreciated and will help improve the clarity and rigor of our work.

Thank you for your careful reading and valuable feedback. We address your concerns as follows:

1. We appreciate your comments on the simulation work. Our primary goal was to verify the theoretical validity of our method rather than to apply it to real data. The numerical result has demonstrated that our algorithm is efficient and effective in a simple but common problem. Your suggestion is very meaningful, and we plan to apply our algorithm to real and large-scale data in future work.

2. Regarding the sublinearly increasing dataset size, this aspect is inherent to our approach and difficult to avoid, as it ensures the necessary accuracy of the algorithm at each step. The choice of sample size and step size remains a fascinating topic in stochastic optimization. Even in standard smooth SGD without further assumptions, a non-vanishing step size requires a sublinearly increasing sampling size to guarantee convergence, since the variance reduction procedure is unavoidable.

   In our paper, the proximal terms $\mu_t$ for each DC subproblem can be pre-selected arbitrarily, as long as they are upper and lower bounded by positive constants. At time $t$, our $O(t^{2+\epsilon})$ sample size for $g$ and $O(t^{1+\epsilon})$ sample size for $h$ match the order of the smooth case. Moreover, our adaptive strategy is also designed to control the sample sizes when the current iterate is far from the critical points. Our sample size has already been an almost tight result, thanks to the novel $O(\sqrt{p/n})$ pointwise convergence rate for the SAA of subdifferential mappings.

3. To improve readability, we will consider moving some of the technical lemmas to the appendix while ensuring that the main ideas remain accessible in the main text. We also recognize that certain proof steps move quickly, and we will provide additional explanations and guidance to enhance clarity. We are also ready to include an additional simulation in our paper.

4. We agree that Robbins-Siegmund's theorem could be used in Theorems 4.8 and 5.3. However, the major part of our proof could not be replaced by this. The convergence of some series, such as the ones on the right-hand side of (18), remains essential; Robbins-Siegmund's theorem cannot simplify these. Regarding Theorem 5.3, we must separately consider iteration steps that satisfy the Summable Condition and the Stepsize Norm Condition, even if the theorem is used.

   That being said, we acknowledge Robbins-Siegmund's theorem as an insightful tool for guiding our convergence analysis, and we will add a remark discussing its relevance. However, the proofs themselves would not be significantly simplified by directly applying the theorem.

Thank you again for your thoughtful feedback. We will incorporate these improvements to enhance the clarity and accessibility of our work.

Thank you for your careful reading and valuable feedback. We address your questions as follows:

1. Remark 2: The main idea is that if there exists an isomorphic mapping between the probability spaces of the random variables $\xi$ and $\zeta$ associated with $G$ and $H$ (e.g., if $\xi$ and $\zeta$ originate from the same probability space, share the same distribution, or even are the same random variable), then we only need to sample the variable with the higher sampling demand. The other variable’s samples can be obtained directly via this mapping, reducing the overall sampling cost without affecting convergence.

2. Assumption 3.2 concerns only the Lipschitz continuity of the original function, not its gradient. The function itself may not even be differentiable, e.g., $\varphi(x,\omega)=|x-\omega|$ with corresponding $L_{\varphi}=1$. We require $\varphi(\,\cdot,\omega)$ to be Lipschitz continuous in $x$ with a universal constant $L_{\varphi}$, independent of $\omega$. Our result does not assume any smoothness.

3. The idea of using the Wasserstein distance to detect distribution shifts in online or decision-dependent optimization is not new, see [1,2]. However, we are the first to directly incorporate a Wasserstein distance term into the descent lemma and establish almost sure convergence.

[1] Drusvyatskiy D, Xiao L. Stochastic optimization with decision-dependent distributions. Mathematics of Operations Research, 2023, 48(2): 954-998.

[2] Che E, Dong J, Tong X T. Stochastic gradient descent with adaptive data. arXiv preprint arXiv:2410.01195, 2024.

4. Establishing non-asymptotic rates remains an interesting but challenging problem. The derivation of Theorems 3.5.(ii) and 3.6.(iii) in [3] suggests that proving strict non-asymptotic rates still requires a smoothness assumption on either $g$ or $h$, even in the deterministic setting. Without such assumptions, obtaining non-asymptotic guarantees becomes significantly more difficult. This challenge persists unless a relaxed convergence criterion, such as nearly $\epsilon$-critical points, is considered.

[3] Hoai An Le Thi, Van Ngai Huynh, Tao Pham Dinh, and Hoang Phuc Hau Luu. Stochastic difference-of-convex-functions algorithms for nonconvex programming. SIAM Journal on Optimization, 32(3):2263–2293, 2022.

Thank you again for your valuable feedback. We appreciate your insights and will carefully consider them in our revisions.

Thank you for your careful reading and valuable feedback. Below, we provide clarifications regarding the comments you raised:

1. L019, right: Thank you for pointing this out. In this paper, "critical point" specifically refers to a "DC critical point," following the convention in other DC programming literature. We will add a paragraph in Section 2 to clarify this distinction.

2. L127, right: Thanks for pointing out this improper statement. We will change the statement to the following: Let $\mathbb{P}(\Omega)$ denote the set of Radon probability measures on $\Omega$, where each measure $P \in \mathbb{P}(\Omega)$ has a finite first moment. That is, $\mathbb{E}_{\xi \sim P}[d(\xi, \xi_0)] < \infty$ for some $\xi_0 \in \Omega$.

3. L160, left: We will modify the definition of $g$ to be extended-real-valued functions so that it covers the indicator function. The function $h$ is real-valued to avoid making $f-g = -\infty$. Thank you again for pointing this out.

4. L280, right: These conditions seem to be necessary. In Section 6, we provide an example of online sparse robust regression to illustrate their role. We will add another example directly after the summable assumptions for further illustrations, as suggested by the reviewer.

5. L160, right; L806; L869; references: We appreciate your careful attention to detail. We will correct these typographical errors and remove uncited references accordingly.

Thank you again for your valuable feedback. We will carefully incorporate these revisions to improve the clarity and precision of our work.