Towards Exact Gradient-based Training on Analog In-memory Computing
Authors: Zhaoxian Wu
Tayfun Gokmen
Malte J. Rasch
Tianyi Chen
Venue: NeurIPS 2024 poster (2024)
Keywords: Analog AI; in-memory computing; stochastic gradient descent; stochastic optimization
Primary area: optimization
TL;DR: Our paper establishes a theoretical foundation for model training on analog devices and shows a heuristic algorithm, Tiki-Taka, can converge to a critical point exactly.

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.

Towards Exact Gradient-based Training on Analog In-memory Computing
Zhaoxian Wu Rensselaer Polytechnic Institute
Tayfun Gokmen
IBM J. Watson Research Center Yorktown Heights, NY 10598
Troy, NY 12180 wuz16@rpi.c edd
tgokmendus imm. com
Malte J. Rasch
Tianyi Chen
IBM T. J. Watson Research Center
Rensselaer Polytechnic Institute Troy, NY 12180 chentiany1190gmiill com com
Yorktown Heights, NY 10598
malte. rasch@googlemail....... com
Abstract
Given the high economic and environmental costs of using large vision or language models, analog in-memory accelerators present promising solution for energy- efficient AI. While inference on analog accelerators has been studied recently, the training perspective 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-basee -based training on analog devices. We begin by characterizing the non-convergent issue SGD, which caused by the asymmetric updates on the analog devices. We then provide lower bound of the asymptotic error to show that there is a fundamental performance limit of SGD-based analog training rather than artifact of our analysis. To address this issue, we study a heuristic analog algorithm called Tiki-Take 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.
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, took $2.4 million to train LLaMA ( and $4.6 million to train GPT-3 [2]. To overcome this issue, a promising technique is application-speciff hardware accelerators for neural networks, such as TPU B NPU 44, 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 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 multiplications (MVMs), which contribute to significant portion of digital computation in model training and inference, e.g., about 80% in VGG16 model [10]. Very recently, the first analog Al chip has been fabricated in IBM's Albany Complex [T and has achieved an accuracy of 92.81 21 % on the
9 to accelerate the ubiquitous matrix-vector
The work was supported by National Science Foundation (NSF) project 2134168, NSF CAREER project 2047177, and the IBM-Renssller Future of Computing Research Collaboration.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

CIFARIO dataset while enjoying 280x and x00x efficiency and throughput value compared with the most-recent GPUs, demonstrating the transformative power of analog computing for Al [[2].
In AIMC accelerators, the trainable matrix weights are represented by the conductance of the resistive elements in analog crossbar array [13 [4]. 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 '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 in-memory pulse update has been developed [T]] which changes the weights by sending consecutive pulses to implement gradient- 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 susceptible 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 overcome this accuracy drop [7 19 20), there is still lack of theoretical studies on the performance and performance limits of SGD on AIMC accelerators.
1.1
Main results
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 perfor- mance limit of using hardware- agnostic digital SGD algorithm for analog training and establish the con- vergence rate of gradient-based ana- log training. Consider the following standard model training problem
10
10-1
d-2e-01
10-5
c=1e-01
a=5e-02
10
0-3e-02
Digital SGD
10-9
Analog SGD
W = arg min S(W) WER
(1)
0
500
1000
1500
2000
2500
Iteration k
where [(:): DRD + R the objective Figure 1: Digital/Analog SGD under different learning rates.
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 is SGD, which iteratively updates weight W via the following recursion
Digital SGD
W = We a (V/(WWWW + +
(2)
where l is the iteration index, a is a positive learning rate and & is the gradient noise with zero mean 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 (2].
In Figure L
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 and thus ask 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 devices
Analog SGD
W WA (())(W))) + sx) ((W,)) + ax O We
where |- and represent the coordinate-we absolute value and multiplication, respectively and is a device-specifie 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 33) comes from the asymmetric update of analog devices. Following this dynamic, we prove that the Analog SGD only converges inexactly to 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:

---

Algorithm
Rate
Asymptotic Error
Digital SGD
25
82
Analog SGD [Theorem]
6²
( Sk)
max
Tiki-Taka [TTeorrm 4
K 1-33P maxx
Lower bound 24
Table 1: Comparison between the convergence of digital and analog training algorithms: K repre- sents the number of iterations, o² is the variance of stochastic gradients. W and P /72 measure the saturation degree, and SK measures the non-ideality of analog devices (c.f. Theorem Asymptotic error refers to the error that does not vanish with K.
Q2) How to mitigate the asymptotic error induced by the asymmetric analog update?
To answer this, we revisit heuristic algorithm Tiki-Take that has been used among experimentalists 22 and establish the first exact convergence result of Tiki-
class of AIMC accelerators.
Our contributions. This paper makes the following contributions (see the comparison in Table
CI) We demonstrate that Analog SGD does not follow the dynamic of SGD in (2. Leveraging the underlying physics, we propose discrete-time dynamic of the gradient-based algorithm on analog devices, and show that it better characterizes the trajectory of Analog SGD.
C2) Based on the proposed dynamic, we establish the convergence of Analog SCD and argue that the performance limit of Analog SGD is combined effect of data noise and device asymmetry. We prove the tightness of our result by showing a matching lower bound.
C3) To improve the performance limit of analog training, we study a heuristic algorithm Tiki-Taka that serves as an alternative to Analog SGD, We show that Tiki-Taka exactly converges to the critical point by reducing the effect of asymmetric bias and noise.
C4) To verify the validity of our discrete- time dynamic for analog training and the tightness of our analysis, we provide simulations on both synthetic and real datasets to show that the asymptotic error of Analog SGD does exist, and Tikii-iTaaaa outperforms Analog SGD.
1.2
Prior art
Since the seminal work on pulse update-based Analog SGD [15], series of gradient- 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 -aki-aaka (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 [77 18], which provides a more accurate but less efficient update. In addition, the successful training by TT-v1 or TT-v2 relies on the shift-ni 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-TTVV (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.
3

---

2 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.
2.1 Revisit SGD theory and its failure in modeling analog training
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 J(W) is L-smooth, i.e., for any W, W' E IR,, it holds [VS(W)- VS(W")II S 1.IW-W' -W
-
(4)
Assumption 2 (Lower bounded). f(W) is lower bounded by f*, i.e. Assumption 3 (Noise mean and variance). The noise &K is independently identically distributed (i.idd) for &- = 0, o,....., K, and has zero mean and bounded variance, i.e. Elc] 0, E||| s o².
ER.
.....,,,,
In non-convex optimization, instead finding a global minimum, it is usually more common find a critical point, which refers to W* satisfying Vf(W)) = O. Under Assumptions
[ if W₁ follows
the digital SGD dynamic (2). the convergence of SGD is well-understood 23 Theorem 4.8]
IVS(W)I ( + L
(5)
K
aK
This result implies that the impact of noise can be controlled by the learning rate a, i.e., after K 2 (21/a²)) iterations, the error is O(a). By forcing a + 0, the error will reduce to zero
Analog SGD violates the SGD theory. The dynamic digital SGD exactly follows 2 up to the machine's 's precision. To verify whether analog training adheres to the same dynamic, conduct a numerical simulation on least-squares problem. We compare Anal og SGD implemented by an analog devices simulator, IBM Analog Hardware Acceleration Kit (AIHWKITT 277, and digital SGD implemented by PYTORCH. The same level of noise obeying Gaussian noise is injected into each algorithm. Beginning from large learning rate 0.2, we reduce the learning rate by half each time and observe the convergences. As Figure || jillustrates, digital SGD behaves as what (5) predicts: it converges with a smaller erгor when small learning rate is chosen. On the contrary, Analog SCD 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[]
2.2 Training dynamic analog devices
Compared to digital devices, the key feature of analog devices analog signal. The input and output of analog arrays are analog signals, which are prone 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 electrical pulse to the resistive element, and the conductance will change by small value, which referred to as pulse update [15]. To apply an update Aw to the weight w, using the pulse update needs to send series of pulses to the resistive element, the number of which proportional to the update magnitude [Aw]. 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? presents the weight change 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 asymmetric update. This means that if we apply

---

weight (conductance)
weight to (conductance)
Aur 4+ (ve)
Av 9 (m)
101
q- (wr)
007
Aur q-(w)
10
number pulses
number of pulses
+AB Awe
+
Ave
Figure 2: The weight's change with the number of pulses. Positive and negative pulses are sent continuously on the left and right half, respectively. Beginning from w, the weight after applying update Aw it is w- or if Aw 2 0 or Aw < O, respectively. The response factors q (w) and (w) are approximately the slope of the curve at w. (Left) Ideal device. q+ (w) = =q-(w)
1. Every point is symmetrie points. (Right) Asymmetric Linear Device (ALD). q+ (w)
(w - / /TT q- (w) = 1 + (w w//TT. The symmetric point W, satisfies q- (w²) = q 1-(w)).
the change Aw 0 and Aw < 0 on the same weight w, the amount of weight change will be different. Considering the weight Wy time k and the expected update AW R we express the
asymmetric update as WK+1 = UW,, AW) with the update function U : R x R + R defined by""
w Ar q+ (w), Aw 0,
U Uww, Aw)
(6)
w + Aw q (w), Aw < O,
where 9+ (-) 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) (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)
2/2 (g) - 4+ (w)) and G(w) == (q-(w)
(+(w), the update in (6) can be expressed in more compact form U Uww, Aw) w + Aw F(w)
|Aw|- G(w). For simplicity, assume that all the coordinates of W use the same update rule, and the analog update can be written as
W4+1 = W4 + AW @ F(W)) AW| G(W))
where |. and @ represent the coordinate- wise absolute value and multiplication, respectively. Note that in (7), the idcal weight update AW is algorithm-specife AW is the gradient in Analog SGD
while it is an auxiliary weight (c.f. in Section 4 in Tiki-Taka.
attempting to scale the Aw by q+ (w) or q 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].
Remark (Physical constraint).
Symmetric point. The asymmetric update makes up and down responses diffferent almost everywhere, Le. 9+ (w) * q-ww) for almost any w. a point w satisfies q+ (w²) = q- (w²) and G(w) = 0, w is called symmetric point. With loss of generality, the response factor is defined so that F(w2) = 1. Therefore, near the symmetric point, the update Aw can be accurately applied on w, i.., U(w", Aw) w Aw. If all the coordinates of matrix W₁ hover around the symmetrie 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 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 [9]. ALD has a positive parameter 7 which reflects the degree of asymmetry and its response factors are written as linear functions 4+ (w) 1- (w w²)/T, (w)) (w)
1 + (w- wº) w/T Consequently, ALD has F(w) = 1, G(w) = (w w and symmetric point w see Figure right. Even though ALD is simplified device model, it is representative enough to
'This paper adopts w to represent element the weight matrix We 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 U'W2,, AW) on matrices W2 and AW denote the coordinate-wing operation on Wi and AW, ie. (W,, AW)]: U ([Waj, [Aw]i), Vi I.
5

---

reveal the key properties and difficulties of gradient- based training algorithms on analog devices. If not otherwise specified, 2 is always 0 for simplicity. In summary, the update of ALD is expressed as
Wk++1 = we + Aw _
| wE or WK+1 = Wa + AW - - AA +
Wa
where the first equation is the update of one coordinate while the second one stacks all the elements together. Replacing AW with noisy gradient a (VV((W)) + ex) reaches the dynamic (3)
2.3 Saturation, fast reset, and bounded weight
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 (Saturation and fast reset). For ALD with a general w², the following stutements are valid (Saturation)
If sign( Aw) = sign (x)., holds that |wk+1 Wk| |1 |w>k
w 1/// |Aw]
(Fast Reset) If sign( Aw) = - -iig(( wx),, it holds that |wx+11 - wyl = |1 + |w - 1/ -AAw).
The proof is deferred to Section F. Remarkably, Lemma 1 holld for any algorithm with any update Aw, and it reveals the impact of the asymmetric update. In principle, Lemma] [] can be written as
|uK+11 - wp| = |1 | Uk - w0) / AAw], where the symmetric point w = is omitted.
When wi is not at the symmetric point w = O, the update is scaled by a factor. When we lies around the symmetric point. |w*+1 wik Awl| where all updates are applied the weight and hence the analog devices closely mimic the performance of digital devices. When Wy moves away from wo, i.c. sign( (Aw) sign( w&)), the update becomes none. When wy gets closer to IT, nearly no update can be applied. This phenomenon is called saturation; see also [22). On the contrary, w) 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 (Bounded weight). Denote ||W as the fo norm W.
W. Given || S 7 and for any sequence fAW& k E N). which satisfies ll I it holds that || [ I T, Ak E N.
The proof is deferred to Section E.2
Theorem 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] Theorem dooes 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 the update is slow near the boundary of the active region. The weight is expected to stay within smaller region to avoid saturation, which necessitates the following assumption.
Assumption 4 (Bounded saturation). There exists a positive constant Wmax < T such that the weight Wy is bounded in lo norm, i.e. || WWass The ratio W maxx/ / is the saturation degree.
4 requires that We is bounded inside a small region, which is a mild assumption in real training. For example, one can apply a clipping operation on Wy to ensure the assumption. In Appendix E.2 we show that Assumption 4 provably holds under the strongly convex assumption. is worth pointing out that Assumption 4 iippicitlly assumes there are critical points in the box {W || < T). Otherwise, the gradient will push the weight to the bound of the box and it becomes possible that W W < ||W S..
Assumption
Intuitively, without the asymmetric bias, the weight is stable near the critical point. In contrast, with asymmetric bias, the noisy gradient that pushes wa toward its symmetric point is amplified by fast reset, while the one that drags wa away from 0 is suppressed by saturation (c.f. Lemma [] Consequently, the weight wn attracted by O, 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 74
if the learning rate is set as
((Wo)-f" and K is sufficiently large such that S t. it holds that LL
1 (IIT (V (F(W)) f
1
~O
K
W
max
W
W W
where Sg denotes the amplification factor given by Sk: == R
k=
The proof of Theorem 2 is deferred to Appendix G. Theorem suggests that the average squared gradient norm is upper bounded by the sum of two terms: the first term vanishes at rate of o(vo2//B which also appears in the SGD's 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 supx-
Σ K
Vf(WW))) S o² Soc exist.
k
Impact of saturation/asymmettii update. The saturation degree Wmax/² affects both con- vergence rate and asymptotic error. The ratio is small if W2 remains close to the symmetric point or 7 is sufficiently large. The exact expression of Sx depends on the specific noise dis- tribution, and thus is difficult to reach. However, Sx reflects the saturation degree near the critical point W when Wt converges to a neighborhood of W* Intuitively, W W* implies
Sк || / /r2 W & /---2 Therefore, if the critical point is near the symmetric point, the asymptotic error SK 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 W and, meanwhile, 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 SCD). There is an instance which satisfies Assump- tion such that Analog SCD generates a sequence (Wa =0 1,.,, K] which satisfies
K-1
a= e (t)) a (0OS5x +
1 1. VK
= 02Sk + ((a)
(10)
K
The proof of Theorem 3 deferred to Appendix G.2 Theorem limplis that Sx 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-Take
Building upon 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, Pk. besides the main one, WK- At the initialization phase, Ps. is initialized as O. At iteration k the stochastic gradient is computed using the main device W₂ and is first applied to Ps. Since P& is also an analog device, the change of P& still follows the dynamic 8 by replacing W₃ with Ps and AW with V f(W,)
+ Ek, that is
3 Pa-1 = Pa + ((V)(WA) + + IVF(W)) EA o P
(TT-P)
where 9 is a learning rate. After that, the value P is read and transferred to the main array Wy via
at Pkt1l O Wt.
Wh+1 = W - aPo+1
(TT-W)
7
7

---

Tiki-Take performs recursion TT-P and ( alternatively until it converges. Empirically, Tiki Taki outperforms Analog SGD terms of the final accuracy. However, Tiki-Taka 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 eliminate asymptotic errors.
Stability of Tiki-Taka. As explained in Section 3 the gradient noise contributes to the asymp- totic 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 Wa already a critical point and P& is initialized as 0, i.c. f(()) = P& = O. After one iteration, the weight W4 drifts because of the noise. For Analog og SGD, the expected drift is
[1 WR- -oE]ee
a B[[ex @ W a B[[ex] O We a.
(11)
In contrast, Tiki Taka updates the auxiliary array by Pa+1 PR + 3e. - Pk = Ben: which implies [8| [[px+1]= = and [8[ P+ = [R[(
fla
After the transfer, expected drift
03 - Bllexll o W& x aB.
E[W [+ W -aEE - W₁ = T
(12)
Comparing [12) with (1] it can be observed that Fiki-Take improves the expected drift from O(a) to (a,3). With sufficiently small B, Tiki-Taka controls the drift and makes the weight stay the critical point. For a more generic scenarios, Ps ل However, it is worth noting that
8 lewl Px] (1 2 ( Pk
E P = B[P& + B&g
(13)
which makes Ps back to 0 when [|[Ex|] 0. Therefore, by controlling the drift, the Tiki-Taka algorithm manages to stay near a critical point.
Note that from (1 the stability of Pk relies on the presence of noise, i.e. R[[ex|] * In addition to a lower bound for the noise also assumed.
the upper bound on the noise in Assumption 3
Assumption 5 (Coordinate-wisz i.i.d. and non-zero noise). For any k 2 0 and i, E I, [Ex]; and [ex]; are i..d. from a distribution De which ensures [(Ex)r<,, [5x] = 0. Furthermore, there exists > 0 and > 0 such that Ej S o²/D and E(ex]o_D, [lg + [sw]:ll 2 ca for any g E R.
Intuitively, Assumption 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 We discuss this assumption in more detail in Appendix D.2
Theorem 4 (Convergence of Teki- -akaa, Suppose Assumption 7 hold and the learning rate is set as O(1/vo2K), B SaL. It holds for Tiki- -aka that the expected infinity norm Ps. is upper Furthermore, if a² and are sufficiently large so c0
bounded by |||| P 1 11&c] S P = 4112,'D, that p2
max /T2 it is valid that
K- K
(vrun))
- I K
E ((WW)
(14)
33P2 max! /2
The proof of Theorem 4 is deferred to Appendix H Theorem 4 first provides the upper bound for the maximum magnitude of Px that decreases as the variance σ² increases or 7 decreases. This
observation is consistent with (3)), which implies the Pa tends to zero when [ A 0. Ensuring stability during the training requires the noise be sufficiently large to render the saturation degree of
Pmax/7 7 sufficiently small. In addition, the condition 33 32 max!
requires the D to be sufficiently
large, which is easy to meet when training large models.
Convergence rate. 4 that Tiki-Take converges at the rate Oly o²L
P2
Therefore, we reach the conclusion that lim simssp--iin J. K-1 V 11 = 0 and
K k=
Eiki-Take eliminates the asymptotic error of Analog SCD. Furthermore, Tiki-Take improves the factor 1/(1 W2 (72) in Analog SGD's convergence (c.f. (9) to 1/(1 1/11-33P2 Paxx /72) wherein W2 max//7 2 and p2 maxs maxx are the saturation degrees in fact. Notice that Pa tends to 0 as indicated
maxx/²)
8

---

1.0
t=1.5
T= 2.0
2.5
10:2
10-3
rWW))
10
0
2000 Computation (k)
1000
2000 Com computation Gradient Computation (k)
1000
2000
1000
1000 Computation (k)
2000
Digital 5GD Dynamic
- Analog SGD Dynamic
Analog SGD Simulation
Figure 3: The convergence of digital SGD dynamic 2 analog dynamic Analog SCD implemented by AIHWKIT (real behavior) under different T.
(proposed) and
by 13)
while W max does not because 0 is usually not critical point. Therefore, usually has max/ ? < W Wmax/T² 2 in practice, implying faster convergence. The convergence matches the lower bound O ((vo2L/ K)) for general stochastic non-convex smooth optimization [24 up constant.
pa
5 Numerical Simulations
In this section, we verify the main theoretical results by simulations on both synthetic datasets and real datasets. We use the PYTORCH generate the curves for SGD in the simulation and open source toolkit AIHW KIT 27 to simulate the behaviors of Analog SGD; see gieggittb...... com/ cwm/IBM/ htt//IMMaahwwiii aihwkit Each simulation is repeated three times, and the mean and standard deviation reported. More details can be referred to in Appendix The code our simulation implementation available at github. com/ Zhaoxiam Wu/ Ww/anallg analog-aaaaea toroggggtriinnggggg.
10-1
10"
10
tm2
102
20-1-
6² C.001
10
of m.001
10: 2
10^2
10a2
550
6 =1.
200
400
50
100
150
200
20
40
Number of Gradieent Computation (3)
Number Deacient Computation (8)
Number of Grbolent Computation
Figure 4: (Left) The convergence of Analog SGD under different r. Reducing leads to a decrease in asymptotic error. When is sufficiently large, Analog SGD tends have similar performance digital SGD. (Middle) The convergence Analog SCD on noise devices under different o². (Right) Analog SGDs that are initialized to different places converge the same error.
5.1 Verification of the analog training dynamic
To verify that the proposed dynamic (3) characterizes analog training better than SGD dynamic 2 we conduct numerical simulation on a least-squares task. and compare Analog SGD implemented by AIHWKIT, the digital and analog dynamics given by ( and ( respectively; see Figure 3 The results show that the proposed dynamic provides an accurate approximation of Analog SCD.
5.2 Ablation study on the asymptotic training error
We verify some critical claims about the asymptotic error of Analog SGD on a least-squares task.
Impact of To verify Theorem that the error diminishes with larger т, assign range of value T and plot the convergence of Analog SCD. The result is reported on the Left Figure 4 When is small, the asymmetric bias introduces notable gap between Analog and Digital SGD. As increases, the gap diminishes. The result demonstrates the asymptotic error decreases as T increases.
Impact of o² To verify the asymptotic error is proportional to o², we inject noise with different variances. The result is reported in the middle of Figure The result illustrates that the asymptotic error increases the noise increases.

---

100
80
Accuracy
60
T= 0.7
t= 0.6
60
Text
97.5
T=000 0.0
99.00
T= 0.8
20
97.0
Analog
Tik-Taka
98.75
78
TIk-Taka
Digital SGD
Digtal
20
20
40
60
80
20
40
60
80
Epoch
0.70
0.78
0.80
0.60
= 0.70
0.80
SGD
98.15 15 + 0.04
99.16
0.08
SGD
11.35
0.00
97.71
0.63
97.78
0.36
88.99
92.15
0.48
93.45
1
TT
97.64 10177
97.62 1 0.05
97.50
0.11
98.84
1 0.07
98.87
0.04
98.86
= 0.07
Figure 5: The test accuracy curves and tables for the model training. "D SGD", "A SGD", and "TT" represent Digital SGD, Analog SGD and Tiki -aki, respectively; (Leftt) FCN. (Right) CNN.
Impact of the initialization. To demonstrate the asymptotic error is not artificial, we perform Analog SCD from different initializations. The result is reported the right of Figure 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.
5.3 Analog training performance on real dataset
We also train vision models to perform image classification tasks real datasets.
MNIST FCN/CNN. We train Fully- connected network (FCN) and convolution neural network (CNN) models on MNIST dataset and
Resnet18
Resnet34
Resnet50
Digital SGD
93.03
93.44
95.92
the performance of Analog SCD and Tiki-Taka under vari- The results reported in Figure 5) By reducing the variance, Tiki-Taka outperforms Analog SGD and reaches com- parable accuracy with digital SGD. On both of the architectures, the accuracy Tiki-TTak 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%.
Analog SGD
93.58
93.58
95.51
Tiki - Taka
93.74
95.15
95.54
Table The test accuracy of Resnet training on CI- FAR 10 dataset after 100 epochs.
drops by < 1%. the FCN training, Analog SGD
CIFAR10 Resnet. We also train three Resnet models with different sizes on CIFAR1O dataset. The last layer is replaced by fully-connected layer mapped onto analog device with parameter
t == 0.8. The results are shown in Table 2 In this task, inalog SGD does not suffer from a significant accuracy drop but is still worth that Tiki-Taka, 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.
6 Conclusions and Limitations
This paper points out that Analog SGD does follow the dynamic of digital SGD and hence, we propose 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 eтror. Numerical simulations demonstrate the existence of Analog SGD's asymptotic error and the efficacy of Tiki One limitation of this work is that the current analysis is device-specific that applies to asymmetric linear device. While it 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.
10

---

References
[1] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13977 2023.
[2] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
[3] Norm Jouppi, George Kurian, Sheng Li, Peter Ma, Rahul Nagarajan, Lifeng Nai, Nishant Patil, Suvinay Subramanian, Andy Swing, Brian Towles, et al. TPU v4: An optically reconfig- urable supercomputer for machine learning with hardware support for embeddings. In Annual International Symposium on Computer Architecture, pages 1-14, 2023.
[4] Hadi Esmaeilzadeh, Adrian Sampson, Luis Ceze, and Doug Burger. Neural acceleration for general-purpose approximate programs. In 45th annual IEEE/ACM international symposium on microarchitecture, pages 449-460. IEEE, 2012.
[5] Dharmendra S Modha, Filipp Akopyan, Alexander Andreopoulos, Rathinakumar Appuswamy, John V Arthur, Andrew S Cassidy, Pallab Datta, Michael V DeBole, Steven K Esser, Car- los Ortega Otero, et al. Neural inference at the frontier of energy, space, and time. Science, 382(6668) 335, 2023.
[6] An Chen. comprehensive crossbar array model with solutions for line resistance and nonlinear device characteristics. IEEE Transactions Electron Devices, 60(4):1318-1324 2013.
[7] Abu Sebastian, Manuel Le Gallo, Riduan Khaddam-Aljameh, and Evangelos Eleftheriou. Memory devices and applications for in-memory computing. Nature Nanotechnology, 15:529- 544, 2020.
[8] Wilfried Haensch, Tayfun Gokmen, and Ruchir Puri. The next generation of deep learning hardware: Analog computing. Proceedings of the IEEE, 107(1):08-112, 2019.
[9] Vivienne Sze, Yu-Hsin Chen, Tien-Ju Yang, and Joel S Emer. Efficient processing of deep neural networks: A tutorial and survey. Proceedings of the IEEE, 105(12):229--333) 2017.
[10] Zihan Zhang, Jianfei Jiang, Yongxin Zhu, Qin Wang, Zhigang Mao, and Naifeng Jing. universal RRAM-based DNN accelerator with programmable crossbars beyond MVM operator. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 41(7):2094 2106, 2021.
[11] Abu Sebastian, Manuel Le Gallo, and Vijay Narayanan. analog AI chip for deep learning inference. https://researdhh i com/blog/ amalog-ai-chip- inferencee 2023.
IBM research's latest
[12] Stefano Ambrogio, Pritish Narayanan, Hsinyu Tsai, Robert M Shelby, Irem Boybat, Carmelo Nolfo, Severin Sidler, Massimo Giordano, Martina Bodini, Nathan CP Farinha, al. Equivalent- accuracy accelerated neural-network training using analogue memory. Nature, 558(7708):60, 2018.
[13] Geoffrey W Burr, Robert M Shelby, Abu Sebastian, Sangbum Kim, Seyoung Kim, Severin Sidler, Kumar Virwani, Masatoshi Ishii, Pritish Narayanan, Alessandro Fumarola, et al. Neuromorphic computing using non-volatile memory. Advances in Physics: X, 2(1):89-124, 2017.
[14] J Joshua Yang, Dmitri B Strukov, and Duncan R Stewart. Memristive devices for computing. Nature nanotechnology. 8(1):13, 2013.
[15] Tayfun Gokmen and Yurii Vlasov. Acceleration of deep neural network training with resistive cross-point devices: Design considerations. Frontiers neuroscience, 10:333, 2016.
[16] Shubham Jain al. Neural network accelerator design with resistive crossbars: Opportunities and challenges. IBM Jourmal of Research and Development, 60-,)

---

[17] S. R. Nandakumar, Manuel Le Gallo, Irem Boybat, Bipin Rajendran, Abu Sebastian, and Evangelos Eleftheriou. Mixed-prectis preccison architecture based on computational memory for training deep neural networks. In IEFF International Symposium Circuits and Systems, pages 1-,,2018.
[18] S. R. Nandakumar, Manuel Le Gallo, Christophe Piveteau, Vinay Joshi, Giovanni Mariani, Irem Boybat, Geethan Karunaratne, Riduan Khaddam- Khaddlm-Alljmmhh, Urs Egger, Anastasios Petropoulos, Theodore Antonakopoulos, Bipin Rajendran, Abu Sebastian, and Evangelos Eleftheriou. Mixed- precision deep learning based on computational memory. Frontiers in Neuroscience, 14, 2020.
[19] Malte J Rasch, Fabio Carta, Omebayode Fagbohungbe, and Tayfun Gokmen. Fast offset corrected in- in-memory training. arXiv preprint arXiv:2303. 04721, 2023.
[20] Nanbo Gong, Malte Rasch, Soon-Cheon Seo, Arthur Gasasira, Paul Solomon, Valeria Bragaglia, Steven Consiglio, Hisashi Higuchi, Chanro Park, Kevin Brew, et al. Deep learning acceleration in 14nm CMOS compatible ReRAM array: device, material and algorithm co-optimization. In IEEE International Electron Devices Meeting, 2022.
[21] Sapan Agarwal, Steven J Plimpton, David R Hughart, Alexander H Hsia, Isaac Richter, Jonathan A Cox, Conrad D James, and Matthew Marinella. Resistive memory device require- ments for a neural algorithm accelerator. In International Joint Conference on Neural Networks, pages 929-938. IEEE, 2016.
[22] Tayfun Gokmen and Wilfried Haensch. Algorithm for training neural networks on resistive device arrays. Frontiers in Neuroscience, 14, 2020.
[23] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223-31, 2018.
[24] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Wood- worth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1-2):165-211 2023.
[25] Tayfun Gokmen. Enabling training of neural networks noisy hardware. Frontiers in Artificial Intelligence, 4:1-14, 2021.
[26] Murat Onen, Tayfun Gokmen, Teodor Todorov, Tomasz Nowicki, Jesús A Del Alamo, John Rozen, Wilfried Haensch, and Seyoung Kim. Neural network training with asymmetric crosspoint elements. Frontiers in artificial intelligence, 5, 2022.
[27] Malte J Rasch, Diego Moreda, Tayfun Gokmen, Manuel Le Gallo, Fabio Carta, Cindy Goldberg, Kaoutar El Maghraoui, Abu Sebastian, and Vijay Narayanan. A flexible and fast PyTorch toolkit for simulating training and inference on analog crossbar arrays. IEEE International Conference on Artificial Intelligence Circuits and Systems, pages 1 1-4, 2021.
[28) Malte J Rasch, Charles Mackin, Manuel Le Gallo, An Chen, Andrea Fasoli, Frédéric Odermatt, Ning Li, S. R. Nandakumar, Pritish Narayanan, Hsinyu Tsai, et al. Hardware-awar training for large-scale and diverse deep learning inference workloads using in-memory computing-base accelerators. Nature Communications, 14(1):5282, 2023.
[29] Weier Wan, Rajkumar Kubendran, Clemens Schaefer, Sukru Bure Eryilmaz, Wenqiang Zhang, Dabin Wu, Stephen Deiss, Priyanka Raina, He Qian, Bin Gao, et al. A compute-in --mmoory chip based on resistive random-access memory. Nature, 60847923),00--51,, 2022.
[30] Riduan Setaddam-Aljamelee Milos Stanisavljevie, J Fornt Mas, Geethan Karunaratne, Matthias Braendli, Femg Liu, Abhairaj Singh, Silvia M Müller, Urs Egger, Anastasios Petropoulos, et al. HERMES core-a 1 14nm CMOS and PCM-based in-memory compute core using an array of 300ps/L.SB linearized CCO-based ades and local digital processing. In 202/ Symposium on VLSI Circuits, pages 1-2. IEEE, 2021.
[31] Chengxin Xue, Yencheng Chiu, Tawei Liu, Tsungyuan Huang, Jesyu Liu, Tingwei Chang, Huiyao Kao, Jinghong Wang, Shihying Wei, Chunying Lee, et al. A CMOSSintegrated compute- in-memory macro based on resistive random-access memory for Al edge devices. Nature Electronics, 4(1):81-90, 2021.
12

---

[32] Laura Fick, Skylar Skrzyniarz, Malav Parikh, Michael B Henry, and David Fick. Analog matrix processor for edge Al real-time video analytics. In IEEE International Solid-State Circuits Conference, volume 65, pages 260-262. IEEE, 2022.
[33] Pritish Narayanan, Stefano Ambrogio, A Okazaki, Kohji Hosokawa, Hsinyu Tsai, A Nomura, T Yasuda, C Mackin, SC Lewis, A Friz, et al. Fully on-chip MAC at 14nm enabled by accurate row-wise programming of PCM-based weights and parallel vector- tratss-tannport in coration-formal In Symposium on VLSI Technology, pages 1-2. IEEE, 2021.
[34] Peng Yao, Huaqiang Wu, Bin Gao, Jianshi Tang, Qingtian Zhang, Wenqiang Zhang, J Joshua Yang, and He Qian. Fully hardware-implement Nature, 577(7792):641-666 2020.
memristor convolutional neural network.
[35] Benjamin Scellier, Maxence Ernoult, Jack Kendall, and Suhas Kumar. Energy- based learning algorithms for analog computing: a comparative study. In Advances in neural information processing systems, 2023.
[36] Hadjer Benmeziane, Corey Lammie, Irem Boybat, Malte J Rasch, Manuel Le Gallo, Hsinyu Tsai, Ramachandran Muralidhar, Smail Niar, Ouarnoughi Hamza, Vijay Narayanan, et al. Analognas: A neural network design framework for accurate inference with analog in-memory computing. In IEEE International Conference on Edge Computing and Communications, pages 233 233.244. IEEE, 2023.
[37] Logan G Wright, Tatsuhiro Onodera, Martin M Stein, Tianyu Wang, Darren T Schachter, Zoey Hu, and Peter L McMahon. Deep physical neural networks trained with backpropagation. Nature, 601(489)) -55555 2022.
[38] Ali Momeni, Babak Rahmani, Benjamin Scellier, Logan G Wright, Clara C McMahon, Peter L andWanjura, Yuhang Li. Anas Skalli, Natalia G. Berloff, Tatsuhiro Onodera, Ilker Oguz, Francesco Morichetti, Philipp del Hougne, Manuel Le Gallo, Abu Sebastian, Azalia Mirhoseini, Cheng Zhang, Danijela Marković, Daniel Brunner, Christophe Moser, Sylvain Gigan, Florian Marquardt, Aydogan Ozcan, Julie Grollier, Andrea J Liu, Demetri Psaltis, Andrea Ali, and Romain Fleury. Training of physical neural networks. arXiv preprint arXiv:2406.03372. 2024.
[39] Demetri Psaltis, David Brady, Biang-Guang Gu, and Steven Lin. Holography in artificial neural networks. Nature, 343 3436655))3325-33,, 1990.
[40] Tyler W Hughes, Ian AD Williamson, Momchil Minkov, and Shanhui Fan. Wave physics as an analog recurrent neural network. Science advances, 5(12):caa66946, 2019.
[41] Alexander N Tait, Thomas Ferreira De Lima, Ellen Zhou, Allie X Wu, Mitchell A Nahmias, Bhavin J Shastri, and Paul R Prucnal. Neuromorphic photonic networks using silicon photonic weight banks. Scientific reports, 7(1):7330, 2017.
[42] Sebastian U Stich. Unified optimal analysis of the (stochastic) gradient method. arXiv preprint 19Xiv:190.004232. 2019.
[43] Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. Transactions on Machine Learning Research, 2022.
[44] Yury Demidovich, Grigory Malinovsky, Igor Sokolov, and Peter Richtárik. A guide through the Zoo of biased sgd. arXiv preprint 23t.:2629..699 2023.
[45] Tianbao Yang, Qihang Lin, and Zhe Li. Unified convergence analysis of stochastic momentum methods for convex and non-convex optimization. arXiv preprint arXiv:/6044 1604003570 2016.
[46] Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. Advances in Neural Information Processing Systems, 33:18261-18271 2020.
[47] Kun Yuan, Bicheng Ying, and Ali H Sayed. On the influence of momentum acceleration on online learning. The Journal of Machine Learning Research, 17(1):6602 26622,66666660 2016.
[48] Vien Mai and Mikael Johansson. Convergence of stochastic gradient method with momentum for non-smooth non-convex optimization. In International conference on machine learning, pages 6630-6639. PMLR, 2020.
13

---

[49] Nanbo Gong, T Idé, S Kim, Irem Boybat, Abu Sebastian, V Narayanan, and Takashi Ando. Signal and noise extraction from analog memory elements for neuromorphic computing. Nature communications, 9(1):2102, 2018.
[50] Geoffrey W Burr, Matthew BrightSky, Abu Sebastian, Huai- Yu Cheng, Jau- Yi Wu, Sangbum Kim, Norma Sosa, Nikolaos Papandreou, Hsiang-Lan Lung, Haralampos Pozidis, Evangelos Eleftheriou, and Chung H Lam. Recent Progress in Phase-Change Memory Technology. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 6(2):146-16) 2016.
[51] Manuel Le Gallo and Abu Sebastian. An overview of phase-change memory device physics. Journal of Physics D: Applied Physics, 53(21):213002, 2020.
[52] Jun- Woo Jang, Sangsu Park, Geoffrey W Burr, Hyunsang Hwang, and Yoon-Ha Jeong. Opti- mization of conductance change in Pri - M -based synaptic devices for neuromorphic systems. IEEE Electron Device Letters, 36(5):457-459, 2015.
[53] Jun- Woo Jang, Sangsu Park, Yoon-Ha Jeong, and Hyunsang Hwang. ReRAM-based synaptic device for neuromorphic computing. In IEEE International Symposium on Circuits and Systems, pages 1054-1057, 2014.
[54] Scokjae Lim, Myounghoon Kwak, and Hyunsang Hwang. Improved synaptic behavior of CBRAM using internal voltage divider for neuromorphic systems. IEEE Transactions on Electron Devices, 65(9):3976-398) 2018
[55] Elliot J Fuller, Scott T Keene, Armantas Melianas, Zhongrui Wang. Sapan Agarwal, Yiyang Li, Yaakov Tuchman, Conrad D James, Matthew J Marinella, J Joshua Yang, Alberto Salleo, and A Alec Talin. Parallel programming of an ionic floating- -oate memory array for scalable neuromorphic computing. Science, 364((444)::70-5744 2019.
[56] Murat Onen, Nicolas Emond, Baoming Wang, Difei Zhang, Frances M Ross, Ju Li, Bilge Yildiz, and Jesús A Del Alamo. Nanosecond protonic programmable resistors for analog deep learning. Science, 377(6605)5539-5444 2022.
[57] Yulong Li, Seyoung Kim, Xiao Sun, Paul Solomon, Tayfun Gokmen, Hsinyu Tsai, Siyu Koswatta, Zhibin Ren, Renee Mo, Chun Chen Yeh, et al. Capacitor-based cross-point array for analog neural network with record symmetry and linearity. In 2018 IEEE Symposium on VLSI Technology, pages 25-26. IEEE, 2018
[58] Seyoung Kim, Teodor Todorov, Murat Onen, Tayfun Gokmen, Douglas Bishop, Paul Solomon, Ko-Tao Lee, Matt Copel, Damon B Farmer, John A Ott, et al. Metal-oxide based, CMOS- compatible ECRAM for deep learning accelerator. In IEEE International Electron Devices Meeting, pages 35-7. IEEE, 2019.
[59] Stefano Fusi and LF Abbott. Limits on the memory storage capacity of bounded synapses. Nature neuroscience, 10(4):485-499 2007.
[60] Jacopo Frascaroli, Stefano Brivio, Erika Covi, and Sabina Spiga. Evidence of soft bound behaviour in analogue memristive devices for neuromorphic computing. Scientific reports, 8(1):1-12, 2018.
[61] Paiyu Chen, Binbin Lin, I-Ting Wang, Tuohung Hou, Jieping Ye, Sarma Vrudhula, Jae-sun Seo, Yu Cao, and Shimeng Yu. Mitigating effects of non-ideal synaptic device characteristies for on-chip learning. In /EEE/ACM International Conference on Computer-Aided Design, pages 194-199. IEFE, 2015.
[62] Lisha Chen, Heshan Devaka Fernando, Yiming Ying, and Tianyi Chen. Three-way trade-off in multi-objective learning: Optimization, generalization and conffict-avoidance, Advances in Neural Information Processing Systems, 2023.
[63] Andreas Winkelbauer. Moments and absolute moments of the normal distribution. arXiv
preprint arXiv: 220. 4340, 2012.
[64] Milton Abramowitz and Irene Stegun. Handbook of mathematical functions with formulas, graphs, and mathematical tables, volume 55. US Government printing office, 1948.
14

---

[65] NIST Digital Library of Mathematical Functions. htttps:/ddmm .nist. gov/ Release 1.1.12 of 2023-12-15. F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds.
[66] Tayfun Gokmen, Murat Onen, and Wilfried Haensch. Training deep convolutional neural networks with resistive cross point devices. Frontiers in neuroscience, 11:538, 2017.
15

---

Supplementary Material for "Towards Exact Gradient-based Training on Analog In-memory Computing"
Table of Contents
Literature Review
Implementation of Asymmetric Updated by Pulse Update
C Examples of Analog Devices)
18
C.1 Example Linear step device (Soft bounds devices)
18
Example 2: Power step device
18
Example Exponential step device
18
D Verification of Assumptions
19
D.I Verilication Assumption 4 under Strongly Convex Objective
19
D.2 Verilication of Assumption Non-zero Property of Gaussian Noise
22
E Proof of Analog Training Properties
23
E. Proof of Lemmall
[]] Saturation and Fast Reset
23
E.2 Proof of Theorem Bounded Weight
23
Proof of Analeg Gradient Descent Convergence F
23
G Proof of Analeg Stochastic Gradient Descent Convergence
24
G. 1 Proof of Theorem 2 Convergence of Analog SCD
24
2 Proof of Theorem
Lower Bound of Analog SGD
26
H
Proof of Tiki Taka Convergence
30
H.1
Proof of Tracking Lemma
30
HI2
Proof of Weight Decay Lemma
33
H.3
Proof of Bounded Pa
34
H4
Proof of Tiki Taka Deseent Lemma
35
11.5
Proof of Theorem 4 Convergence of
36
Simulation Details and Additional Results
38
1.1
Least squares problem
38
2
Classification problem
39
Verification of hounded saturation
39
A Literature Review
This section briefly reviews literature that is related this paper, as complementary Section
Inference and other applications of analog devices. Before designing hardware for training. series of AIMC prototypes focus on accelerating the inference phase 29 30
31
32
33
12 34). The
sate-of-thh-ar result shows that the analog inference is capable reaching comparable accuracy (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-baa based learning algorithms have been studied in [35] and the neural architecture search analog devices has been studied [6].
with digital inference
Relation with physical neural network. Our work is also in spirit related to the recent works on physical neural networks (PNNs) (37 38) we are particularly interested AIMC hardware with resistive crossbar arrays, while PNN is generic concept of implementing neural networks via
16

---

physical system. Various hardware is capable of supporting PNN, such as holographic grating 39 wave-based systems 400, and photonic networks [41] name a few.
Convergence analysis of gradient-based algorithms. In the digital domain, a series of literature has discussed the convergence of gradient- algorithms. As the basis of neural model training, much work focuses on the convergence of SGD 42
43 44 [3] and its variety stochastic gradient descent
with momentum (SGDM) 445 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 digital SGD with bias. From this perspective, the convergence of Analog SGD (c.f. Theorem (
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 both W and Pe involve asymmetric bias.
because the updates of
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, v oo=/K K (24). This lower bound is generic result for any stochastic gradient-based algorithms, which means that the convergence of gradient-based analog algorithms, including Analog SGD and
is also subject to it.
B Implementation of Asymmetric Updated by Pulse Update
The proposed dynamic (3) of Analog SGD in Section iis inspired by the empirical studies in [2 and [19]. However, the proposed dynamic (3) is only an approximation because we not directly apply an arbitrary increment Ave on the weights. Instead, we need to send a series of pulses to analog devices, which leads the change 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 (-,,), we introduce the update function Up(t,) R (+. for the pulsed update, defined by
Up(w,)) 8) = w Awmin (w( w + Awmin 4+ (w): Awmin q-(w), s=
= +,
(15)
where Awmin 0 is the response step size determined by devices. Since Awmin 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 (Wk,s) where the update sign s = Au 2 0 and = otherwise.
The response step size Awmin is usually known by physical measurement. In order to approximate Uww, Aw), analog device first computes the pulse series length (bit length) by
AAw]
BL =
(16)
Awmin
which ensures
BL Awmin - |Awl| <
Awain or BL Awnin - Aw] S Aw
(17)
After that, a total of BL pulses are sent to the analog device, forcing the weight to become
U (w, Aw) Re Up Up o... ..... Un(w, 8) = (,, 8).
(18)
BL
which implement the analog update Uww Aw).
Error analysis. Directly expending the 18 yields
BL
U p BL (w, s) sAwmin
(e + AAu sign(Aw))
(19)
w + smWmin
(w)) + AAwin dl(w) sign(Aw)) + ol A(Amin))
17

---

BL(BL -1)
min (L)) + (Awmin)
do (w) sign(Aw) o(Awmin)
2
w + Aw (w) + O(Awmin) + (((ww)²),
which indicates the difference between U (ww Aww and U BL (w. are higher order infinitesimal. As a concrete example, the Awmin is set as 0.002 [49 or 0. 0.0949 (00 for ReRAM devices.
p
For asymmetric linear device (ALD, defined in Section 2). it holds that 144. (w) 44 (w) (w) 0. Consequently, the difference between Uww, Aw) and U (w, 8)
lq' [w)) and
Awmin (Aumin)
BLL
A AWmmn
(Aw)²
1 s) (ww Aw)]
(20)
2T
Since Awmin and Aw (a) are usually small, the enror can usually be ignored.
Significance.
The significance of the analysis in this section is that it explains how estimate the response factors (+) and g (.) in (3). In (15), it shows that they are, in fact, the response factors
of the given devices, which can be measured by physie measures [49]. In Section C we showcase various capable base materials for analog devices and their response factors.
C Examples of Analog Devices
In AIMC accelerators, weights of models can be represented by the conductance of based materials, such as PCM [50] 55, ReRAM [52 (3), CBRAM [54] [55]. ECRAM [56]. this section, showcase spectrum of alternative devices for analog training.
C.1 Example 1: Linear step device (Soft bounds devices)
A large range of devices, including ReRAM 49 58 have linear response factor
20 Capacitor
57
EcRAM 57 56 EcRamMO
w
w
g+ (w) = Tmax
q (-(w)
(21)
Tmin where Tmin < Tmax and w are constants, whose meaning will be explained later. With these response factors, the function F-) and G(-) can be written
1
1
F(w)
(w
w²)
(22)
2
Tmax
Tmin
G(w) Tiax
(w w))
(23)
Tmin
ALD used in the paper is special linear step device with Tmax and Tmin -T
C.2
Example 2: Power step device
For power step device, q+ (w) and q- (w) are power function with respect to W, which models implements synapse model [59 60)
Tinx
Tmin
q+ (w)
q- (-ww)=
(24)
Tmax
Tmin
Tmax - Tmin
where + and T- are parameters determined by materials.
C.3 Example 3: Exponential step device
In some ReRAM and CMOS-like devices [6121] the response factors are captured by exponential function, i.c. Exponential update step or CMOS-like update behavior.
4+ (w) - exp
Tmax
W
(25)
Tiax Tmin
W Tmin
(w) - exp
(26)
Tiax Tmin
In Figure 6 the curve of response factors and F()) and G(-) are illustrated.
18

---

Linear Step Device
Power Device
Exponential Device
1.00-
1.0
0.75
Response
1.5-
0.50
Tan
1.0
0.5
[w)
0.25
4 (w)
0.0
0.00
Symihsym components
1.5
100
10-
02
0.5
-Flo)
0.
G(w)
-05-
02-
Tnn
-10-
-10
Figure 6: Response factors for different devices (without zero-shifting)
D Verification of Assumptions
D.1 Verification of Assumption under Strongly Convex Objective
This section proves the weight Wi is strongly bounded when the loss function is strongly convex. We prove the result for both Analog GD (Ex = 0) and Analog SGD with EK possessing some special structure. Before proving this, we introduce strongly convex assumption.
Assumption (u-strongly convex). The objective f(W is u-strrogly convex, i.e.
[Vf(W) - f(("))l 2 W WIl,
MA, W' E R...
(27)
Assumptionneensures the critical point W (and hence optimal point) is unique.
D.1.1 Bounded Saturation of Analog GD
The following theorem provides a sufficient condition under which the Assumption Tholds.
Theorem 5 (Bounded saturation of Analog GD)) Suppose Assumptions 2 and 6 hold and define
L Wo W + | 11
Wmaxx=
(28)
/
The sequence }W+} generated by Analog GD satisfies Wa S W Wmaxx
Theorem claims that if both - 11 WI and || are sufficiently small, which means the
i optimal point W* is located inside the active region and Wo is properly initialized, the saturation degree |Wello/T can be sufficiently small as well, even though no projection operation is applied.
Proof of Theorem 5 Given f(+) L-smooth (Assumption 1. we know from (7p that
a ( |
f(W++1) S f(W)) 2
|VS(W))] < ((W)
(29)
where the second inequality comes from the bounded weight (Theorem T.. Consequently, we reach the conclusion that f(W2) < f(Wo), Vk N. The strongly convex assumption (Assumption 6 claims that
1 (f(W)) - ft) S W - W (f(WK) - - =
I Wo WWI (30)
4
Therefore, triangle inequality ensures that
W Wi W 1|0 + || 1
(31)
S Wh - Will + |
L I w*l + ||* 1000
(32)
which completes the proof.
19

---

Remark 2 (Bounded weight of digital GD). Theorem S also holds for digital GD, which can be achieved by forcing in inequality (29) infinite.
In digghdiimesional cases (D > 1). Theorem 5 not exclude the situation || > W loo.
which is unfavorable 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 Wi (and W*) in the next theorem.
Theorem 6 (Bounded saturation of Analog GD with scaler weight). Suppose Assumptions 2 and hold and Wh E R is a scalar. If the learning rate a S 2E'
1 the following statements hold true
(Case 1) If wo 2 w", wo 2 wk (1 aqp(1
|| las () w²) + =n= 2 Wk+11 w":
(Case 2) If wn < w., wp S wk 5 aqp(1 I [) - w²) ) + =" S wk+1 S w². Consequently, the sequence {wk generated by Analog GD satisfies the following relation [w S Wmax == min [ool, [w
Theorem 6 asserts that {wr} converges monotonically from we to wt. If [wol S |w01. we have which improves the bound in Theorem
Wmax
Proof of Theorem 6 Expanding the objective f(-) in a Taylor series around w yields tha
f(w") = f(w) + (Vf(w), w w") + [(w)]| - w w01
(33)
where ji(w) depends on and satisfies y S ju(w) < T. because of the smoothness (Assumption and strong convexity (Assumption ( assumptions. Consequently, the gradient on w can be written as
D
f(w) = [w w")
(34)
with which the gradient descent has the following property
(V(w)) w =(1 (r)(wx)) - w²). wk
(35)
Using this inequality and manipulating ||wK+1 w= w=1 a|
| w'
(36)
|lwk (VW() - [Vw(l we ==11
-
=lwnk (ww)) - w²1 + 2a
(urk - (VV((uk)) - w., (V(()) @ wxll)>
a
[V((w)] O wxl1
72
1 2aj((w)) + a² xzxx)) + 2az((w))( (I) a()(w))) |ewalloo + a² (
| w0 11
T
x2
- 2afl(ww) ||uxilloo ) + ((xxx))) l loc + l / ) ||w w"
Imll - w01
72
where the (a) uses Cauchy's inequality. Noticing Theorem is chosen as (uj(wx)))) < aL < 1, we have || w0 ww - 11. In addition, Lemma D claims that
claims | < 1 and the learning rate
| w S ||1 + ww/TlllaVf(wx)) < w - w01l S We w"
(37)
where the second inequality holds because Theorem D and smoothness assumption (Assumption guarantee || w+/ < and [w)]( < ||w w" ||. respectively. This fact implies that
"Notice that the 2n-momm || and norm || I/so 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.
20

---

Wk+1 w² has the same sign with wR - w". Consequently, inequality (36 and 37 case 1, if w/ 2 w", we have
show that in
| lloe (w w=) + w"
wk 2 au((
(38)
T
2 #k+1 2 w".
Keeping using this inequality reaches the result. Case 2 can be proved by the similar method.
D.1.2 Bounded Saturation of Analog SGD
The following theorem provides a sufficient condition under which the Assumption 4 holdd. In the section, we show that if the noise has special structures, the saturation degree [WWlloo/ is bounded.
Assumption 7 (Random sample noise). The noise can be written as E f((:: V(()), where & is a random variable sampled from an underline data distribution D,, fW: :) is function of W and ç, and the gradient V f(W:: E) taken over W.
Assumption hholds if the noise comes from the random sampling from series of functions.
Theorem 7 (Bounded saturation of Analog SGD). Suppose Assumption 7 holds and each f(W; is L-smooth (Assumptions 7 and j-sttrongy convex (Assumptions ( with respect to W. Denote the minimum of f(W:E) We. If the supremum sup; [ exists, define
W max = sup(llWo - Will) + (Wll()))))))
(39)
The sequence }W&} generated by Analog SGD satisfies [ l S W max uniformly.
Given the strong convexity with respect to W. f(W: has unique minimum, and hence W is well- defined. Similarly, the supremum sup, ( W exists since W exists. Theorem 7 claims that the saturation degree is bounded given the noise comes from random sampling a series of smooth and strongly convex functions. Similar to Theorem 5 Theorem a holds for
digital GD by forcing in inequality (29) infinite. The proof of Theorem 7 is inspired by that of
622 Lemma 1].
Proof. According to Theorem 5 it holds that
L WW wall- || w
(40)
Therefore, triangle inequality ensures that
||alloo < sup ( - Well lu
(41)
sup([ will) (1 [lxc)
sup(llWo w sup [1
which completes the proof.
Similar to Theorem we can improve the bound when the weight is scalar (D 1). The notation
WR (and w²) instead of W₁. (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; E L-smooth (Assumptions) 7 and p-strongly convex (Assumptions 6 with respect to w. Denote the minimum of (w:; E) as w If the supremum supe supe(llwe] (1lw [|} exists, it holds for any E N that
( wo: inf inf(w() s wk I max Wo. supfwr 8
min
(42)
21

---

The theorem is proved by induction. The statement holds trivially at k = 0. Suppose (42 holds for k. W 2 w". Theorem guarantees that we 2 wk+11 2 wa and hence
Proof of Theorem 8
min { wo: inf {wm} &
S w S wk+1
S max wo, sup(w?}
(43)
On the contrary, if wy S w". Theorem guarantees that wn S wh+1 S w and hence
min wo: inf inf(w[]) wy S wh+1 S w max wo wo (oossu(pu))
(44)
which implies w still satisfies
(2)) Now the conclusion is reached.
D.2 Verification of Assumption 5 Non-zero Property of Gaussian Noise
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 non-zero at only one point, c equuls zero. On the contrary, large e 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,
mild because noise is introduced during computation.
Generally, the estimation of с can be challenging because it involves the computation of the raw momentum lel =l] of the noise. Scarifying the rigorousness bit but providing intuitive result, we get the parameter è by considering an approximation of this raw momentum and deducing a bound for this approximation.
In this section, we demonstrate that for Gaussian noise any g, it holds that
_NO0, o2), can be selected as v 2/2 For
B lg ++1l
8
E.ll
-Eel(
+ =1)
(45)
28
82
Eellg =|] +
E [g + s)
72
2,
82
Eellg + al1 +
(g² + +
,2
Because + is Gaussian random variable with mean g and variance 0², the second term in the RHS has closed form [63] given by
2 Fi Eellg + el] = =o -
(- 1
(46)
2' 20
In the equation above, (F (15 is used to denote Kummer's confluent hypergeometric functions. has been shown (64 13.1.5] that when 2 S 0, (:(:s))) has the asymptotic property
r(b)
(a; = [(b a)
(-2) -1 0(1x)=)))))))
(47)
where I(.) is Gamma function. When 2 a small, Fi (a; b; 2) has the following approximation for any a, b R 665 Sec 11.2]
F (a; b; ~ 1 2.
(48)
Let 2
2² Z0
On the one hand when ~ 0, 2 is large and 47
with - and b asserts that
2 T(1/2)
g2 (1
20
2
g2
Eellg el] ov
0
VT(1 +
(49)
T(1)
20
g
20
On the other hand, when 0o, is small and
48
provides that
g²
2
g²
Eg [lg + el] ~ vo. (1
20 = V
- (1
(50)
2n
In conclusion, choosing c = / yields 11g + ++] X
/ / Here 2 is used to indicate the lower
bound holds for an approximation of the left-hand side (LHS).
22

---

E
Proof of Analog Training Properties
E.1 Proof of Lemma Saturation and Fast Reset
Lemma (Saturation and fast reset). For ALD with a general w², the following statements are valid
(Saturation)
If sign((wr) = sign(ws) it holds that |wi++ w/k| |w> - w0\//l | |Aw|.
(Fast Reset)
If sign(Aw) sign( wx), it holds that |wk+1 wxl |1 |wx 1/ |Aw].
Proof of Lemmal
The proof can be completed by simply extending the LHS of
1 Aw (ww w0)
wk++1
wk
Aw
(51)
7
Awl (sign( Aw) = (w/= w)
Isign( Aw) - (wk - w -Awl
sign( (wk w)0 1wok wº1
Aw
sign Aww
Using the fact that w = 0 completes the proof.
E.2 Proof of Theorem Bounded Weight
This section proves that the weight W' is bounded.
W. Theorem (Bounded weight). Denote [|W as the foo norm of W. Given ||olll S and for
any sequence {AWx k E NJ. which satisfies | S it holds that || S,, Vk E N.
Without causing confusion, omit superscript and denote the i-th coordinate of W3 and AW; as we and yi, respectively. It holds that ||W < and |yts| ST
Proof of Theurem 7
W 1 = I|W - 0 + AW; AW&l @ (Wa- - W
(52)
max W/ - w 9s 7 19:1(1;; - =)))²²
REZ.
max (1
1gil)²(us =w02 - 29: =1::))(us - =) + 9
iEZ
max
(1
- 19:1) + 2|9a| (1- =9911) - + 9
iEZ
1
max
(1
(g:l) + 19:1)
iEz
=
Taking square root on both sides completes the proof.
F Proof of Analog Gradient Descent Convergence
In Section 3
we show that the asymptotic error is proportional to the noise variance o². The following theorem prove that the Analog GD converges to critical point.
Theorem 9 (Convergence of Analog GD). Under Assumption S +, it holds that
7 and 4 if the learning rate is set as
[f(WW)) 2(((W)) ~ K
1
(53)
K
W2 Faax /72
A surprising conclusion of Theorem 9 is that the asymmetric update actually will not introduce any asymptotic error in training. also indicates that the asymptotic error comes from the interaction between asymmetric update and noise from another perspective.
23

---

Proof of Theorem
The L-smooth assumption (Assumption I implies that
f(Wa+1) = f(Wi)) + (Vf(WW)) W6+1- - Wi) +
= W - Wi
2
(54)
= =((W)) Vf(WW)]12 -(20
L
W|W Will2
2
1 + Wk+1 W4 (W&)l
2a
1
((W&) - Vf(WWa]] +
Wk+1 - W4 + +vV
20
where the equality comes from
(WWW,, Wk41 Ws) //(())]]
[K++1 W
(55)
2a
WK+1 W4. + aV
2a
The third term in the RHS of (54) can be bounded by
| k+1
We + VVS(We)) = 2r
[/(WW)] @ Wall
(56)
2a
Vf(W )| |
2T
Substituting (56) back into and cooperating with Assumption 4 yield
1 |V
f(W++1) S f(W&)
(57)
x2
W
S f(W&)
Vf(W))112
72
Rearranging and averaging (7) for from 0 to deduce that
[/((W))] 2()(W)) ((W)))
(58)
aK W2 max ?2)
k=
Noticing Assumption claims that f(W)) 2 f", we complete the proof.
G Proof of Analog Stochastic Gradient Descent Convergence
G.1 Proof of T'eeorermm D: Convergence of Analog SGD
This section provides the convergence guarantee of Analog SCD under non-convex assumption on asymmetric linear devices.
Theorem 2 (Convergence of Analog SGD). Under Assumption 7 the learning rate is set
[[Wo)-S* and K is sufficiently large such that S J, it holds that oLLK
K B[ITS(WA)))) so ( ( (1)W)
K-1
1T
255k
W2 WV2nx/72 max
WT
W /
where Sx denotes the amplification factor given by Sx := K
W maxx
Proof of Theorem
The L-smooth assumption (Assumption T
implies that
Ee, (S
S f(W)) + (e,
W Wx)) + Er, [[[ - Wx
(59)
a IVF(WW)112
1 L)E,, [| We aE
< f(W))
2a
24

---

+ LE,, |||+
[W++11 We V ((W)) ( +x)ll
2a
where the second inequality comes from the assumption that noise has expectation 0 (Assumption
Beg (VV(WW))) W6+1
Wa)] = Be, (VV/(WW))))) W441
W4 + arx))
a
[VF((W)]]
1
Eeg W+11 W + aEEll?)
2
2a
1
Es [1ll++++111- Wv + aV +x)l
2a
and the following inequality
L
Ren [1
Wx V LB (1W++ W + aex + T. [I|=x|]]]
(60)
2
With the learning rate a S 2D and bounded variance noise (Assumption 3). (59) becomes
a Ee, ((WW--W))) S S(WW)
-h 2
[[//(W)) + Lo + [W&+1
1
W + a (V/(W)) + Ex)
2a
(61)
Cooperated with Assumption
the last term in the RHS (59) can bounded by
Ee, [[ - W& + (WW) + NE ||
(62)
2a
Be, [IIVS(WW)) + en @ Wxll
2r
$ 2T
a
Re,
[IV/)(W))) + 1 ||
+ ao²
WF(WW))
1
27
27
where the last inequality comes from Assumption 3
Beg [[[][) + ex x [2] = |/ [ + Ee, |||ex|| > [
(63)
Plugging
62
back into 59 yields
| 2
[V/(())] E., (S(W)) ((W o ao 1
(64)
2,
ensures that 1 | 2 - W Wmax/>²>> O, which enables dividing both side of (64 by | 1 Taking expectation over all ck, 6k-1," ... 8o and averaging for l from 0
Assumption
K deduce that
K K
((WW)I
(65)
2(f(W)) ([f(W++1))
2aLo²
1 o² 1/ /72
Σ
+ 1
+
aK(1 - W2 N220x/79
1
W
W
/
K
| /
k=0
2(f(Wo) - fr)
2aLo²
1 /22
aK(1 W2 W2ax/
W2
Ww /72
max
(f(Wo) L
a² 2k
W2 max
where the second inequality uses Assumption 2 and the last equality chooses the learning rate as / /(W)) The proof is completed.
LL
25

---

(Example) Consider an example where all the coordinates are identical, i.e. W₁ W. for some E IR where 1 E IR is the all-one vector. Define W w'1 where w" E IR is constant scalar and a quadratic function f(W)= $ || W+ whose minimum W*, Initialize the weight Furthermore, consider the G.2 Proof of Theorem 3: Lower Bound of Analog SGD
This section provides the lower bound of Analog GD under non-convex assumption on noisy asym- metric linear devices.
Theorem 3 (Lower bound of the error of Analog SGD). There is an instance which satisfies Assump-
tion 7 4 such that Analog SGD generates sequence {Wo k = 0, 1,.,,,,.,,, .K} which satisfies
K-1
a= 0 (tt) a 20002 a(pSkk
+ 1 VK)
)
- O(a)
(10)
K
k=0
The proof is completed based on the following example.
on Wo = W* and choose the learning rate a S min It, p46o/(rVD))
noise defined as follows,
Ek E
(66)
where random variable E E R is sampled by
Ex
DDV
Pk
w.p. Pk.
with Pk
wk
(67)
Ex
==
P-PE
Ph
w.p. - Pk.
2
As a reminder, it is always valid that |wa| | I T (c.f. Theorem 5 and Therefore, the noise distribution is well-defined. Furthermore, without loss of generality assume |w"| S and a < ILVD
Pk S
4/3
Since all the coordinates are identical, Analog SGD can be regarded to train a scalar weight each coordinate. Furthermore, with the definition
L 2 (w w" SA ) whose minimum is wi, = =w" T,
EK T.
[w: Ex)
(68)
the noise & satisfies Assumption Therefore, even though w are time varying, we can regard wh as the initial point and only consider wk+1- By this way, the conditions of Theorem and Theorem are met, and their claim for w is valid.
To prove the lower bound, next introduce several necessary lemmas to facilitate the proof of Theorem The first one is used to verify Assumption 4
Lemma 2. Suppose |w"| < and ILVDD
Define Wmax
5. The sequence (Wx : N)
4/3
generated by Analog SGD (3) on the example above satisfies
|| loc & W Waxx-
(69)
Proof of Lemma
The statement can be proved by induction. When k
|Wol = |wo| 7
W max.
(70)
To prove 669 for & + 1, Theorem 8 asserts that
Wo. inf [ele wett }
min
< [Wa+ale S max
Wo, supf [e];
(71)
or equivalently
w"
1 Pk
Wettle w=
Pk
(72)
LVD
Pk
LDD
Pk
'These requirements are necessitated by Lemma 2 and can be relaxed to |w"| S CUT for any constant c, < In that situation, Lemma 2 remains valid, although W Vax differs.
1.
26

---

According to the triangle inequality, [[ is still bounded by
WWk+ille max ( 4+ k+1 S [w"
LVD
max
- Pk
Pk
V
Pk
pk
(73)
+ W
= =1w01 + LVD
11 OO
+ WHnns/T
S/w01
+ LVD
Wmax/T
S T + (2T)/T 7
4 4/3 V 1- (2T)/T 2
W maxx
Therefore, 69 is confirmed for ls + and the proof of Lemma 2 is completed.
Noise &a defined by (67 is time-varying since W& is changing. The following lemma provides an upper bound for the variation of noise with respect to WA.
Lemma 3. Suppose lW I W mmax= S 2. The following statements always valid
30
15 -ttl
Wk++1
wk/
(74a)
TVD
D
30
152+1 - 5El S
Wk+11
Wk/-
(74b)
TVD
Proof of Lemma
3
Define the functions
1- 9 (x)) = 1 1 x²
g g+())
(75)
x
with which & and Eo can be written as
at = VD g ((T))
E = o
9
(76)
VD
The derivatives of (x) and g (x) is
1
1
1 x
Vg* (x) 2
(11 + ++)()=11110 xx)
+
V
(1 - x/3
(77)
1
1
1 -
Vg (z)
+ V
(78)
((1 + (1++))(1 x))
(1 x)3
whose norms are upper bounded by
2
Vg+(1))
<
+
+2v3
33
(79)
2
v3
2
V9
(z)
<
+
2/3
33
(80)
v3
Therefore, both g (z)) and g (x) Lipschitz continuous and hence
[ _
W Wk++1
g+
W/
<
30
Wk++
wkh |
(81)
D
TV
Wk+11
Wkke
30
Ket1 $
g
<
Wk+1 Wk
(82)
VD
TVD
DD
The proof of Lemma 3 is then completed.
27

---

In the proof of Theorem the most tricky part in the recursion 33) is the gradient wrapped by absolute
value (V)(W&) + Ek/. Fortunately, the expectation E|| V + Exl] 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 a S min 22 x+6o/(TvD) valid, it holds that
and (74) are
20 BlVV)(W)) + Exll
PA pk) 1 1 1 1)Vf(W&).
(83)
vD
Proof of Lemma
The proof of Lemma
4 closely relies on the following inequality
$ $
[W S w" + ER
w
(84)
L
or equivalently, the gradient [V[(W))]; = L([Wa]; w²) satisfies
$ < [V/(WA)], S 5 Vi E I.
(85)
By (85). we claim the signs of [W+)) + &T and [[WW)]] + & never change during the training and thus the absolute value can be removed
V((W))) 5 1 = 4 (WWx)
(86)
()(W&) - = (((W.).
(87)
Accordingly, [[[ ((W&) + exl] can be written
[[(Vf(WW)) =x|]
(88)
Pp
(5t V((W))) + (1 PP)) (ST (-1--(((W)))
Pk
1+ vF(Wa) + +11 P&))
0
Pk
1 - v((WWs))
P
VD
Pk
VD
1 Ph
2a
Pa.(1
Pk)) 1 (2pk - L)V)(W))))
VD
which is the result. Therefore, the rest of proof shows 84 is valid.
Verification of 184. The statement can be proved by induction. When k 0, (84) holds naturally
since Wo W
To prove 84 for k + 1, consider Es = E and e Ex separately, and the conclusion holds for both cases.
Case 1: Ek = 5t
1-Pk
From the induction assumption, is valid that
VDV V
WRek 2 n²
Ph
(89)
LVD
Pk
Therefore, Theorem 6 asserts that [W++1]; [Wa], and hence we have Pk+1 2 Ph. S < St
and
G-+1 S Ep Consequently, the second inequality of (84) can be reached by Theorem
St < wn L
Skt1 L
We+1), -w"
(90)
To obtain the other inequality, notice that
St I.
S
w=
[WK+i]i + (w"
[W
+7,
(st skt1)
(91)
L
50
20
(0) Wottlss + (1 (1- aL(1 (1-
[Wa]e (w
St+1 - (Ww)))
+ - (4t =ttz)
1
L
L
(6)
[W&] (w
St
6aa
5k ))
Wettke + (1- aL(1
[Wak)) +
TVD ([Wk)s - -(w"
L
L
28

---

[We+1]; (1 - aT.(1 [Rx]
6aα
5
([W)):
(w"
L
where (a) comes from Theorem
(b) comes from Lemma and inequality (37).
3 TVD
6ao
Sk+1 )|
- -5 -
We++il+ [Wildl
-
[W*];
(w*
(92)
TVD
The choice of learning rate implies that
1 - aL [Wale]]
600
60
21-a(L a(L +
-
) 2 0
(93)
TVD
TVD
from which and (91 we reach that
Sk+1 < [h++1hi-
w
(94)
Combining (94) and (90) reaches in case 1.
Case 2: Ek 5/
Ps.
1. Noticing the permutation invariant between and 1 -
PP
we find that the proof for case 2 is similar to that of case Therefore, the proof of case 2 is omitted here. In conclusion,
the noise definition (67).
84 still holds for k and (84) verified. Now the proof of Lemma is completed.
After providing the necessary lemmas, we begin to prove Theorem
Proof of Theorem 3 Consider the example constructed above. Before deriving the lower bound, we
demonstrate Assumption 4 hold. obvious that f(()) = L(W W'*) satisfies Assumption !
and f(W) > fr ;= 0 satishes Assumption
2 In addition, Assumption 3 could be verified by noticing
(66) impplics Ee, [Ex] = and IEe, []lxx]] S o². Assumption 4 is verified by Lemma 2
Now we can derive the lower bound. Utilizing Lemma and manipulating the recursion the following result
3 we have
Beg [W W*]
(95)
= Bee WV - (VV((W))) aEk
Vf(W)) + sul O W. W"]
(1 aaL)(W - W*) LEe + + O We
20o
a VP - pk) W₁ (2pk 1)V @ We
= (1 (1-aL) (L-aL)(Wa - W*) TVD
Multiplying the both size of 95) by I. and plugging in the equation V)(WA)) = L(W, - W*) yield
Ez, V (W(W++1))
(96)
2aTo
at.
(1 aL)
Vp pk)
We
-(pp (2pt: (WW)((W) O We
TVD
7
-i-b--L(22p))) - 1) Ws
20Lo
v)(
Vpk - ph) Wr. TVD
where the last equality uses W = wt 1. Recall the probability Ps = 1 {1 we ), we have
1 wk
w
1 p
VP pk)
1
2pk
(97)
72
Substitute them back into (96)
WK 2
aLo TVD
w 2
Egg [WW+)1)) = 1 aL + aL
vf(Wx)
Wx
(98)
72
72
29

---

-1- al. |Wal180
aLo V((WA))
|
We
7²
TVD x²
VS(WE) aT. (1-
aLo V/(W&)) TVD 72
&
We
72
where the first equality utilizes | = | 11 = l Reorganizing 988
we obtain
Wa/T
V V((
Ex, [[(Wk+1)
vf(WW) VI- B/ VD
W 8/7²²
It is worth noticing that the second term in the RHS of 99 is in the order of O(a)
v (WWs) E., [V((W++1)
Ex
[W WK+1]
1
W /T2
1 I /
aL EE V ((W&) Exll
(1 [W /oolo//TT/LL - 11WA+13.777)
aL (
(1 [|
(6) LL max + W*)
(1 W maxx/ (r) W W
(())
where (a) is Lemma I and (b) comes from ||V/(W)) L - -W S L(llWK]
[[ S
Ly & + (ww)) Therefore, the gradient can be rewritten as
WA/T O(a).
v/(We)
(99)
V1 W
VD
Taking the square norm of the gradient and averaging for k from 0 to K - we obtain
K
W 1
IVS(()))
0²
O²Sx O(a)
(100)
K
K
where the following equality is applied
W T DD
1ool
(101)
VD
The proof of Theorem 3 is thus completed.
H Proof of Tiki-Tri -akka Convergence
This section provides the convergence guarantec of the
under the non-convex assumption. Theorem 4 (Convergence of Tiki- Taka), Suppose Assumption 5 hold and the learning rate is set as a O(1/Vo2K) B SaL. It holds for Aaki-Taka that the expected infinity norm Ps is upper bounded by ||| 1 1 p2 paaxx 1' Furthermore, o² and are sufficiently large so that 33P2 P 2 it valid that
K 1
( (((W))
E (
(14)
K
K
33.22
max! 2
K=
H.1 Proof Tracking Lemma
Before the proving Theorem 4 we first introduce two useful lemmas.
30

---

Lemma (Tracking Lemma). Under Assumption and it holds that
TVD
BEstill PR+2
v Vf(W&+1)l
(102)
30
TVD
4
430
||
VS(W&)]
303 [W&+11-
W 1all--
Pk+1 ||
TVD)
TVD
43vD
|
Vf(WA)]| + 223
To make Pk+2 sufficiently close to the true gradient, || 1|2 should be small.
Proof of Lemma
According to the update rule of Ps. have
T TVD
BEN 111
VS(W
(103)
TVD
Pett + BV ((W k+1) + Bek+1 [J(W + E
Pa+1
V VS(W&+11) [
Bo TVD
TVD v((W++1))
30
(Pk+1
Pk+1
TVD
[f(W++1) + o Pk+1 3Ex+1ll2]
Bo TVD [Pk+1 - TVD o
<
Besti [1
Vf(W++1)) + SEx+1l191
1 u
E
[1[G0//DD (V/ + sx+1)) @ Pa+il1?)-
Ur
With Assumption
the first term of (103) be bounded via the same technique as 663 that is
Aa
TVD
E Eea [1I
(P
(((W++)) 3Ex+1 1|
(104)
TVD"
o
(1
fo )2 TVD
TVD ||kKt1
8²
Vf(W
1-u o²
1 u
a
230
TVD v((W++1)]
82
u) ||
TVD
o
where the last inequality holds because
Bo
(1-
230
(1
12 < 10--) -w)
+
(105)
TVD
TVD
The third term the RHS of (103) can be manipulated by the variance decomposition and conse- quently can be bounded by
B²
- #x+1l) @ 1
(106)
2
g2
u
LIEI
8²
E
20 20 +
+ (PP
u
Ek-1
NEI
82
E
E 20
u
LiEI
B2
BELT1
Σ ((V
+
uT
31

---

8
B
ur²
(o²
200 + +0² /
ur
[V/(W++1))
x+]]|
28
8
Pk
Pet1 |
2
ur
Combining (104) and (06)
with 103
provides that
D
Bea+t Reat2lllPe:t Pk|
VS(W=11)1F
(107)
230
TVD
23302
+1
|P
Vf(W 11)
1 -- 2 |
o²
TVD
g2
+ 2r
|P
12c
V/(WW=
330
TvD |P
4,0
V ([(W++)) +22 +
TVD || |
2TVD)
233DD D
+
||Pk+1 (f(WW+1)1l
TO
350
1+ Bo
TVD
|Px+1
?f(Wa)l1
2F 2TVD)
2TVD)
3,00
(1 |
2TVD
T2D
+
1
VS(W++1)
v/(Wa)11 +
2TVD)
30
480
23VD
+
|Pk+11||
P
\S(W++1)I1
TVD
TO
Go
TVD \/(W)) 2
4,0
||
||
W
| 11
TVD
Bo3
TVD
2 D
+
|P
VJ x1]12+ 2,302
TO
Go
TVD
3
4,0
||
Vf(Wa)11
[
W +
| 11
TVD)
Bo3
TVD
43vD
||
V (W + 02
TO
In the inequality above, (a) sets u 3/2; (b) holds because
(1- 2TVD)
3,30
Bo
3a
3,3
Bo
Bo
1+
$
(108)
2TVD/
DD/
TVD
2T D
2T
TVD
and
3,50
2TVD
2TVD
3800
(1+
30
2T
[
1
1
(109)
/T/D/
3o
30
2T
2F 2F /D
30
and
(c) comes from
2
|| (fWW++1)]
(110)
TO
4/VD
43VD
|| [/((W))1 +
P 112 V[(W - V/(
TO
TO
43v/D
4312TVD
| (V)))))
[WE+1
W2
TO
σ
4
3
||
\V(W)))
||
22ll2.
303
TO
where the last inequality holds because 3
2D
Now get the claim. 362
32

---

H.2
Proof of Weight Decay Lemma
Lemma (Weight Decay Lemma), Suppose Assumption
and
hold. If 3 satisfies
CT
2
B < min
(111)
2(4L2 + o2
300
holds that
3co 2r
4
4L2
E BE
Pk+211
||| PRtt 2
f(W&)]
W
W&ll +
Proof of Lemma
6
The proof begins from the manipulation of the expected square norm of P8+2
P1 2
(112)
8 ((VS(W++1) k+11 + (7](W++1) Eat1l Pe+ill9)
11
3 Vf(W + + @ Px+1 + BVV =x++1)11
Bee+t
[1|(1
3 [f(W + @ P&+1 | + 8 8 [[WW/( Ex+111? 112]
[||(1
(1 Vf(W e @ Pk+1, V (V[((++))) +
+ 2-2ea
For the sake of simplicity, below use [g++1]; [V to denote the i-th coordinate of the gradient. According to Assumption the first term in the RHS (112) can be bounded by
3 ((WW+++)) + sk+1l) Pa-111
E Bexilll((1
(113)
8
=Rea
Σ
(1
+
(ext
LIEI
2/3
8²
je (19441l + (ERH1l)91) [Pa+al?
E8
Elentali [1gg+t1l + |Ex+1]
72
7
1EI
2,30
(ALL2 +02)
[PR+i]]
72
iE7
3,00
1
||
where the last inequality holds because of the selection of 3. To bound the third term in the RHS of
(12), we use the unbiased property [E (Assumption 3) and |P S 7 (Theorem
which lead to
Ka-=
8 [ + +E++1) O Pee., + EQT1)
2E
(114)
[(KK1, V](W+++) ([[W++))+&HH)) + -2
K
1 Vf(W+-1) - PE-1, (V +
-2Eenti
23 (PE+1. vf(W+++1) 2,22 Eieti KIV + (Vf(W-)))) + Ea+1) 1 o Patill
< 2,3 (Pe+1. vf(W + 2
Plugging
I13) and (14) into (12) yields
3,00
E E PP [| <
|P + + extill (115)
27
+ 28 (PM+1, [[(W++)))
33

---

Notice that the second term in the RHS of (115) can be upper bounded by Assumption 3 and inequality b and the third term can be bounded by Young's inequality
3co
3T +
23 (P&+1, V((W++1)) 2
||
(116)
00
Inequality (63).
116 and the condition
3 S
lead the result
3ea
3co
2
Be Pk+22 1 (1
Pk+1111 +
([WW++DI1+3332
(117)
2t
ca
Applying the inequality
IV [ V((W))I
(118)
(W W
on 117)
completes the proof.
H.3 Proof of Bounded Ps
Lemma (Bounded Saturation of Pt)). Suppose Assumption and hold. If 3 satisfies
2 1
min
(119)
2(4L2 + t0²)= 3c0" 3c03
it holds that
300 ||
413T,3-
Ex, ||| 22221122 S (1
11 +
(120)
and further
41L27AD
P1+1111)))) p2 max
(121)
c²0²
Proof of Lemma
7 Let i" == arg max; [Px42] We expand the expected square norm of Pk+2 by
Esg Pk+21
(122)
[1l[1 + B ((V)(WW) + sw) - Vf(W)) + Exl 1s+111E
8 VS(W&) exl) 2 Pk+1 (WW) +
[1(1
B Vf(We) kx) + =xl) 2 Petil E (W:)) + ex|3-]
[[e
5
+ 2E
(W()) + @ Pa+1 O (V/(WW) +x),+
For the sake of simplicity, below we use [gN] [WW() denote the i-th coordinate of the gradient. According to Assumption the first term in the RHS of (122) can be bounded by
8
Ee, [[(1
[V(We)) + Ex)) ④ P
(123)
3
Eee
(1
-
-[ga)e + [sx]x- (P
2,9
(tea1:1l9u]: + [sx]<|] + -e Bien Mlgol + [ew))11) |P
g2
Bi
2,00
82 + o²)
[P
72
3,00
|P
2T
34

---

where the last inequality holds because of the selection of 3. To bound the third term in the RHS
of p22.. we use the unbiased property of (ex) [[x]]-] 0 of Assumption 5 and | S in which lead to
Theorem 1
f
2
[11
V((W)) + Exl) @ PR+1 O B(VS(WW)) =
(124)
23
[P
V/(WW)) + sw]i-]
22
Vf(WW) + EW @ PA+1 @ +
=23 Vf(WW))] 232 Be, [IV)(W)) + O Pa+1 @ (VS(W))+ + ++)]-
T < 23 O VS(W))]] + F [V + +x]
Plugging
123 and 124) into 122) yields
Een |I| 2 1
(125)
3,c0
| + 3 [VS(WW) + + O VS(WW)];:
2r
3,80
|| + 3,3² (V(())) 2 Vf(W))) + 38
I
2T
where the last inequality comes from Assumption 5 and variance decomposition 66). Notice that the second term in the RHS of (125) can be upper bounded by Assumption 3 and inequality 663). and the third term can be bounded by Young's inequality
3ca
8,3
Beo
83T 11
23 Pa+1 O Vf(WW)), s
[P4+1l
[Vf(W&)] S
PPk41
[V
2T
co
2r
co
(126)
Inequality (266 and the condition 3 <
2
lead the result
3eg
Beo
10,T
388g2
Ee, Pk+2 I
[V
+
(127)
D
Beo
408L2>'D D
332
(1
)||Pk11
CO 41BLA73D
< (1 3co
|||
where the last inequality holds because the parameter chosen as 1.70 Telescoping over to 3ea
K 1 and using the fact that [[V I [[Vf(W&)]l 2 D. we achieve that
E P1113 s (1 3co Pol1 + 413L"T3D
41L2,AD c²O2
where the last inequality holds due the fact that Po 0. Now we complete the proof.
H.4 Proof of Tiki-Taka Descent Lemma
Lemma (Descent Lemma), Under Assumption it holds that
aTVD \f(WW)12
L
f(W++1) < f(W+)
| - WAll
(128)
20
2aT 2
TVD Vf(W&))1
+
ad
P
TVD 1P
D
Proof of Lemma 8 The L-smooth assumption (Assumption implies that
L [W+1
f(Wen) ((W) (VF(W,, We+T Wa) 2
W
(129)
35

---

f(WA) aTVD
[Vf(WAI1
o
| W
20
2aTVD 2 V((WW)11
W + oTVD
[ DD
a
where the equality comes from
aTVD V Vf(W)), W4+1 W4
o
(V)(W)), W6+1 - Wa)
(130)
aTvD
aT aTVD D
[/((W)]]|
[WK+1
W&ll
2a
20T /D
VD
aTVD VS(WA)1
Wh+1 - Wa
20TV
From the update rule of Tiki-Take and bounded saturation assumption (c.f. Assumption 4 the third term in the RHS of (129) can be bounded by
aTVD
[K++1
W4
v((Wa]l
(131)
2
TVD
VS(W&) 1 1PHil 0 Will
|P
2TVD
TVD
Q0
|P
V/(Wa)112 + ao /3VD
||| O W
TVD
TVD
v((WW) 7DvD |P W
TVD
TVD
00 TVD)
|P
v/(WW)1 + Od
1
TVD
Substituting [31 back into 129 yields
f(W++1) S f(W)) QT
L | - WAll?
(132)
20
20TVD
2
TVD
PR+1
V((W))
|P
TVD
TVD
which completes the proof.
H.S
Proof of Theorem 4: Convergence of Tiki-Taal -Taaa
With the lemmas above, we can begin the proof of Theorem 4
Proof of Theorem The statement that E||| [
S
p2 1112-4 6
has been shown in
max
Lemma 7 Therefore, it suffices to prove the convergence rate.
The proof begins by defining a Lyapunov function
VE = s(W,) - f σ
50 P V/(W)/ + Ler D)
PA-
(133)
8
P 1 [WW))]
Lero
Notice that the last term of VA has the iteration
E Pk+22 2 V f(W [1
(134)
(0)
E P & Vf(W))
1-
36

---

E Be-- PK| V Vf(W++)) - V
(6)
300
)| 41,31229
[V 1?G²
$
I Wxll
1 1- u
co
u
(e)
Beo
VS(WW)) + }| |k Ixx V/((W)] + 823L2
12
(1
Bco | - W&ll2
2r
co
where (a) uses
| + u| 2 -ー
|
1 for any vector 2; y E RDD and scalar 0 < < (b)
follows Lemma
bounded weight (c.f. Theorem 1. and Assumption
(c) specifies
fee
and
2r
the inequalities
Bos/t
Bcer + and
-- S 2.
By inequality 134 Lemma
6 and 8
we have
Ee [V+il
(135)
50
= =f(Wx+1) - - LT
Eg k++1 P142 V/(W
LerD 1 (ex.1ll/P4221 2k+2|1)
8
+
E Eeami PR
V (W++1)11
LCTO
< S(WW) - -r aTvD
L
/S((W)111
|W&+1 - 21al
20
2
2
TVD
|Pk++
[S(WW)]
||
TVD
TVD
0²
(11-
fo
|| TVD
4T,2,313/2
Vf(WW))
1
W&ll
2LT2D
2TVD)
Bo
250
23VD
P 112
|P Vf((W))]]
+ 28802
TVD
TO
20²
300
43T ||tt+1112+
4L23T VS(W))]
(1
k
[
22ll2 + 3,32
LeT D3/2
2r
Ca
2
Boo
823T?233
1273
)l
[V/((W)]1
|| Wo|l3)
2
2r
c
Bco
Rearranging inequality
(35) above, we have
EEN1 (iali(V411
Vx
(136)
aTVD
880
1643LTVD
//WWII
2a
D3/2
c²
L
2LTDD
8L3
2LT BOOVD
|| Well
2
D
3o
cooD
303
TVD
( |903 a0
4L D3/2
TVD)
|P&41
V/(WW)112
D3/2
TVD |Patal1
8²0²
0²
16g
T2D
2
DTVD
(1
163a²
1643L) ace
8o.
16 evDr
I+
22
L
where the second inequality holds because the selection of a and 9 as follows implies the coefficients of the third to fifth term of RHS are greater than 0
S D
5
< <
(137)
6L
d²
A
37

---

By taking B = 8
we bound
E R 14-i[VAc [V&+)]
V
(138)
VTVD
128
1312L2+3D
16
<
+
1
20
cD
c202
cVD)
aTvD
D
128
32
(1
16
max
( 8a 2
20
c²D
7²
cVD)
Taking expectation, averaging
(388
over k from to K and choosing the parameter as
1
Vo
a=0
(139)
d2L2K
D(1 16/(cVD))
deduce that
K
E
(140)
K
k=0
2o
Vo E[4++1]
aLLVD
1+ ../VDD
16
))
aTVDK
1 128//(DD) P2
max/ 7
S 20
aTVDK +OLTVD
Vo
1+ cVD)
16
1
128 (c2 -2222
V1 16/(cVD)
(f(W)) f*)o²L
K
1- 128/(c²D)
-22P2 72
maxx
(f(W))= - f+)0²2
K
1 - 33 /
where the last incquality holds when is sufficiently large. The proof is completed.
I Simulation Details and Additional Results
This section provides details about the experiments in Section 2.1 and 5 The analog training algorithms, including Analog SGD and toolkit AIHW KIT (27). which has Apa license; see github. www.oomm.////.... ai hwkit 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 CIFAR 10, are provided by PYTORCH, which has BSD license; see https::/gii thub. http:://gggccuuu..ooooooooo.tt
are provided by the open- source simulation
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 one hour, depending on the size of the model and the dataset.
Statistical Significance. The simulation reported in Figure 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.
I.1 Least squares problem
In Section 2. and 5.1 we considers the least squares problem on synthetic dataset and ground truth W*
E 2 whose elements are sampled from a Gaussian distribution with mean 0 and variance 2 2ma. Consider a matrix E DD size D 40 and Dout = 100 whose elements are sampled from a Gaussian distribution with variance 3- The label E D.. is generated by AW* where W' are sampled from standard Gaussian distribution with ofy..
The problem can be formulated by
1
min WERD
f(W): = 2 IAA - b11 = -020-1111 [IA(W - W
(141)
38

---

Digital SGD Anal GD Tiki-Taka
Analog GD
20
Tiki
Frequently
Frequently
15
10-
2-
0-
-1.0
-0.5
0.0
0.5
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Weight Values
Saturation
Figure 7: (Left) Distribution the model weight, ie. {[ I). (Right) Saturation
distribution after training, i.c. [[[Wxll//:iiE])
During the training, the noise with variance level og is injected into the gradient. For digital SGD and the proposed Analog SGD dynamic, we add a Gaussian noise with mean 0 and variance og to the gradient. For Analog SGD in AIHWKIT, we add a Gaussian noise with mean O and variance o into W when computing the gradient. The constant 8A defined as the mean of the singular value of A, which is introduced since the noise on W is amplified by A A, whose impact is approximately proportional A's singular value.
In Figure D the response step size AWmin while T = 3. The maximum bit length is 800. The variance are of 0.30². o 1.002. ow 0.45². og (0.01/D)².
In Figure 3 the learning rate is set as a =3c-2. The response step size Awmin is set so that the 300, when the is changing. The maximum bit
number of states is always 300, i.c. 2T 2r/AWmin length is 300. The variance are set as 2 = 0.302, o = 0.50², ow- = 0.30, o = 0.10.
1.2 Classification problem
We conduct training simulations of image classification tasks on series of real datasets. The gradient-based analog training algorithms, including Analog SGD and Tiki-Taka, are implemented by AIHWKIT. In the real implementation of Tiki-Taka, only a few columns rows of Ps are transferred per time to W to balance the communication and computation. our simulations, we transfer 1 column every time. The response step size is Awmin =l-33.
The other setting follows the standard settings of AIHW KIT, including output noise (0.5 % of the quantization bin width), quantization and clipping (output range set 20, output noise 0.1, and input and output quantization to 8 bits). Noise and bound management techniques are used in [66]. learnable scaling factor is set after each analog layer, which is updated using digital SGD.
3-FC/ MNIST. Following the setting in [1], we train model with 3 fully connected layers. The hidden sizes are 256 and 128. The activation functions are Sigmoid. The learning rates are a 0.1 for SGD, a 0.05, 3 0.01 for Analog SGD Tiki-Taka. The batch size 10 for all algorithms.
CNN / MNIST. We train a convolution neural network. which contains 2-convolutional layers, 2- 2amax max-pooling layers, and 2-fully connected layers. The activation functions are Tanh. The learning rates are set as a = 0.1 for digital SGD, a = 0.05, B = 0.01 for Analog SGD or Tiki-Take The batch size is 8 for all algorithms.
Resnet CIFARIO. We train different models from Resnet family, including Resnet18, 34, and 50, The base model is pre-trained ImageNet dataset. The learning rates set 0.15 for digital SGD, a = 0.075, = 0.01 for Analog SGD or Tiki-Taka. The batch size 128 for all algorithms.
I.3 Verification of bounded saturation
To further justify the Assumption 4 we visualize the weight distribution of the trained 3-FC model; see Figure The results show that despite the absence projection or saturation, the weights trained by digital SGD are bounded, which means that it is always possible to find an to represent all the weights in analog devices without being clipped. In the right Figure 7 W Wmax for Analog SGD could be chosen 0.2r. Without constraint the Wmax. Tiki - Taka has a large W Wmax.
39

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state the claims made, including the contributions made in the paper and important assumptions and limitations.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discussed in the Conclusion section.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All have been clearly listed.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We describe all the implementation details, including datasets, models, and hyperparameters of our simulations in Appendix !
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: The code of simulation implementation available github. com/
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We describe all the implementation details, including datasets, models, and hyperparameters of our simulations Appendix !
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The factors of variability, the method for calculating the error bar, the assump- tion on the distributions, and the type of error bar are stated Appendix
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
40

---

Justification:
The computation resource requirements and estimated running time are clearly stated Appendix
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:p/:/oourrps..ccoubbb//aaaas
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: there is no societal impact of the work performed.
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Inswer:[NA]
Justification: The paper poses no such risks.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We explicitly state the license of the code and data used in Appendix
!
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not release new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects. and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA].
Justification: the paper does not involve crowdsourcing nor research with human subjects.
41


Reviews:
[{"review_id": "ZJFBokMkxX", "reviewer": "Reviewer_G3ws", "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.", "questions": "See weaknesses", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-- The proof the convergence of Analog SGD and showing that noise and asymmetric updates together lead to its asymptotic error. \n\n-- Demonstration of Tiki-Taka algorithm precisely converging to the critical point by mitigating the drift caused by asymmetric bias and noise.\n\n-- Empirical simulations using both synthetic and real datasets to confirm the presence of asymptotic error in Analog SGD and to show that Tiki-Taka outperforms Analog SGD.", "weaknesses": "-- The experimental results were obtained on rather small datasets. It'd be great to include the results on ImageNet.\n\n-- 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time spent in reviewing our paper and for the valuable comments. \n\nThe weaknesses identified by the reviewer mainly focus on the datasets and the model archtecture used in the experimental results  as follows. \n\n> - The experimental results were obtained on rather small datasets. It'd be great to include the results on ImageNet.\n> - 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?\n\nAlbeit the main focus of this paper is on the theoretical understanding of analog training, we have still conducted additional experiments during the limited rebuttal period.\n\n\nTo demonstrate the efficiency of Tiki-Taka under various situations, we conducted more simulations on different datasets and model architectures, including MobileNetV2 and large/small MobileNetV3  on CIFAR10/CIRAR100 datasets.\nThe results are listed as follows.\n\nTable 1: Training on CIFAR10 dataset\n||Digital SGD|Analog SGD| Tiki-Taka\n|:-:|:-:|:-:|:-:|\n|MobileNetV2|94.47|93.88|94.24\n|MobileNetV3-Small|93.21|92.47|93.37\n|MobileNetV3-Large|94.78|94.02|94.63\n\nTable 2: Training on CIFAR100 dataset\n||Digital SGD|Analog SGD| Tiki-Taka\n|:-:|:-:|:-:|:-:|\n|MobileNetV2|79.24|78.34|78.75\n|MobileNetV3-Small|76.41|76.13|76.45\n|MobileNetV3-Large|79.62|79.67|80.05\n\nThe results show that Tiki-Taka always achieves better test accuracy than Analog SGD by about 0.5% in almost all cases, which is consistent with our conclusion. Due to the limited time and inadequate GPU resources, we can not perform simulations on a larger scale like training on ImageNet dataset during the rebuttal period.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4XmAXNjQA3", "reviewer": "Reviewer_gG9b", "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.", "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?\n- How does it scale to large batch sizes?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well organized and easy to follow.\n- Concrete theoretical foundings on the proposed algorithm.\n- Benchmark sets and the target network look reasonable, and the result also sound and look promising.\n- Showing cases on various analog devices like ReRAM, etc.", "weaknesses": "- It'd be great if authors present how computations (ops) can be realized on the analog devices.\n- Needs comparison to other analog SGD methods, like [16] or [22].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging the merits of our work. Our point-to-point response to your comments and suggestions follow next.\n\n> W1. It'd be great if authors present how computations (ops) can be realized on the analog devices.\n\nThe workload of forward and backward computation can be separated into two categories: matrix-vector multiplication (MVM) operations and non-MVM operations. \nIn AIM computation hardware, the MVM operations are implemented in analog in-memory arrays, while the other non-MVM operations are conducted in digital circuits.\n\n\nWe illustrate in the attached PDF in Author Rebuttal on how the MVM is implemented by analog devices. In a $3\\times 3$ resistive crossbar array, a matrix $W$ is represented by the conductance of resistor at the crosspoint, where the $(i,j)$-th element of $W$ is represented by the conductance of the $(i,j)$-th resistor. To conduct an MVM operation $z = Wx$, voltage $x_{j}$ is applied between $j$-th and $(j+1)$-th row, where the subscript $j$ is used to imply the $j$-th coordinate. By Ohm's law, the current is $I_{ij}=W_{ij}x_{j}$; and by Kirchhoff's law,  the total current on the $i$-th column is \n$\\sum_{j}I_{ij}=\\sum_{j}W_{ij}x_{j}$.\n\n\n\n> W2. Needs comparison to other analog SGD methods, like [16] or [22].\n\nNote that the goal of this paper is not to develop the state-of-the-art analog training algorithm, but to *understand why* the vanilla SGD training on analog device does not work as expected, and why some correction operations used in the heuristic algorithms such as Tiki-Take work, through the unified lens of asymmetric updates on analog devices. We hope this theoretical understanding can contribute to future developments of analog training algorithms, hardware and material.\n\nIn this context, in the introduction, we have compared the studied algorithm Tiki-Taka (TT-v1) with TT-v2 [22] and TT-v3/v4 [16] (c.f. Sec 1.2). Both [16] and [22] are variants of Tiki-Taka which were proposed to deal with some practical issues in analog training such as the reading noise and non-perfect zero-shifting issues. Since our focus in this paper is on understanding the impact of asymmetric updates on analog devices, in the simulations parts, we omitted the comparison between our paper and [16][22]. \n\nNevertheless, as requested by the reviewer, we have now compared these four methods in the same setting as that in Section 5.3. We train a CNN model under $\\tau=0.7$ on MNIST dataset, whose results are listed below. TT-v2--v4 are always better than TT-v1.\n\n|Digital SGD|Analog SGD| TT-v1 | TT-v2 [22] | TT-v3 [16] | TT-v4 [16]\n|:-:|:-:|:-:|:-:|:-:|:-:|\n|99.24%|82.17%|98.56%|98.94%|98.91%|99.01%\n\n> Q1. How can floating-point (FP) be implemented by analog devices?\n\nThis is a great question! The FP is implemented in the digital domain [12, 31].\nIn the MVM computations, the weights are represented by conductance, while the input and output are represented by current signals. Therefore, the FP is unnecessary for MVM operations.\nThe other operations involving FP computation are non-MVM ones, which are conducted in digital domains. We will add a remark in the revision to clarify it.\n\n> Q2. How does it scale to large batch sizes?\n> \n\nThis is an interesting point! Implementing mini-batch gradient computation on the analog devices are significantly different from that on the digital devices. To implement the large batch in AIM computation hardware, each gradient in a batch is computed sequentially and accumulated to $W_k$ (for Analog SGD) or $P_k$ (for Tiki-Taka). For example, we use batch size 8 in FCN/CNN training and 128 for Resnet training. Studying the impact of batch size on the convergence of analog training will be an interesting future direction!\n\nWe hope the above detailed clarifications can fully resolve your concerns.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tn9uy9Uvx0", "reviewer": "Reviewer_dVXd", "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.", "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?\n\nDoes the AIHWKit very faithfully simulate real analog devices? What are the strengths and limitations of this tool?\n\nThe 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?\n\nI 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?\n\nI 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?\n\nIs 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": "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?", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The topic tackled by the paper is very important. Analog computing could lead to energy efficiency gains of several orders of magnitude for both inference and training, compared to digital neural networks on GPUs. Developing appropriate theoretical models of analog computing to better understand the behavior of these analog systems is of utmost importance. To my knowledge, this paper is the first attempt to study the convergence properties of analog SGD.\n\nThe paper is clear and the study is thorough.", "weaknesses": "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.\nThis, 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.\n\nThe 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.\n\nReference:\n[1] Momeni, Ali, et al. \"Training of Physical Neural Networks.\" arXiv preprint arXiv:2406.03372 (2024).\n\n\nMinor 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We really appreciate your recognizing the importance of our work and for helpful suggestions. Please find our point-by-point reply to your comments below.\n> W1. There is no discussion about which models are accurate and widely accepted.\nAs the reviewer correctly pointed out, adding a discussion about the accuracy of the models are important. The applicability of our analysis relies on the following two analog hardware models: \n- Asymmetric update model (6): The update (6) omits some non-ideality, like cycle-to-cycle/device-to-device variation and analog-digital conversion error [12][27]\n- ALD response model (8): ALD models assume the response factor is a linear function, which is widely adopted in the literature [16,19,23]. \n\nIt explains why the proposed dynamic does not match the real behaviors perfectly in Fig 2. We will clarify the potential error raised from the simplified model in the revision. We hope the discussion helps the readers better evaluate the scope of applicability of the theory.  \n\n> W2.  Including these other PNN training methods would add a lot of value, by broadening the potential impact of the work.\n\nThank you for pointing out this interesting direction and suggesting a recent work. Indeed, this is inspiring! To establish the connection between our work and the PNN training, we will add a paragraph to briefly review the progress as follows in literature review section.\n\n> We are especially interested in AIMC hardware with resistive crossbar arrays. It is a specific implementation of physical neural network (PNN) [R1,R2]. PNN is a model implemented by a physical system involving tunable analog quantity. The quantity is adjusted to implement the learning on some specific tasks. Various hardware is capable of supporting PNN, such as holographic grating [R3], wave-based systems [R4], and photonic networks [R5], to name a few.\n\n[R1] Wright, et al. \"Deep physical neural networks trained with backpropagation.\"\n\n[R2] Momeni, et al. \"Training of Physical Neural Networks.\"\n\n[R3] Psaltis, et al. \"Holography in artificial neural networks.\"\n\n[R4] Hughes, et al. \"Wave physics as an analog recurrent neural network.\"\n\n[R5] Tait, et al. \"Neuromorphic photonic networks using silicon photonic weight banks.\"\n\n> W3. Where do the figures of 4.6 million for training LLaMA and GPT-3 come from?\n\nThanks for the careful reading! The cost is estimated by multiplying the required GPU hours by the AWS price per hour, where the GPU hours are reported in [1]. To avoid confusion, we will rephrase this sentence with the following one.  \n> For example, it requires 184 thousand GPU hours to train an LLAMA2 7 billion model [R6], and this time increases to 1.7 million GPU hours for its 70 billion version [1].\n\n[R6] Touvron, et al. \"Llama 2: Open foundation and fine-tuned chat models.\"\n\n> Q1. Is the model of Eq6 for weight update asymmetry a widely accepted model?\n\nThe answer is affirmative. For example, [16, 52] have already demonstrated different factors scale the update in different weight state. \n\n> Q2. Does the AIHWKit faithfully simulate real analog devices?\n\nAIHWKit is capable of providing real simulations across different granular levels, including IO noise, pulse update, update variation, response factor, and A/D discretization, to name a few. One of the limitations is the significant overhand of detailed simulation and inadequate multi-GPU parallel support, which make it time-consuming to conduct large-scale simulations.\n\n> Q3. Why can the weights be negative?\nThis is just for the mathematical convenience. To implement the negative weight on analog devices, two resistive crossbar arrays, a main array, and a reference array are set. The weight is represented by the difference of the two conductances multiplied by a scaling factor, which can be negative. \n\nThanks for pointing this out! We ignored this detail in our dynamic, but we will clarify it in the revision. \n\n> Q4. Can we conclude from Eq5 that $W_k$ converges? If not, why is Eq.5 important for studying the convergence of (digital) SGD?\n\nIn the convergence study of (digital) SGD, there are typically two types of convergence: the convergence to the stationary point (e.g., $W^*$ such that $\\nabla f(W^*)=0$) or the convergence to the optimal solution (e.g., $W^*$ such that $W^*\\in \\arg\\min_W f(W)$). Without additional assumptions like convexity, the convergence to the stationary point might be the best we can hope for in the worst case. Therefore, with a set of properly choosing decreasing stepsizes, Eq5 has been commonly used as a metric to assess the convergence to the stationary point of SGD; see [20]. As a result, we also use the metric of Eq5 to demonstrate the convergence of analog algorithms. \n\n> Q5. Why is Thm 2 important?\n\nCompared to Thm 3, Thm 2 is important since it serves as another main component to reveal the performance limit of Analog SGD. Thm 3 claims that there exist a *bad* situation that Analog SGD has an asymptotic error but it does not ensure it is the *worst* case. Combining Thm 2 and 3, we claim that $4\\sigma^2 S_K$ is the worst-case possible asympotic error, which provide a better insight.\n\n> Q6. Is the theory provided in this paper limited to backpropagation? \n\nThanks for the inspiring question!\nWe believe our theory can be adapted to other analog training algorithms since algorithms like equilibrium propagation (EP) adopt other methods to determine the update directions. To replace the gradient in our analysis with a given update direction, we can still study the convergence using similar techniques. We will seriously consider this as a future direction.\n\n> Q7. Could the AIHWKit be employed with these other training algorithms?\n\nThe answer is affirmative. AIHWKit enables multiple levels of simulation granularity. To implement other algorithms like EP, one needs to modify the algorithm-level code.\n\nWith the above clarifications, we hope that our responses addressed all your questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank the reviewers for their constructive comments. Comments from all the reviewers were really helpful, which we believe have been fully addressed in detail in our rebuttal. 
    
The attached PDF is the illustration to explain how analog devices implement MVM operations (see the response to Reviewer gG9b).
    
We look forward to the rolling dicussion and further engagement with the reviewers and area chair(s)!

Meta-review: 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.
Decision: Accept (poster)