Identification of efficient COVID-19 diagnostic test through artificial neural networks approach − substantiated by modeling and simulation

Soon after the first COVID-19 positive case was detected in Wuhan, China, the virus spread around the globe, and in no time, it was declared as a global pandemic by the WHO. Testing, which is the first step in identifying and diagnosing COVID-19, became the first need of the masses. Therefore, testing kits for COVID-19 were manufactured for efficiently detecting COVID-19. However, due to limited resources in the densely populated countries, testing capacity even after a year is still a limiting factor for COVID-19 diagnosis on a larger scale and contributes to a lag in disease tracking and containment. Due to this reason, we started this study to provide a better cost-effective solution for enhancing the testing capacity so that the maximum number of people could get tested for COVID-19. For this purpose, we utilized the approach of artificial neural networks (ANN) to acquire the relevant data on COVID-19 and its testing. The data were analyzed by using Machine Learning, and probabilistic algorithms were applied to obtain a statistically proven solution for COVID-19 testing. The results obtained through ANN indicated that sample pooling is not only an effective way but also regarded as a “Gold standard” for testing samples when the prevalence of the disease is low in the population and the chances of getting a positive result are less. We further demonstrated through algorithms that pooling samples from 16 individuals is better than pooling samples of 8 individuals when there is a high likelihood of getting negative test results. These findings provide ground to the fact that if sample pooling will be employed on a larger scale, testing capacity will be considerably increased within limited available resources without compromising the test specificity. It will provide healthcare units and enterprises with solutions through scientifically proven algorithms, thus, saving a considerable amount of time and finances. This will eventually help in containing the spread of the pandemic in densely populated areas including vulnerably confined groups, such as nursing homes, hospitals, cruise ships, and military ships.

Introduction
COVID-19 is a global healthcare problem that has overwhelmed both healthcare and economic sectors on a large scale. If the workforce is required to self-isolate due to contact with a confirmed case of coronavirus, consider ways they can continue to support multidisciplinary team meetings. This may be exacerbated by COVID-19 infection of medical personnel, quarantine requirements, and school closures, all of which may affect the staffing levels and increase stress on the capacity of these institutions [1]. Clinicians and other support staff have to work flexibly to facilitate safe service provision in alternative settings [2]. On one hand, social distancing and separation of clinic workspaces are important steps to reduce the risk of infection [3]. On the other hand, smart, cost-effective methods to identify the spread of viral disease in the community are scarce. To meet the increasing need for personal security devices, including personal protective equipment (PPE), testing kits, and lifesaving drugs, manufacturers utilized their capital exhaustively [1]. They excluded the importance of statistically proven solutions that would help by saving both time and money. Therefore, considering the increasing need of the masses, this study is designed to provide a cost-effective solution to pooled testing. This will not only reduce the cost, amount of workforce, and labor but also would have reduced the burden on the manufacturing sites for the PCR-based testing kits or other novel testing techniques in the market. Similarly, effective measures can be taken to reduce costs in billion dollars and time in days and months.
We started this study by conducting an extensive analysis of current testing techniques that are utilized in the diagnostic centers for COVID-19 testing. We also examined the utilization of artificial intelligence in the domain of healthcare with a particular focus on its role in COVD-19 testing. After a thorough analysis of the literature, we found that all those studies and techniques lacked in improvising the approved testing strategy for COVID-19 testing as they utilized radiographs obtained through CT scans and chest X-rays. According to US FDA, these tests are not approved as diagnostic tests for COVID-19 testing, and only PCRbased tests are regarded as "Gold Standard" for COVID-19 testing. For this reason, this study has been designed to provide a smart, alternative solution to the healthcare sector and enterprises. The principles of artificial neural networks (ANN) were employed in this regard, and the data were collected through bibliometric analysis by using selective keywords. The selected data were then subjected to statistical analysis by applying probabilistic algorithms. The results obtained demonstrated the effectiveness of sample pooling when the disease prevalence is low in the population. Thus, this study provides a cost-effective solution that would help in increasing the testing capacity while reducing the burden of testing and resource availability on the diagnostic centers and manufacturing companies. This ultimately would reduce the disease burden on the healthcare system of low-income countries and will help in robust disease tracking and containment.

Literature review
Though a considerable progress has been made since the first COVID-19 case reported in Wuhan, China, it still needs our efforts to contain its spread to resume the activities back to normal as early as possible and ultimately lessening the burden on the global economy. Considering the minimal potential to test and handle a massive influx of patients even after a year of the pandemic, we need to devise solutions to increase the efficiency without altering the specificity of testing that will ultimately reduce the burden on pharmaceutical and manufacturing companies and the local healthcare sectors as well [4]. Efforts were being made in this regard at the federal and state levels and were disbursed at a local level to provide better living and healthcare facilities to communities. Strategies were being designed to eliminate the need for extended stay-at-home instructions when enforcing risk-based lockdown, testing, touch-tracking, and surveillance procedures as the economic woes of the COVID-19 pandemic intensify [5]. Given the scarce resources and the critical fiscal, public health, and organizational complexities of the existing 14-days quarantine recommendation, it is important to understand whether it is possible to introduce more efficient yet similarly effective testing techniques [5,6]. Therefore, it is the need of the time to improve the testing capacity and timely tackle and control COVID-19 cases. This would not only help in resuming the work, reducing the losses by the corporate sector but also can be taken as an opportunity to meet the needs of the shackled healthcare system in this pandemic.
Amid this healthcare challenge, out of many hard-hit sectors, the corporate sector was one of the main affectees that has faced a considerable setback due to jamming of all sorts of activities in every domain. COVID-19 has shaken not only the healthcare sector but has caused a considerable damage to businesses around the globe as well. Companies that offer information services continued to survive while manufacturing companies had to either close their workplaces or allow workers conditionally with stringent instructions of maintaining social distancing, avoiding congregations, and proper use of PPE. Under the domain of manufacturing enterprises, only those who were producing basic goods were allowed to operate [7]. And, the effect of these restrictions on all sorts of activities when evaluated was in the form of huge financial losses for small businesses due to disruption of the supply chain, reduced profits, and product demand. Due to these reasons, some enterprises could not survive the lockdown and were permanently closed while others are on the verge of collapsing if it continues for 2 or more months [8]. The main reason was found to be a lack of preparedness toward handling a pandemic by over 83% of these micro, small, and medium enterprises. The ultimate consequences can be observed in terms of economic disparity and increased joblessness in the past few months. Therefore, in some countries, a support package was launched to sustain these businesses [9]. But as the pandemic has struck again vivaciously, providing a support package is not sufficient and requires some preventive and control measures as well. Testing being the cornerstone of identifying COVID-19 positive cases is a need of all the enterprises and of every sector that had to shut down its activities under government instructions. To overcome the adversities of pandemic and to resume the activities back to normal by all the surviving enterprises, it is important to test individuals for COVID-19 before officially restoring the operational activities. But a single PCR-based test costs around $100, so it is economically not feasible for businesses to conduct tests of all the employees after facing an economic blow due to the current pandemic [10].
At present, COVID-19 tests approved by U.S Food and Drug Administration are classified as either diagnostic tests or antibody test both of which detects COVID-19 infection differently. Diagnostic tests can be done by detecting viral genetic material via Reverse Transcriptase Polymerase Chain Reaction (RT-PCR) or it can be performed by detecting viral antigens in the test samples. Antibody test, on the other hand, detects the presence of antibodies against the viral antigen. The diagnostic test is usually performed on fresh swabs taken from individuals to detect viral load while an antibody test is performed on individuals who are already exposed to COVID-19 and have antibodies in the blood against the virus. An antibody test cannot be used to diagnose COVID-19 because antibodies sometimes take a week or more to be synthesized against the virus after initial infection and their levels can be detected even after recovering from COVID-19. Therefore, it cannot tell exactly if the body is still carrying the viral load. The only reliable way to detect the viral load of COVID-19 is through diagnostic tests that can indicate an active infection in the individual [11]. But each of these methods has its own drawbacks as well, depending on the context of testing done. Apart from these, radiology has also found its role in identifying COVID-19 cases by using chest X-rays and CT scans. These radiographs indicate the abnormalities in the lungs but cannot be taken as a way to detect COVID-19 [12]. Out of all these mentioned techniques for COVID-19 testing, the most reliable is RT-PCR-based testing ( Table 1). Thus, after identifying the most effective type of diagnostic test, it is important to improve the capacity of already existing techniques so that a maximum number of individuals could be tested for COVID-19 that would ultimately help in identifying disease hotspots and tracing points of contact. As carrying out screening tests on a large scale is not possible with limited resources, Artificial Intelligence and Machine Learning are introduced into the healthcare sector to improve the working capacity with limited available resources.
By using data from diagnostic tests and X-rays or CT scans, AI and ML tools were utilized to improve the detection and tracking of COVID-19 [13][14][15][16][17]. However, these models have limitations in real-world implications despite being them up-to-the mark. Also, most of these studies include a pre-detection technique involved, whether it's an X-ray or CT scan. Mohammed et al. brought a novel strategy of predicting the cases through true positive and negative Mathew's correlation sensitive analysis merged with entropy and Technique for Order of Preference by Similarity to Ideal Solution (TOPSIS) but again the input data has to have previous reliability on other detection methods, which involves regressive and expensive techniques. Moreover, this study is relied on laboratory-and hospital-based data and feature selection [18]. In previous studies, chest CT scans were integrated with clinical symptoms by using AI that helped in improving the detection of COVID-19 even in cases in which a normal CT scan was obtained [19]. AI also helped in differentiating COVID-19 from community-acquired infections like pneumonia [20].
It also contributed to coupling of self-testing with disease tracking which would help in containing the spread of disease [21]. Many COVID-19 hotspots were detected by using AI and it was also used to predict the future hotspots [22]. All these studies demonstrated the use of AI and ML in the healthcare sector, particularly in the case of a pandemic. It should be noted here that in all these AI-and ML-based studies, the area of focus remained improving radiological findings by utilizing chest X-rays and CT scan images of normal and COVID-positive individuals. These tests are not approved as COVID-19 diagnostic tests, but in case of any emergency situation, they can be used to identify the extent of infection in individuals that when combined with clinical symptoms may indicate COVID-19 infection. Therefore, our study utilizes AI for improving the capacity for RT-PCR that is the gold standard for COVID-19 diagnosis. These findings will provide a cost-effective testing solution for the healthcare sector and manufacturing enterprises as well. This study analyses the effectiveness of pooled testing of COVID-19 through ANN approach and Machine Learning by using binary search. For validating the hypothesis, ANN and Machine Learning were used as they have shown high performance in obtaining and interpreting huge volumes of data [23]. It works on similar principles as of the human brain in which the input signal after processing gives an output. In the same way, data fed in ANN are interpreted in different layers, and the results are displayed through the output layer. In the simplest model, three layers exist that are input layer, hidden layer, and output layer. But the intermediate hidden layers may increase in number depending on the amount of information and its complexity [24]. ANN though works on similar principles of human brains, but its processing and results are more profound than a human brain. Its capacity to solve problems that are almost impossible for humans make it an efficient tool used in Artificial Intelligence (AI) and is, therefore, used in this study as well to analyze and model the huge volumes of data fed through the input layer [23,25]. Machine Learning tools were then applied to the data generated through ANN, and by using the binary search tool, the data was sorted. The binary search tool has advantages over linear search as it can sort large volumes of data effectively in a short time and, therefore, is more suitable for sorting populationbased data.
In this study, we have collected bibliometric data that are analyzed through the ANN approach and by Machine Learning have developed algorithms. These algorithms were used in evaluating the efficiency of sample pooling first with eight samples that were later extended to 16 samples. On this basis, in this study, it is proposed that pooling of samples will not only increase the testing capacity but also work without altering the specificity of the testing procedure that will stay the same 96% even with a pool of 16 samples. This will help in reducing the cost and will prove highly economical in populationbased studies where the prevalence rate of diseases is usually low. It will be helpful not only in detecting COVID-19 cases but also in testing both symptomatic and asymptomatic carriers and tracing the points of contact in limited resources [26]. Due to these reasons, it will stand in a more economical position than the current strategy of individual testing that no doubt if has merits, also has demerits of an economic burden on the healthcare sector and an increased consumer demand for manufacturing companies. Therefore, introducing Artificial Intelligence in the healthcare sector not only will provide cost-effective solutions to enterprises but will also provide evidence for further research in the healthcare domain [27]. The ease in scientific data collection by accessing it through devices like antennas and wireless devices has transformed the biotechnology sector by giving smart solutions for healthy lifestyle and wellbeing of people [28,29]. Thus, this study conducted by applying principles of AI will provide grounds to decision-makers to enhance the testing capacity within limited resources and to introduce new strategies to control and confine the pandemic.

Materials and methods
This section introduces the dataset used in this study along with the proposed methodology for conducting this research.

The dataset used
A dataset containing citation information must be collected before starting any bibliometric analysis. Therefore, data were retrieved from databases including PubMed, Scopus, and Web of Science by using keywords related to COVID-19 and was further evaluated.

Proposed methodology
The available information from different Internet sources was obtained for bibliometric analysis. It was further evaluated by using the ANN approach. The output information from ANN was obtained in the form of a map that was constructed by VOSviewer software. The output was further analyzed via MATLAB where probabilistic algorithms were applied to find out the probability of effectiveness of our proposed solution. A collective summary of all the components of the Artificial Intelligence and Machine Learning model adopted for this research is schematically depicted in Figure 1.

ANN model for bibliometric analysis
ANN approach was used in this study because of its effectiveness in processing huge volumes of data. The results obtained via ANN are more reflective, and therefore, it has also been employed in conducting this research. Furthermore, we used the training set to determine average evaluation for model parameters (studies including the ANN, Artificial intelligence, and Machine learning before covid). We then trained the model for 10 runs. The observed data (training data) contains "testing studies prior to covid and their  relevance implication" and the test data represented the studies after the global pandemic and their effective evaluation on the testing system.
We have utilized the results that were analyzed by constructing a map that represents the relationship of different nodes joined together by lines. In our study, nodes represent the research domains, their size represents the amount of work being done while the lines represent the interconnectedness of these research domains with COVID-19.

VOSviewer for constructing maps
VOSviewer is a computer program that helps in constructing and viewing maps generated with bibliometric data. As the name indicates, it constructs maps based on the Visualization Of Similarities (VOS). It has the advantage that it can run on multiple hardware devices as well as operating systems and even can be applied directly onto the Internet source. It generates two types of maps based on either distance between two entities that hold significance in terms of strength of the relation between them or graph-based maps in which the distance holds no significance and does not indicate any strength in their relation. Generally, constructing maps via VOSviewer needs three steps to be performed by calculating similarity matrix based on co-occurrence in the first step followed by applying the VOS mapping technique on similarity matrices in the second step and that is subjected to translation, rotation, or reflection in the last step. These steps are briefly discussed in the following sections.

Calculating similarity matrix
Similarity matrix serves as an input to VOS mapping technique and is obtained by normalizing co-occurrence matrix. The similarity between two entities i and j is given by the following formula, Here, C ij represents the co-occurrence of i and j and W i and W j represent a total number of occurrences of these entities.

VOS mapping technique
VOSviewer constructs a 2D map of n number of items based on a similarity matrix so that the distance between them determines the similarity of the items. This implies that items that are closely linked are mapped in close proximity while those sharing less similarity are placed in a distant position. The VOS mapping technique works on the concept of minimizing a weighted sum of squared Euclidean distances, and therefore, it assigns the average distance of one between two closely related entities. It is mathematically represented as follows: Here, vector x i represents the location of i on a 2-D map and ||•|| represents Euclidean norm Minimization is performed by the following formula: n n x x 2 1 1.
In the first step, constrained optimization is changed into an unconstrained optimization problem that in the second step is subjected to majorization algorithms for further solving.

Translation, rotation, and reflection
As no unique and optimal solution exists for the optimization problem that is addressed in the previous step and consistent results must be produced every time when the same co-occurrence matrix is used for constructing maps via VOSviewer; therefore, three transformations of translation, rotation, and reflection should be applied [30].

Experiments and results
The experimental setup of this study and the results obtained are discussed in this section.

Bibliometric analysis
We started this study by performing bibliometric analysis on a list of keywords that were most commonly used for retrieving information on COVID-19 testing. The keywords used for this research include, COVID-19 testing, COVID-19 testing through binary search, ANN approach for COVID-19 testing, AI in COVID-19 testing, etc. Based on these keywords, data were retrieved from different search engines including ScienceDirect, Web of Science, Scopus, and PubMed. Testing technologies published in top-tier journals were collected, and bibliometric analysis was performed to identify new research domains by carefully tracking the progress made toward COVID-19 diagnostics. The result of this bibliometric analysis was used as the input parameter for the ANN model.

ANN model
Multilayer ANN works by comparing different testing methodologies in three different layers: input layer, hidden layer, and output layer. The aim of using this complex network model was to find out the best testing approach for COVID-19 detection. The ANN model was used to identify the domain carrying benefits for COVID-19 testing by using VOSviewer software. This software made a map based on bibliometric information that shows different domains explored under COVID-19 testing. The weight of each input is represented by the size of the node, and the output is represented in the form of a network.

Mathematical algorithms
Information obtained from the ANN model was further analyzed. It was subjected to MATLAB that helped in statistically validating the probability of our proposed solution. Therefore, we started this study by taking samples in power of two, so that there can be a total of l = log 2 N levels. The model generated was elaborated by using a group of eight individuals. Figure 2 represents all eight samples arranged in four levels. These samples from S1 to S8 belong to eight different individuals and represent the lowest level, level 4. These samples are then paired to give a higher level, level 3, in which four pairs will be formed from eight samples. Pairs from level 3 will again cluster to give level 2 with four samples in each cluster that is ultimately pooled up to give level 1 with all eight available samples. From level L 1 to L l-1 , each sample is formed by adding two child samples of succeeding level such that − become child samples of S(i) In this approach instead of testing all the samples in a linear fashion, we started from the highest level 1 with all samples, i.e., S(2 L − 1) pooled, and if sample S(i) comes out positive, both child samples of S(i) will be tested. By this approach, a possible number of tests to diagnose eight people are t such that t ∈ {1, 7, 9, 11, 13, 15}. All the possible values of t are elaborated in the given figures.
As depicted in Figure 3, if all the samples pooled in S(15) are COVID-19 negative, they will be tested by only a single test performed on this pool of samples. This will be the most effective way in which a minimum number of tests will be performed. Figure 4 shows the number of tests to be performed if either both or one sample of a pair is positive for COVID-19. In such instances, it can be evaluated by performing seven tests starting from level 1 to level 4.     Figure 7 reflects the number of tests to be performed when one or both samples of three pairs from both the clusters are COVID-19 positive will be 13. A total number of tests performed will increase to 15 tests in situations when either both or a single sample from each pair of both clusters is positive. This is shown in Figure 8 and will give the maximum number of tests that will be performed from pooling samples from eight individuals.
All this information on sample pooling suggests that sample pooling for eight individuals will be valuable only when the probability of occurrence of positive cases is low. Therefore, it will be beneficial in epidemics or pandemics when the prevalence rate is low, and there are more chances of getting a negative result than a positive result. If p is the probability of a positive outcome of a test, the probability of the possible number of tests then becomes     As discussed earlier, the number of samples can be taken in the power of two. Therefore, if the number of samples is increased from 8 to 16 samples, then a total of five levels will be made to evaluate the number of tests performed. Therefore, the number of tests performed for all negative cases will be one, and the maximum possible tests performed when either one or two samples of all the pairs are positive will be 31.
The probability for the possible number of tests performed by pooling samples of 16 individuals is discussed by the given algorithm. [ ] Mean for 16 person's sample becomes By using these above-mentioned algorithms, the probability of effectiveness of our proposed solution was evaluated for sample pools of eight individuals and 16 individuals.

Result analysis 4.1 Bibliometric analysis and ANN model
Bibliometric data fed into the ANN model were obtained for analysis through the output layer in the form of a map by using VOSviewer software. The map shows the most searched topics with reference to COVID-19 and is given in Figure 9.
The nodes on this map depict that the most repetitive keywords found in the literature retrieved through different search engines were COVID-19, machine learning, deep learning, ANN, pandemic, chest X-ray, computed tomography, etc. This shows the data collected for this research revolved around the COVID-19 testing and involves the application of AI and ML in controlling the pandemic. It can be seen in Figure 9 that CT scans and chest X-rays were already being under research for their role in identifying COVID-19. Therefore, after careful analysis, it was decided to improve the working capacity of a gold standard of COVID-19 testing that is RT-PCR. Though area of research of many artificial intelligence-based studies revolved around chest X-rays and CT scans, but due to their limitations and inefficiency in correctly detecting COVID-19, we evaluated a different testing strategy focusing on pooling swabs for COVID-19 diagnosis.

Comparison and analysis of COVID-19 linear and pooled testing
Probabilistic results were obtained by applying the above-mentioned algorithms. The results obtained are discussed here. Figure 10a demonstrates the average tests that need to be performed for both linear and pooled testing, when the probability of getting a positive result increases. For linear testing, it can be seen that number of tests is neither increasing nor decreasing for both eight individuals testing and 16 individuals testing. However, a rising curve is obtained for pooled testing that increases sharply in the beginning and then after a certain point attains a steady state. This shows that when the probability of getting a positive result is as low as 20%, the average number of tests to be performed on a pooled sample is lower than the number of tests performed for linear testing. After 20%, it can be seen that number of tests for pooled testing increases than for linear testing, making it the least viable solution in cases where the probability of getting a positive sample is higher.  Figure 10b represents the number of people that can be tested by using only one test when the probability of getting a positive result increases. It can be seen that for linear testing a straight line is obtained showing that only one person will be tested with one test. However, for pooled testing, a sudden decline in the curve can be seen that shows that when the probability of getting a positive is as low as 0%, one test is sufficient to test a pooled sample of either 8 individuals or 16 individuals. However, as the probability starts increasing, the number of tests that should be performed to test samples would also increase. The probability at the point of intersection of all three lines indicates that sample pooling would be an effective and time-saving technique before that point of 19% probability. But, if probability will increase beyond that point, sample pooling will lose all of its effectiveness, and therefore, it will no longer be a recommended testing approach. Figure 10c compares a number of tests required per person for linear testing with pooled testing. A straight line for linear testing represents that one test will be required to test one person irrespective of the probability of getting a positive or negative result. However, for pooled samples, a rising curve is obtained that rises sharply at the beginning when the probability of getting a positive result is low. These rising curves show that the average number of tests per person performed on pooled samples will be low when probability will be low and as soon as the probability increases to 19%, after that, it is no longer significant and the average test per person will start to increase in that case. The point of intersection of these lines demonstrates that sample pooling will be effective only when the probability of getting a positive is low.
All these results suggest that sample pooling holds potential benefits over linear testing, but only in instances when the probability of getting a positive result is low. This suggests that for diseases having a low prevalence rate in different communities, sample pooling would be an effective technique for detecting the disease and taking timely actions. As the prevalence of COVID-19 is low in many countries, this study provides a statistically proven solution, demonstrating the effectiveness of sample pooling in maximizing the number of individuals to be tested.

Case study based on our proposed algorithm
Adopting this approach, a case study was conducted in the Punjab region when positive detection probability was reported to be 6%. In this case study, several tests were conducted with the group pooling of 16 samples in each test. The abovementioned algorithms were applied, and the probability against each case was evaluated. The graph in Figure 11 shows percentages of tests to be performed for each sample pool. All these results obtained from applying algorithms to find out the efficiency of our proposed solution suggest that for population-based studies for diseases that have a low prevalence rate, sample pooling is an effective means of increasing the capacity of testing with minimum available resources. As COVID-19 prevalence is low in many communities, our study will provide scientific grounds to incorporate better and improved solutions in the healthcare sector.

Application of the algorithm on other countries
Evidently, the probability of the number of tests increases with the Covid positive occurrence for each state mentioned ( Figure 12). There is a 98% probability for New Zealand and Australia to have detected a Covid case with the sample pooling suggested above. With the increase in Covid Positive ratio, there is a decline in the percentage of positive test detection. The minimum number of tests performed on a high positive ratio for 16 people pool is 10 with the probability of approx. 40% for USA. For Germany, there need to be 10 repetitions of the test to reach a 30% probability. The recent data available from the source mentioned in Figure 12 can be imported into the supporting file to extrapolate results.

Discussion
Though pandemics are challenging and require a substantial relocation of resources, energies, and capital, but they also bring with them an opportunity for resilience and innovation. As science has progressed rapidly since the last pandemic, this has improved healthcare facilities as well. But this must not undermine the adversities of a challenging situation. Therefore, it is advisable for healthcare systems and enterprises to timely take measures and devises strategies to combat unpleasant circumstances that may last for months or even years in some instances. COVID-19 has made us evaluate our current standing in a pandemic and also how current interdisciplinary knowledge can bring efficient yet simple solutions. Testing, being the first step of identifying and controlling the pandemic, needs a special focus so the concerned authorities could timely take action even with the least available resources [31]. Therefore, in the quest to save time and improve testing capacity, this study was conducted using the ANN approach, and by applying Machine Learning tools, we have found that disease burden would reduce considerably if testing will be done by sample pooling with either 16 samples or eight samples for diseases that have low prevalence rate in different populations.
Statistical algorithms were employed in this regard to evaluating the effectiveness of our hypothesis, and the results supported our proposed solution. It has shown that testing would be reduced to only five levels in a pool of 16 individuals and four levels with eight individuals in each pool. As in most of the communities, the spread of COVID-19 and its, prevalence is low, therefore, this will support both the healthcare sector and government regulatory bodies by performing a greater number of tests with minimal testing resources available saving time and finances, and making tracking of COVID-19 and containing more robust. Though sample pooling will be an effective strategy in increasing the testing capacity, before integrating it with healthcare settings, it is important to evaluate few negative aspects of this technique as well. The testing specificity must be validated via conducting tests on sample pools from communityacquired samples. Though we found that sample pooling can be done when samples are taken in the power of two, but it should also indicate the maximum limit for sample pooling where a positive case can be detected without diluting out. Supporting our findings, a study was performed which demonstrated that the specificity of testing did not alter even with sample pools of 32 and 64 individuals [32], but it might need some extra amplification cycles. Sample pooling must be done carefully as a viral load from recently acquired COVID-19 individuals or those recovered from COVID may not be detected due to low levels giving a false-negative. All these concerns must be carefully addressed before opting sample pooling technique that no doubt has lots of benefits, but the associated potential risks cannot be neglected. Therefore, we can say that the use of Artificial Intelligence and Machine Learning in biological research during a pandemic will provide a basis for answering research questions and giving smart solutions for improved healthcare facilities but these solutions must be validated in labs for their effectiveness before actually implementing them. This will provide safe grounds, increased working capacity, and reduced financial losses to the biological community in such unprecedented times.
In the end, all these benefits of sample pooling do not lie only for the healthcare sector, but they are projected toward enterprises as well. By using such algorithms, they can enhance their own testing capacity and can provide smart solutions to hospitals, nursing homes, prisons, and cruise ships, where due to confined space and insufficient resources for testing, the probability of contracting COVID-19 increases considerably. The increased demand for reagents used in PCR-based testing, pharmacological solutions, and PPE and their burden on manufacturing and pharmacological industries would be reduced, and these companies will be able to meet public demands with the least available resources. Moreover, smart lockdowns and increased testing capacity will serve both local communities and the corporate sector in resuming the functional activities and overcoming the losses of the previous fiscal year. This study provides a scientifically proven solution that, if adopted, will serve all the sectors of society that are hit hard by the pandemic.
This study is based on the principles of Artificial Intelligence and provides the probable solution for the COVID-19 testing; therefore, it holds the limitation of not incorporating the results of wet lab work. Due to this reason, it is advisable to validate it through a pooling of community samples for PCR-based testing before implementing at mass level testing.

Conclusion
Artificial Intelligence and Machine Learning have contributed significantly to providing efficient solutions to healthcare units even in pandemics. Integrating AI-based solutions into healthcare facilities will improve the working capacity of these units. Therefore, research has been going on in this domain to provide smart solutions to both healthcare settings and enterprises. This study was also conducted to utilize the effectiveness of AI and ML solutions in the healthcare sector and by using the approach of ANN, found sample pooling to be an effective strategy for COVID-19 testing when available resources are limited. Our results demonstrated sample pooling would be a cost-effective COVID-19 testing solution as the testing resources are scarce in many communities. The low prevalence rate of COVID-19 in many communities makes our solution easy to adopt because chances of getting a positive case are low when carrying out a mass testing program. Therefore, sample pooling would help in improving testing capacity that would ultimately help in detecting and tracking more robust. Moreover, our findings will also help in minimizing the utilization of testing reagents that would release the burden of increased consumer demand from manufacturing enterprises as well. Our study provides scientifically proven algorithms for COVID-19 testing that if implemented would help in containing the spread of the pandemic and ultimately resuming the activities back to normal. However, these algorithms further need to be tested on community-acquired samples before finally implementing in laboratories. This study can further be improved with the implementations of current data into the proposed methodology and running large-scale simulations. We recommend more methodological work to address the strategic public behavior and involvement with State entities and economic consideration to see the impact of the research.


Accelerating Gossip SGD with Periodic Global Averaging

Communication overhead hinders the scalability of large-scale distributed training. Gossip SGD, where each node averages only with its neighbors, is more communication-efficient than the prevalent parallel SGD. However, its convergence rate is reversely proportional to quantity $1-\beta$ which measures the network connectivity. On large and sparse networks where $1-\beta \to 0$, Gossip SGD requires more iterations to converge, which offsets against its communication benefit. This paper introduces Gossip-PGA, which adds Periodic Global Averaging into Gossip SGD. Its transient stage, i.e., the iterations required to reach asymptotic linear speedup stage, improves from $\Omega(\beta^4 n^3/(1-\beta)^4)$ to $\Omega(\beta^4 n^3 H^4)$ for non-convex problems. The influence of network topology in Gossip-PGA can be controlled by the averaging period $H$. Its transient-stage complexity is also superior to Local SGD which has order $\Omega(n^3 H^4)$. Empirical results of large-scale training on image classification (ResNet50) and language modeling (BERT) validate our theoretical findings.

Introduction
The scale of deep learning nowadays calls for efficient largescale distributed training across multiple computing nodes in the data-center clusters. In distributed optimization, a network of n nodes cooperate to solve the problem where each component f i is local and private to node i and the random variable ξ i denotes the local data that follows distribution D i . We assume each node i can locally evaluate stochastic gradients ∇F i (x; ξ i ) where ξ i ∼ D i , but must communicate to access information from other nodes. (1−β) 2 ) Ω( n 3 β 4 (1−β) 4 ) Ω(n 3 β 4 C 2 β ) Ω( LARGE OR SPARSE NETWORK (WHEN 1 1−β ≥ H ) Ω( n 3 β 4 (1−β) 2 ) Ω( n 3 β 4 (1−β) 4 ) Ω(n 3 β 4 C 2 β ) Ω(n 3 β 4 C 2 β H 2 )   Table 3. The lengths of the transient stages of Local SGD and Gossip-PGA. Gossip-PGA always has shorter transient stages than Local SGD since β < 1 and C β < H. Such superiority becomes more significant on well-connected networks where β → 0.
may nullify its communication efficiency and result in even more training time (see Table 1). Local SGD with a large averaging period meets the same issue.
This paper proposes Gossip-PGA, which adds periodic All-Reduce global averaging into Gossip to accelerate its convergence especially on large and sparse networks. Gossip-PGA also extends Local SGD with fast gossip-style communication after local updates. When the same averaging period H is used, the additional gossip communication in Gossip-PGA endows it with faster convergence than Local SGD.
Challenges. Gossip-PGA can be regarded as a special form of the topology-changing Gossip SGD (Koloskova et al., 2020) and SlowMo (Wang et al., 2019) (in which the base optimizer is set as Gossip SGD, and the momentum coefficient β = 0). However, its theory and practical performance were not carefully investigated in literature. Unanswered important questions include how much acceleration can PGA bring to Gossip and Local SGDs, in what scenario can PGA benefits most, how to adjust the averaging period effectively, and how Gossip-PGA performs in large-scale deep learning systems. Providing quantitative answers to these questions requires new understanding on the interplay between gossip communication and global averaging period. Simply following existing analysis in (Koloskova et al., 2020) will result in incomplete conclusions, see Remark 5. Also, the analysis in SlowMo (Wang et al., 2019) does not consider heterogeneous data distributions and cannot cover our results.

Main Results
This paper proves that Gossip-PGA converges at for both smooth convex and non-convex functions f i (the metrics used for both scenarios can be referred to Theorems 1 and 2), where n is the network size, T is the total number of iterations, σ 2 denotes gradient noise, b 2 gauges data heterogeneity, β ∈ (0, 1) measures how well the network is connected, H is the global averaging period, and we define C β = H−1 k=0 β k and D β = min{H, 1/(1 − β)}. Linear speedup. When T is sufficiently large, the first term 1/ √ nT dominates (2). This also applies to Parallel, Local, and Gossip SGDs. Gossip-PGA and these algorithms all require T = Ω(1/(n 2 )) iterations to reach a desired accuracy , which is inversely proportional to n. We say an algorithm is in its linear-speedup stage at T th iteration if, for this T , the term involving nT is dominating the rate.
Transient stage. Transient stage is referred to those iterations before an algorithm reaches its linear-speedup stage, that is iterations 1, . . . , T where T is relatively small so non-nT terms (i.e., the extra overhead terms in (2)) still dominate the rate. We take Gossip-PGA in the non-iid scenario (b 2/3 ≥ σ) as example. To reach linear speedup, T has to satisfy T  Table 2. Since C β = (1 − β H )/(1 − β) < min{H, 1/(1 − β)}, we conclude Gossip-PGA always has a shorter transient stage than Gossip SGD for any β and H. Moreover, the superiority of Gossip-PGA becomes evident when the network is large and sparse, i.e., 1 − β → 0. In this case, the transient stage of Gossip SGD can grow dramatically (see the second line in Table 2) while Gossip-PGA is controlled by the global period H because C β < H. As a result, Gossip-PGA improves the transient stage of Gossip-SGD from O(n 3 /(1 − β) 4 ) (or O(n 3 /(1 − β) 2 in the iid scenario) to O(n 3 ) when β → 1.
Shorter transient stage than Local SGD. The transient stage comparison between Local SGD and Gossip-PGA is shown in Table 3. Using C β < H, we find Gossip-PGA is always endowed with a shorter transient stage than Local SGD. Moreover, when the network is well-connected such that β → 0, it holds that C β → 1. Gossip-PGA will have a significantly shorter transient stage than Local SGD.

Contributions
• We establish the convergence rate of Gossip-PGA for both smooth convex and non-convex problems. Our results clarify how gossip communication and periodic global averaging collaborate to improve the transient stage of Gossip and Local SGDs. We also established shorter wall-clock training times of Gossip-PGA.
• We propose Gossip-AGA, which has adaptive global averaging periods. Gossip-AGA automatically adjusts H and has convergence guarantees.
• We conduct various experiments (convex logistic regression and large-scale deep learning tasks) to validate all established theoretical results. In particular, the proposed Gossip-PGA/AGA achieves a similar convergence speed to parallel SGD in iterations, but provides 1.3 ∼ 1.9× runtime speed-up. The introduced global averaging steps in Gossip-PGA/AGA remedy the accuracy degradation in Gossip SGD and Local SGD.

Related Work
Decentralized optimization algorithms can be tracked back to (Tsitsiklis et al., 1986). After that, decentralized optimization has been intensively studied in signal processing and control community.  , 2020) proposes a unified framework to analyze algorithms with changing topology and local updates. While it covers Gossip-PGA as a special form, the theoretical and practical benefits of periodic global averaging were not studied therein. The data heterogeneity issue suffered in Gossip SGD is discussed and addressed in (Tang et al., 2018;Yuan et al., 2020;Lu et al., 2019;Xin et al., 2020). Gossip SGD is also extended to asynchronous scenarios in (Lian et al., 2018;Luo et al., 2020).
Local SGD can be traced back to (Zinkevich et al., 2010) which proposed a one-shot averaging. More frequent averaging strategy is proposed in (Zhang et al., 2016), and the convergence property of Local SGD is established in (Yu et al., 2019;Stich, 2019;Bayoumi et al., 2020). Local SGD is also widely-used in federated learning (McMahan et al., 2017;Li et al., 2019a).

Gossip SGD with Periodic Global Average
Assume all computing nodes are connected over a graph G = {V, E} where V = {1, 2, · · · , n} denote the node index and E denote the communication links between all nodes. Similar to existing decentralized algorithms (Nedic & Ozdaglar, 2009;Chen & Sayed, 2012;Lian et al., 2017;Assran et al., 2019), information exchange in the gossip step is only allowed to occur between connected neighbors. To characterize the decentralized communication, we let W ∈ R n×n be a doubly stochastic matrix, i.e., W ≥ 0, W 1 n = 1 n and 1 T n W = 1 T n . The (i, j)-th element w ij is the weight to scale information flowing from node j to node i. If nodes i and j are not neighbors then w ij = 0, and if they are neighbors or identical then the weight w ij > 0. Furthermore, we define N i as the set of neighbors of node i which also includes node i itself.
The Gossip-PGA algorithm is listed in Algorithm 1. In the gossip step, every node i collects information from all its connected neighbors. For global average step, nodes synchronize their model parameters using the efficient All-Reduce primitives. When H → ∞, Gossip-PGA will reduce to standard Gossip SGD; when W = 1 n 11 n , Gossip-Algorithm 1 Gossip-PGA Require: Initialize learning rate γ > 0, weight matrix W , global averaging period H, and let each x (0) i to be equivalent to each other. for k = 0, 1, 2, ..., T − 1, every node i do Sample ξ 2 ) j one gossip step PGA will reduce to vanilla parallel SGD; when W = I, Gossip-PGA will reduce to Local SGD.
All-Reduce v.s. multiple Gossips. In a computing cluster with n nodes, global averaging is typically conducted in an efficient Ring All-Reduce manner, rather than via multiple gossip steps as in (Berahas et al., 2018). The communication time comparison between a single gossip and Ring All-Reduce step is listed in Appendix H. In the one-peer exponential network, the exact global average can be achieved via ln(n) gossip communications, which generally takes more wall-clock time than a single Ring All-Reduce operation. Therefore, we recommend exploiting All-Reduce to conduct global averaging in Gossip-PGA.
Data-center v.s. wireless network. This paper considers deep training within high-performance data-center clusters, in which all GPUs are connected with high-bandwidth channels and the network topology can be fully controlled. Under such setting, the periodic global averaging conducted with Ring All-Reduce has tolerable communication cost, see Appendix H. For scenarios where global averaging is extremely expensive to conduct such as in wireless sensor network, the global averaging can be approximated via multiple gossip steps, or may not be recommended.

Assumptions and analysis highlights
We now establish convergence rates for Gossip-PGA on smooth convex and non-convex problems. For all our theoretical results we make the following standard assumptions.
Assumption 1 (L-SMOOTHNESS). Each local cost function f i (x) is differentiable, and there exists a constant L such that for each x, y ∈ R d : Assumption 2 (GRADIENT NOISE). Recall g (k) i is the stochastic gradient noise defined in line 2 of Algorithm 1. It is assumed that for any k and i that for some constant σ 2 > 0. Moreover, we assume ξ (k) i is independent of each other for any k and i. Filtration is defined as Assumption 3 (WEIGHTING MATRIX). The network is strongly connected and the weight matrix W satisfies W 1 n = 1 n , 1 T n W = 1 T n , null(I − W ) = span(1 n ). We also assume W − 1 n 11 T 2 ≤ β for some β ∈ (0, 1). Remark 1. Quantity β ∈ (0, 1) indicates how well the topology is connected. Smaller β indicates better-connected network while larger β implies worse-connected topology.
Analysis highlights. To derive the influence of periodic global averaging, we have to exploit all useful algorithm structures to achieve its superiority. These structures are: This structure relieves the influence of network topology; • Gossip communications within each period also contribute to consensus among nodes. This structure is crucial to establish superiority to Local SGD; • When network is large and sparse, i.e., H < 1 1−β , the global averaging is more critical to drive consensus. This structure is crucial to establish superiority to Gossip SGD when H < 1 1−β .
• When network is small or dense, i.e., H > 1 1−β , gossip communication is more critical to drive consensus. This structure is crucial to establish superiority to Gossip SGD when H > 1 1−β .
Ignoring any of the above structures in the analysis will result in incomplete conclusions on comparison among Gossip-PGA, Gossip SGD and Local SGD.
Definition 1 (DATA HETEROGENEITY). When each f i (x) is convex, we let b 2 = 1 n n i=1 ∇f i (x ) 2 denote the data heterogeneity.
When each local data follows the same distribution, it holds that f i (x) = f (x) ∀i and hence ∇f i (x ) = ∇f (x ) = 0 which also implies b 2 = 0. With Assumption 4, we let x be one of the global solutions to problem (1). Table 4. Convergence rate comparison between Gossip SGD and Gossip-PGA for smooth convex/non-convex problems. We use notation b 2 to indicate the data heterogeneity for both convex and non-convex scenarios.

Comparison with Gossip SGD
To better illustrate how periodic global averaging helps relieve the affects of network topology in Gossip SGD, we list convergence rates of Gossip SGD and Gossip-PGA for smooth convex or non-convex problems in Table 4. The first line is the general rate expression for both algorithms. In the second line we let D β = min{H, 1/(1 − β)} = 1/(1 − β) for Gossip-PGA, and in the third line we let D β = H. According to this table, we derive the transient stages of Gossip SGD and Gossip-PGA for each scenarios (i.e., large/small network, iid/non-iid data distributions) in  Table 6. Convergence rate comparison between Local SGD (L-SGD) and Gossip-PGA (G-PGA) over smooth convex/non-convex problems. The rate for Local SGD is from (Koloskova et al., 2020;Yu et al., 2019;Li et al., 2019b). the structures listed in Sec. 3.1.
Transient stage in runtime. But what people really care about in practice is runtime. Since both Gossip SGD and Gossip-PGA have the same computational overhead per iteration, we will focus on communication time spent in the transient stage.
Given the bandwidth in a computing cluster with size n, we let α denote the point-to-point latency in the network, and θ denote the communication time cost to transmit a scalar variable. Since variable x in problem (1) has dimension d, it will take θd time to transmit x between two nodes. Under this setting, the All-Reduce global averaging step will take 2θd + nα = O(θd + nα) time (see section 2.5 in (Ben-Nun & Hoefler, 2019)). The gossipstyle communication time varies with different network topologies. For the commonly-used ring or grid topology, it takes |N i |θd + α = O(θd + α) for one gossip communication, where |N i | is the neighborhood size of node i, and |N i | = 3 for the ring and 5 for the grid. As to Gossip-PGA, if we amortize the periodic All-Reduce cost into each communication, it will have |N i |θd + α + (2θd + nα)/H = O(θd + √ nα) when we set H = √ n. With the formula Total time = transient stage (in iteration) × comm. per iter. We calculate and compare the transient time between noniid Gossip-PGA and Gossip-SGD (over the grid topology) in Table 5. Other comparisons for iid scenario or the ring topology can be found in Appendix D. It is observed in all tables that Gossip-PGA has shorter transient time.

Comparison with Local SGD
The convergence rates of Gossip-PGA and Local SGD are listed in Table 6, from which we derive the transient stages of them in Table 3 (details are in Appendix D). As we have explained in the introduction, it is observed from Tables 3 and 6 that (i) Gossip-PGA always converges faster (or has shorter transient stages) than Local SGD for any β and H value, and (ii) Such superiority gets more evident for well-connected network where β → 0.
As to the wall-clock transient time of Local SGD, if we amortize the periodic All-Reduce cost into each local up-date, it will take (2θd + nα)/H = O(θd/H + nα/H) communication time per iteration. Using the transient iteration derived in Table 3, the total transient time for Local SGD (non-iid scenario) will be O(n 3 H 3 (θd + nα)). Comparing it with the total transient time O(n 3 HC 2 β β 4 (Hθd + nα)) for Gossip-PGA, we find Gossip-PGA always has shorter transient runtime for a large H > β 4 C 2 β . Remark 6. While we discuss in detail that the transient time of Gossip-PGA is shorter than Gossip and Local SGDs, it is worth noting that the communication time during the linear speedup stage (i.e., after the transient stage) also contributes to the total training time. In this stage, Gossip-PGA is less efficient due to its periodic global averaging. However, we illustrate that Gossip-PGA is always endowed with shorter total training time than Gossip and Local SGDs with extensive deep learning experiments in Sec. 5.

Gossip SGD with Adaptive Global Average
Gossip-PGA suffers from the burden of tuning H by hand.
A small H will incur more communication overhead while a large value can slow down the convergence. We further propose Gossip-AGA, an adaptive extension of Gossip-PGA.

Intuition. A small consensus variance
for each iteration, then Gossip-PGA reduces to parallel SGD and can reach its fastest convergence. Recall from Lemma 8 in the appendix that the averaged consensus 1 T k=0 E ∇f (x (k) ) 2 +d 2 γ 2 where d 1 and d 2 are constants. It is observed that the initial consensus variance (when T is small) can be significant due to large γ and E ∇f (x (k) ) 2 . In the later stage when T is sufficiently large, both the diminishing step-size γ and gradient E ∇f (x (k) ) 2 go to 0 and hence leading to a small consensus variance naturally. With these observations, it is intuitive to take global synchronizations more frequently in initial stages to reduce the overall consensus variance.

Convergence.
We denote H ( ) as the duration of the -th period. The following corollary establishes convergence for Gossip-PGA with any time-varying but finite global averaging period sequence {H ( ) }: Corollary 1. Suppose Assumptions 1-3 and 5 hold and the time-varying period H Adaptive Strategy. This subsection will propose an adaptive strategy that is inspired by (Wang & Joshi, 2019). If we recover the influence of the initial value F 0 = Ef (x (0) ) on convergence rate (8), Gossip-PGA for non-convex problems will converge at O σF For a fixed T , a period H = σ 3 2 T 1 4 /(βbF 1 4 0 n 3 4 ) will guarantee the linear speedup. Therefore, the initial period H (0) can be chosen as Similarly, for the -th period, workers can be viewed as restarting training at a new initial pointx (T −1 ) where T −1 = H (0) + · · · + H ( −1) . As a result, the -th period H ( ) can be chosen as Since Ef (x (k) ) will decrease as k increases, (9) will generate an increasing sequence of period H ( ) . We list Gossip-AGA as Algorithm 2 in Appendix G and elaborate on implementation details there.

Experimental Results
In this section, we first examine how the transient stage differs for Gossip-PGA, Gossip and Local SGDs on networks with different topology and size on convex logistic regression. Next, we systematically evaluate the aforementioned methods on two typical large-scale deep learning tasks: image classification (over 256 GPUs) and language modeling (over 64 GPUs). See Appendix F for implementation details.

Logistic Regression
We consider a distributed logistic regression problem with are local data samples at agent i with h i,m ∈ R d being the feature vector and y i,m ∈ {+1, −1} being the corresponding label. Each h i,m is generated from the normal distribution N (0; 10I d ). To generate y i,m , we first generate an auxiliary random vector x i ∈ R d with each entry following N (0, 1). Next, we generate y i,m from a uni- We let x i = x ∀i to generate data for iid scenario and x i = x j ∀i, j for non-iid scenario. Each x i is normalized.   Table 7. Comparison of Top-1 validation accuracy (Column 2) and wall-clock training time (Column 3) on different methods after finishing all epochs. We also report the epochs and training time required to reach 76% accuracy (Column 4). "N.A." implies that the target accuracy is not reached when all epochs are completed.
standard deviation with shaded area. It is observed that both Gossip SGD and Gossip-PGA will asymptotically converge at the same rate as parallel SGD (i.e., the linear speedup stage), albeit with different transient stages. Gossip-PGA always has shorter transient stages than Gossip SGD, and such superiority gets more evident when network size increases (recall that 1 − β = O(1/n 2 )). For experiments on different topologies such as grid and exponential graph, on iid data distribution, and comparison with Local SGD, see Appendix F. All experiments are consistent with the theoretical transient stage comparisons in Tables 2 and 3.

Image Classification
The ImageNet-1k (Deng et al., 2009) 1 dataset consists of 1,281,167 training images and 50,000 validation images in 1000 classes. We train ResNet-50 (He et al., 2016) model (∼25.5M parameters) following the training protocol of (Goyal et al., 2017). We train total 120 epochs. The learning rate is warmed up in the first 5 epochs and is decayed by a factor of 10 at 30, 60 and 90 epochs. We set the period to 6 for both Local SGD and Gossip-PGA. In Gossip-AGA, the period is set to 4 initially and changed adaptively afterwards, roughly 9% iterations conduct global averaging. Table 7 shows the top-1 validation accuracy and wall-clock training time of aforementioned methods. It is observed both Gossip-PGA and Gossip-AGA can reach comparable accuracy with parallel SGD after all 120 epochs but with roughly 1.3x ∼ 1.4x training time speed-up. On the other hand, while local and Gossip SGD completes all 120 epochs faster than Gossip-PGA/AGA and parallel SGD, they suffer from a 2.06% and 0.92% accuracy degradation separately. Moreover, both algorithms cannot reach the 76% top-1 accuracy within 120 epochs. We also compare with OSGP (Assran et al., 2019), which adding overlapping on the Gossip SGD. We find OSGP ×2, while faster than Gossip SGD×2, still needs more time than Gossip-PGA to achieve 76% accuracy. To further illustrate how much time it will take local and Gossip SGD to reach the target accuracy, we run another Local SGD and Gossip SGD experiments with extended epochs (i.e., Gossip SGD ×2 trains total 240 epochs and the learning rate is decayed at 60, 120, and 180 epoch. Local SGD ×3 trains total 360 epochs and the learning rate is decayed at 90, 180, and 270 epochs). It is observed that Gossip-SGD ×2 can reach the target with notably more time expense than Gossip-PGA/AGA and parallel SGD, and Local SGD ×3 still cannot reach the 76% accuracy. All these observations validate that periodic global averaging can accelerate Gossip SGD significantly. Figure 2 shows the iteration-wise and runtime-wise convergence in terms of training loss. In the left figure, it is observed Gossip-PGA/AGA converges faster (in iteration) and more accurate than local and Gossip SGD, which is consistent with our theory. In the right figure, it is observed that Gossip-PGA/AGA is the fastest method (in time) that can reach the same training loss as parallel SGD.
Compare with SlowMo. Gossip-PGA is an instance of SlowMo, in which the base optimizer is set as Gossip SGD, slow momentum β = 0, and slow learning rate α = 1. We made experiments to compare Gossip-PGA with SlowMo. It is observed the additional slow momentum update helps SlowMo with large H but degrades it when H is small. This observation is consistent with Fig. 3 Ring Topology. While the convergence property of Gossip-PGA is established over the static network topology, we utilize the dynamic one-peer exponential topology in the above deep experiments because it usually achieves better accuracy. To illustrate the derived theoretical results, we make an additional experiment, over the static ring topology, to compare Gossip-PGA with Gossip SGD in Table 9. It is observed that Gossip-PGA can achieve better accuracy than Gossip SGD after running the same epochs, which coincides with our analysis that Gossip-PGA has faster convergence.
Scalability. We establish in Theorem 2 that Gossip-PGA can achieve linear speedup in the non-convex setting. To  and BookCorpus datasets. We set the period to 6 for both Local SGD and Gossip-PGA. In Gossip-AGA, the period is set to 4 initially and changed adaptively afterwards, roughly 9.6% iterations conduct global averaging.  Figure 3 shows the iteration-wise and runtime-wise convergence w.r.t training loss of the aforementioned methods. The left plot shows Gossip-PGA/AGA has almost the same convergence as Gossip SGD in iterations; the right plot shows that Gossip-AGA is the fastest method in training time that can reach the same accuracy as parallel SGD.

Conclusion
We introduce Gossip-PGA/AGA to mitigate the slow convergence rate of Gossip SGD in distributed training. Theoretically, we prove the convergence improvement in smooth convex and non-convex problem. Empirically, experimental results of large-scale training validate our theories.

A. Preliminary
Notation. We first introduce necessary notations as follows.
• Given two matrices x, y ∈ R n×d , we define inner product x, y = tr(x T y) and the Frobenius norm x 2 F = x, x .
Gossip-PGA in matrix notation. For ease of analysis, we rewrite the main recursion of Gossip-PGA in matrix notation: Gradient noise. We repeat the definition of filtration in Assumption 2 here for convenience.
• With Assumption 2, we can evaluate the magnitude of the averaged gradient noise: where (a) holds because ξ • We define gradient noise as s and (a) holds due to the law of total expectation.
• For any 0 ≤ k < , it holds that Smoothness. Since each f i (x) is assumed to be L-smooth in Assumption 1, it holds that f (x) = 1 n n i=1 f i (x) is also L-smooth. As a result, the following inequality holds for any x, y ∈ R d : Smoothness and convexity. If each f i (x) is further assumed to be convex (see Assumption 4), it holds that f (x) = 1 n n i=1 f i (x) is also convex. For this scenario, it holds for any x, y ∈ R d that: Network weighting matrix. Suppose a weighting matrix W ∈ R n×n satisfies Assumption 3, it holds that Submultiplicativity of the Frobenius norm. Given matrices W ∈ R n×n and y ∈ R n×d , it holds that To verify it, by letting y j be the j-th column of y, we have W y
Next we establish the consensus lemmas in which Gossip-PGA is fundamentally different from Gossip SGD. Note that Gossip-PGA takes global average every H iterations. For any k = 0, 1, · · · , we define τ (k) = max{ : ≤ k and mod( , H) = 0} (21) as the most recent iteration when global average is conducted. In Gossip-PGA, it holds thatx τ (k) = x can only happen when k = 0.
For Gossip-PGA, the real challenge is to investigate how the periodic global averaging helps reduce consensus error and hence accelerate the convergence rate. In fact, there are two forces in Gossip-PGA that drive local model parameters to reach consensus: the gossip communication and the periodic global averaging. Each of these two forces is possible to dominate the consensus controlling in different scenarios: Scenario I. Global averaging is more critical to guarantee consensus on large or sparse network, or when global averaging is conducted frequently.
Scenario II. Gossip communication is more critical to guarantee consensus on small or dense network, or when global averaging is conducted infrequently.
Ignoring either of the above scenario will lead to incomplete or even incorrect conclusions, as shown in Remark 5. In the following, we will establish a specific consensus lemma for each scenario and then unify them into one that precisely characterize how the consensus distance evolves with iterations in Gossip-PGA.
Lemma 2 (CONSENSUS LEMMA: GLOBAL AVERAGING DOMINATING). Under Assumptions 1-4, it holds for k = τ (k), τ (k) + 1, · · · , τ (k) + H − 1 that Observing Lemmas 2 and 3, it is found that bounds (22) and (23) are in the same shape except for some critical coefficients. With the following relation: we can unify Lemmas 2 and 3 into: , and D β = min{ 1 1−β , H}. Remark 8. This lemma reflects how the network topology and the global averaging period contribute to the consensus controlling. For scenario I where the network is large or sparse such that 1/(1 − β) > H, Lemma 4 indicates that the consensus error is mainly controlled by the global averaging period (i.e., D β = H). On the other hand, for scenario II where the network is small or dense such that 1/(1 − β) < H, Lemma 4 indicates that the consensus error is mainly controlled by gossip communication (i.e., D β = 1/(1 − β)).
Using Lemma 4, we derive the upper bound of the weighted running average of E x k −x k 2 F : Lemma 5 (RUNNING CONSENSUS LEMMA). Suppose Assumptions 1-4 hold and step-size γ < 1/(4LβD β ), it holds for T > 0 that where c 2 and c 3 are constants defined as With Lemmas 1 and 5, we can establish the final convergence Theorem 1, see the proof in Sec. B.5.

B.2. Proof of Lemma 1.
This lemma was first established in (Koloskova et al., 2020, Lemma 8). We made slight improvement to tight constants appeared in step-size ranges and upper bound (20). For readers' convenience, we repeat arguments here.
Recall the algorithm in (10). By taking the average on both sides, we reach that By taking expectation over the square of both sides of the above recursion conditioned on F (k−1) , we have Note that the first term can be expanded as follows.
We now bound the term (A): where (a) holds because of the inequality (15) and (17). We next bound term (B) in (31): Substituting (33) and (32) into (31), we have where the last inequality holds when γ < 1 4L . Substituting the above inequality into (30) and taking expectation over the filtration, we reach the result in (20).
To simplify the notation, we define Using these notations, we rewrite (22) for any k = 0, 1, 2, · · · that We next define By taking the running average over both sides in (48) and recalling A (τ (k)) = 0, it holds that We further define With these notations, we have where (a) holds because To guarantee 1 − c 1 D β ≥ 1 2 , it is enough to let γ ≤ 1/(4LβD β ).
B.5. Proof of Theorem 1 Following the notation in (47), we further define F (k) := E x (k) − x 2 F . With these notations, the inequality (20) becomes Taking weighted running average over the above inequality to get where the last inequality holds when γ ≤ 1/(12LβD β ). Substituting c 3 into the above inequality, we have The way to choose step-size γ is adapted from Lemma 15 in (Koloskova et al., 2020). For simplicity, we let and inequality (56) becomes Now we let γ = min C.1. Proof Outline for Theorem 2.
The proof outline for Theorem 2 is similar to that for Theorem 1. The descent lemma (Koloskova et al., 2020, Lemma 10) was established follows.

C.2. Proof of Lemma 6.
This lemma was first established in (Koloskova et al., 2020, Lemma 10). We made slight improvement to tight constants appeared in step-size ranges and upper bound (64). For readers' convenience, we repeat arguments here. Recall that where (a) holds because Note that and Substituting (72) and (73) into (70), taking expectations over F (k) and using the fact that γ < 1 4L , we reach the result in (64).

C.4. Proof of Lemma 8.
We first simplify the notation as follows: With these notations, we can follow the proof of Lemma 5 to get the final result.
Following the notation in (80), we further define F (k) := Ef (x (k) ). With these notations, the inequality (64) becomes Taking the weighted running average over the above inequality and divide T + 1 to get where the last inequality holds when γ ≤ 1 9LHβ . Substituting c 3 into the above inequality, we have By following the arguments (57) -(63), we reach the result in (8).
Hmax k=0 β k = C β , we follow Appendix C.3 and C.4 to reach the consensus distance inequality: where c 2 and c 3 are constants defined as and D β = min{1/(1 − β), H max }, C β = Hmax k=0 β k . With Lemma 6 and inequality (90), we can follow Appendix B.5 to reach the result in Corollary 1.
We implement all the aforementioned algorithms with PyTorch (Paszke et al., 2019) 1.5.1 using NCCL 2.5.7 (CUDA 10.1) as the communication backend. Each server contains 8 V100 GPUs in our cluster and is treated as one node. The inter-node network fabrics are chosen from 25 Gbps TCP (which is a common distributed training platform setting) and 4×100 Gbps RoCE (which is a high-performance distributed training platform setting).
All deep learning experiments are trained in the mixed precision using Pytorch extension package NVIDIA apex (https://github.com/NVIDIA/apex). For Gossip SGD related training, we use the time-varying one-peer exponential graph following (Assran et al., 2019). Workers send and receive a copy of the model's parameters to and from its peer, thus keeping the load balancing among workers. All data are stored in the cloud storage service and downloaded to workers using HTTP during training.

Image Classfication
The Nesterov momentum SGD optimizer is used with a linear scaling learning rate strategy. 32 nodes (each node is with 8 V100 GPUs) are used in all the experiments and the batch-size is set as 256 per node (8,192 in total). The learning rate is warmed up in the first 5 epochs and is decayed by a factor of 10 at 30, 60 and 90 epochs. We train 120 epochs by default (unless specified otherwise) in every experiment and record the epoch and runtime when a 76% top-1 accuracy in the validation set has reached. 25 Gbps TCP network is used for inter-node communication in ResNet-50 training. In 4×100 Gbps RoCE network, the communication overhead is negligible given the high computation-to-communication ratio nature of ResNet models and Parallel SGD with computation and communication pipeline is recommended. We use a period 6 for both Local SGD and Gossip-PGA. In Gossip-AGA, the averaging period is set to 4 in the warm-up stage and changed adaptively afterwards, roughly 9% iterations conduct global averaging.
Language Modeling All experiments are based on NVIDIA BERT implementation with mixed precision support and LAMB optimizer (You et al., 2019). 8 nodes are used in all the experiments with a batch-size 64 per GPU (4096 in total). We do not use gradient accumulation as it is not vertical with Local SGD. We only do phase 1 training and indicate the decreasing of training loss as convergence speed empirically. The learning rate is scaled to 3.75e −4 initially and decayed in a polynomial policy with warm-up. The phase 1 training consists of 112,608 steps in all experiments. We use a period 6 for both Local SGD and Gossip-PGA. In Gossip-AGA, the averaging period is set to 4 in the warm-up phase and changed adaptively afterwards, roughly 9.6% iterations conduct global averaging. O(θd + α) O(θd + √ nα) TRANSIENT TIME O(n 11 θd + n 11 α) O(n 5 θd + n 5.5 α) Table 13. Transient time comparison between Gossip SGD and Gossip-PGA for non-iid scenario over the specific ring (1 − β = O(1/n 2 )) topologiy. We choose H = √ n as the period in Gossip-PGA.
GOSSIP SGD GOSSIP-PGA O(θd + α) O(θd + √ nα) TRANSIENT TIME O(n 7 θd + n 7 α) O(n 4 θd + n 4.5 α) Table 14. Transient time comparison between Gossip SGD and Gossip-PGA for iid scenario over the specific ring (1 − β = O(1/n 2 )) topologiy. We choose H = √ n as the period in Gossip-PGA. In this subsection we will test the performance of Gossip-PGA with iid data distribution and on different topologies. We will also compare it with Local SGD.
Experiments on iid dataset. Figure 4 illustrates how Gossip SGD and Gossip-PGA converges under the iid data distributed setting over the ring topology. Similar to the non-iid scenario shown in Figure 1, it is observed that Gossip-PGA always converges faster (or has shorter transient stages) than Gossip SGD. When network size gets larger and hence β → 1, the superiority of Gossip-PGA gets more evident. Moreover, it is also noticed that the transient stage gap between Gossip SGD and Gossip-PGA is smaller than the non-iid scenario in all three plots in Figure 4. All these observations are consistent with the transient stage comparisons in Table 2.
Experiments on different topologies. Figure 5 illustrates how Gossip SGD and Gossip-PGA converges over the exponential graph, grid and ring topology. For all plots, it is observed that Gossip-PGA is no worse than Gossip SGD. Moreover, as the network gets sparser and hence β → 1 from the left plot to right, it is observed that the superiority of Gossip-PGA gets more evident, which is consistent with the transient stage comparisons between Gossip SGD and Gossip-PGA in Table 2.
Comparison with Local SGD. Figure 6 illustrates how Local SGD and Gossip-PGA converges over the exponential graph, grid and ring topology. The period is set as H = 16. In all three plots, Gossip-PGA always converges faster than Local SGD because of the additional gossip communications. Moreover, since the exponential graph has the smallest β, it is observed Gossip-PGA has almost the same convergence performance as parallel SGD. Figure 7 illustrates how Local SGD and Gossip-PGA converges over the grid topology with different periods. It is observed that Gossip-PGA can be significantly faster when H is large. All these observations are consistent with the transient stage comparisons in Table 3.

F.3. More experiments on image classification.
Training accuracy. Figure F.3 shows the iteration-wise and time-wise training accuracy curves of aforementioned algorithms separately. In the left figure, it is observed Gossip-PGA/AGA converges faster (in iteration) and more accurate than local and Gossip SGD, which is consistent with our theory. In the right figure, it is observed that Gossip-PGA/AGA is the fastest method (in time) that can reach the same training accuracy as parallel SGD.
The effect of averaging period.  Experiments on SGD optimizer (without momentum). In previous Imagenet training, Nesterov momentum SGD optimizer is used. Following common practice (Lian et al., 2017;Assran et al., 2019;Tang et al., 2018), we establish the convergence rate of the non-accelerated method while running experiments with momentum. For the sake of clarity, we further add a new series of experiments on Gossip-SGD without momentum, see Table 16. Gossip-PGA still outperform Gossip-SGD utilizing the SGD optimizer. G. Implementation of Gossip AGA Practical consideration. The Gossip-AGA algorithm is listed in Algorithm 2. We use a counter C to record the number of gossip iterations since last global averaging. The global averaging period H is initialized to a small value H init (e.g. 2∼4).
Once C equals to current H, global averaging happens. In practice, we sample loss scores for the first fewer iterations and get a F init estimation in a running-average fashion. We remove the exponential term in the loss score ratio for flexible period adjustment. Algorithm 2 Gossip-AGA Require: Initialize x 0,i = x 0 , learning rate γ > 0, topology matrix W for all nodes i ∈ {1, 2, ..., n}, global averaging period H = H init , C ← 0, F init ← 0, warmup iterations K w for k = 0, 1, 2, ..., T − 1, every node i do C ← C + 1 Sample mini-batch data ξ ) and loss