Provable Convergence Bounds for Hybrid Dynamical Sampling and Optimization

Thank you for your review, and we appreciate that you saw novelty in our approach. In line with your critique, we have attempted to reduce some of the unnecessarily technical language, and have clarified the LNLS framework in our revised manuscript. We hope that these changes and our responses to your questions assuage your doubts. Due to space constraints, we cannot provide background entirely to our satisfaction. However, we believe there are significant sub-sets of the ICLR community familiar with sampling analysis, analog neural networks, or unconventional computing systems who would find our work useful and insightful, particularly given the uptick in non-von Neumann computing approaches in recent years.

Answers to Questions:

Why do you consider Block Langevin Diffusion? Why can't we optimize w.r.t. all variables?

Dynamical accelerators have a finite device capacity. However, real-world problems will often exceed that capacity, requiring hybrid algorithms such as LNLS to partition the problem into DX-amenable subproblem ``blocks'', hence our proposed block Langevin diffusion model. Ideally we would be able to fit the entire problem onto the DX and optimize all variables concurrently. We consider block-partitioned convergence out of necessity, given the widespread use of LNLS by the DX community. Upon re-reads, we realized that our description of LNLS was unnecessarily technical, hence we have simplified the language (see lines 53-54, 227-230).

Lines 345-347: I guess there should be $\Vert x-y\Vert^2$ instead of $\Vert x^2-y^2\Vert$

Yes, thank you for noticing. We've simplified the notation in line with our later use of the Lipschitz constants, and have removed the exponents entirely.

Assumption 5: How does the function inside the integral depends on $t$?

Our original meaning was that the second moment of the iterate gradient was exponentially integrable, so $x$ should have been written $x(t)$. However, we greatly thank you for raising this question, as we realized in revisions that this assumption was superfluous and only muddied the waters. In our revised article we have removed Assumption 5 and simply assume that the gradient oracle is also dissipative, as we discussed in Appendix D.2 in any case.

Assumption 6: In my experience, this is a very uncommon assumption. Also, Assumption 3 is also very uncommon. We apologize if we were unclear in our meaning, however we politely disagree. Both assumptions (or similar) are common in stochastic/non-convex optimization and sampling works. Here we provide a (non-exhaustive) list of examples. Assumption 3 is usually expressed as bounded oracle variance/bias, see Raginsky et al. 2017, Dalalyan and Karagulyan 2019, Chen et al. 2020, Zou and Gu 2021, and Seok and Cho 2023. Several other works consider more restrictive assumptions on the gradient oracle, such as sub-Gaussian tails (Mou et al. 2018, Pensia et al. 2022).

The dissipativity assumption has been used in Raginsky et al. 2017, Xu et. al 2018, Zou et al. 2021, and Farghly and Rebeschini 2021. This assumption requires that the objective function is strongly convex outside of a bounded region, but allows for non-convexity within that region, and is therefore mainly used in works centering on global optimization within non-convex landscapes. It likely does not appear within most mathematical optimization literature, which tends to focus on convex optimization or on convergence to local stationary points within non-convex problems.

Theorem 3: This theorem yields the convergence rate $\log\frac{1}{\varepsilon} +\frac{1}{\varepsilon}$ which is $\geq 1$ What If one wants to make the Wasserstein distance less or equal $0.001$?

Thank you for pointing out our lack of explanation. Like the traditional unadjusted Langevin algorithm, non-ideal BLD is asymptotically biased: there exists a finite lower bound for the $W_2$ distance to the target measure. In traditional Langevin Monte Carlo, this bias is due to the ``forward-flow'' operator splitting scheme with finite step size (see Wibisono 2018 for an excellent presentation of this topic). In the case of our analysis, the bias is due to analog component variation, since the bias constants are proportional to the non-ideality parameters $M$, $B$.

Thank you.

In line with your critique, we have attempted to reduce some of the unnecessarily technical language, and have clarified the LNLS framework in our revised manuscript. We hope that these changes and our responses to your questions assuage your doubts.

Can you please highlight the changes in blue (or any other color)? I want to see if the changes make the understanding easier.

Is there some relation of Assumption 5 (in the revision) to the strong convexity? How are they connected? For a strongly convex function $f,$ we have $\langle \nabla f(x) - \nabla f(x^*), x - x^* \rangle \geq m ||x - x^*||^2,$ where $x^*$ is the minimum of $f.$ For $c = 0,$ why is $x^* = 0$ in Assumption 5?

Thank you for your favorable review, we were heartened to hear that you found our presentation well-structured and coherent, and that our numerical experiments provided further clarity.

Thank you for your insightful comments, helpful suggestions, and praise of our work. We are particularly grateful for the typographical advice, and we have fixed all of the minor formatting concerns that you raised. Suffice to say, several authors now have the AMS style guide bookmarked for future reference.

Answers to Questions:

In the applications familiar to me, analogue-to-digital conversion tends to be an crucial bottleneck for hybrid analogue/digital accelerators. This affects their accuracy, latency, power efficiency, and, most crucially, die footprint which largely determines their cost. ADCs are so expensive in so many ways that many applications sacrifice as much precision as possible to minimize their use.} In this light, how are those aspects relevant to your work? Do the experiments take them into account? Do previous works on the topic address them? As you correctly note, ADCs incur significant latency, power, and area bottlenecks, leading to the widespread adoption of low-precision output representations ($\leq 8b$). The error introduced by low-precision iterates is certainly relevant to this work. The closest work that we are aware of is a recent pre-print (Seok and Cho 2023), however that work considered intentional gradient quantization rather than optimizing low-precision iterates.

While we could include quantization gradient error under Assumption 3, bounding the asymptotic Wasserstein bias from sampling quantized iterates is less straightforward. Moreover, quantization may also impose lower bounds on the sampling time per block, since the DX state needs to change beyond the detectable precision of the ADC to make forward progress. Given that these are highly non-trivial research problems, we leave consideration to future work. Accordingly, we have added ADC-incurred precision loss to the ``Limitations'' section.

As the authors say, performing experiments with Gaussian distributions allows for closed-form solutions for the 2-Wasserstein distance. Yet, even though the plots from Figure 2 display a $y$-axis with units, it is hard to reason quantitatively reason in terms of $W_2$. Could you provide some general guidance for that? I mean, is a $W_2$ of 1 large? I understand this can be problem-dependent, but some general guidance would be helpful.

We agree that high-dimensional $W_2$ is not the most intuitive metric. Our focus in the numerical experiments was to compare rates of convergence rather than focusing on precise values. E.g., the block methods are slower than full LD with the expected dependence on block size and step duration. We have clarified this focus before discussing results in Section 4.

References:

[1] Ji. Seok and C. Cho, “Stochastic Gradient Langevin Dynamics Based on Quantization with Increasing Resolution,” Oct. 04, 2023, arXiv: arXiv:2305.18864. doi: 10.48550/arXiv.2305.18864.

We thank you for your review, and we have made revisions to address the concerns that you have raised. We have added punctuation to all of our mathematical statements, as other reviewers also raised this issue. To clarify, our work does not assume that the vectors can be decomposed into tensor products. Rather, we simply assume that we are dealing with a product space (namely $\mathbb{R}^d$) which can be decomposed into subspaces. We have replaced the tensor product operator with a Cartesian product operator to clarify this point (line 215).

Thank you for your kind review. We were particularly encouraged to hear that you found our work interesting and novel, and that you thought our literature review and discussion praiseworthy. We have attempted to address your questions in our revised draft as well as directly addressing them below:

Can the authors provide further examples of distributions that would satisfy the LSI? How realistic is that assumption in applications?

Distributions of practical interest satisfying an LSI include high-temperature spin systems (of particular interest within combinatorial optimization), globally strongly log-concave measures with bounded regions of non-log concavity (such as weight-decay regularized machine learning), and log-concave measures which are not strongly log-concave (such as heavy tailed exponential distributions). We have also added these examples to Sec. 3 after our introduction of the LSI.

As we note in our "Limitations" section, assuming an LSI is still relatively restrictive. However, we conjecture that our results can be generalized to weaker functional inequalities, potentially using the methods developed by Chewi et al. 2022.

Random and Cyclic block approaches seem to produce similar outcomes. What is the motivation to choosing one over another? Is there any intuition on which one should I choose based upon my application?

There is no direct convergence reason to favor cyclic over randomized approaches for analog LNLS. However, we believe that cyclic orderings are preferable. Implementations are generally much simpler and are much more straightforward to optimize in practice since the algorithm is more predictable. For instance, we can optimize memory layouts to ensure that contiguous partitions are stored together, reducing overall memory access latency and opening opportunities to exploit the memory hierarchy. Moreover, multi-chip DX proposals such as ``batch mode'' from Sharma et al. 2022 rely on cyclic orderings to implement an efficient hardware pipeline. We have also added notes to this effect in Sec. 3 (lines 286-288) to further motivate our analysis of block orderings.

In Figure 2 (e), why doesn't the curve associated with $\delta=0$ match the ideal curve?

Thank you for noticing this lack of clear notation. Here ``ideal'' was meant to communicate that the full Langevin diffusion had no noise. The $\delta=0.0$ curve represents the block Langevin diffusion without noise, which is why it converges more slowly. We have clarified the text in Sec. 4 to make this more explicit.

References:

[1] S. Chewi, M. A. Erdogdu, M. Li, R. Shen, and S. Zhang, “Analysis of Langevin Monte Carlo from Poincare to Log-Sobolev,” in Proceedings of Thirty Fifth Conference on Learning Theory, PMLR, Jun. 2022, pp. 1–2. Accessed: Nov. 13, 2024. [Online]. Available: https://proceedings.mlr.press/v178/chewi22a.html

[2] A. Sharma, R. Afoakwa, Z. Ignjatovic, and M. Huang, “Increasing ising machine capacity with multi-chip architectures,” in Proceedings of the 49th Annual International Symposium on Computer Architecture, in ISCA ’22. New York, NY, USA: Association for Computing Machinery, Jun. 2022, pp. 508–521. doi: 10.1145/3470496.3527414.