- 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
-
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).
-
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).
-
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
-
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?
-
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?
-
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
Clarification of the main theoretical advances over existing studies (continue)
(Continued from the previous comment)
-
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 cannot guarantee . By Jensen's inequality, one only has . Their Assumption 2.3(ii) (uniformly bounded gradients) is required to bridge this gap, or one must strengthen Assumption 2.3(i) to . 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.
-
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:
-
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.
-
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 , 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.
-
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.
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ˉ) 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.
(Due to the character limit, the response continues in the following comment.)