Towards Exact Gradient-based Training on Analog In-memory Computing

Authors: zhaoxian  wu
tayfun  gokmen
malte j rasch
ibm t j watson
tianyi  chen
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 02:25:57

Abstract: Given the high economic and environmental costs of using large vision or language models, analog in-memory accelerators present a promising solution for energy-efficient AI. While inference on analog accelerators has been studied recently, the training perspective is underexplored. Recent studies have shown that the "workhorse" of digital AI training - stochastic gradient descent (SGD) algorithm converges inexactly when applied to model training on non-ideal devices. This paper puts forth a theoretical foundation for gradient-based training on analog devices. We begin by characterizing the non-convergent issue of SGD, which is caused by the asymmetric updates on the analog devices. We then provide a lower bound of the asymptotic error to show that there is a fundamental performance limit of SGD-based analog training rather than an artifact of our analysis. 
To address this issue, we study a heuristic analog algorithm called Tiki-Taka that has recently exhibited superior empirical performance compared to SGD. We rigorously show its ability to converge to a critical point exactly and hence eliminate the asymptotic error. The simulations verify the correctness of the analyses.

Main paper: 
 introduction: 
 Large vision or language models have recently achieved great success in various applications. However, training large models from scratch requires prolonged durations and substantial energy consumption, which is very costly. For example, it took $2.4 million to train LLaMA [1] and $4.6 million to train GPT-3 [2] . To overcome this issue, a promising technique is application-specific hardware accelerators for neural networks, such as TPU [3] , NPU [4] , and NorthPole chip [5] , just to name a few. Within these accelerators, the memory and processing units are physically split, which requires constant data movements between the memory and processing units. This slows down computation and limits efficiency. In this context, we focus on analog in-memory computing (AIMC) accelerators with resistive crossbar arrays [6, 7, 8, 9] to accelerate the ubiquitous matrix-vector multiplications (MVMs), which contribute to a significant portion of digital computation in model training and inference, e.g., about 80% in VGG16 model [10] . Very recently, the first analog AI chip has been fabricated in IBM's Albany Complex [11] , and has achieved an accuracy of 92.81% on the CIFAR10 dataset while enjoying 280× and 100× efficiency and throughput value compared with the most-recent GPUs, demonstrating the transformative power of analog computing for AI [12] .In AIMC accelerators, the trainable matrix weights are represented by the conductance of the resistive elements in an analog crossbar array [13, 14] . Unlike standard digital devices such as GPU or TPU, trainable matrices, input, and output of MVMs in resistive crossbars are all analog signals, which means that they are effectively continuous physical quantities and are not quantized. In resistive crossbars, the fundamental physics (mainly Kirchhoff's and Ohm's laws) enable the devices to accelerate MVMs in both forward and backward computations. However, the analog representation of model weights requires updating weights in their unique way. To this end, an in-memory pulse update has been developed in [15] , which changes the weights by sending consecutive pulses to implement gradient-based training algorithms like stochastic gradient descent (SGD). Pulse update reduces energy consumption and execution time significantly.While the AIMC architecture has potential advantages, the analog signal in resistive crossbar devices is susceptible to noise and other non-ideal device characteristics [16] , leading to training performance that is often suboptimal when compared to digital counterparts. Despite the increasing number of empirical studies on AIMC that aim to overcome this accuracy drop [17, 18, 19, 20] , there is still a lack of theoretical studies on the performance and performance limits of SGD on AIMC accelerators.The focus of this paper is fundamentally different from the vast majority of work in analog computing. We aim to build a rigorous theoretical foundation of analog training, which can uniquely characterize the performance limit of using a hardwareagnostic digital SGD algorithm for analog training and establish the convergence rate of gradient-based analog training. Consider the following standard model training problem W * := arg minEQUATIONwhere f (•) : R D → R is the objective function, W is all the trainable weight stored in an analog way and D is the model size.In digital training, the workhorse algorithm for solving problem (1) is SGD, which iteratively updates weight W via the following recursion Digital SGDEQUATIONwhere k is the iteration index, α is a positive learning rate and ε k is the gradient noise with zero mean at iteration k. In digital training, the noise usually comes from the mini-batch sampling. In analog training, the noise also arises from the non-ideality of devices, including weight read noise, input/output noise, quantization noise, digital/analog conversion noise, and even thermal noise [21] .In Figure 1 , we first numerically show that the asymptotic performance of SGD running on the analog devices that we term Analog SGD does not follow that of (2) , and thus ask a natural question:Q1) How to better characterize the training trajectory of SGD on analog devices?Building upon the pulse update in [15, 22] , in this paper, we propose the following discrete-time mathematical model to characterize the trajectory of Analog SGD on analog computing devicesEQUATIONwhere | • | and ⊙ represent the coordinate-wise absolute value and multiplication, respectively and τ is a device-specific parameter. We will explain the underlying rationale of this model (3) in Section 2.2. But before that, compared to (2) , the extra term of (3) comes from the asymmetric update of analog devices. Following this dynamic, we prove that the Analog SGD only converges inexactly to a critical point, with the asymptotic error depending on the non-ideality of the analog device. Since the inexact convergence guarantee usually leads to an unfavorable result, it raises another question:Since the seminal work on pulse update-based Analog SGD [15] , a series of gradient-based training algorithms have been proposed to enable training on analog devices. Despite its potential energy and speed advantage, Analog SGD suffers from asymmetric update and noise issues, leading to large errors in training. To overcome the asymmetric issue, a new algorithm so-termed Tiki-Taka (TT-v1) introduces an auxiliary array to estimate the moving average of gradients, whose weight is then transferred to the main array periodically [22] . However, the weight transfer process between arrays still suffers from noise. To deal with this issue, TT-v2 [25] introduces an extra digital array to filter out the high-frequency noise. Enabled by these approaches, researchers successfully trained a model on the realistic prototype analog devices and reached comparable performance on a real dataset [20] .Another major hurdle comes from noisy analog signals, which can perturb the gradient computed by analog devices. As an alternative, a hybrid scheme that accelerates the forward and backward pass in-memory and computes gradient in the digital domain has been proposed in [17, 18] , which provides a more accurate but less efficient update. In addition, the successful training by TT-v1 or TT-v2 relies on the zero-shifting technique [26] , which corrects the symmetric point of devices as zero. However, the correction is inaccurate because it also involves analog signals. To deal with this issue, Chopped-TTv2 (c-TTv2) and analog gradient accumulation with dynamic reference have been proposed in [19] . Because of these efforts, analog training has empirically shown great promise in achieving a similar level of accuracy as digital training, with reduced energy consumption and training time. Despite its good performance, it is still mysterious about when and why they work. 
the physics of analog training: 
 Unlike digital devices, analog devices represent the trainable weights by the conductance of the base materials, which have undergone offset and scaling due to physical laws. This difference leads to entirely different training dynamics on analog devices, which will be discussed in this section.This section shows that the convergence theory developed for digital SGD fails to characterize the analog training. Before that, we introduce standard assumptions for analyzing digital training. Assumption 1 (L-smoothness). The objective f (W ) is L-smooth, i.e., for any W, W ′ ∈ R D , it holdsEQUATION) Assumption 2 (Lower bounded). f (W ) is lower bounded by f * , i.e. f (W ) ≥ f * , ∀W ∈ R D .Assumption 3 (Noise mean and variance). The noise ε k is independently identically distributed (i.i.d.) for k = 0, 1, . . . , K, and has zero mean and bounded variance, i.e.,E[ε] = 0, E[∥ε∥ 2 ] ≤ σ 2 .In non-convex optimization, instead of finding a global minimum, it is usually more common to find a critical point, which refers to W * satisfying ∇f (W * ) = 0. Under Assumptions 1-3, if W k follows the digital SGD dynamic (2), the convergence of SGD is well-understood [23, Theorem 4.8]EQUATIONThis result implies that the impact of noise can be controlled by the learning rate α, i.e., after K ≥ Ω(1/α 2 ) iterations, the error is O(α). By forcing α → 0, the error will reduce to zero.Analog SGD violates the SGD theory. The dynamic of digital SGD exactly follows (2) up to the machine's precision. To verify whether analog training adheres to the same dynamic, we conduct a numerical simulation on a least-squares problem. We compare Analog SGD implemented by an analog devices simulator, IBM Analog Hardware Acceleration Kit (AIHWKIT) [27] , and digital SGD implemented by PYTORCH. The same level of noise obeying Gaussian noise is injected into each algorithm. Beginning from a large learning rate α = 0.2, we reduce the learning rate by half each time and observe the convergences. As Figure 1 illustrates, digital SGD behaves as what (5) predicts: it converges with a smaller error when a small learning rate is chosen. On the contrary, Analog SGD converges with a much larger error, which does not decrease as the learning rate decreases. This result demonstrates the discrepancy between the theory of digital SGD and the performance of Analog SGD. More details are deferred to Appendix I.Compared to digital devices, the key feature of analog devices is analog signal. The input and output of analog arrays are analog signals, which are prone to be perturbed by noise, including read noise and input/output noise [21, 28] . Moreover, real training typically involves the utilization of mini-batch samples, which also introduces noise. Besides the data noise, another notable feature of analog accelerators is that the model weight is represented by material conductance.Pulse update. To change the weights in analog devices, one needs to send an electrical pulse to the resistive element, and the conductance will change by a small value, which is referred to as pulse update [15] . To apply an update ∆w to the weight w, using the pulse update needs to send a series of pulses to the resistive element, the number of which is proportional to the update magnitude |∆w|. Since the increments responding to each pulse are small typically, we can regard the change in conductance as a continuous process. Consequently, common operations involving significant weight changes, like copying the weight, are expensive in analog accelerators. In contrast, gradient-based algorithms typically update small amounts at each iteration, rendering the pulse update extremely efficient. Figure 2 presents the weight change on AIMC devices with pulse number.Asymmetric update. Even though the pulse update is performed efficiently inside AIMC accelerators, it suffers from a phenomenon that we refer to as asymmetric update. This means that if we apply (w) = 1 - (w -w ⋄ )/τ, q -(w) = 1 + (w -w ⋄ )/τ . The symmetric point w ⋄ satisfies q + (w ⋄ ) = q -(w ⋄ ).the change ∆w > 0 and ∆w < 0 on the same weight w, the amount of weight change will be different. Considering the weight W k at time k and the expected update ∆W ∈ R D , we express the asymmetric update asEQUATIONwhere q + (•) and q -(•) : R → R + are up and down response factors, respectively. The response factors measure the ideality of analog tiles. In the ideal situation, q + (w) = q -(w) ≡ 1 (see Figure 2 , left), and analog algorithms have the same numerical behavior of the digital ones. Defining the symmetric and asymmetric components as F (w) :=1 2 (q -(w) + q + (w)) and G(w) := 1 2 (q -(w)q + (w)), the update in ( 6) can be expressed in a more compact form U (w, ∆w) = w + ∆w • F (w) -|∆w| • G(w). For simplicity, assume that all the coordinates of W use the same update rule, and the analog update can be written asEQUATIONwhere | • | and ⊙ represent the coordinate-wise absolute value and multiplication, respectively. Note that in (7) , the ideal weight update ∆W is algorithm-specific: ∆W is the gradient in Analog SGD while it is an auxiliary weight (c.f. in Section 4) in Tiki-Taka. Remark 1 (Physical constraint). It is attempting to scale the ∆w by q + (w) or q -(w) to cancel the effect of asymmetric update in (6) dynamically. However, this is impractical since it is hard to implement the reading and scaling at the same time on analog tiles [22] .Symmetric point. The asymmetric update makes up and down responses different almost everywhere, i.e. q + (w) ̸ = q -(w) for almost any w. If a point w ⋄ satisfies q + (w ⋄ ) = q -(w ⋄ ) and G(w) = 0, w ⋄ is called a symmetric point. With loss of generality, the response factor is defined so that F (w ⋄ ) = 1. Therefore, near the symmetric point, the update ∆w can be accurately applied on w, i.e., U (w ⋄ , ∆w) ≈ w ⋄ + ∆w. If all the coordinates of matrix W k hover around the symmetric point, the analog devices can exhibit performance that resembles the digital ones. In the next section, we will show that the weight is biased toward its symmetric point.Asymmetric linear device. Although our unified formulation (7) can capture the response behaviors of different materials, this paper mainly focuses on the behaviors of the asymmetric linear device (ALD), similar to the setting in [19] . ALD has a positive parameter τ which reflects the degree of asymmetry and its response factors are written as linear functions q + (w) = 1-(w -w ⋄ )/τ, q -(w) = 1 + (w -w ⋄ )/τ . Consequently, ALD has F (w) = 1, G(w) = (w -w ⋄ )/τ ,w k+1 = w k + ∆w - 1 τ |∆w| • w k or W k+1 = W k + ∆W - 1 τ |∆W | ⊙ W k (8)where the first equation is the update of one coordinate while the second one stacks all the elements together. Replacing ∆W with noisy gradient α(∇f (W k ) + ε k ) reaches the dynamic (3).Based on the ALD dynamic (8), we study the properties of analog training, which serve as the stepping stone of our analyses. Recall that the asymmetric update leads to different magnitudes of increase and decrease. The following lemma characterizes the difference between two directions.Lemma 1 (Saturation and fast reset). For ALD with a general w ⋄ , the following statements are valid(Saturation) If sign(∆w) = sign(w k ), it holds that |w k+1 -w k | = |1 -|w k -w ⋄ |/τ | • |∆w|. (Fast Reset) If sign(∆w) = -sign(w k ), it holds that |w k+1 -w k | = |1 + |w k -w ⋄ |/τ | • |∆w|.The proof is deferred to Section E.1. Remarkably, Lemma 1 holds for any algorithm with any update ∆w, and it reveals the impact of the asymmetric update. In principle, Lemma 1 can be written as|w k+1 -w k | = |1 ± |w k -w ⋄ |/τ | • |∆w|,where the symmetric point w ⋄ = 0 is omitted.When w k is not at the symmetric point w ⋄ = 0, the update is scaled by a factor. When w k lies around the symmetric point, |w k+1 -w k | ≈ |∆w|, where all updates are applied to the weight and hence the analog devices closely mimic the performance of digital devices. When w k moves away from w ⋄ , i.e. sign(∆w) = sign(w k ), the update becomes none. When w k gets closer to ±τ , nearly no update can be applied. This phenomenon is called saturation; see also [22] . On the contrary, w k changes faster when it moves toward w ⋄ , which is referred to as fast reset.Because of the saturation property, the weight on the analog devices is intrinsically bounded, which will be helpful in the later analysis. The following theorem discusses the bounded property.Theorem 1 (Bounded weight). Denote ∥W ∥ ∞ as the ℓ ∞ norm of W . Given ∥W 0 ∥ ∞ ≤ τ and for any sequence{∆W k : k ∈ N}, which satisfies ∥∆W k ∥ ∞ ≤ τ , it holds that ∥W k ∥ ∞ ≤ τ, ∀k ∈ N.The proof is deferred to Section E.2. Theorem 1 claims that the weight is guaranteed to be bounded, even without explicit projection, which makes analog training different from its digital counterpart. Similar to Lemma 1, Theorem 1 does not depend on any specific analog training algorithm. 
performance limits of analog stochastic gradient descent: 
 After modeling the dynamic of analog training, we next discuss the convergence of Analog SGD. As shown by Lemma 1, the update is slow near the boundary of the active region. The weight is expected to stay within a smaller region to avoid saturation, which necessitates the following assumption.Assumption 4 (Bounded saturation). There exists a positive constant W max < τ such that the weightW k is bounded in ℓ ∞ norm, i.e., ∥W k ∥ ∞ ≤ W max .The ratio W max /τ is the saturation degree.Assumption 4 requires that W k is bounded inside a small region, which is a mild assumption in real training. For example, one can apply a clipping operation on w k to ensure the assumption. In Appendix E.2, we show that Assumption 4 provably holds under the strongly convex assumption.It is worth pointing out that Assumption 4 implicitly assumes there are critical points in the box {W : ∥W ∥ ∞ ≤ τ }. Otherwise, the gradient will push the weight to the bound of the box and it becomes possible thatW max < ∥W k ∥ ∞ ≤ τ .Intuitively, without the asymmetric bias, the weight is stable near the critical point. In contrast, with asymmetric bias, the noisy gradient that pushes w k toward its symmetric point is amplified by fast reset, while the one that drags w k away from 0 is suppressed by saturation (c.f. Lemma 1). Consequently, the weight w k is attracted by 0, which prevents the stability of Analog SGD around the critical point. We characterize the convergence of Analog SGD in the following theorem.Theorem 2 (Convergence of Analog SGD). Under Assumption 1-4, if the learning rate is set asα = f (W0)-f * σ 2 LKand K is sufficiently large such that α ≤ 1 L , it holds thatEQUATIONwhere S K denotes the amplification factor given by SK := 1 K K k=0 ∥W k ∥ 2 ∞ /τ 2 1-∥W k ∥ 2 ∞ /τ 2 ≤ W 2 max /τ 2 1-W 2 max /τ 2 .The proof of Theorem 2 is deferred to Appendix G.1. Theorem 2 suggests that the average squared gradient norm is upper bounded by the sum of two terms: the first term vanishes at a rate of O( σ 2 /K) which also appears in the SGD's convergence bound (5) ; the second term contributes to the asymptotic error of Analog SGD, which does not vanish with the total number of iterations K; that is, lim sup K→∞1 K K-1 k=0 E[∥∇f (W k )∥ 2 ] ≤ σ 2 S ∞ exist.Impact of saturation/asymmetric update. The saturation degree W max /τ affects both convergence rate and asymptotic error. The ratio is small if W k remains close to the symmetric point or τ is sufficiently large. The exact expression of S K depends on the specific noise distribution, and thus is difficult to reach. However, S K reflects the saturation degree near the critical point W * when W k converges to a neighborhood of W * . Intuitively,W k ≈ W * implies S K ≈ ∥W * ∥ 2 ∞ /τ 2 1-∥W * ∥ 2∞ /τ 2 . Therefore, if the critical point is near the symmetric point, the asymptotic error S K could be small. The asymmetric update has a negative impact on both rate and error. It slows down the convergence of SGD by a factor 1/(1 -W 2 max /τ 2 ), and, meanwhile, a smaller τ increases the asymptotic error.To demonstrate the asymptotic error in Theorem 2 is not artificial, we provide a lower bound next. Theorem 3 (Lower bound of the error of Analog SGD). There is an instance which satisfies Assumption 1-4 such that Analog SGD generates a sequenceEQUATION)The proof of Theorem 3 is deferred to Appendix G.2. Theorem 3 implies that σ 2 S K in the right-hand side (RHS) of (9) can not be improved and therefore the lower bound of the asymptotic error. It demonstrates that the presence of asymptotic error is intrinsic and not an artifact of the convergence analysis. The nonzero asymptotic error also reveals the fundamental performance limits of using Analog SGD for analog training, pointing out a new venue for algorithmic development. 
eliminating asymptotic error of analog training: tiki-taka: 
 Building upon our understanding on the modeling of gradient-based analog training in Section 2 and the asymptotic error of Analog SGD in Section 3, this section will be devoted to understanding means to overcome such asymptotic error in analog training.We will focus on our study on a heuristic algorithm Tiki-Taka that has shown great promise in practice [22] . The key idea of Tiki-Taka is to maintain an auxiliary array to estimate the true gradient. To be specific, Tiki-Taka introduces another analog device, P k , besides the main one, W k . At the initialization phase, P k is initialized as 0. At iteration k, the stochastic gradient is computed using the main device W k and is first applied to P k . Since P k is also an analog device, the change of P k still follows the dynamic (8) by replacing W k with P k and ∆W with ∇f (W k ) + ε k , that isP k+1 = P k + β(∇f (W k ) + ε k ) - β τ |∇f (W k ) + ε k | ⊙ P k (TT-P)where β is a learning rate. After that, the value P k+1 is read and transferred to the main array W k viaW k+1 = W k -αP k+1 - α τ |P k+1 | ⊙ W k . (TT-W)Tiki-Taka performs recursion (TT-P) and (TT-W) alternatively until it converges. Empirically, Tiki-Taka outperforms Analog SGD in terms of the final accuracy. However, Tiki-Taka is a heuristic algorithm, and there are no convergence guarantees so far. In this section, we demonstrate that the improvement of Tiki-Taka stems from its ability to eliminate asymptotic errors.Stability of Tiki-Taka. As explained in Section 3, the gradient noise contributes to the asymptotic error of Analog SGD. To eliminate the error, the idea under Tiki-Taka is to reduce the noise impact. To see how Tiki-Taka reduces the noise, consider the case where W k is already a critical point and P k is initialized as 0, i.e. ∇f (W k ) = P k = 0. After one iteration, the weight W k drifts because of the noise. For Analog SGD, the expected drift isEQUATIONIn contrast, Tiki-Taka updates the auxiliary array byP k+1 = P k + βε k -β τ |ε k | ⊙ P k = βε k , which implies E[P k+1 ] = 0 and E[|P k+1 |] = βE[|ε k |].After the transfer, its expected drift isEQUATIONComparing ( 12) with ( 11), it can be observed that Tiki-Taka improves the expected drift from O(α) to O(αβ). With sufficiently small β, Tiki-Taka controls the drift and makes the weight stay at the critical point. For a more generic scenarios, P k ̸ = 0. However, it is worth noting thatEQUATIONwhich makes P k back to 0 when E[|ε k |] ̸ = 0. Therefore, by controlling the drift, the Tiki-Taka algorithm manages to stay near a critical point.Note that from (13), the stability of P k relies on the presence of noise, i.e. E[|ε k |] ̸ = 0. In addition to the upper bound on the noise in Assumption 3, a lower bound for the noise is also assumed. Assumption 5 (Coordinate-wise i.i.d. and non-zero noise). For any k ≥ 0 and i, j ∈ I,[ε k ] i and [ε k ] j are i.i.d. from a distribution D c which ensures E [ε k ]i∼Dc [ε k ] = 0. Furthermore, there exists σ > 0 and c > 0 such that E [ε k ]i∼Dc [[ε k ] 2 i ] ≤ σ 2 /D and E [ε k ]i∼Dc [|g + [ε k ] i |] ≥ cσ for any g ∈ R.Intuitively, Assumption 5 requires the non-zero noise, which is mild since the random sampling and the physical properties of analog devices always introduce noise. The factor D in the denominator makes it consistent with Assumption 3. We discuss this assumption in more detail in Appendix D.2. Theorem 4 (Convergence of Tiki-Taka). Suppose Assumption 1-5 hold and the learning rate is set asEQUATION)The proof of Theorem 4 is deferred to Appendix H. Theorem 4 first provides the upper bound for the maximum magnitude of P k that decreases as the variance σ 2 increases or τ decreases. This observation is consistent with (13) , which implies the P k tends to zero whenβ τ E[|ε k |] ̸ = 0.Ensuring stability during the training requires the noise to be sufficiently large to render the saturation degree of P max /τ sufficiently small. In addition, the condition 33P 2 max /τ 2 < 1 requires the D to be sufficiently large, which is easy to meet when training large models.Convergence rate. Theorem 4 claims that Tiki-Taka converges at the rate O(σ 2 L K 1 1-33P 2 max /τ 2 ).Therefore, we reach the conclusion that lim sup K→inf1 K K-1 k=0 E[∥∇f (W k )∥ 2 ]= 0 and Tiki-Taka eliminates the asymptotic error of Analog SGD. Furthermore, Tiki-Taka improves the factor 1/(1 -W 2 max /τ 2 ) in Analog SGD's convergence (c.f. ( 9)) to 1/(1 -33P 2 max /τ 2 ), wherein W 2 max /τ 2 and P 2 max /τ 2 are the saturation degrees in fact. Notice that P k tends to 0 as indicated by (13) while W max does not because 0 is usually not a critical point. Therefore, it usually has P 2 max /τ 2 ≪ W 2 max /τ 2 in practice, implying faster convergence. The convergence matches the lower bound O( σ 2 L/K) for general stochastic non-convex smooth optimization [24] up to a constant. 
numerical simulations: 
 In this section, we verify the main theoretical results by simulations on both synthetic datasets and real datasets. We use the PYTORCH to generate the curves for SGD in the simulation and use open source toolkit AIHWKIT [27] to simulate the behaviors of Analog SGD; see github.com/IBM/aihwkit. Each simulation is repeated three times, and the mean and standard deviation are reported. More details can be referred to in Appendix I. The code of our simulation implementation is available at github.com/Zhaoxian-Wu/analog-training. To verify that the proposed dynamic (3) characterizes analog training better than SGD dynamic (2), we conduct a numerical simulation on a least-squares task, and compare Analog SGD implemented by AIHWKIT, the digital and analog dynamics given by ( 2) and (3), respectively; see Figure 3 . The results show that the proposed dynamic provides an accurate approximation of Analog SGD.We verify some critical claims about the asymptotic error of Analog SGD on a least-squares task.Impact of τ . To verify Theorem 2 that the error diminishes with a larger τ , we assign a range of value τ and plot the convergence of Analog SGD. The result is reported on the Left of Figure 4 . When τ is small, the asymmetric bias introduces a notable gap between Analog and Digital SGD. As τ increases, the gap diminishes. The result demonstrates the asymptotic error decreases as τ increases.Impact of σ 2 . To verify the asymptotic error is proportional to σ 2 , we inject noise with different variances. The result is reported in the middle of Figure 4 . The result illustrates that the asymptotic error increases as the noise increases. Impact of the initialization. To demonstrate the asymptotic error is not artificial, we perform Analog SGD from different initializations. The result is reported on the right of Figure 4 . The result illustrates that Analog SGD converges to a similar location regardless of the initialization. The smooth convergence curve ensures the error comes from bias instead of limited machine precision. Therefore, the asymptotic error is intrinsic and independent of the initialization.We also train vision models to perform image classification tasks on real datasets. MNIST FCN/CNN. We train Fullyconnected network (FCN) and convolution neural network (CNN) models on MNIST dataset and see the performance of Analog SGD and Tiki-Taka under various τ . The results are reported in Figure 5 . By reducing the variance, Tiki-Taka outperforms Analog SGD and reaches comparable accuracy with digital SGD. On both of the architectures, the accuracy of Tiki-Taka drops by < 1%. In the FCN training, Analog SGD achieves acceptable accuracy on τ = 0.78 and τ = 0.80 but converges much more slowly. In the CNN training, the accuracy of Analog SGD always drops by > 6%.CIFAR10 Resnet. We also train three Resnet models with different sizes on CIFAR10 dataset. The last layer is replaced by a fully-connected layer mapped onto an analog device with parameter τ = 0.8. The results are shown in Table 2 . In this task, Analog SGD does not suffer from a significant accuracy drop but is still worth that Tiki-Taka, A surprising observation for analog training is that both Analog SGD and Tiki-Taka outperform Digital SGD. We conjecture it happens because the noise introduced by analog devices makes the network more robust to outlier data. 
conclusions and limitations: 
 This paper points out that Analog SGD does not follow the dynamic of digital SGD and hence, we propose a better dynamic to formulate the analog training. Based on this dynamic, we studies the convergence of two gradient-based analog training algorithms, Analog SGD and Tiki-Taka. The theoretical results demonstrate that Analog SGD suffers from asymptotic error, which comes from the noise and asymmetric update. To overcome this issue, we show that Tiki-Taka is able to stay in the critical point without suffering from an asymptotic error. Numerical simulations demonstrate the existence of Analog SGD's asymptotic error and the efficacy of Tiki-Taka. One limitation of this work is that the current analysis is device-specific that applies to asymmetric linear device. While it is an interesting and popular analog device, it is also important to extend our convergence analysis to more general analog devices and develop other device-specific analog algorithms in future work. 
 
 Appendix: Training on Analog In-memory Computing" This section briefly reviews literature that is related to this paper, as complementary to Section 1.Inference and other applications of analog devices. Before designing hardware for training, a series of AIMC prototypes focus on accelerating the inference phase [29, 30, 31, 32, 33, 12, 34] . The state-of-the-art result shows that the analog inference is capable of reaching comparable accuracy with digital inference [28] . Besides analog model training and inference, researchers also managed to exploit the advantages of analog devices to facilitate the machine learning task. For example, energy-based learning algorithms have been studied in [35] , and the neural architecture search on analog devices has been studied in [36] .Relation with physical neural network. Our work is also in spirit related to the recent works on physical neural networks (PNNs) [37, 38] . But we are particularly interested in AIMC hardware with resistive crossbar arrays, while PNN is a generic concept of implementing neural networks via a physical system. Various hardware is capable of supporting PNN, such as holographic grating [39] , wave-based systems [40] , and photonic networks [41] , to name a few.Convergence analysis of gradient-based algorithms. In the digital domain, a series of literature has discussed the convergence of gradient-based algorithms. As the basis of neural model training, much work focuses on the convergence of SGD [42, 43, 44, 23] and its variety stochastic gradient descent with momentum (SGDM) [45, 46, 47, 48] . Notice that the difference between digital SGD (2) and Analog SGD (3) lies on the asymmetric bias term, which implies Analog SGD can be regarded as a digital SGD with bias. From this perspective, the convergence of Analog SGD (c.f. Theorem 2) is similar to that of the digital bias-SGD counterparts. However, the results in this paper are still challenging and non-trivial, especially in the convergence of Tiki-Taka, because the updates of both W k and P k involve asymmetric bias.Nowadays, gradient-based algorithms demonstrate their powerful capabilities in model training. In fact, both SGD and SGDM have reached the theoretical lower bound of the convergence rate, σ 2 /K [24] . This lower bound is a generic result for any stochastic gradient-based algorithms, which means that the convergence of gradient-based analog algorithms, including Analog SGD and Tiki-Taka, is also subject to it.The proposed dynamic (3) of Analog SGD in Section 2 is inspired by the empirical studies in [22] and [19] . However, the proposed dynamic (3) is only an approximation because we can not directly apply an arbitrary increment ∆w on the weights. Instead, we need to send a series of pulses to analog devices, which leads to the change on the weight. In this section, we introduce the implementation of analog update U (•, •) in ( 6) by pulse update and analyze the error of pulse update implementation.Implementation. Similar to U (•, •), we introduce the update function U p (•, •) : R × {+, -} → R for the pulsed update, defined byEQUATIONwhere ∆w min > 0 is the response step size determined by devices. Since ∆w min is the minimum change of weight, it is sometimes called the resolution or granularity of the devices. Given the initial weight w, the updated weight after receiving one pulse is U p (W k , s) where the update sign s = + if ∆w ≥ 0 and s =otherwise.The response step size ∆w min is usually known by physical measurement. In order to approximate U (w, ∆w), analog device first computes the pulse series length (bit length) byEQUATIONwhich ensuresEQUATIONAfter that, a total of BL pulses are sent to the analog device, forcing the weight to becomeEQUATION)which implement the analog update U (w, ∆w).Error analysis. Directly expending the (18) yieldsEQUATION= w + s∆w min BL -1 t=0 q s (w) + t∆w min • q ′ s (w) • sign(∆w) + o(∆w min ) = w + s∆w min BL q s (w) + (∆w min ) 2 BL(BL -1) 2 q ′ s (w) • sign(∆w) + o(∆w min ) = w + ∆w • q s (w) + O(∆w min ) + O((∆w) 2 ),which indicates the difference between U (w, ∆w) and U BL p (w, s) are higher order infinitesimal. As a concrete example, the ∆w min is set as 0.002 [49] or 0.0949 [20] for ReRAM devices.For asymmetric linear device (ALD, defined in Section 2), it holds that |q ′ + (w)| = |q ′ -(w)| = 1 τ and q ′′ + (w) = q ′′ -(w) = 0. Consequently, the difference between U (w, ∆w) and U BL p (w, s) isEQUATION)Since ∆w min and ∆w = O(α) are usually small, the error can usually be ignored.Significance. The significance of the analysis in this section is that it explains how to estimate the response factors q + (•) and q -(•) in (3). In (15) , it shows that they are, in fact, the response factors of the given devices, which can be measured by physic measures [49] . In Section C, we showcase various capable base materials for analog devices and their response factors.In AIMC accelerators, weights of models can be represented by the conductance of based materials, such as PCM [50, 51] , ReRAM [52, 53] , CBRAM [54, 55] , or ECRAM [56] . In this section, we showcase a spectrum of alternative devices for analog training.A large range of devices, including ReRAM [49, 20] , Capacitor [57] , EcRAM [57, 56] , EcRamMO [58] , have linear response factorEQUATIONwhere τ min < 0 < τ max and w ⋄ are constants, whose meaning will be explained later. With these response factors, the function F (•) and G(•) can be written asEQUATIONEQUATION)ALD used in the paper is a special linear step device with τ max = τ and τ min = -τ .For power step device, q + (w) and q -(w) are power function with respect to W , which models implements synapse model [59, 60] .EQUATIONwhere γ + and γ -are parameters determined by materials.In some ReRAM and CMOS-like devices [61, 21] , the response factors are captured by an exponential function, i.e. Exponential update step or CMOS-like update behavior.EQUATIONEQUATIONIn Figure 6 , the curve of response factors and F (•) and G(•) are illustrated. This section proves the weight W k is strongly bounded when the loss function is strongly convex. We prove the result for both Analog GD (ε k = 0) and Analog SGD with ε k possessing some special structure. Before proving this, we introduce strongly convex assumption. Assumption 6 (µ-strongly convex). The objective f (W ) is µ-strongly convex, i.e.EQUATIONAssumption 6 ensures the critical point W * (and hence optimal point) is unique.The following theorem provides a sufficient condition under which the Assumption 4 holds. Theorem 5 (Bounded saturation of Analog GD). Suppose Assumptions 1 and 6 hold and defineEQUATION)The sequence {W k } generated by Analog GD satisfies ∥W k ∥ ∞ ≤ W max .Theorem 5 claims that if both L µ ∥W 0 -W * ∥ and ∥W * ∥ ∞ are sufficiently small, which means the optimal point W * is located inside the active region and W 0 is properly initialized, the saturation degree ∥W k ∥ ∞ /τ can be sufficiently small as well, even though no projection operation is applied.Proof of Theorem 5. Given f (•) is L-smooth (Assumption 1), we know from (57) thatEQUATIONwhere the second inequality comes from the bounded weight (Theorem 1). Consequently, we reach the conclusion that f (W k ) ≤ f (W 0 ), ∀k ∈ N. The strongly convex assumption (Assumption 6) claims thatEQUATIONTherefore, triangle inequality ensures thatEQUATIONwhich completes the proof.Remark 2 (Bounded weight of digital GD). Theorem 5 also holds for digital GD, which can be achieved by forcing τ in inequality (29) to infinite.In high-dimensional cases (D > 1), Theorem 5 does not exclude the situation ∥W k ∥ ∞ > ∥W * ∥ ∞ , which is unfavorable in the example of Analog SGD's lower bound (c.f. Section G.2). To facilitate the proof of the lower bound, we consider the scalar case (D = 1). To distinguish between vectors and scalars, we use the notation w k (and w * ) instead of W k (and W * ) in the next theorem. Theorem 6 (Bounded saturation of Analog GD with scaler weight). Suppose Assumptions 1 and 6 hold and w k ∈ R is a scalar. If the learning rate α ≤ 1 2L , the following statements hold true Proof of Theorem 6. Expanding the objective f (•) in a Taylor series around w yields that2 (Case 1) If w 0 ≥ w * , w 0 ≥ w k ≥ (1 -αµ(1 -∥w k ∥∞ τ ))(w k -w * ) + w * ≥ w k+1 ≥ w * ; (Case 2) If w 0 < w * , w 0 ≤ w k ≤ (1 -αµ(1 -∥w k ∥∞ τ ))(w k -w * ) + w * ≤ w k+1 ≤ w * .EQUATION)where μ(w) depends on w and satisfies µ ≤ μ(w) ≤ L because of the smoothness (Assumption 1) and strong convexity (Assumption 6) assumptions. Consequently, the gradient on w can be written asEQUATIONwith which the gradient descent has the following propertyEQUATIONUsing this inequality and manipulating ∥w k+1 -w * ∥ 2 as ∥w k+1 -w * ∥ 2 (36)= ∥w k -α∇f (w k ) - α τ |∇f (w k )| ⊙ w k -w * ∥ 2 = ∥w k -α∇f (w k ) -w * ∥ 2 + 2α τ ⟨w k -α∇f (w k ) -w * , |∇f (w k )| ⊙ w k ∥⟩ + α 2 τ 2 ∥|∇f (w k )| ⊙ w k ∥ 2 (a) ≤ 1 -2αμ(w k ) + α 2 μ(w k ) 2 + 2αμ(w k )(1 -αμ(w k )) ∥w k ∥ ∞ τ + α 2 μ(w k ) 2 ∥w k ∥ 2 ∞ τ 2 ∥w k -w * ∥ 2 = 1 -2αμ(w k )(1 - ∥w k ∥ ∞ τ ) + α 2 μ(w k ) 2 (1 -2 ∥w k ∥ ∞ τ + ∥w k ∥ 2 ∞ τ 2 ) ∥w k -w * ∥ 2 = 1 -αμ(w k )(1 - ∥w k ∥ ∞ τ ) 2 ∥w k -w * ∥ 2where the (a) uses Cauchy's inequality. Noticing Theorem 1 claims ∥w k ∥∞ τ ≤ 1 and the learning rate is chosen as αμ(w k ) ≤ αL ≤ 1, we have ∥w k+1 -w * ∥ 2 ≤ ∥w k -w * ∥ 2 .In addition, Lemma 1 claims thatEQUATION)where the second inequality holds because Theorem 1 and smoothness assumption (Assumption 1 guarantee ∥1 + w k /τ ∥ ≤ 2 and ∥∇f (w k )∥ ≤ ∥w k -w * ∥, respectively. This fact implies that w k+1 -w * has the same sign with w k -w * . Consequently, inequality (36) and (37) show that in case 1, if w k ≥ w * , we haveEQUATION≥ w k+1 ≥ w * .Keeping using this inequality reaches the result. Case 2 can be proved by the similar method.The following theorem provides a sufficient condition under which the Assumption 4 holds. In the section, we show that if the noise has special structures, the saturation degree ∥W k ∥ ∞ /τ is bounded. Assumption 7 (Random sample noise). The noise can be written as ε = ∇f (W ; ξ) -∇f (W ), where ξ is a random variable sampled from an underline data distribution D f , f (W ; ξ) is a function of W and ξ, and the gradient ∇f (W ; ξ) is taken over W .Assumption 7 holds if the noise comes from the random sampling from a series of functions. Theorem 7 (Bounded saturation of Analog SGD). Suppose Assumption 7 holds and each f (W ; ξ) is L-smooth (Assumptions 1) and µ-strongly convex (Assumptions 6) with respect to W . Denote the minimum of f (W ; ξ) as W * ξ . If the supremum sup ξ {∥W * ξ ∥ ∞ } exists, defineEQUATION)The sequence {W k } generated by Analog SGD satisfies ∥W k ∥ ∞ ≤ W max uniformly.Given the strong convexity with respect to W , f (W ; ξ) has unique minimum, and hence W * ξ is welldefined. Similarly, the supremum sup ξ {∥W 0 -W * ξ ∥} exists since sup ξ {∥W * ξ ∥ ∞ } exists. Theorem 7 claims that the saturation degree is bounded given the noise comes from random sampling over a series of smooth and strongly convex functions. Similar to Theorem 5, Theorem 7 also holds for digital GD by forcing τ in inequality (29) to infinite. The proof of Theorem 7 is inspired by that of [62, Lemma 1] .Proof. According to Theorem 5, it holds thatEQUATIONTherefore, triangle inequality ensures thatEQUATION≤ sup ξ {∥W k -W * ξ ∥} + sup ξ {∥W * ξ ∥ ∞ } ≤ L µ sup ξ {∥W 0 -W * ξ ∥} + sup ξ {∥W * ξ ∥ ∞ }which completes the proof.Similar to Theorem 6, we can improve the bound when the weight is scalar (D = 1). The notation w k (and w * ) instead of W k (and W * ) are adopted here to indicate the scalar situation.Theorem 8 (Bounded saturation of Analog GD). Suppose Assumption 7 holds and for any ξ, f (w; ξ) is L-smooth (Assumptions 1) and µ-strongly convex (Assumptions 6) with respect to w. Denote the minimum of f (w; ξ) as w * ξ . If the supremum sup ξ {∥w * ξ ∥} exists, it holds for any k ∈ N thatEQUATION)Proof of Theorem 8. The theorem is proved by induction. The statement holds trivially at k = 0. Suppose (42) holds for k. If W k ≥ w * , Theorem 6 guarantees that w k ≥ w k+1 ≥ w * ξ and henceEQUATIONOn the contrary, if w k ≤ w * , Theorem 6 guarantees that w k ≤ w k+1 ≤ w * ξ and henceEQUATIONwhich implies w k+1 still satisfies (42) . Now the conclusion is reached.This section verifies Assumption 5. In principle, Assumption 5 requires the expectation that noise is non-zero. To see that, note that when the probability density function of D is non-zero at only one point, c equals zero. On the contrary, large c is at the other side of the spectrum, which appears when the probability density function is relatively "uniformly distributed" throughout the probability space.In analog acceleration devices, it is mild because noise is introduced during computation.Generally, the estimation of c can be challenging because it involves the computation of the raw momentum E ε [|g + ε|] of the noise. Scarifying the rigorousness a bit but providing an intuitive result, we get the parameter c by considering an approximation of this raw momentum and deducing a bound for this approximation.In this section, we demonstrate that for Gaussian noise ε ∼ N (0, σ 2 ), c can be selected as 2 π . For any g, it holds thatE ε [∥1 - β τ |g + ε|∥ 2 ∞ ] = E ε [(1 - β τ |g + ε|) 2 ] (45) = 1 - 2β τ E ε [|g + ε|] + β 2 τ 2 E ε [(g + ε) 2 ] = 1 - 2β τ E ε [|g + ε|] + β 2 τ 2 (g 2 + σ 2). Because g + ε is Gaussian random variable with mean g and variance σ 2 , the second term in the RHS has closed form [63] given byEQUATION)In the equation above, 1 F 1 (•; •; •) is used to denote Kummer's confluent hypergeometric functions. It has been shown [64, 13.1.5 ] that when z ≤ 0, 1 F 1 (•; •; •) has the asymptotic propertyEQUATIONwhereEQUATION)Let z = -g 2 2σ 2 . On the one hand when σ ∼ 0, z is large and ( 47) with a = -1 2 and b = 1 2 asserts thatE ε [|g + ε|] ∼ σ 2 π • Γ(1/2) Γ(1)EQUATION)On the other hand, when σ → ∞, z is small and (48) provides thatEQUATIONIn conclusion, choosing c= 2 π yields E ε [|g + ε|] ≿ 2 π σ.Here ≿ is used to indicate the lower bound holds for an approximation of the left-hand side (LHS).Lemma 1 (Saturation and fast reset). For ALD with a general w ⋄ , the following statements are valid(Saturation) If sign(∆w) = sign(w k ), it holds that |w k+1 -w k | = |1 -|w k -w ⋄ |/τ | • |∆w|. (Fast Reset) If sign(∆w) = -sign(w k ), it holds that |w k+1 -w k | = |1 + |w k -w ⋄ |/τ | • |∆w|.Proof of Lemma 1. The proof can be completed by simply extending the LHS of|w k+1 -w k | = ∆w - 1 τ |∆w|(w k -w ⋄ ) (51) = |∆w|(sign(∆w) - 1 τ (w k -w ⋄ )) = |sign(∆w) - 1 τ (w k -w ⋄ )| • |∆w| = 1 - sign(w k -w ⋄ ) sign(∆w) |w k -w ⋄ | τ • |∆w|.Using the fact that w ⋄ = 0 completes the proof.This section proves that the weight W k is bounded. Theorem 1 (Bounded weight). Denote ∥W ∥ ∞ as the ℓ ∞ norm of W . Given ∥W 0 ∥ ∞ ≤ τ and for any sequence{∆W k : k ∈ N}, which satisfies ∥∆W k ∥ ∞ ≤ τ , it holds that ∥W k ∥ ∞ ≤ τ, ∀k ∈ N.Proof of Theorem 1. Without causing confusion, omit the superscript k and denote the i-th coordinate of W k and ∆W k as w i and g i , respectively. It holds that∥W k ∥ 2 ∞ < τ and |g ij | ≤ τ ∥W k+1 -W ⋄ ∥ 2 ∞ = ∥W k -W ⋄ + ∆W k - 1 τ |∆W k | ⊙ (W k -W ⋄ )∥ 2 ∞ (52) = max i∈I (w i -w ⋄ -g i - 1 τ |g i |(w i -w ⋄ )) 2 = max i∈I (1 - 1 τ |g i |) 2 (w i -w ⋄ ) 2 -2g i (1 - 1 τ |g i |)(w i -w ⋄ ) + g 2 i ≤ max i∈I (1 - 1 τ |g i |) 2 τ 2 + 2|g i | (1 - 1 τ |g i |)τ + g 2 i = max i∈I (1 - 1 τ |g i |) τ + |g i | 2 = τ 2 .Taking square root on both sides completes the proof.In Section 3, we show that the asymptotic error is proportional to the noise variance σ 2 . The following theorem prove that the Analog GD converges to a critical point. Theorem 9 (Convergence of Analog GD). Under Assumption 1, 2 and 4, if the learning rate is set asEQUATION)A surprising conclusion of Theorem 9 is that the asymmetric update actually will not introduce any asymptotic error in training. It also indicates that the asymptotic error comes from the interaction between asymmetric update and noise from another perspective.Proof of Theorem 9. The L-smooth assumption (Assumption 1) implies thatf (W k+1 ) ≤ f (W k ) + ⟨∇f (W k ), W k+1 -W k ⟩ + L 2 ∥W k+1 -W k ∥ 2 (54) = f (W k ) - α 2 ∥∇f (W k )∥ 2 -( 1 2α - L 2 )∥W k+1 -W k ∥ 2 + 1 2α ∥W k+1 -W k + α∇f (W k )∥ 2 ≤ f (W k ) - α 2 ∥∇f (W k )∥ 2 + 1 2α ∥W k+1 -W k + α∇f (W k )∥ 2where the equality comes fromEQUATION+ 1 2α ∥W k+1 -W k + α∇f (W k )∥ 2 .The third term in the RHS of ( 54) can be bounded by1 2α ∥W k+1 -W k + α∇f (W k )∥ 2 = α 2τ 2 ∥|∇f (W k )| ⊙ W k ∥ 2 (56) ≤ α 2τ 2 ∥∇f (W k )∥ 2 ∥W k ∥ 2 ∞ .Substituting (56) back into (54) and cooperating with Assumption 4 yieldf (W k+1 ) ≤ f (W k ) - α 2 1 - ∥W k ∥ 2 ∞ τ 2 ∥∇f (W k )∥ 2 (57) ≤ f (W k ) - α 2 1 - W 2 max τ 2 ∥∇f (W k )∥ 2 .Rearranging and averaging (57) for k from 0 to K -1 deduce thatEQUATION)Noticing Assumption 2 claims that f (W k ) ≥ f * , we complete the proof.G.1 Proof of Theorem 2: Convergence of Analog SGDThis section provides the convergence guarantee of Analog SGD under non-convex assumption on asymmetric linear devices. Theorem 2 (Convergence of Analog SGD). Under Assumption 1-4, if the learning rate is set asα = f (W0)-f * σ 2 LKand K is sufficiently large such that α ≤ 1 L , it holds thatEQUATIONwhere S K denotes the amplification factor given by SK := 1 K K k=0 ∥W k ∥ 2 ∞ /τ 2 1-∥W k ∥ 2 ∞ /τ 2 ≤ W 2 max /τ 2 1-W 2 max /τ 2 .Proof of Theorem 2. The L-smooth assumption (Assumption 1) implies thatEQUATION) ≤ f (W k ) - α 2 ∥∇f (W k )∥ 2 -( 1 2α -L)E ε k [∥W k+1 -W k + αε k ∥ 2 ] + α 2 LE ε k [∥ε k ∥ 2 ] + 1 2α ∥W k+1 -W k + α(∇f (W k ) + ε k )∥ 2where the second inequality comes from the assumption that noise has expectation 0 (Assumption 3)E ε k [⟨∇f (W k ), W k+1 -W k ⟩] = E ε k [⟨∇f (W k ), W k+1 -W k + αε k ⟩] = - α 2 ∥∇f (W k )∥ 2 - 1 2α E ε k [∥W k+1 -W k + αε k ∥ 2 ] + 1 2α E ε k [∥W k+1 -W k + α(∇f (W k ) + ε k )∥ 2 ]and the following inequalityEQUATION)With the learning rate α ≤ 1 2L and bounded variance of noise (Assumption 3), ( 59) becomesEQUATION)Cooperated with Assumption 3, the last term in the RHS of ( 59) can be bounded by1 2α E ε k [∥W k+1 -W k + α∇f (W k ) + αε k ∥ 2 ] (62) = α 2τ 2 E ε k [∥|∇f (W k ) + ε k | ⊙ W k ∥ 2 ] ≤ α 2τ 2 E ε k [∥∇f (W k ) + ε k ∥ 2 ] ∥W k ∥ 2 ∞ ≤ α 2τ 2 ∥∇f (W k )∥ 2 ∥W k ∥ 2 ∞ + ασ 2 2τ 2 ∥W k ∥ 2 ∞where the last inequality comes from Assumption 3EQUATIONPlugging (62) back into (59) yieldsEQUATIONEQUATION) ≤ 2(f (W 0 ) -E[f (W k+1 )]) αK(1 -W 2 max /τ 2 ) + 2αLσ 2 1 -W 2 max /τ 2 + 1 K K k=0 σ 2 ∥W k ∥ 2 ∞ /τ 2 1 -∥W k ∥ 2 ∞ /τ 2 ≤ 2(f (W 0 ) -f * ) αK(1 -W 2 max /τ 2 ) + 2αLσ 2 1 -W 2 max /τ 2 + 1 K K k=0 σ 2 ∥W k ∥ 2 ∞ /τ 2 1 -∥W k ∥ 2 ∞ /τ 2 = 4 (f (W 0 ) -f * )σ 2 L K 1 1 -W 2 max /τ 2 + σ 2 S Kwhere the second inequality uses Assumption 2 and the last equality chooses the learning rate asα = f (W0)-f * σ 2 LK .The proof is completed.This section provides the lower bound of Analog GD under non-convex assumption on noisy asymmetric linear devices. Theorem 3 (Lower bound of the error of Analog SGD). There is an instance which satisfies Assumption 1-4 such that Analog SGD generates a sequence {W k : k = 0, 1, • • • , K} which satisfiesEQUATION)The proof is completed based on the following example.(Example) Consider an example where all the coordinates are identical, i.e. W k = w k 1 for some w k ∈ R where 1 ∈ R D is the all-one vector. Define W * = w * 1 where w * ∈ R is a constant scalar and a quadratic function f (W ) := L 2 ∥W -W * ∥ 2 whose minimum is W * . Initialize the weight on W 0 = W * and choose the learning rate α ≤ min{ 1 2L ,1 µ+6σ/(τ √ D) }.Furthermore, consider the noise defined as follows,EQUATIONwhere random variable ξ k ∈ R is sampled byEQUATIONAs a reminder, it is always valid that|w k | = ∥W k ∥ ∞ ≤ τ (c.f. Theorem 5) and 0 ≤ p k ≤ 1.Therefore, the noise distribution is well-defined. Furthermore, without loss of generality3 , we assume|w * | ≤ τ 4 and σ ≤ τ L √ D 4 √ 3 .Since all the coordinates are identical, Analog SGD can be regarded to train a scalar weight at each coordinate. Furthermore, with the definitionEQUATIONthe noise ξ k satisfies Assumption 7. Therefore, even though w * ξ k are time varying, we can regard w k as the initial point and only consider w k+1 . By this way, the conditions of Theorem 6 and Theorem 8 are met, and their claim for w k+1 is valid.To prove the lower bound, we next introduce several necessary lemmas to facilitate the proof of Theorem 3. The first one is used to verify Assumption 4.Lemma 2. Suppose |w * | ≤ τ 4 and σ ≤ τ L √ D 4 √ 3 . Define W max := τ 2 .The sequence {W k : k ∈ N} generated by Analog SGD (3) on the example above satisfiesEQUATION)Proof of Lemma 2. The statement can be proved by induction. When k = 0,EQUATIONTo prove (69) for k + 1, Theorem 8 asserts thatEQUATIONor equivalentlyEQUATIONAccording to the triangle inequality, ∥W k+1 ∥ ∞ is still bounded by∥W k+1 ∥ ∞ = max i {|[W k+1 ] i |} ≤ |w * | + σ L √ D max 1 -p k p k , p k 1 -p k (73) = |w * | + σ L √ D 1 + ∥W k ∥ ∞ /τ 1 -∥W k ∥ ∞ /τ ≤|w * | + σ L √ D 1 + W max /τ 1 -W max /τ ≤ τ 4 + τ 4 √ 3 1 + (2τ )/τ 1 -(2τ )/τ = τ 2 = W max .Therefore, (69) is confirmed for k + 1 and the proof of Lemma 2 is completed.Noise ξ k defined by ( 67) is time-varying since W k is changing. The following lemma provides an upper bound for the variation of noise with respect toW k . Lemma 3. Suppose ∥W k ∥ ∞ ≤ W max ≤ τ 2 .The following statements are always validEQUATIONEQUATIONProof of Lemma 3. Define the functionsEQUATIONwith which ξ + k and ξ - k can be written asEQUATIONThe derivatives of g + (x) and g -(x) isEQUATIONEQUATIONwhose norms are upper bounded byEQUATIONEQUATIONTherefore, both g + (x) and g -(x) are Lipschitz continuous and henceEQUATIONEQUATIONThe proof of Lemma 3 is then completed.In the proof of Theorem 3, the most tricky part in the recursion (3) is the gradient wrapped by absolute value |∇f(W k ) + ε k |. Fortunately, the expectation E[|∇f (W k ) + ε k |]can be expressed explicitly in the example above, which is demonstrated by the following lemma. Lemma 4. Suppose the learning rate is chosen such that α ≤ min{ 1 2L ,EQUATIONProof of Lemma 4. The proof of Lemma 4 closely relies on the following inequalityEQUATIONor equivalently, the gradientEQUATIONBy (85), we claim the signs of[∇f (W k )] i + ξ + k and [∇f (W k )] i + ξ -k never change during the training and thus the absolute value can be removedEQUATIONEQUATIONAccordingly,EQUATION= p k ξ + k 1 + ∇f (W k ) + (1 -p k ) ξ - k 1 -∇f (W k ) = p k σ √ D 1 -p k p k • 1 + ∇f (W k ) + (1 -p k ) σ √ D p k 1 -p k • 1 -∇f (W k ) = 2σ √ D p k (1 -p k ) • 1 + (2p k -1)∇f (W k )which is the result. Therefore, the rest of proof shows (84) is valid.Verification of (84). The statement can be proved by induction. When k = 0, (84) holds naturally since W 0 = W * .To prove (84) for k + 1, we consider ε k = ξ + k 1 and ε k = ξ - k 1 separately, and the conclusion holds for both cases.Case 1:ε k = ξ + k 1 = σ √ D 1-p k p k • 1.From the induction assumption, it is valid thatEQUATIONTherefore, Theorem 6 asserts that[W k+1 ] i ≤ [W k ] i and hence we have p k+1 ≥ p k , ξ + k+1 ≤ ξ + k and ξ - k+1 ≤ ξ - k .Consequently, the second inequality of (84) can be reached by Theorem 8EQUATION)To obtain the other inequality, notice thatEQUATION) (a) = [W k+1 ] i + (1 -αL(1 - [W k ] i τ ))(w * - ξ + k+1 L -[W k ] i ) + 1 L (ξ + k -ξ + k+1 ) (b) ≤ [W k+1 ] i + (1 -αL(1 - [W k ] i τ ))(w * - ξ + k+1 L -[W k ] i ) + 6ασ τ √ D ([W k ] i -(w * - ξ + k+1 L )) = [W k+1 ] i -(1 -αL(1 - [W k ] i τ ) - 6ασ τ √ D )([W k ] i -(w * - ξ + k+1 L ))where (a) comes from Theorem 6, (b) comes from Lemma 3 and inequality (37) .EQUATION)The choice of learning rate implies thatEQUATIONfrom which and (91) we reach thatEQUATIONCombining ( 94) and ( 90) reaches (84) in case 1.Case 2:ε k = ξ - k 1 = -σ √ D p k 1-p k • 1.Noticing the permutation invariant between p k and 1 -p k in the noise definition (67), we find that the proof for case 2 is similar to that of case 1. Therefore, the proof of case 2 is omitted here.In conclusion, (84) still holds for k + 1 and (84) is verified. Now the proof of Lemma 4 is completed.After providing the necessary lemmas, we begin to prove Theorem 3.Proof of Theorem 3. Consider the example constructed above. Before deriving the lower bound, we demonstrate Assumption 1-4 hold. It is obvious that ∇f (W ) = L(W -W * ) satisfies Assumption 1 and f (W ) ≥ f * := 0 satisfies Assumption 2. In addition, Assumption 3 could be verified by noticing (66) impplies E ε k [ε k ] = 0 and E ε k [∥ε k ∥ 2 ] ≤ σ 2 .E ε k [W k+1 -W * ] (95) = E ε k [W k -α∇f (W k ) -αε k - α τ |∇f (W k ) + ε k | ⊙ W k -W * ] = (1 -αL)(W k -W * ) - α τ E ε k [|∇f (W k ) + ε k |] ⊙ W k = (1 -αL)(W k -W * ) - 2ασ τ √ D p k (1 -p k ) • W k - α τ (2p k -1)∇f (W k ) ⊙ W kMultiplying the both size of (95) by L and plugging in the equation ∇f(W k ) = L(W k -W * ) yield E ε k [∇f (W k+1 )] (96) = (1 -αL)∇f (W k ) - 2αLσ τ √ D p k (1 -p k ) • W k - αL τ (2p k -1)∇f (W k ) ⊙ W k = 1 -αL -αL(2p k -1) w k τ ∇f (W k ) - 2αLσ τ √ D p k (1 -p k ) • W k .where the last equality uses W k = w k 1. Recall the probability p k = 1 2 (1 -w k τ ), we haveEQUATIONSubstitute them back into (96)E ε k [∇f (W k+1 )] = 1 -αL + αL |w k | 2 τ 2 ∇f (W k ) - αLσ τ √ D 1 - |w k | 2 τ 2 • W k (98) = 1 -αL + αL ∥W k ∥ 2 ∞ τ 2 ∇f (W k ) - αLσ τ √ D 1 - ∥W k ∥ 2 ∞ τ 2 • W k = ∇f (W k ) -αL 1 - ∥W k ∥ 2 ∞ τ 2 ∇f (W k ) - αLσ τ √ D 1 - ∥W k ∥ 2 ∞ τ 2 • W kwhere the first equality utilizes|w k | 2 = ∥w k 1∥ 2 ∞ = ∥W k ∥ 2 ∞ .Reorganizing (98), we obtain∇f (W k ) = - σ 1 -∥W k ∥ 2 ∞ /τ 2 W k /τ √ D + ∇f (W k ) -E ε k [∇f (W k+1 )] 1 -∥W k ∥ 2 ∞ /τ 2 .It is worth noticing that the second term in the RHS of (99) is in the order of O(α)∇f (W k ) -E ε k [∇f (W k+1 )] 1 -∥W k ∥ 2 ∞ /τ 2 = L E ε k [W k -W k+1 ] 1 -∥W k ∥ 2 ∞ /τ 2 (a) ≤ αL ∥E ε k [∇f (W k ) + ε k ]∥ (1 -∥W k ∥ ∞ /τ )(1 -∥W k ∥ 2 ∞ /τ 2 ) = αL ∥∇f (W k )∥ (1 -∥W k ∥ ∞ /τ )(1 -∥W k ∥ 2 ∞ /τ 2 ) (b) ≤ αL 2 (W max + W * )D (1 -W max /τ )(1 -W 2 max /τ 2 ) = O(α)where (a) is Lemma 1 and (b)comes from ∥∇f (W k )∥ = L∥W k -W * ∥ ≤ L(∥W k ∥ + ∥W * ∥) ≤ L √ D(∥W k ∥ ∞ + |w * |).Therefore, the gradient can be rewritten asEQUATIONTaking the square norm of the gradient and averaging for k from 0 to K -1 we obtainEQUATIONwhere the following equality is appliedEQUATION)The proof of Theorem 3 is thus completed.This section provides the convergence guarantee of the Tiki-Taka under the non-convex assumption.Theorem 4 (Convergence of Tiki-Taka). Suppose Assumption 1-5 hold and the learning rate is set as α = O(1/ √ σ 2 K), β = 8αL. It holds for Tiki-Taka that the expected infinity normP k is upper bounded by E[∥P k+1 ∥ 2 ∞ ] ≤ P 2 max := 41L 2 τ 4 D c 2 σ 2 .Furthermore, if σ 2 and D are sufficiently large so that 33P 2 max /τ 2 < 1 it is valid thatEQUATIONBefore the proving Theorem 4, we first introduce two useful lemmas.Lemma 5 (Tracking Lemma). Under Assumption 1 and 3, it holds thatE ε k+1 [∥P k+2 - τ √ D σ ∇f (W k+1 )∥ 2 ] (102) ≤ 1 - βσ τ √ D ∥P k+1 - τ √ D σ ∇f (W k )∥ 2 + 4L 2 τ 3 D 3/2 βσ 3 ∥W k+1 -W k ∥ 2 + 4βσ τ √ D ∥P k+1 ∥ 2 + 4β √ D τ σ ∥P k+1 ∥ 2 ∞ ∥∇f (W k )∥ 2 + 2β 2 σ 2 .To make P k+2 sufficiently close to the true gradient, ∥P k+1 ∥ 2 should be small.Proof of Lemma 5. According to the update rule of P k , we haveE ε k+1 [∥P k+2 - τ √ D σ ∇f (W k+1 )∥ 2 ] (103) = E ε k+1 [∥P k+1 + β∇f (W k+1 ) + βε k+1 - β τ |∇f (W k+1 ) + ε k+1 | ⊙ P k+1 - τ √ D σ ∇f (W k+1 )∥ 2 ] = E ε k+1 [∥(1 - βσ τ √ D )(P k+1 - τ √ D σ ∇f (W k+1 )) + βσ τ √ D P k+1 - β τ |∇f (W k+1 ) + ε k+1 | ⊙ P k+1 + βε k+1 ∥ 2 ] ≤ 1 1 -u E ε k+1 [∥(1 - βσ τ √ D )(P k+1 - τ √ D σ ∇f (W k+1 )) + βε k+1 ∥ 2 ] + β 2 uτ 2 E ε k+1 [∥(σ1/ √ D -|∇f (W k+1 ) + ε k+1 |) ⊙ P k+1 ∥ 2 ].With Assumption 3, the first term of (103) can be bounded via the same technique as (63) , that is1 1 -u E ε k+1 [∥(1 - βσ τ √ D )(P k+1 - τ √ D σ ∇f (W k+1 )) + βε k+1 ∥ 2 ] (104) ≤ (1 -βσ τ √ D ) 2 1 -u ∥P k+1 - τ √ D σ ∇f (W k+1 )∥ 2 + β 2 1 -u σ 2 ≤ 1 - 2βσ τ √ D + u ∥P k+1 - τ √ D σ ∇f (W k+1 )∥ 2 + β 2 1 -u σ 2where the last inequality holds becauseEQUATIONThe third term in the RHS of (103) can be manipulated by the variance decomposition and consequently can be bounded byβ 2 uτ 2 E ε k+1 [∥(σ1/ √ D -|∇f (W k+1 ) + ε k+1 |) ⊙ P k+1 ∥ 2 ] (106) = β 2 uτ 2 E ε k+1 i∈I (σ/ √ D -|[∇f (W k+1 ) + ε k+1 ] i |) 2 [P k+1 ] 2 i = β 2 uτ 2 E ε k+1 i∈I (σ 2 /D -2σ|[∇f (W k+1 ) + ε k+1 ] i | + [∇f (W k+1 ) + ε k+1 ] 2 i )[P k+1 ] 2 i = β 2 uτ 2 E ε k+1 i∈I (σ 2 /D -2σ|[∇f (W k+1 ) + ε k+1 ] i |)[P k+1 ] 2 i + β 2 uτ 2 E ε k+1 i∈I ([∇f (W k+1 ) + ε k+1 ] 2 i )[P k+1 ] 2 i ≤ β 2 uτ 2 (σ 2 /D -2cσ 2 + σ 2 /D)∥P k+1 ∥ 2 + β 2 uτ 2 ∥P k+1 ∥ 2 ∞ ∥∇f (W k+1 )∥ 2 ≤ 2β 2 σ 2 uτ 2 D ∥P k+1 ∥ 2 + β 2 uτ 2 ∥P k+1 ∥ 2 ∞ ∥∇f (W k+1 )∥ 2 .Combining (104) and ( 106) with (103) provides thatE ε k+1 [∥P k+2 - τ √ D σ ∇f (W k+1 )∥ 2 ] (107) ≤ 1 - 2βσ τ √ D + u ∥P k+1 - τ √ D σ ∇f (W k+1 )∥ 2 + β 2 1 -u σ 2 + 2β 2 σ 2 uτ 2 D ∥P k+1 ∥ 2 + β 2 uτ 2 ∥P k+1 ∥ 2 ∞ ∥∇f (W k+1 )∥ 2 (a) ≤ 1 - 3βσ 2τ √ D ∥P k+1 - τ √ D σ ∇f (W k+1 )∥ 2 + 2β 2 σ 2 + 4βσ τ √ D ∥P k+1 ∥ 2 + 2β √ D τ σ ∥P k+1 ∥ 2 ∞ ∥∇f (W k+1 )∥ 2 ≤ 1 - 3βσ 2τ √ D 1 + βσ 2τ √ D ∥P k+1 - τ √ D σ ∇f (W k )∥ 2 + 1 - 3βσ 2τ √ D 1 + 2τ √ D βσ τ 2 D σ 2 ∥∇f (W k+1 ) -∇f (W k )∥ 2 + 2β 2 σ 2 + 4βσ τ √ D ∥P k+1 ∥ 2 + 2β √ D τ σ ∥P k+1 ∥ 2 ∞ ∥∇f (W k+1 )∥ 2 (b) ≤ 1 - βσ τ √ D ∥P k+1 - τ √ D σ ∇f (W k )∥ 2 + 2L 2 τ 3 D 3/2 βσ 3 ∥W k+1 -W k ∥ 2 + 4βσ τ √ D ∥P k+1 ∥ 2 + 2β √ D τ σ ∥P k+1 ∥ 2 ∞ ∥∇f (W k+1 )∥ 2 + 2β 2 σ 2 , (c) ≤ 1 - βσ τ √ D ∥P k+1 - τ √ D σ ∇f (W k )∥ 2 + 4L 2 τ 3 D 3/2 βσ 3 ∥W k+1 -W k ∥ 2 + 4βσ τ √ D ∥P k+1 ∥ 2 + 4β √ D τ σ ∥P k+1 ∥ 2 ∞ ∥∇f (W k )∥ 2 + 2β 2 σ 2 .In the inequality above, (a) sets u = β/2; (b) holds becauseEQUATIONandEQUATIONand (c) comes from2β √ D τ σ ∥P k+1 ∥ 2 ∞ ∥∇f (W k+1 )∥ 2 (110) ≤ 4β √ D τ σ ∥P k+1 ∥ 2 ∞ ∥∇f (W k )∥ 2 + 4β √ D τ σ ∥P k+1 ∥ 2 ∞ ∥∇f (W k+1 ) -∇f (W k )∥ 2 ≤ 4β √ D τ σ ∥P k+1 ∥ 2 ∞ ∥∇f (W k )∥ 2 + 4βL 2 τ √ D σ ∥W k+1 -W k ∥ 2 ≤ 4β √ D τ σ ∥P k+1 ∥ 2 ∞ ∥∇f (W k )∥ 2 + 2L 2 τ 3 D 3/2 βσ 3 ∥W k+1 -W k ∥ 2 .where the last inequality holds because β ≤ 2τ 2 D βσ 2 . Now we get the claim.Lemma 6 (Weight Decay Lemma). Suppose Assumption 1, 3 and 5 hold. If β satisfiesEQUATIONit holds thatE ε k+1 [∥P k+2 ∥ 2 ] ≤ (1 - βcσ 2τ )∥P k+1 ∥ 2 + 4βτ cσ ∥∇f (W k )∥ 2 + 4L 2 βτ cσ ∥W k+1 -W k ∥ 2 + 3β 2 σ 2 .Proof of Lemma 6. The proof begins from the manipulation of the expected square norm of P k+2E ε k+1 [∥P k+2 ∥ 2 ] (112) = E ε k+1 [∥P k+1 + β(∇f (W k+1 ) + ε k+1 ) - β τ |∇f (W k+1 ) + ε k+1 | ⊙ P k+1 ∥ 2 ] = E ε k+1 [∥(1 - β τ |∇f (W k+1 ) + ε k+1 |) ⊙ P k+1 + β(∇f (W k+1 ) + ε k+1 )∥ 2 ] = E ε k+1 [∥(1 - β τ |∇f (W k+1 ) + ε k+1 |) ⊙ P k+1 ∥ 2 ] + β 2 E ε k+1 [∥∇f (W k+1 ) + ε k+1 ∥ 2 ] + 2E ε k+1 (1 - β τ |∇f (W k+1 ) + ε k+1 |) ⊙ P k+1 , β(∇f (W k+1 ) + ε k+1 ) .For the sake of simplicity, below we use [g k+1 ] i := [∇f (W k+1 )] i to denote the i-th coordinate of the gradient. According to Assumption 5, the first term in the RHS of (112) can be bounded byE ε k+1 [∥(1 - β τ |∇f (W k+1 ) + ε k+1 |) ⊙ P k+1 ∥ 2 ] (113) = E ε k+1 i∈I (1 - β τ |[g k+1 ] i + [ε k+1 ] i |) 2 [P k+1 ] 2 i = i∈I 1 - 2β τ E [ε k+1 ]i [|[g k+1 ] i + [ε k+1 ] i |] + β 2 τ 2 E [ε k+1 ]i [([g k+1 ] i + [ε k+1 ] i ) 2 ] [P k+1 ] 2 i ≤ i∈I 1 - 2βcσ τ + β 2 (4L 2 τ 2 + σ 2 ) τ 2 [P k+1 ] 2 i ≤ 1 - 3βcσ 2τ ∥P k+1 ∥ 2 ,where the last inequality holds because of the selection of β. To bound the third term in the RHS of (112), we use the unbiased property of E ε k+1 [ε k+1 ] = 0 (Assumption 3) and ∥P k ∥ ∞ ≤ τ (Theorem 1), which lead to2E ε k+1 (1 - β τ |∇f (W k+1 ) + ε k+1 |) ⊙ P k+1 , β(∇f (W k+1 ) + ε k+1 ) (114) = 2βE ε k+1 [⟨P k+1 , ∇f (W k+1 ) + ε k+1 ⟩] -2E ε k+1 β τ |∇f (W k+1 ) + ε k+1 | ⊙ P k+1 , β(∇f (W k+1 ) + ε k+1 ) = 2β ⟨P k+1 , ∇f (W k+1 )⟩ - 2β 2 τ E ε k+1 [⟨|∇f (W k+1 ) + ε k+1 |, (∇f (W k+1 ) + ε k+1 ) ⊙ P k+1 ⟩] ≤ 2β ⟨P k+1 , ∇f (W k+1 )⟩ + 2β 2 E ε k+1 ∥∇f (W k+1 ) + ε k+1 ∥ 2 .Plugging (113) and ( 114) into (112) yieldsE ε k+1 [∥P k+2 ∥ 2 ] ≤ 1 - 3βcσ 2τ ∥P k+1 ∥ 2 + 3β 2 E ε k+1 [∥∇f (W k+1 ) + ε k+1 ∥ 2 ] (115) + 2β ⟨P k+1 , ∇f (W k+1 )⟩ .Notice that the second term in the RHS of (115) can be upper bounded by Assumption 3 and inequality (63) , and the third term can be bounded by Young's inequalityEQUATIONInequality ( 63), (116) and the condition β ≤ 2 3cσ lead to the resultEQUATION)Applying the inequality∥∇f (W k+1 )∥ 2 ≤ 2∥∇f (W k )∥ 2 + 2∥∇f (W k+1 ) -∇f (W k )∥ 2 (118) ≤ 2∥∇f (W k )∥ 2 + 2L 2 ∥W k+1 -W k ∥ 2on (117) completes the proof.Lemma 7 (Bounded Saturation of P k ). Suppose Assumption 1, 3 and 5 hold. If β satisfiesEQUATIONit holds thatEQUATIONand furtherEQUATIONProof of Lemma 7. Let i * := arg max i |[P k+2 ] i |. We expand the expected square norm of P k+2 byE ε k [∥P k+2 ∥ 2 ∞ ] (122) = E ε k [∥P k+1 + β(∇f (W k ) + ε k ) - β τ |∇f (W k ) + ε k | ⊙ P k+1 ∥ 2 ∞ ] = E ε k [∥(1 - β τ |∇f (W k ) + ε k |) ⊙ P k+1 + β(∇f (W k ) + ε k )∥ 2 ∞ ] = E ε k [[(1 - β τ |∇f (W k ) + ε k |) ⊙ P k+1 ] 2 i * ] + β 2 E ε k [[∇f (W k ) + ε k ] 2 i * ] + 2E ε k [(1 - β τ |∇f (W k ) + ε k |) ⊙ P k+1 ⊙ β(∇f (W k ) + ε k )] i * .For the sake of simplicity, below we use [g k ] i := [∇f (W k )] i to denote the i-th coordinate of the gradient. According to Assumption 5, the first term in the RHS of (122) can be bounded byE ε k [[(1 - β τ |∇f (W k ) + ε k |) ⊙ P k+1 ] 2 i * ] (123) = E ε k (1 - β τ |[g k ] i * + [ε k ] i * |) 2 [P k+1 ] 2 i * = 1 - 2β τ E [ε k ]i [|[g k ] i + [ε k ] i |] + β 2 τ 2 E [ε k ]i [([g k ] i + [ε k ] i ) 2 ] [P k+1 ] 2 i * ≤ 1 - 2βcσ τ + β 2 (4L 2 τ 2 + σ 2 ) τ 2 [P k+1 ] 2 i * ≤ 1 - 3βcσ 2τ ∥P k+1 ∥ 2 ∞where the last inequality holds because of the selection of β. To bound the third term in the RHS of (122), we use the unbiased property of 123) and ( 124) into (122) yieldsE [ε k ] i * [[ε k ] i * ] = 0 of Assumption 5 and ∥P k+1 ∥ ∞ ≤ τ in Theorem 1, which lead to 2E ε k [(1 - β τ |∇f (W k ) + ε k |) ⊙ P k+1 ⊙ β(∇f (W k ) + ε k )] i * (124) = 2βE ε k [[P k+1 ⊙ ∇f (W k ) + ε k ] i * ] -2E ε k [ β τ |∇f (W k ) + ε k | ⊙ P k+1 ⊙ β(∇f (W k ) + ε k )] i * = 2β[P k+1 ⊙ ∇f (W k )] i * - 2β 2 τ E ε k [[|∇f (W k ) + ε k | ⊙ P k+1 ⊙ (∇f (W k ) + ε k )] i * ] ≤ 2β[P k+1 ⊙ ∇f (W k )] i * + 2β 2 E ε k [[∇f (W k ) + ε k ] 2 i * ]. Plugging (E ε k [∥P k+2 ∥ 2 ∞ ] (125) ≤ 1 - 3βcσ 2τ ∥P k+1 ∥ 2 ∞ + 3β 2 E ε k [[∇f (W k ) + ε k ] 2 i * ] + 2β[P k+1 ⊙ ∇f (W k )] i * . ≤ 1 - 3βcσ 2τ ∥P k+1 ∥ 2 ∞ + 3β 2 ∥∇f (W k )∥ 2 ∞ + 2β[P k+1 ⊙ ∇f (W k )] i * + 3β 2 σ 2 Dwhere the last inequality comes from Assumption 5 and variance decomposition (63) . Notice that the second term in the RHS of (125) can be upper bounded by Assumption 3 and inequality (63) , and the third term can be bounded by Young's inequalityEQUATIONInequality (126) and the condition β ≤ 2 3cσ lead to the resultE ε k [∥P k+2 ∥ 2 ∞ ] ≤ (1 - βcσ τ )∥P k+1 ∥ 2 ∞ + 10βτ cσ ∥∇f (W k )∥ 2 ∞ + 3β 2 σ 2 D (127) ≤ (1 - βcσ τ )∥P k+1 ∥ 2 ∞ + 40βL 2 τ 3 D cσ + 3β 2 σ 2 D ≤ (1 - βcσ τ )∥P k+1 ∥ 2 ∞ + 41βL 4 τ 3 D cσwhere the last inequality holds because the parameter is chosen as β ≤ L 2 τ 3 D 3cσ 3 . Telescoping over 0 to K -1 and using the fact that ∥∇f (W k )∥ 2 ∞ ≤ ∥∇f (W k )∥ 2 ≤ 4L 2 τ 2 D, we achieve thatE[∥P k ∥ 2 ∞ ] ≤ (1 - βcσ τ ) k ∥P 0 ∥ 2 ∞ + 41βL 2 τ 3 D cσ ≤ 41L 2 τ 4 D c 2 σ 2 .where the last inequality holds due to the fact that P 0 = 0. Now we complete the proof.H.4 Proof of Tiki-Taka Descent Lemma Lemma 8 (Descent Lemma). Under Assumption 1, it holds thatEQUATION+ ασ τ √ D ∥P k+1 - τ √ D σ ∇f (W k )∥ 2 + ασ τ √ D ∥P k+1 ∥ 2 .Proof of Lemma 8. The L-smooth assumption (Assumption 1) implies thatf (W k+1 ) ≤ f (W k ) + ⟨∇f (W k ), W k+1 -W k ⟩ + L 2 ∥W k+1 -W k ∥ 2 (129) = f (W k ) - ατ √ D 2σ ∥∇f (W k )∥ 2 - σ 2ατ √ D - L 2 ∥W k+1 -W k ∥ 2 + σ 2ατ √ D ∥W k+1 -W k + ατ √ D σ ∇f (W k )∥ 2where the equality comes from⟨∇f (W k ), W k+1 -W k ⟩ = σ ατ √ D ατ √ D σ ∇f (W k ), W k+1 -W k (130) = - ατ √ D 2σ ∥∇f (W k )∥ 2 - σ 2ατ √ D ∥W k+1 -W k ∥ 2 + σ 2ατ √ D ∥W k+1 -W k + ατ √ D σ ∇f (W k )∥ 2 .From the update rule of Tiki-Taka and bounded saturation assumption (c.f. Assumption 4), the third term in the RHS of (129) can be bounded byσ 2ατ √ D ∥W k+1 -W k + ατ √ D σ ∇f (W k )∥ 2 (131) = ασ 2τ √ D ∥P k+1 - τ √ D σ ∇f (W k ) + 1 τ |P k+1 | ⊙ W k ∥ 2 ≤ ασ τ √ D ∥P k+1 - τ √ D σ ∇f (W k )∥ 2 + ασ τ 3 √ D ∥|P k+1 | ⊙ W k ∥ 2 ≤ ασ τ √ D ∥P k+1 - τ √ σ ∇f (W k )∥ 2 + ασ τ 3 √ D ∥P k+1 ∥ 2 ∥W k ∥ 2 ∞ ≤ ασ τ √ D ∥P k+1 - τ √ D σ ∇f (W k )∥ 2 + ασ τ √ D ∥P k+1 ∥ 2 .Substituting (131) back into (129) yieldsEQUATION+ ασ τ √ D ∥P k+1 - τ √ D σ ∇f (W k )∥ 2 + ασ τ √ D ∥P k+1 ∥ 2which completes the proof. The proof begins by defining a Lyapunov functionV k := f (W k ) -f * + σ Lτ √ D ∥P k+1 -∇f (W k )∥ 2 + 5σ Lcτ D ∥P k+1 ∥ 2 (133) + 8 Lcτ σ ∥P k+1 ∥ 2 ∞ ∥∇f (W k )∥ 2 .Notice that the last term of V k has the iterationEQUATION) (a) ≤ 1 1 -u E ε k+1 [∥P k+2 ∥ 2 ∞ ∥∇f (W k )∥ 2 ] + 1 u E ε k+1 [∥P k+2 ∥ 2 ∞ ∥∇f (W k+1 ) -∇f (W k )∥ 2 ] (b) ≤ 1 1 -u (1 - βcσ τ )∥P k+1 ∥ 2 ∞ 41βL 2 τ 3 D cσ ∥∇f (W k )∥ 2 + L 2 τ 2 u ∥W k+1 -W k ∥ 2 (c) ≤ (1 - βcσ 2τ )∥P k+1 ∥ 2 ∞ ∥∇f (W k )∥ 2 + 82βL 2 τ 3 D cσ ∥∇f (W k )∥ 2 + L 2 τ 3 βcσ ∥W k+1 -W k ∥ 2where (a) uses ∥x + y∥ 2 ≤ 1 1-u ∥x∥ 2 + 1 u ∥y∥ 2 for any vector x, y ∈ R D and scalar 0 < u < 1; (b) follows Lemma 7, bounded weight (c.f. Theorem 1), and Assumption 1; (c) specifies u = βcσ 2τ and the inequalities 1-βcσ/τ 1-u ≤ 1 -βcσ τ + u and 1 1-u ≤ 2. By inequality (134), Lemma 5, 6 and 8, we haveE ε k+1 [V k+1 ] (135) = f k+1 ) -f * + σ Lτ √ D E ε k+1 [∥P k+2 -∇f (W k+1 )∥ 2 ] + 5σ Lcτ D E ε k+1 [∥P k+2 ∥ 2 ] + 8 Lcτ σ E ε k+1 [∥P k+2 ∥ 2 ∞ ∥∇f (W k+1 )∥ 2 ] ≤ f (W k ) -f * - ατ √ D 2σ ∥∇f (W k )∥ 2 - σ 2ατ √ D - L 2 ∥W k+1 -W k ∥ 2 + ασ τ √ D ∥P k+1 - τ √ D σ ∇f (W k )∥ 2 + ασ τ √ D ∥P k+1 ∥ 2 + σ 2 2Lτ 2 D 1 - βσ 2τ √ D ∥P k+1 - τ √ D σ ∇f (W k )∥ 2 + 4L 2 τ 3 D 3/2 βσ 3 ∥W k+1 -W k ∥ 2 + 2βσ τ √ D ∥P k+1 ∥ 2 + 2β √ D τ σ ∥P k+1 ∥ 2 ∞ ∥∇f (W k )∥ 2 + 2β 2 σ 2 + 2σ 2 Lcτ 2 D 3/2 (1 - βcσ 2τ )∥P k+1 ∥ 2 + 4βτ cσ ∥∇f (W k )∥ 2 + 4L 2 βτ cσ ∥W k+1 -W k ∥ 2 + 3β 2 σ 2 + 2 Lcτ 2 √ D (1 - βcσ 2τ )∥P k+1 ∥ 2 ∞ ∥∇f (W k )∥ 2 + 82βL 2 τ 3 D cσ ∥∇f (W k )∥ 2 + L 2 τ 3 βcσ ∥W k+1 -W k ∥ 2 .Rearranging inequality (135) above, we haveE ε k+1 [V k+1 ] -V k (136) ≤ - ατ √ D 2σ - 8βσ Lc 2 τ D 3/2 - 164βLτ √ D c 2 σ ∥∇f (W k )∥ 2 - σ 2ατ √ D - L 2 - 2Lτ √ D βσ - 8Lβ c 2 σ √ D - 2Lτ βc 2 σ √ D ∥W k+1 -W k ∥ 2 - βσ 3 4Lτ 3 D 3/2 - ασ τ √ D ∥P k+1 - τ √ D σ ∇f (W k )∥ 2 - βσ 3 Lτ 3 D 3/2 - ασ τ √ D ∥P k+1 ∥ 2 + β 2 σ 2 L σ 2 τ 2 D + 16σ 2 cτ 2 D 3/2 ≤ - ατ √ D 2σ 1 - 16βσ 2 αLc 2 τ 2 D 2 - 164βL αc 2 ∥∇f (W k )∥ 2 + β 2 σ 4 Lτ 2 D 1 + 16 c √ Dwhere the second inequality holds because the selection of α and β as follows implies the coefficients of the third to fifth term of RHS are greater than 0EQUATION)By taking β = 8αLτ 2 D σ 2, we boundE ε k+1 [V k+1 ] -V k (138) ≤ - ατ √ D 2σ 1 - 128 c 2 D - 1312L 2 τ 2 D c 2 σ 2 ∥∇f (W k )∥ 2 + 8α 2 Lτ 2 D 1 + 16 c √ D ≤ - ατ √ D 2σ 1 - 128 c 2 D - 32P 2 max τ 2 ∥∇f (W k )∥ 2 + 8α 2 Lτ 2 D 1 + 16 c √ D .Taking expectation, averaging (138) over k from 0 to K -1, and choosing the parameter α asEQUATIONdeduce thatE 1 K K-1 k=0 ∥∇f (W k )∥ 2 (140) ≤ 2σ V 0 -E[V k+1 ] ατ √ DK + αLτ √ D 1 + 16 c √ D 1 1 -128/(c 2 D) -32P 2 max /τ 2 ≤ 2σ V 0 ατ √ DK + αLτ √ D 1 + 16 c √ D 1 1 -128/(c 2 D) -32P 2 max /τ 2 = O   (f (W 0 ) -f * )σ 2 L K 1 + 16/(c √ D) 1 -128/(c 2 D) -32P 2 max /τ 2   . = O (f (W 0 ) -f * )σ 2 L K 1 1 -33P 2max /τ 2 where the last inequality holds when D is sufficiently large. The proof is completed.This section provides details about the experiments in Section 2.1 and 5. The analog training algorithms, including Analog SGD and Tiki-Taka, are provided by the open-source simulation toolkit AIHWKIT [27] , which has Apache-2.0 license; see github.com/IBM/aihwkit. We use Softbound device provided by AIHWKIT to simulate the asymmetric linear device (ALD), by setting its upper and lower bound as τ . The digital algorithm, including SGD, and dataset used in this paper, including MNIST and CIFAR10, are provided by PYTORCH, which has BSD license; see https://github.com/pytorch/pytorch.Hardware. We conduct our experiments on an NVIDIA RTX 3090 GPU, which has 24GB memory and maximum power 350W. The simulations take from 30 minutes to one hour, depending on the size of the model and the dataset.Statistical Significance. The simulation reported in Figure 5 is repeated three times. The randomness originates from the data shuffling, random initialization, and random noise in the analog device simulator. The mean and standard deviation are calculated using statistics library. This paper adopts w to represent the element of the weight matrix W k without specifying its index. This makes the formulations more concise and uses the fact that analog devices update all coordinates in parallel. The notation U (W k , ∆W ) on matrices W k and ∆W denote the coordinate-wise operation on W k and ∆W , i.e.[U (W k , ∆W )]i := U ([W k ]i, [∆w]i), ∀i ∈ I.Notice that the ℓ2-norm ∥ • ∥ and ℓ∞-norm ∥ • ∥∞ reduce to absolute value, when w is a scalar. Similarly, inner product ⟨•, •⟩ reduces to multiplication. We adopt the same notations for both vector and scalar weights to make the notations consistent and easy to read.These requirements are necessitated by Lemma 2 and can be relaxed to |w * | ≤ c * τ for any constant c * < 1.In that situation, Lemma 2 remains valid, although Wmax differs. 


Decision: The authors analyze Tiki-Taka, an algorithm designed for analog in-memory optimization and theoretically confirm its superior performance compared to vanilla Analog SGD. The concerns raised by the reviewers have been largely addressed through authors' rebuttal and all reviewers think the paper should be accepted.

Reviews: review: paper_summary: paper_summary: This paper presents a theoretical framework for gradient-based training on analog devices. This work first identifies the non-convergence problem of Analog SGD, which stems from asymptotic errors due to asymmetric updates and gradient noise and then presents a convergence analysis of Tiki-Taka, demonstrating its ability to accurately converge to a critical point, thereby eliminating the asymptotic error.
strength_weakness: strength_weakness: -- The experimental results were obtained on rather small datasets. It'd be great to include the results on ImageNet.

-- The experiments were limited to one type of networks (i.e., resnet) on CIFAR dataset. How does it generalize on other networks such as Transformers, or mobile CNNs?
questions: questions: See weaknesses
limitations: limitations: NA
paper_summary: paper_summary: The paper introduces the training on the analog in-memory accelerators with SGD. The traditional analog SGD algorithm suffers from inexact convergence due to asymmetric updates/gradient noise. The paper shows theoretical foundations for gradient-based training on analog devices. The authors propose Tiki-Taka, which reflects the device model to the Analog SGD. It shows better empirical performance, e.g., it can eliminate asymptotic errors and converge to critical points. They show the theoretical and empirical efficacy of the proposed approaches in overcoming training limitations on the analog devices.
strength_weakness: strength_weakness: - It'd be great if authors present how computations (ops) can be realized on the analog devices.
- Needs comparison to other analog SGD methods, like [16] or [22].
questions: questions: - Floating-point operations are not trivial on analog devices. How can they be implemented? Additionally, for SGD training, how are analog devices more efficient compared to digital devices?
- How does it scale to large batch sizes?
limitations: limitations: N/A
paper_summary: paper_summary: This is a theoretical paper about training analog systems based on resistive memories. The paper tackles specifically the problem of weight update asymmetry in such resistive devices. The paper develops a model for the weight dynamics under “Analog SGD”, taking into account weight update asymmetry, and it shows that Analog SGD does not converge, due to an asymptotic error. The paper then shows that the Tiki-Taka algorithm, developed in prior works for such analog devices, has better convergence properties. Tiki-Taka eliminates the asymptotic error and converges to a critical point. Simulations corroborate the theory.
strength_weakness: strength_weakness: The theoretical analysis rests on a set of models and assumptions. Thus, the applicability of the conclusions rests on the validity of all these models/assumptions. In practice, I expect none of these assumptions to perfectly capture the real behavior of the system. For example, Figure 2 hints that the analog SGD dynamics (Eq3) better fits real behaviors than the digital SGD dynamics (Eq2), but the matching still seems to be far from perfect.
This, of course, is not a problem, however, what is more problematic is that there does not seem to be any discussion in the paper about which assumptions/models are accurate and widely accepted, and which ones less accurately capture empirical data or are still debated by the community.

The paper implicitly assumes that backpropagation (BP) is used for computing the weight gradients. However, a large (and growing) group of researchers in neuromorphic computing (or ”physical neural networks”) think that BP is not the best fit for analog devices, and they are exploring alternative training methods. See e.g. Ref [1] below for a very recent review of such algorithms. In particular, Ref [1] discusses several algorithms that extract or estimate the weight gradients in broad classes of analog systems. My understanding is that it wouldn’t take too much time and effort to extend the present study to include these other gradient-descent-based algorithms. In my view, including these other methods would add a lot of value to the paper, by broadening the potential impact of the work.

Reference:
[1] Momeni, Ali, et al. "Training of Physical Neural Networks." arXiv preprint arXiv:2406.03372 (2024).


Minor remark. One claim in the introduction is not properly referenced. Specifically, where do the figures of $2.4 million and $4.6 million for training LLaMA and GPT-3 come from? The references provided are the LLaMA and GPT-3 papers, which do not provide these figures, if I am not mistaken.
questions: questions: Is the model of Eq6 for weight update asymmetry a widely accepted model? Does it match empirical data? Similarly, are the forms of q+ and q- for ALD, written at lines 174-175, widely accepted and/or corroborated by data?

Does the AIHWKit very faithfully simulate real analog devices? What are the strengths and limitations of this tool?

The paper is concerned with analog resistive memories where the weights are implemented as conductances (which are positive, I suppose), but on Figure 6 (Appendix L), I see that the weight values can be negative. Lemma 1 also indicates that w_k can be either positive or negative. Could you clarify this point?

I understand that the RHS of Eq.5 can be arbitrarily small by choosing alpha = sqrt(1/K) and letting K -> infinity. But, unless I am mistaken, this does not imply that the sequence grad f(W_k) converges to zero. Can we conclude from Eq5 that W_k converges? If not, why is Eq.5 important for studying the convergence of (digital) SGD?

I am not sure to understand why Theorem 2 is important. To my understanding, the important result is Theorem 3, which shows that analog SGD does not converge, contrary to digital SGD (Eq.5). Could you clarify this point?

Is the theory of analog SGD and Tiki-Taka provided in this paper limited to backpropagation? Or could it be used with other methods that compute weight gradients, e.g. Equilibrium Propagation and/or other algorithms presented in Ref [1] above? Similarly, could the AIHWKit be employed with these other training algorithms?
limitations: limitations: The applicability of the theoretical results depends on the validity of the underlying assumptions – see my comment above. To be clear, I am supportive of the methodology followed by the authors. However, given that the overall model will be at most as accurate as the least accurate assumption, it would be extremely useful to know which assumptions/models we can trust 100% (i.e. are well accepted), and which ones are still debated / less supported by experiments. This would help future works identify what are the main “bottlenecks” of the study, to investigate those in depth and perhaps further improve the model. For instance, can we really trust Eq3 as “the right model” of weight dynamics? Or should one merely think of it as a better model than Eq. 2?

Comments: comment: Thank you for your detailed replies to my questions!
Thanks for the detailed response. It has clarified some of my confusion and improved my understanding on the paper. For W2, to clarify my comment, it'd be great if you can elaborate differences to existing algorithms.