Quasi-Global Momentum:
Accelerating Decentralized Deep Learning on Heterogeneous Data

Tao Linto
Sai Praneeth Karimireddyto
Sebastian U. Stichto
Martin Jaggito

toEPFL, Lausanne, Switzerland

Tao<EMAIL_ADDRESS>
Machine Learning, ICML

[Andreux et al., 2020]
Andreux, M., du Terrail, J. O., Beguier, C., and Tramel, E. W.
Siloed federated learning for multi-centric histopathology datasets.
In Domain Adaptation and Representation Transfer, and
Distributed and Collaborative Learning, pp.  129–139. Springer, 2020.

[Arjevani et al., 2019]
Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., and
Woodworth, B.
Lower bounds for non-convex stochastic optimization.
arXiv preprint arXiv:1912.02365, 2019.

[Assran et al., 2019]
Assran, M., Loizou, N., Ballas, N., and Rabbat, M.
Stochastic gradient push for distributed deep learning.
In International Conference on Machine Learning, pp.  344–353. PMLR, 2019.

[Balu et al., 2020]
Balu, A., Jiang, Z., Tan, S. Y., Hedge, C., Lee, Y. M., and Sarkar, S.
Decentralized deep learning using momentum-accelerated consensus.
arXiv preprint arXiv:2010.11166, 2020.

[Bottou et al., 2016]
Bottou, L., Curtis, F. E., and Nocedal, J.
Optimization methods for large-scale machine learning.
arXiv preprint arXiv:1606.04838, 2016.

[Boyd et al., 2006]
Boyd, S., Ghosh, A., Prabhakar, B., and Shah, D.
Randomized gossip algorithms.
IEEE Transactions on Information Theory, 520
(6):0 2508–2530, 2006.

[Chrabaszcz et al., 2017]
Chrabaszcz, P., Loshchilov, I., and Hutter, F.
A downsampled variant of ImageNet as an alternative to the CIFAR
arXiv preprint arXiv:1707.08819, 2017.

[Das et al., 2020]
Das, R., Acharya, A., Hashemi, A., Sanghavi, S., Dhillon, I. S., and Topcu, U.
Faster non-convex federated learning via global and local momentum.
arXiv preprint arXiv:2012.04061, 2020.

[Defazio & Bottou, 2019]
Defazio, A. and Bottou, L.
On the ineffectiveness of variance reduced optimization for deep
In Advances in Neural Information Processing Systems, 2019.

[Dekel et al., 2012]
Dekel, O., Gilad-Bachrach, R., Shamir, O., and Xiao, L.
Optimal distributed online prediction using mini-batches.
The Journal of Machine Learning Research, 13:0
165–202, 2012.

[Deng et al., 2009]
Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L.
ImageNet: A Large-Scale Hierarchical Image Database.
In Proceedings of the IEEE/CVF Conference on Computer Vision
and Pattern Recognition (CVPR), 2009.

[Diao et al., 2021]
Diao, E., Ding, J., and Tarokh, V.
HeteroFL: Computation and communication efficient federated
learning for heterogeneous clients.
In International Conference on Learning Representations, 2021.
URL <https://openreview.net/forum?id=TNkPBBYFkXg>.

[Gitman et al., 2019]
Gitman, I., Lang, H., Zhang, P., and Xiao, L.
Understanding the role of momentum in stochastic gradient methods.
In Advances in Neural Information Processing Systems, pp.  9633–9643, 2019.

[Goyal et al., 2017]
Goyal, P., Dollár, P., Girshick, R., Noordhuis, P., Wesolowski, L., Kyrola,
A., Tulloch, A., Jia, Y., and He, K.
Accurate, large minibatch SGD: Training ImageNet in 1 hour.
arXiv preprint arXiv:1706.02677, 2017.

[Haddadpour et al., 2021]
Haddadpour, F., Kamani, M. M., Mokhtari, A., and Mahdavi, M.
Federated learning with compression: Unified analysis and sharp
In International Conference on Artificial Intelligence and
Statistics, pp.  2350–2358. PMLR, 2021.

[He et al., 2020]
He, C., Li, S., So, J., Zhang, M., Wang, H., Wang, X., Vepakomma, P., Singh,
A., Qiu, H., Shen, L., et al.
Fedml: A research library and benchmark for federated machine
arXiv preprint arXiv:2007.13518, 2020.

[He et al., 2015]
He, K., Zhang, X., Ren, S., and Sun, J.
Delving deep into rectifiers: Surpassing human-level performance on
imagenet classification.
In Proceedings of the IEEE international conference on computer
vision, pp.  1026–1034, 2015.

[He et al., 2016]
He, K., Zhang, X., Ren, S., and Sun, J.
Deep residual learning for image recognition.
In Proceedings of the IEEE Conference on Computer Vision and
Pattern Recognition, pp.  770–778, 2016.

[He et al., 2019]
He, T., Zhang, Z., Zhang, H., Zhang, Z., Xie, J., and Li, M.
Bag of tricks for image classification with convolutional neural
In Proceedings of the IEEE/CVF Conference on Computer Vision
and Pattern Recognition, pp.  558–567, 2019.

[Hendrikx et al., 2019]
Hendrikx, H., Bach, F., and Massoulié, L.
Accelerated decentralized optimization with local updates for smooth
and strongly convex objectives.
In International Conference on Artificial Intelligence and
Statistics, pp.  897–906. PMLR, 2019.

[Hoffer et al., 2018]
Hoffer, E., Banner, R., Golan, I., and Soudry, D.
Norm matters: efficient and accurate normalization schemes in deep
In Advances in Neural Information Processing Systems, pp.  2160–2170, 2018.

[Hsieh et al., 2020]
Hsieh, K., Phanishayee, A., Mutlu, O., and Gibbons, P.
The non-iid data quagmire of decentralized machine learning.
In International Conference on Machine Learning, pp.  4387–4398. PMLR, 2020.

[Hsu et al., 2019]
Hsu, T.-M. H., Qi, H., and Brown, M.
Measuring the effects of non-identical data distribution for
federated visual classification.
arXiv preprint arXiv:1909.06335, 2019.

[Huang et al., 2016]
Huang, G., Liu, Z., Weinberger, K. Q., and van der Maaten, L.
Densely connected convolutional networks.
arXiv preprint arXiv:1608.06993, 2016.

[Ioffe & Szegedy, 2015]
Ioffe, S. and Szegedy, C.
Batch normalization: Accelerating deep network training by reducing
internal covariate shift.
arXiv preprint arXiv:1502.03167, 2015.

[Kairouz et al., 2019]
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N.,
Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al.
Advances and open problems in federated learning.
arXiv preprint arXiv:1912.04977, 2019.

[Karimireddy et al., 2020]
Karimireddy, S. P., Jaggi, M., Kale, S., Mohri, M., Reddi, S. J., Stich, S. U.,
and Suresh, A. T.
Mime: Mimicking centralized stochastic algorithms in federated
arXiv preprint arXiv:2008.03606, 2020a.

[Karimireddy et al., 2020]
Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S. J., Stich, S. U., and
Suresh, A. T.
Scaffold: Stochastic controlled averaging for on-device federated
In International Conference on Machine Learning. PMLR,

[Kempe et al., 2003]
Kempe, D., Dobra, A., and Gehrke, J.
Gossip-based computation of aggregate information.
In 44th Annual IEEE Symposium on Foundations of Computer
Science, 2003. Proceedings., pp.  482–491. IEEE, 2003.

[Koloskova et al., 2019]
Koloskova, A., Stich, S. U., and Jaggi, M.
Decentralized stochastic optimization and gossip algorithms with
compressed communication.
In International Conference on Machine Learning, volume 97,
pp.  3479–3487. PMLR, 2019.

[Koloskova et al., 2020]
Koloskova, A., Lin, T., Stich, S. U., and Jaggi, M.
Decentralized deep learning with arbitrary communication compression.
In International Conference on Learning Representations,
URL <https://openreview.net/forum?id=SkgGCkrKvH>.

[Koloskova et al., 2020]
Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., and Stich, S. U.
A unified theory of decentralized SGD with changing topology and
local updates.
In International Conference on Machine Learning. PMLR,

[Konecnỳ et al., 2016]
Konecnỳ, J., McMahan, H. B., Yu, F. X., Richtarik, P., Suresh, A. T.,
and Bacon, D.
Federated learning: Strategies for improving communication
arXiv preprint arXiv:1610.05492, 2016.

[Kong et al., 2021]
Kong, L., Lin, T., Koloskova, A., Jaggi, M., and Stich, S. U.
Consensus control for decentralized deep learning.
In International Conference on Machine Learning. PMLR, 2021.

[Krizhevsky & Hinton, 2009]
Krizhevsky, A. and Hinton, G.
Learning multiple layers of features from tiny images.

[Lee et al., 2015]
Lee, J. D., Lin, Q., Ma, T., and Yang, T.
Distributed stochastic variance reduced gradient methods and a lower
bound for communication complexity.
arXiv preprint arXiv:1507.07595, 2015.

[Li et al., 2021]
Li, X., Jiang, M., Zhang, X., Kamp, M., and Dou, Q.
FedBN: Federated learning on non-IID features via local batch
In International Conference on Learning Representations, 2021.
URL <https://openreview.net/forum?id=6YEQUn0QICG>.

[Lian et al., 2017]
Lian, X., Zhang, C., Zhang, H., Hsieh, C.-J., Zhang, W., and Liu, J.
Can decentralized algorithms outperform centralized algorithms? a
case study for decentralized parallel stochastic gradient descent.
In Advances in Neural Information Processing Systems, pp.  5336–5346, 2017.

[Lian et al., 2018]
Lian, X., Zhang, W., Zhang, C., and Liu, J.
Asynchronous decentralized parallel stochastic gradient descent.
In International Conference on Machine Learning, pp.  3043–3052. PMLR, 2018.

[Lin et al., 2020]
Lin, T., Kong, L., Stich, S., and Jaggi, M.
Extrapolation for large-batch training in deep learning.
In International Conference on Machine Learning, pp.  6094–6104. PMLR, 2020a.

[Lin et al., 2020]
Lin, T., Kong, L., Stich, S. U., and Jaggi, M.
Ensemble distillation for robust model fusion in federated learning.
In Advances in Neural Information Processing Systems,

[Lin et al., 2020]
Lin, T., Stich, S. U., Patel, K. K., and Jaggi, M.
Don't use large mini-batches, use local SGD.
In International Conference on Learning Representations,
URL <https://openreview.net/forum?id=B1eyO1BFPr>.

[Liu et al., 2020]
Liu, H., Brock, A., Simonyan, K., and Le, Q. V.
Evolving normalization-activation layers.
arXiv preprint arXiv:2004.02967, 2020.

[Lu et al., 2019]
Lu, S., Zhang, X., Sun, H., and Hong, M.
GNSD: A gradient-tracking based nonconvex stochastic algorithm for
decentralized optimization.
In 2019 IEEE Data Science Workshop (DSW), pp.  315–321.
IEEE, 2019.

[Lu & De Sa, 2020]
Lu, Y. and De Sa, C.
Moniqua: Modulo quantized communication in decentralized sgd.
In International Conference on Machine Learning, 2020.

[Lucas et al., 2019]
Lucas, J., Sun, S., Zemel, R., and Grosse, R.
Aggregated momentum: Stability through passive damping.
In International Conference on Learning Representations, 2019.
URL <https://openreview.net/forum?id=Syxt5oC5YQ>.

[Luo et al., 2019]
Luo, P., Wang, X., Shao, W., and Peng, Z.
Towards understanding regularization in batch normalization.
In International Conference on Learning Representations, 2019.
URL <https://openreview.net/forum?id=HJlLKjR9FQ>.

[Ma & Yarats, 2019]
Ma, J. and Yarats, D.
Quasi-hyperbolic momentum and Adam for deep learning.
In International Conference on Learning Representations, 2019.
URL <https://openreview.net/forum?id=S1fUpoR5FQ>.

[McMahan et al., 2017]
McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A.
Communication-efficient learning of deep networks from decentralized
In Artificial Intelligence and Statistics, pp.  1273–1282,

[Mosbach et al., 2021]
Mosbach, M., Andriushchenko, M., and Klakow, D.
On the stability of fine-tuning {bert}: Misconceptions,
explanations, and strong baselines.
In International Conference on Learning Representations, 2021.
URL <https://openreview.net/forum?id=nzpLWnVAyah>.

[Nadiradze et al., 2020]
Nadiradze, G., Sabour, A., Alistarh, D., Sharma, A., Markov, I., and Aksenov,
SwarmSGD: Scalable decentralized SGD with local updates.
arXiv preprint arXiv:1910.12308, 2020.

[Nedić et al., 2018]
Nedić, A., Olshevsky, A., and Rabbat, M. G.
Network topology and communication-computation tradeoffs in
decentralized optimization.
Proceedings of the IEEE, 1060 (5):0 953–976,

[Neglia et al., 2020]
Neglia, G., Xu, C., Towsley, D., and Calbi, G.
Decentralized gradient methods: does topology matter?
In International Conference on Artificial Intelligence and
Statistics, 2020.

[Pan et al., 2020]
Pan, T., Liu, J., and Wang, J.
D-SPIDER-SFO: A decentralized optimization algorithm with faster
convergence rate for nonconvex problems.
In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 34, pp.  1619–1626, 2020.

[Pu & Nedić, 2020]
Pu, S. and Nedić, A.
Distributed stochastic gradient tracking methods.
Mathematical Programming, pp.  1–49, 2020.

[Rosenbrock, 1960]
Rosenbrock, H.
An automatic method for finding the greatest or least value of a
The Computer Journal, 30 (3):0 175–184, 1960.

[Sanh et al., 2019]
Sanh, V., Debut, L., Chaumond, J., and Wolf, T.
DistilBERT, a distilled version of BERT: smaller, faster, cheaper
and lighter.
arXiv preprint arXiv:1910.01108, 2019.

[Santurkar et al., 2018]
Santurkar, S., Tsipras, D., Ilyas, A., and Madry, A.
How does batch normalization help optimization?
In Advances in Neural Information Processing Systems, pp.  2483–2493, 2018.

[Scaman et al., 2017]
Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., and Massoulié, L.
Optimal algorithms for smooth and strongly convex distributed
optimization in networks.
In International Conference on Machine Learning. PMLR, 2017.

[Scaman et al., 2018]
Scaman, K., Bach, F., Bubeck, S., Massoulié, L., and Lee, Y. T.
Optimal algorithms for non-smooth distributed optimization in
In Advances in Neural Information Processing Systems, pp.  2740–2749, 2018.

[Shi et al., 2015]
Shi, W., Ling, Q., Wu, G., and Yin, W.
Extra: An exact first-order algorithm for decentralized consensus
SIAM Journal on Optimization, 250 (2):0
944–966, 2015.

[Simonyan & Zisserman, 2014]
Simonyan, K. and Zisserman, A.
Very deep convolutional networks for large-scale image recognition.
arXiv preprint arXiv:1409.1556, 2014.

[Singh et al., 2020]
Singh, N., Data, D., George, J., and Diggavi, S.
SQuARM-SGD: Communication-efficient momentum SGD for
decentralized optimization.
arXiv preprint arXiv:2005.07041, 2020.

[Sutskever et al., 2013]
Sutskever, I., Martens, J., Dahl, G., and Hinton, G.
On the importance of initialization and momentum in deep learning.
In International Conference on Machine Learning, pp.  1139–1147. PMLR, 2013.

[Taheri et al., 2020]
Taheri, H., Mokhtari, A., Hassani, H., and Pedarsani, R.
Quantized decentralized stochastic learning over directed graphs.
In International Conference on Machine Learning, pp.  9324–9333. PMLR, 2020.

[Tan & Le, 2019]
Tan, M. and Le, Q.
Efficientnet: Rethinking model scaling for convolutional neural
In International Conference on Machine Learning, pp.  6105–6114. PMLR, 2019.

[Tang et al., 2018]
Tang, H., Gan, S., Zhang, C., Zhang, T., and Liu, J.
Communication compression for decentralized training.
In Advances in Neural Information Processing Systems,
volume 31, pp.  7652–7662, 2018a.

[Tang et al., 2018]
Tang, H., Lian, X., Yan, M., Zhang, C., and Liu, J.
$D^2$: Decentralized training over decentralized data.
In International Conference on Machine Learning,

[Tsitsiklis, 1984]
Tsitsiklis, J. N.
Problems in decentralized decision making and computation.
Technical report, Massachusetts Inst of Tech Cambridge Lab for
Information and Decision Systems, 1984.

[Vogels et al., 2020]
Vogels, T., Karimireddy, S. P., and Jaggi, M.
Powergossip: Practical low-rank communication compression in
decentralized deep learning.
In Advances in Neural Information Processing Systems, 2020.

[Wang et al., 2019]
Wang, J., Sahu, A. K., Yang, Z., Joshi, G., and Kar, S.
MATCHA: Speeding up decentralized SGD via matching decomposition
arXiv preprint arXiv:1905.09435, 2019.

[Wang et al., 2020]
Wang, J., Liu, Q., Liang, H., Joshi, G., and Poor, H. V.
Tackling the objective inconsistency problem in heterogeneous
federated optimization.
In Advances in Neural Information Processing Systems,

[Wang et al., 2020]
Wang, J., Sahu, A. K., Joshi, G., and Kar, S.
Exploring the error-runtime trade-off in decentralized optimization.
In Asilomar Conference on Signals, Systems, and Computers,

[Wang et al., 2020]
Wang, J., Tantia, V., Ballas, N., and Rabbat, M.
SlowMo: Improving communication-efficient distributed SGD with
slow momentum.
In International Conference on Learning Representations,
URL <https://openreview.net/forum?id=SkxJ8REYPH>.

[Wolf et al., 2019]
Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, A., Cistac, P.,
Rault, T., Louf, R., Funtowicz, M., et al.
Huggingface's transformers: State-of-the-art natural language
arXiv preprint arXiv:1910.03771, 2019.

[Wu & He, 2018]
Wu, Y. and He, K.
Group normalization.
In Proceedings of the European conference on computer vision
(ECCV), pp.  3–19, 2018.

[Xiao & Boyd, 2004]
Xiao, L. and Boyd, S.
Fast linear iterations for distributed averaging.
Systems & Control Letters, 530 (1):0 65–78,

[Xin et al., 2020]
Xin, R., Khan, U. A., and Kar, S.
Variance-reduced decentralized stochastic optimization with
accelerated convergence.
IEEE Transactions on Signal Processing, 68:0
6255–6271, 2020.

[Yan et al., 2018]
Yan, Y., Yang, T., Li, Z., Lin, Q., and Yang, Y.
A unified analysis of stochastic momentum methods for deep learning.
In International Joint Conference on Artificial Intelligence,
pp.  2955–2961, 2018.
URL <https://doi.org/10.24963/ijcai.2018/410>.

[Yu et al., 2019]
Yu, H., Jin, R., and Yang, S.
On the linear speedup analysis of communication efficient momentum
SGD for distributed non-convex optimization.
In International Conference on Machine Learning, 2019.

[Yuan & Alghunaim, 2021]
Yuan, K. and Alghunaim, S. A.
Removing data heterogeneity influence enhances network topology
dependence of decentralized sgd.
arXiv preprint arXiv:2105.08023, 2021.

[Yuan et al., 2020]
Yuan, K., Alghunaim, S. A., Ying, B., and Sayed, A. H.
On the influence of bias-correction on distributed stochastic
IEEE Transactions on Signal Processing, 68:0
4352–4367, 2020a.

[Yuan et al., 2020]
Yuan, K., Xu, W., and Ling, Q.
Can primal methods outperform primal-dual methods in decentralized
dynamic optimization?
IEEE Transactions on Signal Processing, 68:0
4466–4480, 2020b.

[Yurochkin et al., 2019]
Yurochkin, M., Agarwal, M., Ghosh, S., Greenewald, K., Hoang, N., and Khazaeni,
Bayesian nonparametric federated learning of neural networks.
In International Conference on Machine Learning, pp.  7252–7261. PMLR, 2019.

[Zhang et al., 2019]
Zhang, G., Wang, C., Xu, B., and Grosse, R.
Three mechanisms of weight decay regularization.
In International Conference on Learning Representations, 2019.
URL <https://openreview.net/forum?id=B1lz-3Rct7>.

[Zhang et al., 2020]
Zhang, J., Karimireddy, S. P., Veit, A., Kim, S., Reddi, S. J., Kumar, S., and
Sra, S.
Why ADAM beats SGD for attention models.
In Advances in Neural Information Processing Systems, 2020.

[Zhang et al., 2015]
Zhang, X., Zhao, J., and LeCun, Y.
Character-level convolutional networks for text classification.
In Advances in Neural Information Processing Systems, 2015.

[Zhao et al., 2018]
Zhao, Y., Li, M., Lai, L., Suda, N., Civin, D., and Chandra, V.
Federated learning with non-iid data.
arXiv preprint arXiv:1806.00582, 2018.


# Propagating Parameter Uncertainty in Power System Nonlinear Dynamic
Simulations Using a Koopman Operator-Based Surrogate Model

Yijun Xu, , Marcos Netto, , Lamine Mili This work was authored in part by the
National Renewable Energy Laboratory (NREL), operated by Alliance for
Sustainable Energy, LLC, for the U.S. Department of Energy (DOE) under
contract no. DE-AC36-08GO28308. This work was supported by the Laboratory
Directed Research and Development (LDRD) program at NREL. The views expressed
in the article do not necessarily represent the views of the DOE or the U.S.
Government. The U.S. Government and the publisher, by accepting the article
for publication, acknowledges that the U.S. Government retains a nonexclusive,
paid-up, irrevocable, worldwide license to publish or reproduce the published
form of this work, or allow others to do so, for U.S. Government purposes.Y.
Xu, and L. Mili are with the Bradley Department of Electrical and Computer
Engineering, Virginia Tech, Northern Virginia Center, Falls Church, VA 22043,
USA. M. Netto is with the Power Systems Engineering Center, NREL, Golden, CO
80401, USA. Corresponding author<EMAIL_ADDRESS>
###### Abstract

We propose a Koopman operator-based surrogate model for propagating parameter
uncertainties in power system nonlinear dynamic simulations. First, we augment
a priori known state-space model by reformulating parameters deemed uncertain
as pseudo-state variables. Then, we apply the Koopman operator theory to the
resulting state-space model and obtain a linear dynamical system model. This
transformation allows us to analyze the evolution of the system dynamics
through its Koopman eigenfunctions, eigenvalues, and modes. Of particular
importance for this letter, the obtained linear dynamical system is a
surrogate that enables the evaluation of parameter uncertainties by simply
perturbing the initial conditions of the Koopman eigenfunctions associated
with the pseudo-state variables. Simulations carried out on the New England
test system reveal the excellent performance of the proposed method in terms
of accuracy and computational efficiency.

###### Index Terms:

Koopman operator; parameter uncertainty; statistical dynamic simulation;
uncertainty propagation.

##  I Introduction

The uncertainties associated with electricity demand and supply, weather
forecasting, measurement systems errors, and modeling accuracy bring grand
challenges to the design and operation of modern power systems. Thus,
uncertainty quantification (UQ) has driven substantial research within the
power system community. See, e.g., [1, 2, 3]. In particular, propagating
uncertainties in power system nonlinear dynamic simulations is an important
problem and the focus of this letter.

Monte Carlo (MC) simulation is arguably the prevailing method for uncertainty
propagation. Though straightforward, MC simulation exhibits a prohibitive
computational burden for practical applications in sizeable electric power
systems. Analytical methods based on a linear approximation [1] of a nonlinear
system model improve the computational efficiency of the simulations but at
the expense of a significant loss of accuracy when the simulations involve
events that push the system far from the system stable equilibrium point.
Likewise, second-order approximations [2] improve the accuracy but lose
computational efficiency because they require the numerical evaluation of
higher-order derivatives. Conversely, statistical methods [3] simplify the
approximation procedure while maintaining high computational efficiency but
often lack physical meaning and interpretability. This letter proposes an
alternative approach to propagate parameter uncertainty in power system
nonlinear dynamic simulations based on the Koopman operator. Unlike analytical
methods that perform first-order or second-order approximations of the system
nonlinear model, the Koopman operator-based surrogate model captures the full
nonlinear dynamics and is derivative-free. Unlike statistical methods, the
proposed method retains physical interpretability and therefore is suitable
for applications such as coherency identification [4] and selective modal
analysis [5], among others. Furthermore, a Koopman operator-based surrogate
[6, 7] of a power system nonlinear dynamic model enables the evaluation of a
large set of parameters with low computational cost and high accuracy while
propagating parameter uncertainties in power system dynamic simulations.

##  II Koopman Operator

Let an autonomous nonlinear dynamical system evolving on a finite-dimensional
manifold $M$ be governed by

$\bm{\dot{x}}(t)=\bm{f}(\bm{x}(t)),$ (1)

where $t\in\mathbb{R}$, $\bm{x}\in\mathbb{R}^{n_{x}}\subset{M}$ is the state,
and $\bm{f}:M\to{M}$ is a nonlinear function. Let an observable $g(\bm{x})$ be
a continuous function defined in $M$, $g:M\to\mathbb{R}$. The _Koopman
operator_ , $\mathcal{K}_{t}$, is a linear, infinite-dimensional operator that
acts on $g$,

$\mathcal{K}_{t}\,{g}=g(\bm{S}_{t}),$ (2)

where
$\bm{S}_{t}:{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}M}\to{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}M};\,\bm{x}(0)\to\bm{x}(t)=\bm{x}(0)+\int_{0}^{t}\bm{f}(\bm{x}(\tau))d\tau$
is called the flow. Because the Koopman operator is linear, its eigenvalues,
$\lambda_{i}$, and eigenfunctions, $\phi_{i}$, are defined by
$\mathcal{K}_{t}\phi_{i}=e^{\lambda_{i}t}\phi_{i}$, $i=1,...,\infty$. In
practice, one estimates a subset of the Koopman eigenvalues and
eigenfunctions. To this end, let
$\bm{g}:{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}M}\to\mathbb{R}^{n_{d}}$,
$n_{d}\geq{n_{x}}$. If all $n_{d}$ elements of $\bm{g}$ lie within the span of
the eigenfunctions $\phi_{i}$, then

$\bm{g}(\bm{x}(t))=\sum_{i=1}^{n_{d}}\phi_{i}(\bm{x}(t))\,\bm{\upsilon}_{i}=\sum_{i=1}^{n_{d}}\phi_{i}(\bm{x}(0))\,\bm{\upsilon}_{i}\,e^{\lambda_{i}t},$
(3)

where $\bm{\upsilon}_{i}\in\mathbb{C}$, $i=1,...,n_{d}$, are the Koopman
modes. The interpretation of (2)–(3) is straightforward. Instead of focusing
on the evolution of the state, $\bm{x}$, one shifts the focus to the
observables, $\bm{g}(\bm{x})$. The advantage is that the observables evolve
linearly with time, see (3), without neglecting the nonlinear dynamics of the
underlying dynamical system (1). The linear representation (3) is crucial to
the proposed method’s accuracy and computational efficiency, irrespective of
nonlinearities. Note that $\bm{g}(\bm{x})$ can be any continuous function of
the state, $\bm{x}$, including the state itself. See, e.g., [8] for a
principled way of selecting these observables. Given a set of observables, it
is straightforward to estimate a subset of the Koopman tuples
$\\{\lambda_{i},\phi_{i},\bm{\upsilon}_{i}\\}$. To this end, this work adopts
the extended dynamic mode decomposition (EDMD) method [9]. Following [9], “if
the data provided to the EDMD method are generated by a Markov process instead
of a deterministic dynamical system, the algorithm approximates the
eigenfunctions of the Kolmogorov backward equation, which could be considered
as the stochastic Koopman operator.”

##  III The Proposed Method

Let a deterministic power system model be

$\bm{\dot{x}}=\bm{f}(\bm{x},\bm{y}),\quad\bm{0}=\bm{h}(\bm{x},\bm{y}),$ (4)

where $\bm{y}\in\mathbb{R}^{n_{y}}$ denotes algebraic variables,
$\bm{h}:M\to\mathbb{R}^{n_{y}}$ is a nonlinear function, and $\bm{x}$ and
$\bm{f}$ are as defined in (1). Further, let $\bm{\xi}$ be a random vector
following a given probability density function. Now, suppose that
$\bm{m}(\bm{\xi})$, a subset of the model parameters111We consider synchronous
generators’ instead of transmission lines’ model parameters because the former
directly impact the differential equations., is uncertain. To propagate the
parameter uncertainty through the system model, consider a set of $n_{mc}$
samples, drawn from a multivariate probability distribution of $\bm{\xi}$,
$\\{\bm{\xi}^{(j)}\\}^{n_{mc}}_{j=1}$. Then, for each $\bm{\xi}^{(j)}$,
$j=1,...,n_{mc}$, one evaluates a modified model given by

$\bm{\dot{x}}=\bm{f}(\bm{x},\bm{y},\bm{m}(\bm{\xi}^{(j)})),\quad\bm{0}=\bm{h}(\bm{x},\bm{y}),$
(5)

to obtain $n_{mc}$ trajectories, from which one can quantify the sample mean
and the sample variance of the states. Obviously, this MC simulation can be
computationally costly for real-time applications in sizeable electric power
networks. Now, let us introduce the propagation of parameter uncertainties
using the Koopman operator.

###  III-A Reformulation of the Dynamic Model

The kernel idea in this letter is to augment (1) with $n_{m}$ differential
equations [10], as follows:

$\begin{cases}\dot{\bm{x}}(t)=\bm{f}(\bm{x}(t),{\bm{m}}(t)),\\\
\dot{\bm{m}}(t)=\bm{0},\\\ \end{cases}$ (6)

thereby allowing one to cast the problem of parameter uncertainty propagation
into the Koopman operator framework. The dimension of the augmented model (6)
is $n_{x}+n_{m}$, where $n_{m}$ is the number of parameters deemed uncertain.
Note that generator model parameters are time-invariant, constant values
represented by _pseudo-state variables_ in (6). Now, we are in the position to
act on the parameter space using the Koopman operator formalism. Note that
although the model parameters are typically considered time-invariant, as they
are here, exceptions do exist, e.g., adaptive control gain in inverter-based
resources. Nonetheless, one can still capture these exceptions in (6) as long
as ordinary differential equations can describe them; in that case,
specifically, $\dot{\bm{m}}(t)=\bm{0}$ would be modified accordingly. This
fact demonstrates the flexibility in reformulating the augmented model, though
this specific case goes beyond the scope of this letter.

###  III-B Simulation-Based Data Collection

We are now in a position to estimate the Koopman operator. The estimation of
the Koopman operator relies exclusively on data, either numerical or
experimental. In this letter, we use numerical data obtained from simulations.
To this end, we first perturb the initial conditions of the pseudo-
states—namely, the parameters ${\bm{m}}(0)$ in (6)—at different random values,
$\bm{\xi}^{(j)}$, $j=1,\dots,n_{t}$. More specifically, we adopt a model

${\bm{m}}^{(j)}(0)=\bm{m}+{\bm{\xi}^{(j)}}$ (7)

to obtain a set $\\{{\bm{m}^{(j)}}(0)\\}^{n_{t}}_{j=1}$, where $n_{t}$ denotes
the number of sampled trajectories. Note that the values of $\bm{m}$ can be
obtained from the manufacturer data. Then, we repeatedly evaluate

$\begin{cases}\dot{\bm{x}}(t)=\bm{f}(\bm{x}(t),{\bm{m}}(t)),&{\bm{x}({0})},\\\
\dot{\bm{m}}(t)=\bm{0},&{{\bm{m}^{j}({0})}},j=1,\dots,n_{t},\\\ \end{cases}$
(8)

to obtain $n_{t}$ trajectories of the system states, including the pseudo-
states, as the training data. Note that to ensure the training efficiency,
$n_{t}$ should be designed to be a small number while maintaining a faster
convergence rate than the MC sampling. Specifically, we generate
$\\{\bm{\xi}^{j}\\}^{n_{t}}_{j=1}$ via the Latin hypercube sampling technique
for its well-known capability in experiment design. Using the simulated data
obtained with the augmented model (8), we estimate a subset of the Koopman
tuples, $\\{\lambda_{i},\phi_{i},\bm{\upsilon}_{i}\\}$, using the EDMD method
[8, 9]. Note that identifying a Koopman operator-based surrogate model
requires the computation of the Moore-Penrose pseudo-inverse of a data matrix.
The latter might be time-consuming depending on the matrix dimension and the
numerical implementation. Nevertheless, highly efficient implementations of
the Moore-Penrose pseudo-inverse are available.

###  III-C UQ through Koopman Operator-Based Surrogate Model

For convenience, define $\bm{x}_{a}^{\top}=[\bm{x}^{\top}\,\bm{m}^{\top}]$.
Let us use (3) to mimic the system performances described in (6) as a Koopman
operator-based surrogate model. Obviously, (3) is in a much simpler functional
form than (6) to represent a complex dynamical system [6], such as the dynamic
power system considered here. This surrogate allows us to efficiently conduct
uncertainty quantification, i.e.,
$\bm{x}_{ak}\approx\sum_{i=1}^{n_{d}}\phi_{i}({\bm{x}_{a0}})\bm{\upsilon}_{i}\mu_{i}^{k}$,
at a large number of parameter values, $\\{{\bm{m}}^{(j)}\\}^{n_{mc}}_{j=1}$.
Note that $\mu_{i}$ relates to the continuous-time Koopman eigenvalues
$\lambda_{i}=\ln\left({\mu_{i}}\right)/\Delta{t}$, where $\Delta{t}$ is the
data sampling time.

To numerically achieve this realization procedure, we simply assign each
parameter sample, $\bm{m}^{(j)}$, as the initial conditions to the associated
pseudo-states while keeping the initial conditions of the true system states
unchanged to get an updated ${\bm{x}_{a0}^{(j)}}$, whose randomness can be
further reflected in the _Koopman eigenfunctions_ through
$\bm{\phi}({\bm{x}_{a0}^{(j)}})\approx\bm{L}{\bm{g}({\bm{x}_{a0}^{(j)}})}$.
The matrix $\bm{L}$ stands for the left eigenvectors of the finite-dimensional
approximation to the Koopman operator; refer to [8] for details. The other
part in (3) remains unchanged, and then we have

${\bm{x}_{ak}^{(j)}}\approx\sum_{i=1}^{n_{d}}\phi_{i}({{\bm{x}_{a}}_{0}^{(j)}})\bm{\upsilon}_{i}\mu_{i}^{k},\quad
j=1,\ldots,n_{mc}.$ (9)

Now, using the set of $\\{{{{\bm{x}_{ak}}}^{(j)}}\\}_{j=1}^{n_{mc}}$, we can
quantify the uncertainties—e.g., the mean, the variance, the probability
density function—in the system states at any given time, $k$.

##  IV Simulation Results

Using the proposed method, we test its performance on the $10$-machine,
$39$-bus New England power system with a classic generator model. The system
dynamics are triggered by opening Line $15$-$16$. We assume that the parameter
values of the inertia for each generator are not well known. We suppose that
they follow a Gaussian distribution with the mean being the original
manufacturer data and the standard deviation being $10\%$ of the mean value to
account for the parameter uncertainties. We use an MC simulation with $10,000$
samples to obtain the benchmark results for comparison.

For the Koopman method, we set $n_{t}=75$, and we select the quantity of
interest as the rotor angle of Generator $2$ with respect to that of Generator
$10$, denoted as $\delta_{2-10}$, as an example. Note that the choice of the
observables for the Koopman operator is an open research topic; therefore, we
demonstrate two test cases with different observables. For the first case, we
use the second-order multivariate _Hermite polynomials_. For the second case,
in addition to the Hermite polynomials, we further introduce a cosine function
and a sine function for each true state variable separately. The evolution of
their means and standard deviations are depicted in Fig. 1, which shows that,
under different observables, their means are quite accurate. Regarding the
variance, although small differences are obtained during the first $5$ s,
these values increase as time evolves. This makes sense because the errors can
accumulate over time [3]. This is precisely what is observed when executing
the polynomial-chaos-expansion (PCE) method based on the sparse-grid rule
[11], whose computing time amounts to $32$ seconds. A similar computing time
for the Koopman operator method is recorded. However, while the Koopman
operator method has been applied with some success to coherency
identification, stability assessment and modal analysis, among others, it
still calls for further research. Indeed, the Koopman surrogate approach can
not only serve as an alternative of the PCE method in UQ, but it can also help
us to better deal with power system uncertainties. Also, as observed in Fig.
2, which depicts the probability density function of $\delta_{2-10}$ at $t=2$
s, the Koopman surrogate has the capability of accurately representing the
full probability density of the system state at a given time. Compared with
the MC simulations, which, as indicated in Table I, take nearly $0.5$ hour to
complete, the Koopman surrogate using Hermite polynomials takes only $0.5$
minute, hence achieving a speedup of more than $50\times$ while maintaining a
good accuracy. Note that parallel computing is directly applicable to the
training and the partial realization of the Koopman surrogate, resulting in a
significant improvement of the computational efficiency of the method. In
addition, these simulations demonstrate the flexibility of using different
observables in the Koopman approximation. Note that by adequately tuning the
observable functions [8], the Koopman surrogate still has the potential to be
further improved in long-term dynamic simulations and its commuting efficiency
for larger-dimensional systems.

The proposed method is also able to deal with non-Gaussian uncertainties.
Indeed, once the Koopman surrogate is trained, it can be directly evaluated by
processing non-Gaussian distributed samples,
$\\{{\bm{m}}^{(j)}\\}^{n_{mc}}_{j=1}$, to propagate uncertainties. Considering
power system applications, let us assume that the parameter values of the
inertia for each synchronous generator follows a uniform probability
distribution with $10\%$ errors. The other settings remain unchanged. From
Fig. 3, we can see that the Koopman method works well in approximating the
mean and the variance under an uniform distribution. However, when it comes to
higher moments, such as the skewness and the kurtosis as shown in Fig. 3, the
Koopman method does not provide accurate results. Therefore, improving the
performance of the Koopman method in higher-order moments deserves further
exploration.

TABLE I: CPU time: MC simulation and Koopman operator-based method Method | MC | Koopman: Training / Realization / Total
---|---|---
CPU time |  $1627.28$ s |  $12.4$ / $15.31$ / $30.83$ s
Figure 1: Sample mean and standard deviation of $\delta_{2-10}$ obtained with
MC simulation, PCE-based, and Koopman operator-based methods under Gaussian
distribution. Figure 2: Probability density function of $\delta_{2-10}$
obtained with MC simulation and the Koopman operator-based methods.

##  V Conclusions

In this letter, we propose a Koopman surrogate method for propagating
uncertainties in power system dynamic simulations that achieve good
performance in terms of accuracy and computational efficiency.

Figure 3: Sample mean, standard deviation, skewness, and kurtosis of
$\delta_{2-10}$ obtained with MC simulation and the Koopman operator-based
method under Uniform distribution.

## References

  * [1] I. Hiskens and J. Alseddiqui, “Sensitivity, approximation, and uncertainty in power system dynamic simulation,” _IEEE Trans. Power Syst._ , vol. 21, no. 4, pp. 1808–1820, 2006.
  * [2] H. Choi, P. J. Seiler, and S. V. Dhople, “Propagating uncertainty in power-system DAE models with semidefinite programming,” _IEEE Trans. Power Syst._ , vol. 32, no. 4, pp. 3146–3156, 2017.
  * [3] Y. Xu, L. Mili, A. Sandu, M. R. von Spakovsky, and J. Zhao, “Propagating uncertainty in power system dynamic simulations using polynomial chaos,” _IEEE Trans. Power Syst._ , vol. 34, no. 1, pp. 338–348, 2019.
  * [4] Y. Susuki and I. Mezić, “Nonlinear Koopman modes and coherency identification of coupled swing dynamics,” _IEEE Trans. Power Syst._ , vol. 26, no. 4, pp. 1894–1904, 2011.
  * [5] M. Netto, Y. Susuki, and L. Mili, “Data-driven participation factors for nonlinear systems based on Koopman mode decomposition,” _IEEE Control Systems Letters_ , vol. 3, no. 1, pp. 198–203, 2019.
  * [6] D. Lehmberg, F. Dietrich, I. G. Kevrekidis, H.-J. Bungartz, and G. Köster, “Exploring Koopman operator based surrogate models—accelerating the analysis of critical pedestrian densities,” in _Traffic and Granular Flow 2019_. Cham: Springer, 2020, pp. 149–157.
  * [7] S. Peitz, S. E. Otto, and C. W. Rowley, “Data-driven model predictive control using interpolated Koopman generators,” _SIAM Journal on Applied Dynamical Systems_ , vol. 19, no. 3, pp. 2162–2193, 2020.
  * [8] M. Netto, Y. Susuki, V. Krishnan, and Y. Zhang, “On analytical construction of observable functions in extended dynamic mode decomposition for nonlinear estimation and prediction,” _IEEE Control Systems Letters_ , vol. 5, no. 6, pp. 1868–1873, 2021.
  * [9] M. O. Williams, I. G. Kevrekidis, and C. W. Rowley, “A data-driven approximation of the Koopman operator: Extending dynamic mode decomposition,” _J Nonlinear Sci_ , vol. 25, no. 6, pp. 1307–1346, 2015\.
  * [10] J. J. Meyers, A. M. Leonard, J. D. Rogers, and A. R. Gerlach, “Koopman operator approach to optimal control selection under uncertainty,” in _2019 American Control Conference (ACC)_ , 2019, pp. 2964–2971.
  * [11] D. Xiu, _Numerical methods for stochastic computations_. Princeton University Press, 2010.