An Online Adaptive Sampling Algorithm for Stochastic Difference-of-convex Optimization with Time-varying Distributions
Authors: Yuhan Ye
Ying Cui
Jingyi Wang
Venue: ICML 2025 oral (2025)
Keywords: nonsmooth
difference-of-convex
distribution shift
online optimization
Primary area: optimization->stochastic
TL;DR: We propose an online adaptive DCA under time-varying distributions, with a novel pointwise convergence rate for the SAA of subdifferential mappings.

Abstract: We propose an online adaptive sampling algorithm for solving stochastic nonsmooth difference-of-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(\sqrt{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 confirm that the proposed algorithm is both efficient and effective for addressing stochastic nonsmooth problems.

An Online Adaptive Sampling Algorithm for Stochastic Difference-of-convex Optimization with Time-varying Distributions
Yuhan Ye
Ying Cui
Jingyi Wang?
Abstract
where C' C IR is convex set, E, C Ω are random vectors with probability measures Pç. Pc. respectively, and G, H : (RR, 2) + R are Carathéodory functions, i.e., they are continuous in æ for all E, E Ω and Borel measurable in g and < for all æ E C. In addition, we assume G and H are convex in (though not necessarily smooth), making f a difference-of-convex (DC) function.
We propose online adaptive sampling algo- rithm for solving stochastic nonsmooth difference- of-convex (DC) problems under time-varying dis- tributions. At each iteration, the algorithm relies solely on data generated from the current distribu- tion and employs distinct adaptive sampling rates for the convex and concave components of the DC function, novel design guided by 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 re- quirement of our proposed algorithm matches the results achieved in the smooth case 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 subdifferential mappings, where p is the dimen- sion of the variable and is the sample size result of independent interest. Numerical experi- ments show that the algorithm is efficient for ad- dressing online stochastic nonsmooth problems.
When functions and h are fully accessible, problem (I) can be solved via the classical DC algorithm (DCA), At each iteration, a convex subproblem is solved by lin- earizing h via the subgradient at the previous point, ie, H
I(+1 argmin (0( 2i (x xx) + l| - ==|l²] for aEC
some ye E -h((a)) and μ 0. Due the convexity of h, it can be shown that the objective sequence {f(x))) is non-increasing, and the iterates asymptotically converge to so-called DC critical point of problem (I).
However, in many applications, functions and are not fully known and can only be estimated from sampled data. This challenge is compounded when the underlying data- generating distribution is time-varying, in the case of fluctuating demand. The convergence analysis of stochas- tic DCA is, therefore, significantly more complex than its deterministic counterpart, as it must account for the sample average approximation (SAA) error in both the convex com- ponent and the linearized concave component. The latter, in particular, closely tied to the convergence rate of the SAA error for subdifferential mappings when H/ is nonsmooth in 2, introducing additional difficulty in the analysis.
1. Introduction
We consider the class of stochastic nonsmooth nonconvex optimization problems in the form of
In this paper, we propose an online adaptive sampling al- gorithm to solve problem (1). At each iteration, new data from the current distribution is used to construct a stochastic approximation of the linearized DC function, while previ- ous samples are discarded. Unlike stochastic DCAs that aggregate past samples compute current solutions, our method is more robust to distributional shifts occurring dur- ing the data generations along the iterations. The algorithm dynamically determines the sample sizes needed to estimate and δh, adapting to the optimization path throughout the process. Specifically, when the current iterate far from critical points, less precise yet computationally inexpensive function values and subgradient estimates suffice. However,
minimize f(x)= Eg (G(,
Eg (H(x,)),
zec
Lg(w))
2b(x))
'School of Mathematical Sciences, Peking University, Beijing, China 'Department of Industrial Engineering and Operations Re- search, University of California, Berkeley, Berkeley, CA, United States *Center for Applied Scientific Computing, Lawrence Liver- more National Laboratory. Livermore, CA, United States. Corre- spondence to: Yuhan Ye <yyho3@mit.edu>> @mi..ddu>>
Proceedings of the nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

An Online Adaptive Algorithm for Stochastic DC Optimization with Timy-varying Distributions
as the iterates approach the critical points, higher accuracy in function and subgradient estimation becomes crucial for theoretical guarantees and effective practical performance.
dependent high-probability bounds on the distance between the empirical and population subdifferentials under the Hausdorff metric. However, the population objective is essentially required to be smooth. In Mei et al. (2018), the authors discuss uniform convergence of gradients for smooth objectives under the assumption that the gradient is sub-Gaussian with respect to the population data. In Foster et al. (2018), the authors provide dimension-inde -indepeddnndeeeeeeett High-probability convergence rates of gradients for smooth Lipschitz generalized linear models, utilizing a "chain rule" for Rademacher complexity. These works do not directly examine the convergence behavior of subdifferential sets. More recently, Ruan (2024) achieves a tight O( ((pp/) rate (modulo logarithmic factors) for the uniform convergence of weakly convex subdifferential mappings. This complements the O O(Vp/n) uniform convergence rate of subdifferentials in Davis and Drusvyatskiy (2022). However, their result is based on the convex-smooth composite structure, as well as subexponential assumptions for random vector and process, see Assumption C in Ruan (2024).
We summarize the contribution of the paper as follows:
We derive a novel O( p//) convergence rate (modulo logarithmic factors) for the expected pointwise SAA error of set-valued subdifferential mappings (Theorems 3.4 and 3.5), matching the convergence rate of single- valued gradient mappings in the smooth case, where p is the dimension of the variable and is the sample size. Our results complement existing work (Davis and Drusvyatskiy, 2022; Ruan, 2024) on the uniform convergence rate for the SAA error for subdifferen- tial mappings. We adopt a new proof technique that analyzes the one-sided deviation of subdifferential set- valued functions through their support functions.
We propose an online adaptive stochastic framework for DC optimization under tine-arriing distributions. Unlike existing algorithms in the literature (Le Thi et al., 2024), which require a Borel measurable sub- gradient selector that is challenging to implement in practice, our algorithm allows the selection of any sub- gradient from the sampled subdifferential set. Further- more, our algorithm operates under weak assumptions on the data generation process, allowing the underly- ing distributions to vary over time without necessarily matching the true distribution. We establish theoret- ical guarantees under the novel assumption that the cumulative Wasserstein-1 distance between successive distributions over iterations is bounded.
Stochastic and Online DC Optimization. While de- terministic DC algorithms have been extensively studied in existing literature (Le Thi and Pham Dinh, 2018), their stochastic counterparts have only recently gained attention (Thi et al., 2017: Le Thi et al., 2020). The first work that allowed both components in a DC problem to be nonsmooth was presented in Le Thi et al. (2022), where an SDCA scheme was proposed that stores all past information for constructing future subproblems. This approach achieves near-optimal sample size requirement by adding just one sample per DCA subproblem. Le Thi et al. (2024) pio- neered the study of DCA in an online setting, eliminating the need to store historical information. Their approach re- samples at each iteration and employs SAAS to approximate the linearized DC function using new samples, resulting in adaptive capabilities that offer a significant advantage over those in Le Thi et al. (2022). However, this method relies on the realization of Borel measurable subgradient selector, as specified in Assumption 1 of Le Thi et al. (2024).
Assume that we draw Ng.r samples to estimate g and Nn.t samples to estimate ah at time f. For any 0g E (0, 1/2) and as E (0, 1), we establish the almost sure convergence of the iterative sequence to a critical point
co. We further propose adaptive sampling strategy to adjust sample sizes at each step based on progress from the most recent iteration. In practice, the adaptive strategy enhances performance compared to its non-adaptive counterpart by potentially reducing the number of sam- ples required during the initial stage of the algorithm.
under the condition that Σ1>0
Moreover, non-asymptotic convergence of stochastic DC optimization has been studied in Nitanda and Suzuki (2017); Xu et al. (2019), which propose stochastic proximal DC al- gorithms by adding quadratic terms for DC subproblems. Nevertheless, these analyses rely on smoothness or Hölder continuity of the gradient, which are often too strong for many nonsmooth functions. Recent work in nonsmooth weakly convex optimization (Davis and Drusvyatskiy, 2018; Sun and Sun, 2022; Moudafi, 2022; Yao et al., 2022) has introduced Moreau envelope smoothing approximations for both components, enabling a non-asymptotic convergence analysis to nearly e-critical points for deterministic prob- lems a relaxed convergence criterion. These works have yet to establish complete non-asymptotic convergence for
1.1. Related Literature
Non-asymptotic convergence analysis of SAAs. An im- portant step in our analysis is the error estimation of SAAS of g and 0h. The non-asymptotic convergence analysis of SAAS for expected functions has been well-studied in the existing literature; see, for example, the monograph Shapiro (2000). For the SAA convergence rate of subdiffer- entials, Xu (2010) demonstrates non-asymptotic, dimension-
2

---

An Online Adaptive Algorithm for Stochastic DC Optimization with Timc-varying Distributions
non-smooth DC problems since gap remains between nearly e-critical points and true critical points.
when is Lipschitz continuous near T.
The Clarke subdifferential of at T is the set acr(E) A {u E Ro r r=; d) 2 v d, Vd E R²). If r is strictly dif- ferentiable at æ. then acr(ā) = {Vr(z)). We say that r is Clarke regular at 7 E O if r is directionally dif- ferentiable at I and r0 d) = r'(;; for all d E R". This Clarke regularity at 2 is equivalent to have r(z) 2 r(0) (8)+ (x (x- + =II) for any 7 @er(z), which is natural satisfied when is convex. Moreover, if func- tion fails to satisfy the Clarke regularity at x. there does not exist an approximate linear lower bound of the original function based on the Clarke subdifferentials with a small o error locally. Since the concept of Clarke subdifferential coincides with the usual subdifferential in convex analysis for a convex function, we simply refer to Clarke subgradient as subgradient in the remainder of the paper.
Recent studies have explored online optimization under distribution shifts, particularly within online convex op- timization and stochastic approximation methods. Stan- dard approaches typically assess performance through re- gret bounds relative to defined measure of distribution shifts (e.g., Besbes et al. (2015); Fahrbach et al. (2023); Sankararaman and Narayanaswamy (2023)). Our proposed algorithm differs due to the nonsmooth nonconvex structure, where regret- based analysis is inapplicable, as our results rely on asymptotic convergence properties instead.
A daptiie Sampling in Stochastic Optimization. Adap- tive sampling methods offer advantages over fixed-sample approaches, such as leveraging parallelism and generating iterates with reduced variance due to progressively increas- ing sample sizes. Adaptive strategies often use gradient approximation tests to regulate accuracy. Examples include norm- bumn- tests (Carter, 1991; Byrd et al., 2012). inner product tests (Bollapragada et al., 2018) 8), and other meth- ods (Cartis and Scheinberg. 2018; Jin et al., 2021). For a comprehensive overview of adaptive sampling techniques, readers referred to Curtis and Scheinberg (2020).
Let A Rp = Trm be a set-valued mapping. Its outer limit at x E R2 is defined as lim sup A(x) ==
x-2 J.
U lim (imsupA(aa)) = {" 3 x" o" -2 1-000 u with u" E A(z")). We say A is outer semicontinuous (osc) at I E IRP if lim sup (uppsux))))) S A(7). Clarke subd-
u"
x-$
ifferential is outer semicontinuous, which is necessary in establishing subsequential convergence, by Proposition 6.6 in (Rockafellar and Wets, 1998). In addition, for a Lipschitz r, dr(x) is locally bounded, see Theorem 9.13 in (Rockafel- lar and Wets, 1998).
2. Preliminaries
We first summarize the notation used throughout the pa- per. We write Rº as the p-dimensional Euclidean space equipped with the inner product (z. y) xTy y and the in- duced norm ||=||| A Vx VxTz. x. The symbol [B(x, is used to denote the closed ball of radius > 0 centered at a vec- tor x E Rº. Let A and C be two nonempty subsets of RP. The distance from vector x IRP to A is defined as (x, A) A inf [|y z||l The one-sided deviation
A point x² E Rp is called DC critical point if 0 E Øg(#*) ah(="), or equivalently 0g(x*) n @h(=") A 0. In this paper, the terminology critical point refers to DC criticality, as defined in the literature on DC programming.
Next, we review some basics of random set-valued map- pings and their expectations. Let (2, F, P) be a probability space, and for fixed x, let A(x, w) : Ω - 2R be gen- eral set-valued mapping taking values in closed subsets of RP. The expectation E[A(2, w]] is defined as the set of E[A(æ, w)] over all integrable selections, where integrability follows Aumann's 's sense (Aumann, 1965). It is well defined if ([H, be a random lower semicontinuous function, where g (9, P) - E is a random vector with support E C Rmm. If is (()))
yEA
of A from C is defined D(A,C) A dist(a C).
=EA
The Hausdorff distance between A and C' is defined as (HAAA) C) == max (D(A, C), A)).
We proceed by introducing fundamental concepts from nons- mooth analysis. For detailed discussions, we refer the reader to the monographs (Clarke, 1990; Rockafellar and Wets, 1998; Mordukhovich, 2006). Let O R be function defined on an open set O C IRP The classical one-sided directional derivative of r at ē
< xc. Let r(x,e) : RP x = + R
in x. where B[x([[]] < oc; and for any x, r(x, {) is Clarke regular for a.e. E. Then, B[r(x, E)] is Clarke regular, and [r, {)] = E[0,r(x, ()), by Theo- rem 2.7.2 in (Clarke, 1990).
E O along the direction r(ā + td) r(ā)
d E RP defined as r' (z; d) lim
t The function r is said to be directionally differentiable at & E O if it is directionally differentiable along any direc- tion d' E RR. In contrast, the Clarke directional deriva- tive of r at ā E O along the direction d E R is defined r(z + td) - r(x) which is finite
<jo
Throughout this paper, we assume that the sample space Ω is equipped with a metric d(.,.), :). making it a metric space. Let P(2) denote the set of Radon probability measures on Ω. where each measure P E P(..) has finite first moment. That is, Eer (d(E, < co for some to Ω.
as r (i; A limsup
a- 210
t
3

---

An Online Adaptive Algorithm for Stochastic DC Optimization with Tary-narying Distributions
For v, E P(?)), their Wasserstein-1 1 distance is defined
We begin by introducing a lemma regarding the conver- gence rate of SAAs in expectation. This result is de- rived from the Rademacher average of the random func- tion zi(z,,o) as discussed in Corollary 3.2 of (Ermoliev and Norkin, 2013) and further explored in Theorem 10.1.5 of (Cui and Pang. 2021). Let r be any positive scalar. For a random function ((,,), : DD(S [0,r]*) + R and i.i.d random variables (w) ......") = @" drawn from the distribution of w, define the SAA error as 8n (1), w²) := suPxED, 1 ++E: vi (z, - En (, [- We then have the following basic estimates, see, e.g. Theo- rem 3.1 in (Ermoliev and Norkin, 2013).
Wi(u,) = sup (Ex~n(g(X)] (B>w(g(())) (eL
where (12) denotes the set of all Lipschitz functions
g: 22 + R with the Lipschitz constant 1.
3. The Convergence Rate for the SAA Error of Subdifferential Mappings
In this section, we establish novel pointwise convergence rate of O(yp/n)) for subdifferential mappings, where p is the dimension of the variable and is the sample size. This stochas-
Lemma 3.1. (Basic Estimates). functions (((:,w) are bounded by constant M and Lipschitz continuous with con- stant Ly in the first variable x uniformly in w, then for any a E (0, 1/2), s O. it holds that
addresses major challenge in subgradient- tic nonsmooth problems: analyzing the sampling error of stochastic subgradients regarding the sample size.
For random function (((,w): D. RP) + R and inde- pendent and identically distributed (i.i.d)) random variables (w", ,). A th drawn from the same distribution of
M
E 6n (w, S 2VD Loo + v(1 2a)e
/nC,
w. we could use 1/2 E==1" T (I,w*) as an SAA estimation of the subgradient of Es [p(z,w)], where (x) is
P [V Bandn (v),0)) S 2exp {
s²
2M/
subgradient selector that satisfies (ar,w*) E Ousi (I,ww))
To analyze the asymptotic behavior of An (1,, x, a0 need the following assumption.
In the smooth case, each T (ax, w is an unbiased estimate of the expected gradient at x. since E,,, [V..p((,,)) w)] VE [f((, This leads to straightforward O (+) con- vergence rate for the squared error in relation to the sample size n. i.e.,
(x,w*)
Assumption 3.2. The function (p(,,w is convex and Lips- chitz continuous with Lipschitz constant Ly, in terms of the first variable x E Dep uniformly in w.
The support function of a set S is defined as au, S) - supses u² s. It is well known that (u, S) = a (u, conv S), where conv denotes the convex hull of S. Moreover, for any nonempty sets S and S it follows from (Christian, 2002) that a (u, S + S*) = o(u, + a S",
1 Σ Valp(a,w"))
Egg
VIE [so w]]l
I
(2) where 2² is the uniform variance of V V2 w²). However, this result does not directly extend to nonsmooth set-valued subdifferentials. Some studies impose additional assump- tion that for any x, r(x, -) is Borel measurable with respect to w, enabling a similar convergence rate to (2). In prac- tice, however, implementing a Borel measurable subgradient selector is challenging and often infeasible.
(3)
Furthermore, the Hömander's formula, according to Theo- rem II-18 in (Castaing and Valadier, 1977), states that for any two nonempty convex and compact subsets A and B of R":
DD (A, B) = max (a(u, A) -ouu B)).
(4)
To address this challenge, we analyze the convergence rate of the sample average subdifferential mapping dp(x)) :=
[|]]@11
Using the above formula, derive the following lemma that converts our targeted quantity An (1,, 2z, @*) into the SAA error of support functions; see, e.g., (Xu, 2010). Its proof, as well as proofs for Theorems 3,4 and 3.5, can be found in the appendix.
En -k=1 0gp wh) to its expected counterpart 0p(xx)
B. (x))) We define the SAA error for az( .)
Ω + 2 as
1 M n
Dop (2, EE (..d
An (p,, x, x"))
Lemma 3.3. Under Assumption 3.2, for any x E Dep
An (vp, x. (e,"")
In the following, we shall develop novel O( /P/n) conver- gence rate (modulo logarithmic factors) for An (4,, x, w²). Our results enable algorithms to select any subgradient from the sampled subdifferential set at each iteration while achiev- ing a sampling error bound comparable to the smooth case.
1 Σ (u, 0.4 (z,w²)) - E. lo (u, 0, wi)l n
max |
We now derive the SAA convergence in expectation.
4

---

An Online Adaptive Algorithm for Stochastic DC Optimization with Taryivarying Distributions
Theorem 3.4. Under Assumption 3.2, any (0,
4.1. The Algorithmic Framework
We assume that at time i, the data sets Sg.t A (5+ Noi and Ni.e J=i Sh.e & + are generated from the distributions Pε. and Pq... respectively, where the latter distributions may not be exactly the same as the true distributions Pg and Pc. Let (x)x) - Eg-re, (G E)], h4 - Eg- (H <)], and fz) _ ge(x) - ht (z). At time t and iterate 21, we use the data from S,, to construct stochastic estimate (e(-) of the function g(-), and the data from Sp,t to construct a stochastic estimate h4 (xx))) of h(r4),, well as a stochastic estimate De of the subgradient (h(x))) The overall estimation model M-)-) is given by:
sup ,ED,
1 (An (10,00,00) n7.
where e 2 2/ + /o/ /l///lll//////
Moreover. for any s >>0 0,
P P(n (p,, x²) 2 S exp (21)))
Remark 1. The concentration-type probabilistic results in Lemma 3.1 and Theorem 3.4 are due to McDiarnid's bounded difference inequality. They will play an important role in the proof of Theorem 3.5.
Next, we strengthen the above theorem to bound the squared SAA error, which is the key result of this section.
1 (d) _ (e + +d) - he((re) 5f d
2 puelldl
(5)
Theorem 3.5. Under Assumption 3.2, for any a E (0, 1/2),
where #4 > 0 is the proximal parameter. The convex sub- problem to be solved at iteration t is
a' (a, 1/2), we have
An (2(,,,,))))
c
minimize d
Mc(d)
sup ENn =ED,
n2a
(6)
subject to It + dE
where e & & ce+ Lip (2(e
+ Li with à A
The first-order optimality condition of subproblem (6) at the unique optimal solution de is
Vp(2L + Lp/v(1- (all-20)cc) 20))c).
Ze+1 Dr + uade + ū. =0,
(7)
When u0: w,w is smooth, Theorem 3.5 simply becomes
where Et+1 E (x: + de) and or E Oic(:; + de) with ic being the indicator function of C. Our proposed online stochastic proximal DC algorithm (ospDCA) framework presented in Algorithm I, while the exact rule to update the parameters 14: N g,t. Nr.; will be discussed later.
L
sup ESn (p,,, DED,
n
that is. == 12 and our result almost matches the SAA convergence rate in the smooth case. The tools we have developed here can play a crucial role in non-asymptotic convergence analysis of other snggraddentthasedd stochastic nonsmooth problems. For example, enables a "variance reduction" technique similar to that used in smooth optimization. (Bollapragada et al., 2018; Byrd et al., 2012)
1/2. This demonstrates that
Algorithm The oCP framework
1: Initialize Wo: Moo N₂ Ng.0: No.D for t= 1,2, do
3: Generate i.i.d. samples Sg.1 = (gt:))/2rr and Sn, =
(ct)) No.: T== from pg.t and Ps.s, which are independent of the past samples.
4: Construct the approximation model M,(d) in (5)
4. The Algorithm and Convergence
by setting (x) Ng., En G (a,, (x,E4.).. ha(x)
No. NNi H (x. Ch.)), and select ū. E ah, (wt) =
Before presenting our algorithm, we first list all the needed assumptions for the stochastic functions G and H. Assumption 4.1. (Assumptions for Functions)
No. Emn 0,H (tt).
5:
Solve the convex subproblem (6) to obtain d.
6: Set I++1 x2 + d.
1. The feasible region C' is convex and closed, and there exists a scalar such that f(x) > f for all x E C.
7: Update M441, Ng,441,
end for
2. G(GE) is Pg-coe (pg 2 0) and H(,,)) () is PM- convex (ph 2 0) over C for almost every &, S E St
Under Assumption 4.1, it is trivial to verify that (z) and g(x) are L,ppschhh Ps- convex; and (x) and h(x)) are Ln--Lipschiz, Ph-convex.
3. G(+,E) is Lg Lipschitz continuous and H(,, ; <) is LN- Lipschitz continuous over C for almost every E,C E Q.
Let F, & a (S 1, Sp.2.... Sg Sp.-1) be a filtration, i.c., an increasing sequence of a fielld generated by the samples used in the past t iterations.
4. For all x E C. G(z, )) is Le-Lipschitz continuous and H(x, .) is T.ç-Lipsehitz continuous over Ω
5

---

An Online Adaptive Algorithm for Stochastic DC Optimization with Time-varying Distributions
Remark 2. If there exists an isomorphic mapping ø from Fi, Pg.e) to (9t, Pc,,), Step of Algorithm 1 can be
where Cn. = =On (Cn + Ln /2tah-aaa (f(2LA + (1-1111a,, -((1))))))) d),
vah
+ Li with C₁
simplified when Ng.t 2 N,,,, as follows:
Generate i.i.d. samples g. = (5"h) Min from the distri-
Remark 4. With regard to the estimation error from sam- pling, Liu et al. (2022) assumes that the variance of the stochastic objectives is bounded. Similarly, Berahas et al. (2021) needs an unbiased gradient estimation with bounded variance in the study of stochastic sequential quadratic pro- gramming. Sequential quadratic programming is extended to the nonsmooth DC problems with smooth convex compo- nent in the deterministic Wang and Petra (2023) and stochas- tic settings Wang et al. (2023), where again a bounded vari- ance of subgradient estimation is required. In Shashaani et al. (2018), the Monte Carlo estimate of the objective is also assumed to be unbiased, and its variance uniformly bounded. The tools developed in Section 3 provide a tight SAA bound for Oh, allowing to derive result analogous to the one in smooth optimization discussed above.
bution of &. which are independent of previous samples.
N,.,, 2. For i = ,,,,,..,NNn...... set 5h ((( and let Sp,t
(5")) J==1
similar procedure applies when ga < Nh.e
4.2. Convergence Analysis
In this section, we present the convergence result of Al- gorithm based on Assumptions 4.1. brief outline of the convergence analysis provided in the main text, with detailed proofs available in the appendix.
We first analyze the inexact sufficient descent property at the f-th iteration and derive the following inequality. The
result and its proof is similar to the deterministic case, see, e.g., Theorem 3 in (Tao and An, 1997) and Theorem 3.7 in (Tao and An, 1998).
In the following lemma, we present the sufficient descent property in expectation.
Lemma 4.5. At the 1-th iteration, the following stands for any c > 0:
Lemma 4.2. (The Sufficient Descent Property) For any y1 E (h,(2)),, the step 1 from Algorithm| satisfies
E [fc(xe)) - 1 | Fel
f((x))-((Z((1)) 2 (yt - 3e) + (Me + Pg + ph -000
||de|1
Pg + Ph
E ||del| Fi]
Cg
14 +
c
2
14
N.No
+ (a())) (xx) (((+)))) + (x(+1)))
Cn
L W1 (Pe,,t,,,
4cNa. h,t
To further the analysis, the SAA error bound derived in Section comes into play. By Lemma 3.1, we could derive
(8)
where ag (0, 1/2) and an E (0, with corresponding constants Cg and Cj defined in Corollaries 4.3 and 4.4.
the SAA error estimation for ge ge (1)+1) as follows. Corollary 4.3. For any 0g E 1/2). we have
The following analysis is conducted under the key assump- tions stated below.
C Ne No
[00( - - 10( + g((x)))
Assumption 4.6. (Assumptions for Distributions) The se- quences P&.f and Pe. converge to P3 and Pe in Wasserstein- distance, that is,
where Cg = 4.pplg(TTg + Tnn) 2 L. /11-20,Je)
lim (PC,,,, P&) = 0 and lim (P Pc) = 0, t-000
Remark 3. Note that we relax the assumption that G(z, E) is globally uniformly bounded, as posed in Le Thi et al. (2024). Instead, we use the proximal term He to ensure that d, does not become too large. This guarantees that G(I,, {)- G(z++1,8) remains uniformly bounded with respect to μa, which facilitates our SAA error analysis of ge (x(x)) - ge (1++1) (see the proof of Corollary 4.3 for details).
t-000
Furthermore, the cumulative Wasserstein-1 distance be- tween successive distributions, which measures the com- plexity of distribution shift on the data stream, is bounded:
+00
+00
(i.PEen < oc, and Wi(PE,, < co.
The SAA error estimation for (xxe is direct corollary of Theorem 3.5:
Remark 5. Since the Wasserstein-11 distance of some com- mon distributions is easy to calculate or control, it is not hard to construct examples of time-varying exponential or uniform distributions that satisfy this assumption. A simple example is the regression problem with finite number of out- liers or finite times of distribution shifts (due to the change
Corollary 4.4. For any On E (0, 1), a/ E (on, 1), we have
Cn
sup E [ (8hr(z1), Ohe(z.) [F]] < #EC
nas
6

---

An Online Adaptive Algorithm for Stochastic DC Optimization with Tiry-varying Distributions
of environment). An example of online sparse robust re- gression will be provided in Section 6, where time-varying multivariate normal distributions satisfying the above as- sumption are considered.
the stepsize d,, as demonstrated in Lemma 4.2. By applying the Cauchy-Schwarz inequality, we elevate the SAA error of 0h from first-order to second-order in expectation (see Lemma 4.5), for which Theorem 3.5 establishes the tight convergence rate.
Assumption 4.7. (Assumptions for Parameters)
According to Assumption 4.7 (a), the proximal terms f for each DC subproblem can be pre-selected arbitrarily, as long as they are upper and lower bounded by positive constants. Regarding the sample size requirement given in Assumption 4.7 (b), this 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 sizes and step sizes remains an active research topic in stochastic optimization. Even for stochastic gradient descent applied to smooth optimization problems, a non-diminishing step size selection requires sublinearly increasing sampling sizes to guarantee convergence.
(a) There exist 0 < f < j such that j S Mr S R. V2
(b) There exist 0g E 10,1 ag E (0, such that
Σ 220
<0.
(9)
N g.t
N
Now, we are ready to present the squared summable property of the iteration step {de), , and its almost sure convergence to zero. These results are important for the later analysis.
Theorem 4.8. Under Assumptions 4.6 and 4.7, we have
5. An Adaptive Sampling Algorithm
lim E
Σ |all" iFo 120
oc, hence E [[|de] [Fo] + O.
In this section, we introduce an adaptive sampling strategy for updating Pe, NN,.. NN., in Algorithm As discussed in the convergence analysis, the key requirement is to ensure that Assumption 4.7 holds. Since Assumption 4.7 (a) is rela- tively easy to satisfy, we mainly focus on developing strate- gies to satisfy Assumption 4.7 (b). Given pre-determined constants at Cu > 0, a common approach is to increase the sample sizes sublinearly based on the following condition:
Furthermore, lo |de = 0 with probability 1.
To proceed, we first provide a technical Lemma, which concerns the law of large numbers (LINN) for SAA sequence.
Lemma 4.9. Under Assumptions 4.6 and 4.7, for any fixed R > 0, E C,. E B( R), the following limits hold as t + oo with probability 1:
Condition 5.1. Suppose that Ng.e and Ni, are pre-defined such that Σiso (Nr-e + + N < oo, we say that the Summable Condition holds at the t-th iteration if the pa- rameters Ct, Ng.t No, are chosen to satisfy:
(x(x)- (e())) - -(((xx) -i(())) - 0,
he(x)- - hT) - -hhe(z) - he() -
We are ready to present our main convergence result, which is the best that can be achieved under stochastic nonconvex and nonsmooth conditions.
Pg + Ph
Ng.t 2 No.s Nu. 2 Nu. and a S ca. S nut
Cp.
2
(10)
Theorem 4.10. Under Assumptions 4.6 and 4.7, every ac- cumulation point of the sequence {xe} produced by Algo- rithum 1 is DC critical point of f with probability I.
However, these pre-determined sample sizes do not adapt to the algorithm's progress at each iteration. In the following, we introduce a practical condition that determines Ny.: and Ná. based on the optimization path. Intuitively, a larger stepsize in the early iterations suggests that the current point is far from critical points when less precise but computa- tionally cheaper estimates are sufficient. In contrast, the algorithm nears the critical points, the stepsize decreases, re- quiring more accurate estimations to ensure both theoretical guarantees and practical performance. Building on this intu- ition, we propose a practical Stepsize Norm Condition for adaptive sampling, where the sample size at each iteration is determined by the current stepsize.
The above theorem only provides the asymptotic conver- gence of the algorithm, not the non-asymptotic complexity. The known complexity of the deterministic de algorithm in (Le Thi et al., 2020) requires a smoothness assumption on either g or h. We left it as a future work to derive the iteration complexity of our proposed algorithm.
The sample size requirement of our algorithm is presented in (9). Notably, the bounds on exponents og and on are different. To provide some intuition, this difference arises from the DC structure and the improved convergence rate of the SAA error for the subdifferential mapping. Specifically, linearizing the function h couples the SAA error of Oh with
Condition 5.2. We say that Stepsize Norm Condition stands at the 1-th iteration parameters Ca Pt, Ng.t, No.
7

---

An Online Adaptive Algorithm for Stochastic DC Optimization with Tiry-varying Distributions
are selected satisfy:
Algorithm 2 Adaptive ospDCA
Require: Initial point zo. error estimation parameter ag (0, 1/2), as (0, with corresponding Cg, Ch de- fined in Corollaries 4.3 and 4.4, sample size upper bound sequence (Ng.t) and {Na,t} which satisfy h,t + +N -N < oc, predetermined prox- g.t imal parameters {ur} with upper bound få and lower bound/ J..
(44-1- - Cu= cL-1) |dd-1l1>> 2
C2 Me 5i
+
C N
4 S Mr + Patph
Cy.
2
(11)
Σ 2120
Remark 6. Here, Cr acts as an intermediate variable for parameter updates, linking others ensure convergence. These variables serve only determine jt,, Ng.t, and Nr,--
1: for 1. 0, 1, do
2: Generate i.i.d. samples ( Nas and (c" Naa from the distribution of & and Ç. which are indepen- dent of the past samples.
As presented in the following theorem, Assumption 4.7 (b) stands when either condition is satisfied. This plays critical role in designing a practical adaptive ospDCA with convergence guarantee. Compared to the gradient ac- curacy condition and other variance-base based tests in (Byrd et al., 2012; Bollapragada et al., 2018), our adaptive sam- pling scheme is not only practically implementable but also backed by rigorous theoretical guarantees.
3: Set (x(x)) = - EM G (1, hy(x) =
Ny.
NR. EM H (z,, (h)), and select ÿr E ah, (12)-
4: Solve the convex subproblem to obtain d.:
minimize
gx(2, d) - -x, - of d + zu:lld)
Theorem 5.3. If either Summable Condition (10) or Step- size Norm Condition (11) is satisfied for sufficiently large t, and Assumptions 4.7 (a) and 4.6 stand, then Assumption 4.7 (b) stands.
2
subject to
21 + d EC
5: Set Fz+1 = + de.
6: Update Ng.e41 and No. such that one of the fol-
To eliminate the intermediate variable e2 and adapt the al- gorithm for any predetermined sequence {ur} satisfying 0 < j S 14 S P. we propose a simplified algorithm by fix- PPh
lowings stands:
1. (mL - 4) |Ide|12
C, 2,41
+ (20 n.44
ing C = 2 + - C/ and setting C₂ -. as detailed in Algorithm 2. The complete version of the adaptive sampling ospDCA can be found in the appendix; see Algorithm 3.
2. No 2 Nocti, and No,t 2 Nuat1.
end for
Remark 7. Consider the subproblem when updating the sample size Ng.t and Nu.t- In order to minimize the total number of samples, one could derive that N,,; 2Cr N3/1 Hence the optimal order of Ny, V Cg(2p,
decomposition: min(1,a]85], 1+0|8811 a Syl). Thus, the final problem formulation in expectation form is:
min ((z,))D,, [G(B,,, -,((),, BER
is O(N9))). Furthermore, if the updating rule of Ng and NA. is based on this result, then sample size upper bound sequence Nr. is no longer required.
where ((8,2,y) by + a|3,)) h(B)= = Ei= max(1, (|35)) This expectation-bast for- mulation enables efficient online optimization, making it well-suited for large-scale and streaming data scenarios.
6. An Application: Online Sparse Robust Regression
Baselines. We implemented four baselines to compare with our proposed adaptive ospDCA. The first one is OspDCA with a pre-determined, sublinearly growing sample size of 22.1 per iteration, without adaptivity. The second baseline is DCA, introduced in Le Thi et al. (2024), where we added an additional proximal term. This algorithm draws one new sample per iteration and uses aggregated samples to construct sample averages. The third and fourth baselines are ospDCA with a fixed sample size per iteration, using 100 and 1000 new samples for SAA, respectively.
We consider the online linear regression problem with ro- bust loss and ppomsity- DC regularization. Given streaming data {z,, y:) }e drawn from unknown and vary- ing distributions D,, the optimization problem is formulated as minimizing the expected objective:
min E (D. lly - 2311 + A Σ min(1, min(1,a)8,) BERP
The regularization term Σj min(1, (|3, is a capped-
Datasets and Setup. For the problem, we set a = 1, x= 0.01, and generate synthetic datasets. Specifically, at each time step f, the feature vector xa is sampled uniformly from
l penalty, which approximates the sparsity- indducin to- norm. To facilitate optimization, we use the following DC
8

---

An Online Adaptive Algorithm for Stochastic DC Optimization with Time-varying Distributions
furformance tamnalon
Performance Cve
uniformly Lipschitz in (2,y) ) for every B.
Results. We evaluate the performance by tracking the dis- tance between the current iterate B, and the optimal solution Popt. We plot the evolution of convergence error and com- putational time in Figures 1 and 3. Across all experiments, the performance of adaptive ospDCA consistently surpasses the baseline methods. This demonstrates that our proposed algorithm significantly improves convergence efficiency.
00
10
During early iterations, the sample size of adaptive ospDCA is relatively small, leading to reduced precision but higher computational efficiency. As the iteration points approach the optimal solution, the sample size increases to enhance estimation accuracy. This transition leads to faster progress in later iterations. ultimately surpassing other algorithms. Compared to its non-adaptive counterpart, adaptive oSpDCA invests more time and samples in the later iterations (which are closer to the optimal and thus more important), as il- lustrated in Figures 2 and 4. The adaptivity makes it more efficient overall and more robust to distribution shifts. Addi- tional experimental results are provided in the appendix.
(a) p 50, Poge
[10,- -05, 0,
hurformance Dver Iamaaiona
(b) p= 200, Sapt = [10, - 15, -....
Figure 1. Algorithm behavior for online sparse robust regression.
7. Conclusion
Soogle iterrtiono
Sample Becotions
In this work, we propose an efficient online adaptive sam- pling algorithm for stochastic nonsmooth difference-of- convex (DC) optimization problems with time-varying data distributions. The algorithm relies only on samples drawn from the distribution at the current iterate and adopts distinct adaptive sampling rates for the convex and concave compo- nents of the DC objective. We further prove that, under mild convergence conditions the non-stationary distributions, the generated sequence almost surely has a subsequence that converges to a DC critical point. One of the core contribu- tion of this paper lies in generalizing previous results the field of stochastic online DC optimization to broader class of nonsmooth DC problems with ameevarying distributions, while maintaining sampling size requirement comparable to the smooth case. Numerical experiments demonstrate that our algorithm performs well on online sparse robust regression tasks.
uspoch
30--0
100
20000
8002
200
Sample size for experiment (a).
Sample size for experiment (h).
Figure 2. Sample size per iteration.
[-1, Ij. The corresponding label is given by
V/ x. (Pops + 5,) E,
where Pope is known sparse optimal solution with nonzero entries at specific locations, ~ N00 1) represents additive noise, and & denotes time-dependent distribution shift. follows that W1(D, 1)+1) & |16e - 1111 In order to ensure that the cumulative Wasserstein-1 distance for D. remains bounded, we set 6, = (-1)' 10001-00-21 21p. where 1p represents a p-dimensional column vector where all entries equal to 1. We initialize 3 at zero, set the proximal coefficient 14; = 1, Og = 0.45 1/2), and run the experiment until a predefined runtime limit is reached. It is straightforward to verify that G(-, x, y) is 1- I-Lipschitz for every x, y. and h(-) is Aa- Lipschitt Furthermore, if we impose a bounded constraint on 8, then G(B,,,) is also
A Acknowledgements
Yuhan Ye is partially supported by the Blite Undergraduate Training Program of the School of Mathematical Sciences at Peking University. Ying Cui is supported by the National Science Foundation under Grants CCF-2416172 and DMS- 2416250, and the National Institutes of Health under Grant IR01CA287413-01. Jingyi Wang's work is performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under Contract DE-AC52- 07NA27344, Release number L.NNL-JRNI-8465111

---

An Online Adaptive Algorithm for Stochastic DC Optimization with Time-varying Distributions
Impact Statement
Damek Davis and Dmitriy Drusvyatskiy. Stochastic model- based minimization of weakly convex functions, 2018.
This paper presents work whose goal to advance the field of Optimization. There are many potential societal con- sequences of our work, none of which we feel must be specifically highlighted here.
Damek Davis and Dmitriy Drusvyatskiy. Graphical con- vergence of subgradients in nonconvex optimization and learning. Mathematics of Operations Research, 47(1): 209-231, 2022.
References
Yuri M Ermoliev and Vladimir I Norkin. Sample average approximation method for compound stochastic optimiza- tion problems. SIAM Journal on Optimization, 23(4): 2231 2231-2263, 2013.
Robert J Aumann. Integrals of set-valued functions. Journal of Mathematical Analysis and Applications, 12(1):1-12, 1965.
Albert S Berahas, Frank E Curtis, Daniel P Robinson, and
Matthew Fahrbach, Adel Javanmard, Vahab Mirrokni, and Pratik Worah. Learning rate schedules in the presence distribution shift. In Proceedings of the 40th Inter- national Conference on Machine Learning. volume 202 of Proceedings of Machine Learning Research, pages 9523-9546. PMLR, 23-29 Jul 2023.
Baoyu Zhou. Sequential quadratic optimization for non- linear equality constrained stochastic optimization. SIAM
J. Optim., 13527933 2021.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non- stationary stochastic optimization. Operations Research, 63(5):1227-1244, 2015.
Dylan Foster, Ayush Sekhari, and Karthik Sridharan. Uni- form convergence of gradients for non-convex learning and optimization. In Advances in Neural Information Processing Systems, 2018.
Raghu Bollapragada, Richard Byrd, and Jorge Nocedal. Adaptive sampling strategies for stochastic optimization. SIAM Journal on Optimization, 28(4):3312-3344 2018.
Richard H Byrd, Gillian M Chin, Jorge Nocedal, and Yuchen Wu. Sample size selection in optimization methods for machine learning. Mathematical programming, 134(1):
Billy Jin, Katya Scheinberg, and Miaolan Xie. High proba- bility complexity bounds for line search based on stochas- tic oracles. 2021.
127-155, 2012.
Hoai An Le Thi and Tao Pham Dinh. De programming and dea: thirty years of developments. Mathematical Programming, 169, 01 2018.
Richard G Carter. On the global convergence of trust region algorithms using inexact gradient information. SIAM Journal on Numerical Analysis, 28(1): (8(1):251 1-65,, 1991.
Coralia Cartis and Katya Scheinberg. Global convergence rate analysis of unconstrained optimization methods based on probabilistic models. Mathematical Program- ming, 169(2):337-375, 2018.
Hoai An Le Thi, Hoai Minh Le, Duy Nhat Phan, and Bach Tran. Stochastic dea for minimizing a large sum of DC functions with application to multi-class logistic regres- sion. Neural Networks, 132:220-22 2310022211222000 2020.
Charles Castaing and Michel Valadier. Measurable mul- tifunctions, pages 59-90. Springer Berlin Heidelberg, Berlin, Heidelberg, 1977.
Hoai An Le Thi, Van Ngai Huynh, Tao Pham Dinh, and Hoang Phuc Hau Luu. Stochastic differencc-of-convee functions algorithms for nonconvex programming. SIAM Journal Optimization, 32(3):2263-229)) 2022.
Hess Christian. Chapter 14 set-valued integration and set-valued probability theory: An overview. In E. PAP, editor, Handbook of Measure Theory, pages 617-673. North-Holland, Amsterdam, 2002.
Hoai An Le Thi, Hoang Phuc Hau Luu, and Tao Pham Dinh. Online stochastic DCA with applications to prin- cipal component analysis. IEEE Trunsactions Neural Networks and Learning Systems, 35(5):7035-7047, 2024.
Frank Clarke. Optimization and Nonsmooth Analysis. SIAM, 1990.
Junyi Liu, Ying Cui, and Jong-Shi Pang. Solving nonsmooth and nonconvex compound stochastic programs with ap- plications to risk measure minimization. Mathematics of Operations Research, 47, 03 2022.
Ying Cui and Jong-Shi Pang. Modern Nonconvex Nondiffer- entiable Optimization. SIAM, 2021.
Frank E Curtis and Katya Scheinberg. Adaptive stochastic optimization: A framework for analyzing stochastic opti- mization algorithms. IEEE Signal Processing Magazine, 37(5):32 42, 2020.
Song Mei, Yu Bai, and Andrea Montanari. The landscape of empirical risk for nonconvex losses. Annals of Statistics, 46(6A):2747-2774, 2018.
10

---

An Online Adaptive Algorithm for Stochastic DC Optimization with Time-varying Distributions
Boris S Mordukhovich. Variational Analysis and Gen- eralized Differentiation I: Basic Theory, volume 330. Springer Science & Business Media, 2006.
Selection in Classification. In Proceedings of the 34th In- ternational Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3394 3403. PMLR, 06 Aug 2017.
Abdellatif Moudafi. Regularization of DC Optimization. Pure and Applied Functional Analysis, 2022.
Jingyi Wang and Cosmin G Petra. A sequential quadratic programming algorithm for nonsmooth problems with upper-C" objective. SIAM Journal Optimization, 33 11:2379-2405 2023.
Atsushi Nitanda and Taiji Suzuki. Stochastic Difference of Convex Algorithm and its Application to Training Deep Boltzmann Machines. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 470-478. PMLR, 20-22 Apr 2017.
Jingyi Wang, Ignacio Aravena, and Cosmin G Petra. sequential quadratic programming method for nonsmooth stochastic optimization with upper-C" objective, 2023.
Nikolaos S Papageorgiou. On the theory of banach space valued multifunctions. 1. integration and conditional ex- pectation. Journal of Multivariate Analysis, 17(2):185- 206, 1985. ISSN 0047-259X.
Huifu Xu. Uniform exponential convergence of sample aver- age random functions under general sampling with appli- cations in stochastic programming. Journal of Mathemat- ical Analysis and Applications, 368(2):692- 2010.
R. T. Rockafellar and R. J-B Wets. Variational Analysis. Springer-Veriie Berlin Heidelberg, 1998.
Xu, Qi Qi, Qihang Lin, Rong Jin, and Tianbao Yang. Stochastic optimization for de functions and non-smooth non-convex regularizers with non-asymptotic conver- gence. In Proceedings of the 36th International Con- ference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 6942-6951. PMLR, 2019.
Feng Ruan. Subgradient convergence implies subdifferential convergence on weakly convex functions: With uniform rates guarantees, 2024.
Abishek Sankararaman and Balakrishnan Narayanaswamy. Online robust non-stationary estimation. In Advances in Neural Information Processing Systems, volume 36, pages 50506-50544. Curran Associates, Inc., 2023.
Yao Yao, Qihang Lin, and Tianbao Yang. Large-scale opti- mization of partial auc in range of false positive rates, 2022.
Alexander Shapiro. Stochastic Programming by Monte Carlo Simulation Methods. Humboldi-Universittt zu Berlin, aaahemmticch-auuuussssschhiiiii Fakultät II, Institut für Mathematik, 2000.
Sara Shashaani, Fatemeh S Hashemi, and Raghu Pasupa- thy. ASTRO-DF: A class of adaptive sampling trust- region algorithms for derivative-free stochastic optimiza- tion. SIAM Journal on Optimization, 3144):314--3176, 2018.
Kaizhao Sun and Xu Andy Sun. Algorithms for difference- of-convex programs based on bifference-of-morces envelopes smoothing. INFORMS J. Optim., 5:321-339, 2022.
Pham Dinh Tao and Le Thi Hoai An. A D.C. optimization algorithm for solving the trust-region subproblem. SIAM Journal on Optimization, 8(2):476-505, 1998.
Pham Dinh Tao and LT Hoai An. Convex analysis approach to de programming: theory, algorithms and applications. Acta mathematica vietnamica, 22(1):289-335 1997.
Hoai An Le Thi, Hoai Minh Le, Duy Nhat Phan, and Bach Tran. Stochastic DCA for the Large-sum of Non-convex Functions Problem and its Application Group Variable

---

An Online Adaptive Algorithm for Stochastic DC Optimization with Tary-narying Distributions
A. Convergence Rate for the SAA Error of Subdifferential Mappings
A.1. Proof of Lemma 3.3
Proof. By direction computation, we have
D
Omp wr) BB (x))((
Oz4 (1) }. conv Re (02p(1;
TD
conv
Σ Ozp (1)w²)
sup
U1 n1
a (u, Eu ( (xr wI)
||
sup
a 00y (z,
(u, LEw (0, w]ll
||
o (u, 0o4 (z, w)) Ew lo (2, (xpp((,,))))
sup ||]|
n
By the convexity of yp (z, W), O240 (x) is convex and compact, hence - dzp (x, w²) and E. [0, w)] are convex. The first equality stands. The second equality is due to (4). The third equality is due (3). The last equality is due the interchangeability of E. and a; see Proposition 3.4 in (Papageorgiou, 1985) for details.
Following the same derivation, we also have
1 n 72
Σ 02 (I,ww) (e)-)))===
1 Σ a (u, d. (x,
Rew [r)
= sup ||x] 1
B la (u, (xp,,,(
n
We thus conclude the proof using the definition of the Hausdorff distance Hl.
A.2. Proof of Theorem 3.4
Proof. For any Dap by Lemma 3.3,
1
E An
= Es sup ||
(u,ww) - Ew (w)
where (u, = o (u, Ozpp ()). To satisfy the condition in Lemma 3.1, we first verify that (b. are uniformly bounded by constant Tup and Lipschitz continuous with constant Tup in the first variable u E TB(0, 1) S [-1,1] uniformly in w.
The first property trivial since sup (|ا $ Lip. Now, we prove the second property. For any u.v B(0, 1),
suppose that a (u, Ox w)) u s where & E O25 w).. Then we have
(v. 0 (x. w)) 2 TT ITs ||u w||||||| 2 (u, 0.5e w)) I 111uu w/|-
Similarly, (u, 0 (x, w)) > a (v. 0.s0 (x, w)) Lullur v/I, hence (w) is LipLichchitz continuous in (B, 1).
We thus finish the proof after using Lemma 3.1.
A.3. Proof of Theorem 3.5
2+. Proof. For any x E Pg. let ō An (v9, w²), which is bounded by Lip. By Lemma 3.4, E.n and P f exp -2/ (2T2)) } stands for any s > a' (a, 1/2).
n"
12

---

An Online Adaptive Algorithm for Stochastic DC Optimization with Time-varying Distributions
Hence for any >> O, have
821(8 C+s
e+ $ na
B.n [0-]
+ Eg
81 2
na
c+8
2 è 8+8)
< Egn [0]
P2P P
na
na'
< c(c + 8) +(t+s) 22 Eg exp - (212)}
where the first inequality is due to 8 2 Lyp, and the last inequality is due to Lemma 3.4.
Take V2Lp Inn, could obtain that
à (e+ 2 Va'lnn) + T
B (82) s
20
Since vlnn S n 222
we have for any a' E (a,1/2),
2a/o'-aje"
c+ v2Lg
Ja
+ L
2 2a
Exn [691 s
2a
where ē= (2(2 + Tup/ V(1 - 20)
B. Convergence Analysis
B.1. Proof of Lemma 4.2
Proof. From the convexity of ge(-) and he).), have
(x(x)) - (x + d:) + =T = 2
2 Pg 1|d,11?
(12)
he(2, + d,) he(xx)) vtt de 2 ph. de d
for 2 E Ögr + de), x. + d, E C. Therefore,
fe(xt) [1(xx+1) = ge(xz) - l((())) - -0((0+1))))++)))) + 1((x+11)
-x(e) (e(()+11) - -he(x)) + (x(44441) + (gx(xx)) - Dr (xx)) - [gx(x)+1) - (x++1)l
(13)
2 _ de + 3/2 de 5 (Pg + pn)]ldd.12 + gr(e))
ge(xx) ge(x441) (c((e+)).
Taking the dot product with d, of the first line of (7), we have
- - de + v/ dg = ||d 2 + R.dy
24 2 + [ic(x;) - ic( + + - v-d()
(14)
2/4 || 1|
where the first inequality uses the second line of (7) and the second inequality comes from the convexity of C and ic(:). Applying (14) to (13) leads to
fe(xx)) fe(xx+1) 2 (yr - Tde + 14 + Pg + Ph
|| 12 + ge(e)) - (xx) - ge (x++1) + (e(+++1)-
(15)
2
13

---

An Online Adaptive Algorithm for Stochastic DC Optimization with Tary-varying Distributions
B.2. Proof of Corollary 4.3
Proof. First we prove that ||de]| < 2(4,+ba), Since de is the solution of subproblem (6), we have
Ht
( de) - he(2))) -b, de 2 uelldell M.(d,) - M, (xx) - (x(
Hence we have 1 sdelldel? s (x() (0 + d,) o/ de - [d + Lb). which implies ||dell - 2 2(b
Let b(x+ and (xx E) = G(r, { - G( E). which is Tpg-Lipsciit. By Lemma 3.1,
1
n
Co Na 91
Es,..
sup
Σ
+ (oz + dmn 5 EE (xx + E
Ft
S
n 6.
where Cg = 22 + / (1 ). Noticed that
1 n
(0( g (2(+1) + gc(t))
sup 62 m.
s (ot + E
PEN (az + dzr
n
Hence, we finish the proof by substituting ra for its definition.
B.3. Proof of Lemma 4.5
Proof. By Lemma 4.2, for any Ur E (2h4(2)), c c>0 20, 0,
fe (x1) - fe (x0+1) 2 (ye- - 31)² T
de + Me +
Pg + Ph ||ābll + (zx)) - (x)) - (((()))) + (e(x141)
2
2 (14 + Pg + Ph
c) |idel 2 + (x())) gx(1)) - (0(()))))))))))))))))))))))))-)- + (1(+1))
1
llye - -Dell2
2
4c
Take such that dist(Br, (x,)) = 11//= - Dell. we have
fi (x+) fe (xx+1) 2 (Mt + Pg + Ph. <) ||de 2 + gxx) - (x() - gc(Ix+1) + (x++1)
dist ahe())))
2
4e
2 (E + Pg Ph c) || 2 + (x:) - (x)) (c( + (
p2 (0he(z)), Oha(z)))
4c
(16)
By Assumptions 4.1, and the definition of Wasserstein-1 distance, we have
g: (x++1) - ge+1 (((4(1++1) Be (G(E,4)))) - Pe- [G(I++1,)]
Pc.),
h1(1))1)= (+4141+41) Eg (x Ee (H(C411 s L. (P,.4. Pç..).
Hence, we have
Se (x - se+11 (I++1) 2 Taking expectation for both sides of (16), (17) under Fe, we finish the proof after Corollaries 4.3 and 4.4.
Pe.)) W Pc.))
(17)
B.4. Proof of Theorem 4.8
Proof. Fix c 5. Taking the expectation with respect Fo and summing over all / in Lemma 4.5, derive
E
μt + Pg
+ Ph
SE [E - fn (x Σ
Cg
+
Ch
2
2
JNN g.t
2ü
0
1=0
(18)
WLeWi (Peat1, Pe.) + L:Wi (Prati, Pc.)).
14

---

An Online Adaptive Algorithm for Stochastic DC Optimization with Tirc-varying Distributions
Fix any e > there exists N 0 such that for any N, (1 c. Pt),WI(PP.. s.n Pc) S e. Similar (17), we have (sr)) - fxx)) & (P(P..m L + ( P.) Since fx) 2 f. we have (x() 2 <(T + T&)) + f. which is lower bounded uniformly over N.
Combining Assumptions 4.6 and 4.7, the right hand side of (18) is upper bounded and the left hand side of (18) is greater than $ Ei=o |dd||| the first part of the theorem is proved by letting n + 0C.
We proceed by contradiction for the second part of the theorem. Suppose there exists >> 0 and a >> 0 such that
P lim suplldee
2 t Fo
2 a.
(19)
E 1l1c 19,1
By Chebyshev's 's inequality, we have IP (Ildel 2 Fo)
I
Since E [[dd]1][Fo] is finitely summable, there exists
T >> 0 such that Ei= P (11ăel) 2 c Fo) s <inr R
F| Fo
< a. Therefore,
P suplldel 2 6 Fo =P =P (+20
limsup |Idell 2 E Fo
PP (1del) 2 é Fo) < a.
(20)
This is contradiction against (19). Hence, we could obtain that lim |dell = 0 with probability 1.
B.5. Proof of Lemma 4.9
Proof. We prove this by contradiction. Let (xx, {) = G(x, {) - G(2, dr(x) = 9((x) (2). and Te = (t) Suppose there exist constants e >> 0 and a > 0 such that I (lim (0((z) - (z) 2 c Fu) 2 a.
2 -10) [b]
By Chebyshev's inequality, we have P (z)
(x)) 2 c Fo) S
Note that Egn ((x {)]
(I)r), and since & (ar, E) v I.g R, its variance is bounded by r2 Thus, we have E [[d)((() - {x) F s No. and
R22
1 R²
taking expectation with respect to Fo, we get E [(v((=) - 5x(x) / Fu] S
LgRe No.""
Summing over t, we obtain
12
Σ B - Fo 1=0
y
+00,
1=0
since Er Nyjh +00 holds for oig
< 4.2 Therefore, there exists T
> 0 such that
-P( [im sup (0)(x) - (xx)) 2 e Fo <
P lum (x) - 5e(+)) 2 2elFo) =P lim
P (l),(x) - -x(()) 2 2e Fo) < a.
(+20
This contradicts our assumption, and thus we conclude that lime- (0)(x) - [x(1) = 0 with probability 1. The proof for L.,12
the second part is similar, since the condition E
No. < 0o also holds.
B.6. Proof of Theorem 4.10
Proof. Let be an accumulation point of {at). From the optimality condition (7), there exist ž441 E (ge()))1) and 0, E 0ic((1411 i) for each I, such that
E T. + u4d, + 82 0.
(21)
We can assume lim In, = x where x E C. Further, He and & are bounded due to the Lipschitz continuity of G(r, { and (a, <). Thus, 0, is also bounded, and there exist accumulation points for {u+} and ) Without loss of generality, with the same subsequence, we assume In. + ÿ and 2 + z. Therefore Tn. - ÿ and 2n,41 + Σ. By (21), we have
0 = - Dn: + Un, dn, + Uny-
(22)
By Theorem 4.8 and Assumption 4.7, lim m,de = 0 with probability 1. Thus, lim Ing = 2 - E with probability 1. Given that Fn, E dic (xa, the outer semicontinuity of dic(.) leads to lime- Un, E (.)
15

---

An Online Adaptive Algorithm for Stochastic DC Optimization with Time-varying Distributions
Finally, we prove that y E ah( and ž E @g(()). As yn (In.) have
Fy, (I In.) - hx(x) - he(),.), for all æ E R).
(23)
Notice that
(1(( - M(T) S (x) M(T)) + Ln 11 - :11
and for all i E (B R).
- 14, hx(x)) + Le
Hence for all x E B(E, R), we have
- (h(x))))) [x)(x) - - - h(=)) SLn 1 - Ø1 + L.
Combine with Lemma 4.9 and the fact that 2n, + I and Wi (Pc,, Pc) + 0, we conclude that he(2)) (e( + h(x) h()) for all B(,,, R) with probability Hence, by letting for all x [2,, R). This inequality yields E Oh (æ). The proof of E 0g(ø) is analogous. Therefore, prove that is a DC critical point of f with probability 1.
in (23), one obtains sj (x- S h(xx) 1(())
C. An Adaptive Sampling Algorithm
C.1. Proof of Theorem 5.3
Proof. Let Ti be the set of when Summable Condition is satisfied; To be the set of when Stepsize Norm Condition is satisfied. Supposed that when t 2 T, t E T2 If E T2, we derive from Lemma 4.5 (the proof of Lemma 4.5 does not rely on Assumption 4.7.(b)) that
Pg + Ph
E ff (2,) fet1 (Z)+1) [F 2 (14 +
cB
2
( + Pg + Ph
- cu - cz)
l|d
Le Pt.))
LcWi Pç.))
2
Taking expectation under Fo from both side, we have
E Ei (2x) - fet1 (#1+1) Foo 2 (m: + + Ph
G) || |F0] - -(w-
Pg + Ph Cp
EE 1
2
2
LeW1(PE,tI. Pε.)) L. Pç.e).
Ift Ti (0,1, - 1}. take expectation under Fo, have
E If (2.) - fe+1 (I0+1) Fol 2 ((p + Pg Ph)) - c1)LE [| de 1
)
C
Cn
T.eWi Pe.) - T. Pt.))
N
Nc,No.
Taking sum for each t, we have
E
14 +
Pg
+ Ph
|F
S E. [Fo (2o)
(xn)
Fol +
T-1 Σ
C
+
Cn
MeN git
No
1=0
Σ
Cg
+
Ch
(HL-1 + Pg ph
c.-1 -cp
|
116-_112/5o
(24)
No git
No
2
THET
T=T,TTTa
(P
L Wi Pc.)).
16

---

An Online Adaptive Algorithm for Stochastic DC Optimization with Tiry-varying Distributions
Hence, could obtain that
E
cu Fo
(F(oo(o) - fn (5o
C Ne git
+
Cn No,
Σ
Cg Cg 1NN git
Cn 4
(LeWi(PG411) P(,)) W LLWi(P Pc,a))
T=
(25)
As derived in Theorem 4.8, is lower bounded when is sufficiently large. Therefore, E [fo (zo) fn (In) |Fo] is bounded above. By the definition of Summable Condition and Assumption 4.7, we have
C. N
Ch No,
n-1
Cg juN
C 4eeN
+
T=TE
(=T,ETi
Moreover, as we derived in Corollary 4.3.
|d 1
which is bounded. follows that
10 < cc. Take - co, since the right-hand side of (25) is bounded, we have
lim
Σ 220
[del
Foo
<0.
(26)
toc
Supposed that when t 2 TU Ift Ti, we have
N₂. 2 Ng. and Nr,1 2 Nr.1, where
(Nwa + +Nr000 00.
(27)
If t T2, we have
C
C
C
+
AN
Ai +
PatPh 2
Na.
N g.t.
A(14 + PotPh - Cp) No..
g.
2 2
C
Ch
Mr N
Ac,No.
(28)
Pc-1 +
Pg Ph.
Cp
Cc-1
|1
A
Pg
Ph.
Cp
C--1
||de-al1?
where the first and last inequality due to Assumption 4.7, The second and third inequality is due to the definition of Stepsize Norm Condition (11). (28) implies that
C
C₁
<
(
Pg +
11
(29)
4( +
Pa
Naa
2
2
By (27), (29) and (26), follows that
Σ
C
C
T-1
C
C₂
+
+
NN
4(fe
+
PotPA
Noa
juNaz
4(0 +
Poten
Nan h.1
120
1=
Cg
Cn
Pg + Ph
A++
|d-1112 oc.
j
4(a + Puten
Naa
2
TTTET
12THETa
Hence, derive from the above that 4.7 (b) holds.
17

---

An Online Adaptive Algorithm for Stochastic DC Optimization with Tiry-varying Distributions
C.2. Adaptive ospDCA: A Full Version
Algorithm 3 Adaptive ospDCA
Require:
Initial point z0, initial parameter μa- co, Ng.0 and N1,0, enror estimation parameter ag E (0,1/2), on (0, 1) with corresponding Cg: Ch defined in Corollaries 4.3 and 4.4, stepsize norm condition parameter Cjs < 0, sample size upper bound sequence {Ng.a} J and {Na,,} which satisfy Σ1z0 (Ni,t" + -Ng.t" and lower bound jú that satisfy f > it.
stepsize upper bound
1:
for = 0, 1, 2, ... do
2: Generate iid samples (5t.)) No. and {( Nr. from the distribution of and S, which are independent of the past. T== 3: Set (x(x) No. En G (x) hx(x) Nu. IN H (t.). and select Ur Thg (x+).
J=
4: Solve the convex subproblem to obtain d.:
minimize (e + d) - -xr( - Ve d 2 1|l]
subject to xe C.
5: Take the step T441 = 8z + d.
6: Update ji S M141 S f. ct+1. NN got and Nh.+1 such that one the followings stands:
1. [it + Potph cp -ca |db||22 2
C. +
Cn
and C++1 I Me+11 + PstPh
Cp.
Ng 2 Notti, Nr. 2 N1,141, and at S C4+1 S 14+1
Potph
Cp. 2
7: end for
18

---

An Online Adaptive Algorithm for Stochastic DC Optimization with Time-varying Distributions
D. More Experimental Results
Performance Over Beeations
Perfermanne Over Time
DEERiCA (tatt
IaDDEA
Spi0C4
(NpECC 94A
OSEUKAA With SMA HAW
Disteinee Saludor
Disterce to Optimall Sahudar
100
10-1
10-1
30"1
5014
CIPOCA
EIPOCA
1000
10
(c) p 100, Boge
[5, 5,0,0000 0,0,
Performance Over Ieeraions
Performanne Over Time
Adaptive DEERCC (cart)
IRDDEA
Spp0C4
UnsDCCA 54A
OSBUKLA With 1AW
Disteinc Cottmnal Salubor
Disterce to Cptimal Salutar
100
10:11
Sp.0CA
CIPOCA
EIPOCA
1000
10-1
(d) p 200, Som
[5,
0,
0).
Performance Over Iterations
Perfermance Ovee Time
Adsptiv
Adaptira oupoca
aEA
SpiOC4
PaA with 100
SNHDCA
ISBULA with sin 1RR0
ESSULA With STA 1980
Disteicc to Cytemal Saluber
Disternc to Cptimal Saludor
100
10
10-2
(e) p Sog [5, 5, ,0], 8, (-1)' 21p-
Figure 3. Algorithm behavior for online sparse robust regression.
19

---

An Online Adaptive Algorithm for Stochastic DC Optimization with Tire-varying Distributions
Sampla Siza Iterations
Sample Iterations
Sample Size Over lterations
Adeplive sapOCA lears)
opp
oqutta
125/0
0000
Samdl Stee
0332
7500
3000
30000
2000
9000
25
40
330
50
75
160
225
135
780
Sample size for experiment (c).
Sample size for experiment (d).
Sample size for experiment (e).
Figure 4. Sample size iteration.
20


Reviews:
[{"review_id": "mBEZVfpq4r", "reviewer": "Reviewer_q3uU", "summary": "This paper proposes algorithms for solving a stochastic DC program in a time-varying setting. Specifically, the distributions used to define stochastic convex components may vary over time and are assumed to converge to the true distributions. The proposed algorithm is a variant of the classic DC algorithm and uses SAA to estimate the current distributions on the fly. The main result is an almost sure convergence guarantee to DC critical points, up to taking subsequences. To prove this result, the authors develop a new upper bound on the estimation error of the SAA scheme for convex subdifferentials in terms of the excess of one set over another. Overall, I think the contribution is interesting and meaningful for solving a difficult stochastic DC program.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reading and valuable feedback. Below, we provide clarifications regarding the comments you raised:  \n\n1. **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.  \n\n2. **L127, right:** Thanks for pointing out this improper statement. We will change the statement to the following:\n   *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$.*  \n\n3. **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.  \n\n4. **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.\n\n5. **L160, right; L806; L869; references:** We appreciate your careful attention to detail. We will correct these typographical errors and remove uncited references accordingly.  \n\nThank you again for your valuable feedback. We will carefully incorporate these revisions to improve the clarity and precision of our work.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, I have checked some of the proofs in Appendices A and B, and they look good to me.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "The new algorithmic framework in this paper is built on the classic DCA and SAA schemes. The authors propose new theoretical results to determine the number of samples sufficient for almost sure convergence to a DC critical point.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Overall, I think this paper makes good and interesting contributions to DC programming in the modern stochastic setting. I only have the following comments.\n\n- L019, right: I suggest using the term \"DC critical point\" here rather than \"critical point,\" since the latter is sometimes used interchangeably with \"stationary point\" and has a totally different meaning compared to a DC critical point.\n\n- L127, right: It seems $\\mathbb{P}(\\Omega)$ is a set of distributions. Hence, it is not clear to me what the meaning of $\\xi \\sim \\mathbb{P}(\\Omega)$ is.\n\n- L160, left: It seems that $g, h$ here are convex extended-real-valued functions, since you need to use the indicator function $i_C:\\mathbb{R}^p\\to\\overline{\\mathbb{R}}$ to represent the constraint $x \\in C$. However, I cannot find their concrete definitions.\n\n- L160, right: The function $\\phi$ should be $\\varphi$?\n\n- L280, right: Compared with the convergence conditions in L328, left, these two summable conditions seem a bit stringent. It would be illustrative if a concrete example were discussed that satisfies this summable condition.\n\n- L806: Lemma 4.3 should be Corollary 4.3.\n\n- L869: \\bar{z}_{n}  should be \\bar{z}_{n_t + 1}.\n\n- Some papers are listed in the references without a citation in the main paper, e.g., (Kantorovich, 1958), (Goldstein, 1977), (Geyer, 1994), (Mehta, 2016, 2014), (Liu et al., 2018) and many others.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GmEZF9iTY5", "reviewer": "Reviewer_rStE", "summary": "The paper studies stochastic difference-of-convex (DC) optimization. The analysis accounts for distribution shifts, and for non-smoothness of the components is derived, introducing some non-trivial technical contributions. The obtained algorithm is validated in a numerical experiment.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reading and valuable feedback. We address your questions as follows:  \n\n1. **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.  \n\n2. **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.  \n\n3. 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.  \n\n[1] Drusvyatskiy D, Xiao L. Stochastic optimization with decision-dependent distributions. Mathematics of Operations Research, 2023, 48(2): 954-998.\n\n[2] Che E, Dong J, Tong X T. Stochastic gradient descent with adaptive data. arXiv preprint arXiv:2410.01195, 2024.\n\n4. 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.\n\n[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.\n\nThank you again for your valuable feedback. We appreciate your insights and will carefully consider them in our revisions.", "claims_and_evidence": "The paper is extremely well written in my opinion. All claims are motivated, situated with respect to prior work, which makes is rather easy to follow even for non-experts.", "methods_and_evaluation_criteria": "Then proposed methods make sense, and are essentially generalizations of prior discussed work.", "theoretical_claims": "I did not closely check the correctness of the claims. I believe they are overall correct, as the proofs are sketched and motivated in the main text in a rather convincing manner, and the main claim generalize prior known results.", "experimental_designs_or_analyses": "I did not check the validity of the experiment itself.", "relation_to_broader_scientific_literature": "The authors do a fantastic job in my opinion situating this work with respect to prior works on this topic. Even small technical derivations are compared to prior analogous results, as well as the main ideas.", "essential_references_not_discussed": "I am not aware of essential references which are missed.", "other_strengths_and_weaknesses": "As I mentioned, the paper is extremely well written in my opinion.\n\nThe technical contributions, even beyond the end results, are quite nice.\n\nIn particular, accounting for distribution shifts in the descent lemma by incorporating a Wasserstein distance term (Lemma 4.5) is a very interesting idea, which I have not seen before. This approach is really nice, and can be applied to many other optimization scenarios.", "other_comments_or_suggestions": "Additional comments:\n\n- Remark 2 is unclear to me, what does an isomorphic map imply here and why?", "questions_for_authors": "- Assumption 3.2 confuses me - wouldn't this correspond later to the gradient being Lipschitz? If so, this would require smoothness, which the authors are trying to avoid. I kindly ask the authors clarify this issue.\n\nQuestions to the authors:\n\n- Is the idea of incorporating a Wasserstein distance term in the descent lemma (Lemma 4.5) novel in this work?\n\n- It would be nice to derive non-asymptotic rates, which seems doable via the provided descent lemma (perhaps under further quantifiable assumptions). Is there a clear difficulty in doing so? It is fine to leave this for future work nonetheless.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4BsZJmgEaf", "reviewer": "Reviewer_AmGZ", "summary": "The authors address the minimization of a function defined as the difference of two convex functions.\nMoreover, these two convex functions are expressed as the expectations of random functions.\nThe authors then propose online estimators based on an adaptive sampling algorithm.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reading and valuable feedback. We address your concerns as follows:  \n\n1. 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.\n\n2. 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.\n\n   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.\n\n4. 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.\n\n5. 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. \n\n    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.  \n\nThank you again for your thoughtful feedback. We will incorporate these improvements to enhance the clarity and accessibility of our work.", "claims_and_evidence": "The proofs seem solid.", "methods_and_evaluation_criteria": "The simulation work is somewhat limited but very promising. However, the methods have not been applied to real data.", "theoretical_claims": "The proofs seem true.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The key contribution consists in considering subdifferentiable sets while in the existing literature, authors often consider smooth functions.", "essential_references_not_discussed": "Not to my knowledge.", "other_strengths_and_weaknesses": "The proposed methods and results are very interesting.\nHowever, I have a few remarks:\n\n- I believe the discussion on the number of data points to generate should be expanded. The approach appears computationally intensive since, at each step, a larger dataset needs to be simulated than in the previous step. That said, I do agree that the simulations suggest the proposed method is computationally faster than existing methods.\n- The paper is somewhat difficult to read, partly due to the complexity of the problem studied and partly because of the large number of technical lemmas in the core of the paper (e.g., Lemmas 3.3 and 4.2). These lemmas do not seem to aid comprehension and instead make the paper heavier. It would be better to move them to the appendix, freeing up space for more in-depth simulations or an application to real data.\n- The proofs are challenging to follow, with some steps moving quite quickly.", "other_comments_or_suggestions": "It's just a suggestion, but wouldn't the proofs have been simpler (at least to establish the almost sure convergence of the estimators) by using Robbins-Siegmund's theorem?", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Wx9UnWmORt", "reviewer": "Reviewer_Fi1S", "summary": "In this paper, the authors propose an online adaptive sampling algorithm for solving nonsmooth DC problems under time-varying distributions. \nTheir major technique is the development of a convergence rate for the sample average approximation of subdifferential mapping.\nBased on the technique, they show their algorithm converges subsequentially to DC critical points almost surely under proper assumptions.\n\n## update after rebuttal\nThe author's reply makes sense, so I keep my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reading and valuable feedback. We address your comments as follows:  \n\n1. 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)$:\n\n$$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))],$$\n\nwhere $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. \n\nLet $\\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.\n\nFor 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).\n\n2. 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.\n\n[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.\n\n3. 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).  \n\nThank you again for your valuable feedback. Your insights are greatly appreciated and will help improve the clarity and rigor of our work.", "claims_and_evidence": "The authors propose stochastic algorithms to solve the nonsmooth DC problem, and they provide the asymptotic convergence of their algorithm under mild assumptions.\nTheir theoretical findings are both solid and interesting. \nMy only concern for this paper is what machine learning applications belong to the class of stochastic DC problems under time-varying distributions. \nI have noticed the author listed the online sparse robust regression as an application of their problem. \nCould you provide more machine-learning examples of the nonsmooth DC problem?\nIn addition, is there any real-world time-varying data distribution that satisfies Assumption 4.6, could you provide some examples?", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria for solving the problem make sense to me, and the author provides a rigorous theoretical analysis of their methods.", "theoretical_claims": "See above.", "experimental_designs_or_analyses": "The experimental designs are valid and sound.", "relation_to_broader_scientific_literature": "See above.", "essential_references_not_discussed": "I think most related works are cited and discussed.", "other_strengths_and_weaknesses": "Since there are many works developing stochastic methods with non-asymptotic convergence rates for nonconvex nonsmooth optimization problems. \nIs it possible to show the proposed methods with a non-asymptotic convergence rate for solving the stochastic DC problems?", "other_comments_or_suggestions": "I found some small typos in the paper:\n\n* In line 209, did you miss a square for the $\\delta_n$?\n* In assumption 4.1, I think it is better to say $\\rho_g$-strongly convex.\n* In Lemma 4.2, there is no definition of the function $f_t$, although it is not hard to guess.\n* The conclusion and future work section is missing in this paper.\n* In Line 708, what is $\\alpha_h$? Should it be $\\alpha'$?", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper investigates stochastic optimization of difference-of-convex (DC) functions, where both components are expressed as expectations over random functions and the data distribution may shift over time. The authors develop an online adaptive sampling algorithm and provide rigorous asymptotic convergence guarantees to DC-critical points under mild assumptions. A key technical innovation is a convergence rate for the sample average approximation of subdifferential mappings, with the analysis carefully incorporating distributional shifts via Wasserstein distances. The main convergence result  is nontrivial and appears technically sound.
Decision: Accept (oral)