acceptodds
Under review as a conference paper at ICLR 2027

A Mini-batch Proximal Adam Algorithm for Nonsmooth Nonconvex Stochastic Composite Optimization via MCMC Sampling

Abstract

We propose MCMC-ProxAdam, a novel stochastic proximal gradient algorithm designed to solve constrained nonconvex stochastic composite optimization problems with a nonsmooth convex regularizer, in settings where the gradient of smooth part is intractable and must be estimated via MCMC sampling. We depart from the traditional assumption of bounded stochastic gradient by introducing bounded sub-exponential norm for the stochastic gradient, then we derive a Bernstein-type inequality for the mini-batch stochastic estimator under non-stationary Markov chains, allowing our framework to accommodate biased and unbounded stochastic gradient common in practical scenarios. Leveraging this Bernstein-type inequality, we derive error bounds for the mini-batch gradient estimator and establish the convergence result for MCMC-ProxAdam in the nonsmooth nonconvex setting. Numerical experiments on energy-based models (EBMs) for image generation tasks across the MNIST, CIFAR-10, and CelebA datasets demonstrate that the proposed algorithm is capable of solving nonconvex composite optimization problems with a convex nonsmooth term, with numerical performance empirically validating our theoretical convergence results.

Primary area:
optimization
Keywords:
A Mini-batch Proximal Adam Algorithm, Nonsmooth Nonconvex Stochastic Composite Optimization, MCMC Sampling

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_64tWOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes MCMC-ProxAdam for nonsmooth nonconvex stochastic composite optimization, where gradients are approximated using potentially biased and unbounded MCMC estimators. The authors develop a Bernstein-type concentration inequality under sub-exponential gradient assumptions and establish convergence guarantees for the proposed adaptive proximal algorithm. Experiments on energy-based models across several image datasets demonstrate its practical effectiveness.

Critical strengths

The paper addresses a meaningful optimization problem by combining nonsmooth regularization, adaptive updates, and dependent MCMC sampling. The theoretical treatment of potentially biased and unbounded gradient estimators is particularly valuable.

The experiments cover multiple image-generation datasets and show consistent improvements over the considered baselines. The additional ablation and sensitivity studies provide useful evidence of the method's practical effectiveness.

Critical weaknesses
  1. The convergence analysis contains inconsistencies that weaken the theoretical guarantees. The momentum parameter schedules in the corollaries appear incompatible with conditions required by the supporting proofs, while some steps in the gradient estimator error analysis require further justification (see Corollaries 1–2, Lemma C.5, and Appendix B.5 of the submitted paper).

  2. The connection between the theoretical assumptions and experimental implementation remains insufficiently established. The Langevin sampler used in the experiments is not shown to preserve the required target distribution, while the spectral-gap assumption alone does not account for potential discretization bias, as discussed in Durmus and Moulines (2017).

  3. The theoretical novelty relative to existing literature is not sufficiently distinguished. Previous studies have already investigated nonconvex composite optimization with dependent data (Alacaoglu and Lyu, 2023) and Adam-type algorithms under Markovian sampling (Xiong et al., 2021). The paper should more clearly identify the additional theoretical contributions beyond these related frameworks.

References

[1] Durmus, A., and Moulines, É. (2017). Nonasymptotic Convergence Analysis for the Unadjusted Langevin Algorithm. Annals of Applied Probability.

[2] Alacaoglu, A., and Lyu, H. (2023). Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data. ICML.

[3] Xiong, H., Xu, T., Liang, Y., and Zhang, W. (2021). Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling. AAAI.

Questions for authors
  1. Could the authors clarify the apparent inconsistencies between the momentum parameter schedules and the assumptions required by the convergence proofs? Do the main convergence guarantees remain valid after correcting these conditions?

  2. How does the Langevin sampling procedure used in the experiments satisfy the theoretical assumptions regarding the target stationary distribution? If the sampler introduces additional bias, how is this bias accounted for in the convergence analysis?

  3. Could the authors further clarify the main theoretical advances over existing studies on nonconvex composite optimization with dependent data (Alacaoglu and Lyu, 2023) and Adam-type methods under Markovian sampling (Xiong et al., 2021)? In particular, which results or assumptions distinguish the proposed framework from these approaches?

5 comments
AuthorsOpenReview ↗

Clarification of the main theoretical advances over existing studies

Response:

We sincerely thank the reviewer for these insightful comments. We address the three points as follows.

Q1:Changing parameters to overcome inconsistency

Response: We sincerely thank the reviewer for raising this important point. As this is a common concern among all three reviewers, we have provided a detailed response under Reviewer 4wby's comment. In brief, the inconsistency stems from parameter specification rather than the proof structure. With the corrections described in Sec. 4, the proofs of Lemma C.5 and Theorem 2 remain valid. The O(1/Nˉ)\mathcal{O}(1/\sqrt{\bar N}) convergence rate in Corollary 2 is unchanged; only the constants are affected.

Q2: Illustration of experimental sampler

Response. We thank the reviewer for this insightful question. As Reviewer AYLW also asks the same question, we have provided a detailed response under Reviewer AYLW's comment. In brief, following the standard practice established by Du & Mordatch (2019), we rely on Unadjusted Langevin Dynamics (ULA) but mitigate its bias via two key engineering techniques: Replay Buffer (to maintain persistent chains and effectively extend the chain length) and Spectral Normalization (to bound the Lipschitz constant and stabilize the discrete steps). Furthermore, following (Du & Mordatch, 2019) (Appendix A.13), we empirically validate that the stationary distribution of our ULA sampler is relatively close to the target distribution. Specifically, we plot the energy distribution of samples generated by our iterative ULA procedure and compare it with that of the training data. The two distributions relatively overlap (as shown in Figure 2, Appendix D.7 of the revised version), indicating that ULA combined with engineering techniques currently serves as an effective choice for EBM training. Your question about how the sampler's additional bias affects the convergence analysis is highly relevant. We plan to conduct further studies on this aspect in our future work.

Q3: Clarification of the main theoretical advances over existing studies

Response. We sincerely thank the reviewer for pointing out these two highly relevant works. Our main theoretical contribution, which fundamentally distinguishes our work from theirs, is the analysis of new MCMC error bounds for the mini-batch gradient estimator under the difficult setting of non-stationary Markov chains and potentially unbounded stochastic gradients. Based on these bounds, we establish the convergence rate of a mini-batch proximal Adam-type algorithm for minimizing a general composite function (nonconvex smooth + nonsmooth convex) on a closed convex feasible region. We detail the distinctions below.

Comparison with Alacaoglu and Lyu (2023). As a pioneering work, Alacaoglu and Lyu (2023) is the closest related work and is listed in Table 1 of our manuscript. We deeply appreciate their contributions to convergence of first-order methods for constrained nonconvex optimization with dependent data. To highlight our distinct focus, we will add a detailed comparison in three aspects to the revised manuscript.

  1. Assumptions: Global vs. Local Weak Convexity. Since Assumption 2.1 of Alacaoglu and Lyu (2023) implies a ρ\rho-Lipschitz gradient, their proof structurally requires global ρ\rho-weak convexity. Specifically, their Moreau envelope (Eq. 4-5) minimizes the proximal operator over the entire space Rp\mathbb{R}^p. To guarantee this minimum is unique and the envelope is differentiable (Eq. 6), they require global weak convexity (e.g., Lemma B.3 for the Lipschitz continuity of the proximal operator). Because this lemma underpins their Key Lemma 2.4 and Theorems 3.1, 3.3, 3.4, 3.5, 3.8, their error bounds collapse if ff is highly nonconvex outside Θ\Theta. In contrast, our projection steps confine all iterates to the feasible region Θ\Theta. We only require LL- smoothness on Θ\Theta (Eq. 2), which implies local weak convexity, and do not need a globally defined proximal operator.

(Due to the character limit, the response continues in the following comment.)

AuthorsOpenReview ↗

Clarification of the main theoretical advances over existing studies (continue)

(Continued from the previous comment)

  1. Stochastic gradient: They use a single-sample stochastic gradient and assume Assumption 2.3 for biased gradient estimation: either (i) bounded expectation of the gradient norm, or (ii) uniformly bounded gradients. Notably, in their derivation from Eq. (94) to Eq. (95), Assumption 2.3(i) alone (along with Assumption 2.2) is insufficient. The condition E[∥G(θ,xt−1)∥∣Ft]≤L\mathbb{E}[\lVert G(\theta,x_{t-1}) \rVert \mid \mathcal{F}_t] \le L cannot guarantee E[∥G(θt,xt+1)∥2∣Ft−k]≤L2\mathbb{E}[\lVert G(\theta_t, x_{t+1})\rVert ^2 \mid \mathcal{F}_{t-k}] \le L^2. By Jensen's inequality, one only has (E[∥G∥∣Ft−k])2≤E[∥G∥2∣Ft−k](\mathbb{E}[\lVert G\rVert \mid \mathcal{F}_{t-k}])^2 \le \mathbb{E}[\lVert G\rVert ^2 \mid \mathcal{F}_{t-k}]. Their Assumption 2.3(ii) (uniformly bounded gradients) is required to bridge this gap, or one must strengthen Assumption 2.3(i) to E[∥G(θ,xt+1)∥2∣Ft−k]≤L2\mathbb{E}[\lVert G(\theta,x_{t+1})\rVert ^2\mid \mathcal{F}_{t-k}] \le L^2. In contrast, we consider the mini-batch gradient estimation error. We analyze random vectors with sub-exponential norms and establish a Bernstein's inequality under non-stationary Markov chains. This allows us to prove the error bounds in our Theorem 1 under only a sub-exponential norm boundedness condition, which permits unbounded gradients.

  2. Problem scope and algorithms. They mainly focus on stochastic optimization (1) without nonsmooth term under a static, time-homogeneous Markov chain with perfect mixing, designing projected gradient, AdaGrad-norm, and heavy-ball methods. Their extension to unconstrained composite problems (Sec. 3.4) via proximal SGD cannot cover the closed convex feasible region we consider. They also address state-dependent Markov chains (Sec. 3.5) via projected SGD controlled by the Poisson equation (Assumptions 3.6–3.7). In contrast, we develop a proximal Adam-type method with adaptive first/second-moment estimates and a coordinate-wise diagonal preconditioner for constrained composite optimization. Proving convergence for this adaptive proximal update under biased, dependent MCMC gradients requires analyzing the complex interaction between adaptive moments, the proximal step, and sampling errors. Thus, our assumptions are weaker and cover a strictly broader class of nonconvex problems. Moreover, our analysis for proximal Adam extends to general dependent data as long as the bounds in Theorem 1 holds.

Comparison with Xiong et al. (2021).

Both Xiong et al. (2021) and our work study Adam-type algorithms under Markovian sampling. We appreciate their novel analysis of PG-AMSGrad under a time-varying Markov chain. Our work differs in the following aspects:

  1. Problem Setting. We address a general constrained nonsmooth nonconvex composite optimization problem with a mini-batch proximal Adam. In contrast, Xiong et al. (2021) study two specific unconstrained reinforcement learning (RL) tasks: policy gradient (PG) and temporal difference (TD) learning, using AMSGrad updates. PG is a special unconstrained smooth optimization problem, while TD is a fixed-point estimation problem rather than a composite optimization problem.

  2. Assumptions. We allow the MCMC-generated stochastic gradient to be unbounded, requiring only a sub-exponential norm bound. For PG-AMSGrad, Xiong et al. (2021) require the stochastic gradient to be uniformly bounded. However, in their setting, this requirement is automatically guaranteed by the bounded reward function R(s,a)∈[0,Rmax⁡]R(s,a) \in [0, R_{\max}], the finite action space, and the bounded score function under Lipschitz policies in Assumption 1 in their paper. This boundedness is a direct artifact of the RL physical setup and additional Assumption 1, not a general optimization assumption. Our work operates without such RL-specific structural priors.

  3. Convergence Guarantees. With both constant (Corollary 2) and diminishing step sizes (Corollary 3), our MCMC-ProxAdam achieves a convergence rate and converges to a stationary point. Under a constant step size, PG-AMSGrad in Xiong et al. (2021) converges only to a neighborhood of a stationary point (see Theorem 1 in their paper).

Thank you for the detailed responses and revisions. I acknowledge that the corrected momentum parameter conditions address an important part of my first concern, and that the expanded comparisons with Alacaoglu and Lyu (2023) and Xiong et al. (2021) better clarify the theoretical contributions.

However, my concern regarding the connection between the theoretical assumptions and the experimental sampler remains. While the additional engineering details and energy-distribution visualization are informative, they do not establish that the unadjusted Langevin sampler preserves the required target distribution. The revised manuscript also acknowledges that the resulting sampling bias is not yet incorporated into the convergence analysis.

Furthermore, some steps in the gradient estimator error analysis, particularly in Appendix B.5, still appear to require correction.

I appreciate the authors' efforts in addressing my comments. Nevertheless, these remaining theoretical concerns prevent me from changing my overall assessment, and I will maintain my current rating.

Reviewer_AYLWOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The primary contributions of this work include: 1) a Bernstein-type concentration inequality for vector-valued MCMC estimators that are initialized away from stationarity; bounds on the error of such estimators when the tail of the gradient is sub-exponential; 2) a convergence analysis based on these bounds. This allows for the use of unbounded gradient realizations while maintaining control over moments. With a uniform spectral-gap assumption and appropriate choice of parameters, the paper establishes an O(N−1/2)O(N^{-1/2}) bound on the total number of gradient oracle calls, with a batch size proportional to N\sqrt N and a weaker 4/34/3-moment criterion for its momentum-based gradient mapping.

Critical strengths

The authors have introduced a substantial theory for using adaptive proximal optimization with Markov Chain Monte Carlo (MCMC) estimated gradients. This is an important development as it combines several difficult issues, such as non-convex objectives. convex non-smooth regularization, adaptive preconditioning, and biased/correlated gradient estimates which may be unbounded. Their main technical contribution was to establish a relationship between a concentration inequality for vector-valued Markov-chain averages under sub-exponential tails and explicit estimator error bounds and an optimizer convergence guarantee. This work shows a good mathematical basis for using proximal adaptive methods in the environment and shows how the results depend on both sampling accuracy and mixing.

Critical weaknesses
  1. The advertised convergence rate has inconsistent parameter conditions. Corollaries 1–2 prescribe α=ϵ/(2L)\alpha=\epsilon/(2L), $\beta=\alpha/(c\epsilon)$, and c≤1/(4L)c\leq1/(4L), implying β=12Lc≥2.\beta=\frac{1}{2Lc}\geq2. However, the momentum-error argument in Lemma C.5 relies on 0<β≤10<\beta\leq1, its inequalities can fail for the prescribed values. Thus, the main rate is not established as written.

  2. The experimental sampler is not shown to satisfy the theory’s target-distribution assumption. The estimator bounds require a Markov chain whose stationary distribution is the distribution defining the true gradient. Equation 5(line 210) uses an unadjusted Langevin update with separately chosen step size and noise variance. This generally introduces stationary-distribution bias. The paper does not provide an implemented acceptance correction or a bound on this additional bias. A positive spectral gap alone cannot establish that the chain targets the correct distribution. Thus, the FID experiments do not substantiate the claimed applicability of the convergence analysis to the implemented EBM training procedure. This may leave a material gap between the theoretical contribution and its principal application.

Questions for authors
  1. Corollaries 1–2 specify α=ϵ/(2L)\alpha=\epsilon/(2L), β=α/(cϵ)\beta=\alpha/(c\epsilon), and c≤1/(4L)c\leq1/(4L), which imply β≥2\beta\geq2. How is this reconciled with the condition 0<β≤10<\beta\leq1 needed by the momentum-error argument in Lemma C.5? Is there a typographical error or a missing restriction?

  2. What ensures that the Langevin sampler in Equation (5), with the step size and noise variance used in the experiments, has the required target distribution pθp_\theta as its stationary distribution? Is a Metropolis–Hastings correction implemented? If not, can the authors quantify the discrepancy between the sampler’s stationary distribution and pθp_\theta, and explain how this additional gradient bias affects Theorem 1 and the subsequent convergence guarantees?

5 comments
AuthorsOpenReview ↗

Illustration of experimental sampler

Response:

We sincerely thank the reviewer for these insightful comments. We address the two points as follows.

Q1:Changing parameters to overcome inconsistency

Response: We thank the reviewer for raising this important question. As this is a common concern shared by all three reviewers, we have provided a detailed response under Reviewer 4wby's comment. In brief, this inconsistency is caused by parameter specification rather than a problem with the proof structure. After making the corrections described in Section 4, the proofs of Lemma C.5 and Theorem 2 remain valid. The $ \mathcal{O}\left(\frac{1}{\sqrt{\bar N }}\right)$ convergence rate in Corollary 2 is unchanged, with only the constants being affected.

Q2: Illustration of experimental sampler

Response. We sincerely thank the reviewer for raising this fundamental and insightful question regarding the stationary distribution of our sampler. We fully acknowledge that in theory, the unadjusted Langevin update (Eq. 5) introduces a discretization bias, and adding a Metropolis-Hastings (MH) correction or significantly decreasing the step size η\eta (as analyzed by Durmus and Moulines, 2017) should reduce this bias and bring the stationary distribution closer to the target distribution pθ(z)p_\theta(z).

However, in the context of high-dimensional EBM training, we found these exact or conservative sampling strategies are practically infeasible:

  1. Metropolis-Hastings Correction: We attempted to implement MH-corrected Langevin sampling (MALA). However, the FID degraded significantly and the algorithm failed to converge. In high-dimensional spaces, the acceptance rate collapses to near zero unless the step size is infinitesimally small, which effectively freezes the Markov chains and prevents exploration of low-energy regions.

  2. Decreasing Step Size η\eta: We also tested decreasing η\eta. While this theoretically reduces the stationary bias, the mixing time increases drastically. Given a limited sampling budget, the chains cannot reach the low-energy regions, providing ineffective negative samples and leading to training failure (as evidenced by the significantly degraded FID).

These observations are consistent with the official code of (Du & Mordatch, 2019) and the widely used tutorial code (https://uvadlc-notebooks.readthedocs.io/...): applying MH correction or decreasing η\eta in these implementations also leads to dramatic numerical degradation and non-convergence. This aligns with the explicit statement in Du & Mordatch (2019) (Page 20): "We found it difficult to apply vanilla HMC to EBM training as optimal step sizes and leapfrog simulation numbers differed greatly during training, though applying adaptive HMC would be an interesting extension."

This highlights a core challenge in EBM training: because the energy landscape EθE_\theta is dynamically updated, the optimal sampling parameters shift constantly. Consequently, fixed-step exact samplers (like HMC or MALA) are extremely brittle, and overly small steps prevent exploration.

Therefore, following the standard practice established by Du & Mordatch (2019), we rely on Unadjusted Langevin Dynamics (ULA) but mitigate its bias via two key engineering techniques: Replay Buffer (to maintain persistent chains and effectively extend the mixing time) and Spectral Normalization (to bound the Lipschitz constant and stabilize the discrete steps). Our ablation study (shown in Tables A-B below) demonstrates that further reducing the step size or increasing the number of steps of unadjusted Langevin process does not significantly improve sample quality. This empirically confirms that our chosen hyperparameters are well within the tolerable bias regime for effective maximum likelihood training.

Table A: Sensitivity analysis of MCMC-ProxAdam with respect to η\eta on L1L_1 model with λreg=1e-9\lambda_{\text{reg}} = 1\text{e-}9

Epochη=1\eta=1η=3\eta=3η=5\eta=5η=7\eta=7η=10\eta=10
5403.70289.5378.9863.6654.01
10355.91331.2060.4550.5048.53
15371.83353.8743.7951.2541.58
20374.78377.0447.2239.3947.23
25--260.3540.1332.42
30--271.6735.5731.75
35--271.7231.4530.41
40--273.8631.9431.02
45--271.6837.0736.26
50--269.8026.0825.83
55--271.9928.4728.05

(Due to the character limit, the response continues in the following comment.)

AuthorsOpenReview ↗

Illustration of experimental sampler (continue)

(Continued from the previous comment)

Table B: Sensitivity analysis of MCMC-ProxAdam with respect to number of steps kk of unadjusted Langevin process on L1L_1 model with λreg=1e-9\lambda_{\text{reg}} = 1\text{e-}9

Epochk=60k=60k=65k=65k=70k=70k=75k=75k=80k=80k=85k=85k=90k=90
554.0156.3768.7061.6769.2460.6276.08
1048.5356.7754.1566.1156.8173.1163.04
1541.5839.4544.0657.0146.5359.3769.56
2047.2342.2649.2244.6755.4646.2049.64
2532.4232.5233.7851.6150.8648.0448.94
3031.7533.8037.8730.6231.0736.4037.54
3530.4128.4833.9129.6939.0838.5138.04
4031.0241.3731.2540.0840.7237.9039.09
4536.2634.3335.1543.7735.4136.4438.76
5025.8333.3732.3730.9830.1533.2032.32
5528.0531.6929.1927.7333.8736.5834.81

Furthermore, to indicate that the distribution generated by our ULA sampler is relatively close to the target distribution, we follow the analysis in Appendix A.13 and Figure 29 of (Du & Mordatch, 2019). In Appendix D. 7 of the revised version, we plot in Figure 2 the energy distribution of samples obtained from our iterative unadjusted Langevin procedure, and compare it with the energy distribution of the training data on MNIST. As shown in Figure 2, both distributions match each other relatively close, providing empirical evidence that the distribution generated by our unadjusted Langevin procedure, is relatively close to the target distribution.

We thank the reviewer again for this excellent question. We fully acknowledge that a rigorous theoretical analysis of the stationary distribution is required when ULA is adopted as the MCMC sampler, whereas exact samplers (e.g., MH sampler) would not alter our theoretical results. Therefore, in our future work, we plan to quantify the discrepancy between the sampler's stationary distribution and the target distribution, and formalize how this additional gradient bias affects Theorem 1 and the convergence guarantees for the ULA case. Nevertheless, from a practical standpoint, our empirical findings indicate that ULA combined with engineering techniques currently serves as an effective choice for EBM training.

We hope that the response addresses your concerns. We have updated the manuscript accordingly in the revised version. In addition, the code used to generate Figure 2 in Appendix D.7 of the revised manuscript has been included in the new Supplementary Materials. Thank you again for your time and effort in reviewing our manuscript and providing your valuable comments.

I thank the authors for addressing my questions and providing additional results. I will maintain my current score recommendation.

Reviewer_4wbyOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies nonsmooth nonconvex stochastic composite optimization with MCMC-based gradient estimation. The proposed MCMC-ProxAdam combines MCMC sampling, Adam updates, and proximal operator. The paper establishes gradient estimation bounds under relaxed assumptions and claims an O(1/nT)O(1/\sqrt{nT}) convergence rate.

Critical strengths

The paper clearly motivates the challenges of MCMC-based stochastic optimization and identifies the limitations of existing approaches.

The gradient estimation error bounds under relaxed assumptions are potentially valuable theoretical contributions.

Critical weaknesses

Theorem 2 and Corollaries 1-2 require βt+1≥2\beta_{t+1} \geq 2, whereas the proof of Lemma C.5 requires 0<βt≤10 < \beta_t \leq 1, specifically in the application of Young's inequality in (I) and the final inequality in (III) (Lines 1404-1426). Since Theorem 2 and its corollaries rely on Lemma C.5, this inconsistency raises serious concerns about the validity of the main convergence guarantees.

Questions for authors

See weakness.

2 comments
AuthorsOpenReview ↗

Changing parameters to overcome the inconsistency

Response:

We sincerely thank all three reviewers for raising this important point. As this is a common concern, we provide a detailed response here, which also applies to the identical questions raised by the other reviewers. The identified inconsistency does exist. We found that it is an error in the parameter specification rather than a problem with the proof structure. After making the corrections described in Section 4, the proofs of Lemma C.5 and Theorem 2 remain valid. The $ \mathcal{O}\left(\frac{1}{\sqrt{\bar N }}\right)$ convergence rate in Corollary 2 is unchanged, with only the constants being affected. In the revised manuscript, we make changes as follows.

For Theorem 2. Change $ \alpha_t \le \frac{\epsilon}{2L} $ to

\alpha_t \leq c\epsilon,\quad t=0,\ldots,T-1,\qquad \beta_0\in (0,1],$$ and keep the other parameter settings unchanged in Theorem 2 and Corollaries 1-2. Then $\beta_{t+1} \le 1$ holds for $t=0,\ldots,T-1$, resolving the contradiction. Furthermore, the revised setting of parameter $\alpha_t$ implies $\alpha_t \le c\epsilon \le \frac{\epsilon}{4L} < \frac{\epsilon}{2L}$, which is used in the proof of Theorem 2 (see Lines 1538-1542) still satisfied. Since $\beta_{t+1} = \frac{\alpha_t}{c\epsilon}$ and the condition $c \in (0, \frac{1}{4L}]$ remain unchanged, all subsequent proofs of Theorem 2 require no modifications and remain valid. | Condition | Used in | Original Theorem 2 | Revised | |---|---|---|---| | $\alpha_t \le \frac{\epsilon}{2L}$ | (46)$\to$(47) | Satisfied | Satisfied ($\alpha_t \le \frac{\epsilon}{4L}$) | | $\beta_t \in (0,1],\ t = 1, \dots, T$ | Lemma C.5, (48)–(49) | Not satisfied ($\beta_t = \frac{1}{2Lc} \ge 2$) | Satisfied | | $\beta_{t+1} = \frac{\alpha_t}{c\epsilon}$ | (51), (52), (54) | Satisfied | Satisfied | | $c \le \frac{1}{4L}$ | (54) | Satisfied | Satisfied | | $(1-\beta_0)^2 \le 1$ | (53) | Unspecified | Satisfied ($\beta_0 \in (0, 1]$) | **For Corollaries 1, 2, 4:** **Corollary 1.** Change $\alpha_t = \frac{\epsilon}{2L}$ to $\alpha_t \equiv c \epsilon \bar \beta,\quad \bar \beta\in (0,1].$ Then by substituting $\sum_{t=0}^{T-1} \alpha_t = c\epsilon \bar \beta T$ into (12) yields $$\left( \mathbb{E} \left[ \|\mathcal{G}^{D_R}(\theta_R, m_R, \alpha_R)\|^{\frac{4}{3}} \right] \right)^{\frac{3}{2}} \le (\sqrt{B'} + \epsilon) \Bigg( \frac{D}{c\epsilon \bar{\beta}T} + \frac{4}{\epsilon \bar{\beta}T} \mathcal{O}\left(\frac{\sigma^2}{\gamma^* n}\right) + \frac{8}{\epsilon} \mathcal{O}\left(\frac{\sigma^2}{\gamma^* n}\right) \Bigg).$$ **Corollary 2.** Also change $\alpha_t = \frac{\epsilon}{2L}$ to $\alpha_t \equiv c \epsilon \bar \beta,\quad \bar \beta\in (0,1].$ Then we derive $$\left( \mathbb{E} \left[ \|\mathcal{G}^{D_R}(\theta_R, m_R, \alpha_R)\|^{\frac{4}{3}} \right] \right)^{\frac{3}{2}} \le \mathcal{O}\left(\frac{D_1}{\bar{N}}\right) + \mathcal{O}\left(\frac{D_2}{\sqrt{\bar{N}}}\right),$$ where $$D_1= \frac{8(\sqrt{B'} + \epsilon)\sigma^2}{\epsilon \bar{\beta}\gamma*} ,\quad D_2 = \frac{2(\sqrt{B'} + \epsilon)D}{c\epsilon \bar{\beta}} + \frac{8\sigma^2(\sqrt{B'} + \epsilon)}{\epsilon\gamma*}$$ instead of the values of $D_1$ and $D_2$ in the original version. **Corollary 4.** Since Corollary 4 is derived from Corollary 2, we only need to use the scalars $D_1$ and $D_2$ in Corollary 2 of the revised version. **For Corollary 3:** The change of parameters (R1) in Theorem 2, makes the original Corollary 3 does not hold. The reason is that its parameters are given by $$\alpha_t = \frac{\hat{\alpha}\sqrt{n}}{\sqrt{t+1}}, \qquad \beta_{t+1} = \frac{\alpha_t}{c\epsilon}.$$ In order to guarantee $\alpha_t \le c\epsilon$ in (R1) of Theorem 2 in the revised version, we need $$\hat \alpha \le \frac{c\epsilon}{\sqrt{n}}.$$ Therefore $\hat \alpha$ can not be a constant independent of $n$. Consequently, $$\sum_{t=0}^{T-1}\alpha_t = \hat{\alpha}\sqrt{n} \sum_{t=0}^{T-1}\frac{1}{\sqrt{t+1}} \le c\epsilon \mathcal{O}\left(\sqrt{T}\right).$$ Therefore, we can only bound the $D$-dependent term in (12) by $$\frac{(\sqrt{B'}+\epsilon)D} {c\epsilon \mathcal{O}(\sqrt{T})}.$$ Since $T=\mathcal{O}(\bar{N}^{1/2})$, this term is of order $$\mathcal{O}(\bar{N}^{-1/4}).$$ Hence, (12) with the original setting of parameters in Corollary 3, cannot establish an $\mathcal{O}(1/\sqrt{\bar{N}})$ convergence rate as in the original version. To get a better convergence rate with a decaying step size, in the revised version we choose $$\alpha_t = \frac{c\epsilon\bar{\beta}}{\sqrt{t+1}}, \qquad n = \mathcal{O}(\bar{N}^{1/3}).$$ Then, according to (12), the convergence rate is $$\mathcal{O}(\bar{N}^{-1/3}),$$ following the similar arguments of Corollary 3 in the original version. We hope that the response addresses your concerns. We have updated the manuscript accordingly in the revised version. Thank you again for your time and effort in reviewing our manuscript and providing your valuable comments.
AuthorsOpenReview ↗

Revisions to Appendix B.5

We would like to thank you for carefully reviewing our manuscript again. We also sincerely thank Reviewer 64tW for identifying that some steps in Appendix B.5 require correction. We have examined these steps and implemented the revisions. The corresponding modified parts in Appendix B.5 have been highlighted in red in the revised manuscript. Thank you again for your careful review and insightful comments, which have substantially improved our paper.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.