Extension of Interval-Valued Fermatean Fuzzy TOPSIS for Evaluating and Benchmarking COVID-19 Vaccines

: In order to help curb the spread of the COVID-19 pandemic, this paper develops a multi-attribute decision-making framework for COVID-19 vaccine evaluation based on their major clinical characteristics and efficacy. Firstly, a new multi-criteria Technique for Order of Preference by Similarity to Ideal Solution (TOPSIS) modification has been constructed in an interval-valued Fermatean fuzzy (IVFF) environment, improving the shortcomings of traditional TOPSIS. Secondly, a new conceptual framework for static and dynamic evaluation of COVID-19 vaccines has been built. The proposed methodology incorporates a variety of crisp and fuzzy MCDM methods. The analysis of the results of two practical examples shows that the new framework for vaccine comparison is feasible and effective, and finally, some recommendations for enhancement of government anti-COVID-19 strategies are suggested. distance measure; technique for order of preference by similarity to ideal solution (TOPSIS); IVFF TOPSIS; COVID-19; online public attitude; vaccination strategies MSC: 94D05

Introduction
The coronavirus epidemic is one of the most serious challenges facing countries in the world since World War II [1]. More than 550 million people have been infected and at least 6.3 million have died so far from severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) [2]. Due to unprecedented investments in research and development and global collaboration, scientists have rapidly developed a variety of vaccines against coronavirus disease 2019  in record time [3]. According to World Health Organization (WHO) [4], vaccination prevents a disease from spreading through a population and decreases severe COVID-19 illness and deaths.
However, there is false and misleading content on the Internet that vaccines modify DNA, harm or cause poisoning of the human body, etc. [5]. All these misconceptions about the safety and effects of COVID-19 vaccines can lead to hesitation and denial of vaccination among the population. The lack of a common perspective on the worldwide health crisis can cause significant damage to public health, through paranoia and fear, and leave people unprotected or more vulnerable to the virus [6].
In September 2021, WHO [7] set an ambitious global action plan-to reach 70% global vaccination coverage, including 100% of those aged over 60, 100% of health workers, and 100% of those with underlying conditions by 30 June 2022. In the European Union, by 1 September 2021, just eight months after the start of COVID-19 vaccination, 70% of the adult population has already been fully vaccinated [8]. Unfortunately, the picture is different in other parts of the globe. In low-income countries, the share of vaccinated is still very small-less than 15% of the population has been inoculated within the specified period. In 90 out of 220 countries, only between 20% and 70% of the population has been vaccinated within the same period [9]. This delay in the immunization process could prolong the fight against the pandemic and has serious economic consequences, such as a slowdown in economic recovery, lack of supply in global labor markets, an increase in government debt, and a decline in investments.
Insufficient production of vaccines, their supply chain challenges, and uneven global distribution have a particularly negative impact on the low-income population of the world: • Citizens live at elevated risk of health problems and higher mortality from COVID-19 and related comorbidities.

•
There is a growing probability of the emergence of a black market for vaccines against COVID-19.

•
Elderly and vulnerable people can easily fall victim to vaccine fraud.
The main challenges of insufficient vaccination and low immunization rates to the governments are as follows: • Vaccines shortages-require a solving budget, transportation, and logistics problems such as supply chain disruptions and delays caused by suppliers.

•
Providing an informed choice of vaccine-raises the question of comparing available vaccines based on different indicators and objective decision-making.

•
Vaccine hesitancy-specific concerns of some communities can be overcome through coordinated public information campaigns at the local and global levels. • Delayed vaccination and lack of immunity-require more restrictions if the pandemic returns.
Many of the above-mentioned challenges could be overcome by improving public health strategies by adding administrative activities. To resolve the second challenge, multi-criteria decision-making (MCDM) methods can be applied. These techniques can handle the problem of vaccine selection involving a multitude of criteria in sorting a finite set of decision alternatives and emphasizing the best feasible option. MCDM methods have a wide variety of applications, including product selection [10,11] and customer prioritization [12].
Unlike classic MCDM methods, their fuzzy variants may select the best alternative in case of imprecise and vague estimates. Many MCDM methods have been modified using fuzzy sets and their advances variations [13][14][15][16]. The application of fuzzy assessments describes real-life situations more objectively and improves ranking in case of subjectivity and inaccuracy in assessment. The main advantage of fuzzy multi-criteria algorithms for decision analysis is that they construct more realistic rankings in decision-making process [17].
In this paper, our tasks are the following: (1) develop and verify new MCDM framework for COVID-19 vaccine selection, and (2) study and evaluate new modification of multi-criteria Technique for Order of Preference by Similarity to Ideal Solution (TOPSIS) method as a tool for comparison and prioritizing of COVID-19 vaccines. We compare vaccines' features under two scenarios-in static and dynamic situations and compare different vaccines to understand which ones are more effective and safer.
The contributions of this paper can be summarized as follows: (1) We analyze and summarize the existing multi-criteria approaches for COVID-19 vaccines selection. We classify them according to the included techniques and types of estimates (numeric, interval and linguistic values; crisp and fuzzy numbers) and divide them into three main categories by their complexity (number of multi-criteria techniques), flexibility (fuzziness character) and iteration (single or repeated data processing), respectively. (2) We design a theoretical framework for ranking COVID-19 vaccines based on single and hybrid methods with both crisp and fuzzy estimates. The former employ only one weight determination or ranking method, while the latter uses a combination of weight determination and ranking methods. We also apply several auxiliary techniques such as fuzzy interval arithmetic operations, robustness, and sensitivity analysis to improve the efficacy of decision analysis and approach benchmark rankings. To enhance the efficiency of the developed fuzzy Fermatean group TOPSIS method, we implement a recently proposed 3D distance metric to achieve a better multi-criteria comparison of vaccines' features. (3) Finally, we construct static and dynamic rankings with real-world COVID-19 datasets based on single or repeated multi-criteria decision analysis. In the former case, we employ experts' opinions as input for decision matrices. In the latter case, the ranking depends on measuring public attitudes towards vaccines. The dynamics detection may also be based on the user's behavior and feelings, expressed in social media data. The comparative analysis of obtained results with other multi-criteria baselines shows the effectiveness as well as the necessity of proposed ideas.
This paper is organized as follows: Section 2 presents the literature review outlining the motivation of our study. Section 3 describes the proposed theoretical decision-making framework for vaccine selection, main characteristics, and operations with interval-valued Fermatean fuzzy numbers (IVFFNs) and new TOPSIS modification in the IVFF environment. Section 4 provides details about two practical examples and ends with a discussion on the obtained results. The last section summarizes the work completed, concludes with final remarks, and set up directions for future works.

Literature Review on MCDM and Its Applications in COVID-19 Vaccine Evaluation
Although vaccines against COVID-19 have recently been developed, they have already been explored in many studies. Some of scholars reflect only the medical point of view and their research is essentially descriptive or generic. They usually make purely medical comparisons and often do not rely on advanced statistical methods for data analysis. Another part of studies involves modern computational approaches such as machine learning, optimization, and MCDM methods. The advantage of the latter approach is that MCDM does not require large datasets and computationally intensive procedures.
Öztaş et al. have discovered the most important criteria that count in decision-making considering uncertainties associated with parameters such as risks, and costs for individuals in order to select the right COVID-19 vaccine. A survey study for assessment according to the given most important criteria based on expert opinion is conducted through the Best Worst Method (BWM) for weight determination. The obtained results show that the efficacy criterion has the highest score, and it is followed by storage requirements, incorporated vaccine technology, and international acceptance criterion. Participants prioritize the origin and price of the vaccine behind all other criteria [18].
Ozsahin et al. have evaluated fifteen important vaccines based on criteria such as dose number, dose schedule, storage advantages, efficacy, and side effects. In this evaluation, the researchers have used the fuzzy PROMETHEE approach, and the importance level of the criteria has been determined based on expert opinion [20].
Çetin et al. have compared, rated, and ranked SARS-CoV-2 vaccines as well as vaccine platforms in multi-attributes using grey systems theory. The authors have selected twelve leading vaccines and fourteen attributes such as efficacy rate, safety (reactogenicity) and protection against variants to children use, approvals to prices, logistics, and market share [21].
Öztürk et al. have employed the interval-valued intuitionistic fuzzy VIseKriterijumska Optimize Kompromisno Resenje (VIKOR) method for COVID-19 vaccine selection using criteria such as side effects of vaccines, supply chain processes, storage conditions, costs and perception on people in decision-making [22]. Forestal and Pi have created a hybrid methodology based on ELimination Et Choice Translating REality III (ELECTRE III)-Genetic Algorithm (GA) and TOPSIS to select the optimal SARS-CoV-2 vaccine [23].
Ecer has developed a new intuitionistic fuzzy (IF) extension of the multi-attributive ideal-real comparative analysis (MAIRCA) framework to assess coronavirus vaccines. Based on the group decision-making, the IF-MAIRCA both extracts the criteria weights and discovers the prioritization of the alternatives under uncertainty. In this work, five coronavirus vaccines are evaluated according to various criteria. The findings demonstrate that the most significant criteria considered in coronavirus vaccine selection are the duration of protection, the effectiveness of the vaccine, success against the mutations, and logistics, whereas the best coronavirus vaccine is Vaxzevria (AZD1222) [24].
According to their complexity (number of decision methods used), the existing models may be divided into two groups-single [18,21] or hybrid [19,23] multi-criteria techniques, respectively. According to input data specifics, models can also be divided into two groupscrisp [18,19,21,23] or fuzzy [20,22,24] estimates. The first group is developed for arithmetic calculations and distance metrics for crisp input values, while the second one unites multicriteria methods working in fuzzy environments. The last third category also includes two groups of methods: non-iterative and iterative. The former involves the ranking of particular alternatives that are already known to the decision-maker. The latter prioritizes a dynamic set of alternatives on an ongoing basis (e.g., periodically), including in real time. All the above-mentioned studies refer to non-iterative methods.
The literature review shows that there is no universal approach or unified procedure for solving the COVID-19 vaccine selection problem. The previous studies provide some insights on the comparison of vaccines, but they also demonstrate some shortcomings: (1) The majority of proposed multi-criteria solutions do not offer a holistic (multi-stage) solution but focus only on specific parts of the problem such as: (1) determining the relative importance of a few medical attributes in the criteria system [18] or (2) generating of vaccines ranking based on only one multi-criteria method [19,21]. (2) There are only a few studies [20,22,24] that can handle inaccurate attribute estimates.
As the evaluation of COVID-19 vaccines often depends on qualitative factors, their assessments should be made by a group of experts using classic fuzzy numbers or their advanced variants. (3) Most of existing fuzzy solutions implement only one or two MCDM methods in a non-iterative procedure [20,22].
However, evaluation should be a holistic process depending on many factors; for example, technological, economic and organizational parameters, which can often be expressed only by inaccurate, unclear and uncertain estimates. To overcome the abovementioned drawbacks, in this paper we propose a new fuzzy methodology for COVID-19 vaccine selection. The choice of a specific vaccine according to the public health strategy or individual preferences is a complex procedure, influenced by many features. While at national level preferred vaccine depends on factors such as national vaccination program, availability and affordability (storage and transport requirements) of vaccines, at individual level, choice may be influenced by health status, age, lifestyle, occupation of the person as well as GP or immunization provider recommendations.
To solve COVID-19 vaccine selection problem, we propose to follow a unified way applying a new integrated multi-criteria framework for vaccines' data processing. The group multi-criteria approach has the potential to solve this multi-factor problem. Alternatives include a variety of COVID-19 vaccines currently available in a particular country. The solution to the problem is the vaccine that best meets the national requirements or recipient's preferences.

Literature Review on Proposed Vaccines' Evaluation Criteria
The COVID-19 vaccines usually contain an agent that resembles the disease-causing microorganism and are often made from an attenuated, inactivated, or killed form of the virus or one of its surface proteins. The immune response protects from infection if the real virus enters the human body. According to the literature review, the most important characteristics for COVID-19 vaccine evaluation are the following: type of vaccine, number of doses, dose schedule, storage conditions, efficacy, and side effects [18][19][20][21][22]24,25]. In this subsection, we present these vaccines' peculiarities in order to build an attribute-based evaluation system.
(1) Vaccine Type There are three main approaches to designing COVID-19 vaccines using: viral vector; parts (subunits) or whole virus; genetic material, providing instructions for making specific proteins that can trigger the immune system.

•
Viral vector vaccines-these vaccines use a harmless virus version called "vector" to deliver to the body a gene of SARS-CoV-2. Cells employ it to produce a harmless fragment of the coronavirus, or so-called "spike" protein, found on the surface of SARS-CoV-2. Once the immune system recognizes this foreign protein, it creates antibodies and defensive white blood cells. If the body later becomes infected with the COVID-19 virus, the antibodies will fight it. The Jcovden COVID-19 vaccine (Janssen) is a vector vaccine. AstraZeneca and the University of Oxford have also developed a vector COVID-19 vaccine (Vaxzevria). • Antigen vaccines-they use specific antigens to stimulate the immune system. Subunit antigen vaccines include only the parts of a virus that stimulate the immune system. This type of COVID-19 vaccine also contains harmless proteins. The immune system recognizes it as a foreign protein and thus activates the body's natural defenses. Nuvaxovid (Novavax) is a protein subunit COVID-19 vaccine. The second group of antigen vaccines is those with the inactivated whole virus. They are produced using traditional vaccine technology and has established methods and a high level of safety. A theoretical advantage of inactivated vaccines is that they contain additional viral proteins, which could broaden protection beyond anti-spike protein responses and reduce the escape of variants from vaccine immunity. Valneva COVID-19 vaccine (VLA2001) is currently the only whole virus, inactivated vaccine candidate in clinical trials against COVID-19 in Europe.

•
Nucleic acid vaccines-messenger RiboNucleic Acid (mRNA) teaches cells how to produce a protein (or part of a protein) that elicits an immune response. The technology for creating an mRNA vaccine has been developed for several decades. These vaccines do not contain live viruses and do not affect human DNA. mRNAs are the vaccines of Pfizer/Biontech and Moderna, Comirnaty, and Spikevax, respectively.
(2) Number of doses and dose schedule The number of doses and time interval between doses are important indicators that affect the vaccination rate. Each next dose further complicates the vaccination procedure and prolongs the time required for its primary series. It is crucial to maintain users' motivation to finish a multi-dose vaccination. The vaccine schedule is also an essential factor influencing the completion of the vaccination process.

(3) Storage Advantages
Conditions of use and storage, shelf life, and stringent requirements in vaccine transport are very important in state-level procurement planning. The solution to various supply chain problems does not affect in any way the choice of vaccine at the individual level. However, they may influence government decision-making regarding vaccine policy and deployment. Currently, Comirnaty is the only COVID-19 vaccine that should be stored and transported at ultra-low temperature conditions (−60 • C to −86 • C). Recommended temperatures for the majority of vaccines are between 2 • C and 8 • C for the refrigerator and between −50 • C and −15 • C for the freezer.

(4) Efficacy
The efficacy of vaccines refers to the degree to which a vaccine prevents symptomatic or asymptomatic infection in clinical trials. Effectiveness is associated with preventing person-to-person virus transmission; protecting against serious illness and hospitalization, and significantly reducing the risk of death. It has been found that after its administration, the efficacy of the COVID-19 vaccines gradually decreases over time. The level of protection of COVID-19 vaccines ranges among different age groups and virus strains.
(5) Side Effects COVID-19 vaccines can cause side effects, but not everybody will experience them. In addition, most side effects of vaccination are mild and short-term. Scientists continue to accumulate and analyze data on the frequency of adverse reactions after vaccine administration and their severity. Based on datasets collected so far, some numerical indicators can be formed for the side effects caused by COVID-19 vaccines.
The above list of attributes for vaccines' comparison can be expanded using additional indicators such as medical (number of doses administered, the number of hospitalizations, number of severe cases among the vaccine group), technological (production technology, composition, dose quantity) or economic (cost per dose) parameters.

Literature Review on COVID-19 Vaccines
In this subsection, we present the most widely used COVID-19 vaccines, approved by the world's leading authorities.

1.
Comirnaty (also known as Pfizer-BioNTech COVID-19 Vaccine) (BNT162b2), Pfizer, New York City, NY, USA, https://www.pfizer.com; BioNTech, Mainz, Germany (https://www.biontech.com, accessed on 7 July 2022) Comirnaty is a vaccine for preventing COVID-19 in people aged 5 years and older. Comirnaty contains mRNA molecules with instructions for producing a protein from SARS-CoV-2. Comirnaty does not contain the virus itself and cannot cause COVID-19. According to the WHO Strategic Advisory Group of Experts on Immunization (SAGE), the Pfizer-BioNTech COVID-19 mRNA vaccine is safe and effective. The vaccine is approved for use as a two-dose series. Individuals may receive the second dose 4-8 weeks after the first dose in the primary series. The efficacy of Comirnaty is 95% [20].

2.
Spikevax (previously COVID-19 Vaccine Moderna) (mRNA-1273), Moderna, Cambridge, MA, USA (https://www.modernatx.com, accessed on 7 July 2022) Spikevax is a vaccine for preventing COVID-19 in people aged 6 years and older. Spikevax contains mRNA molecules, which have instructions for making the spike protein. Spikevax does not contain the virus itself and cannot cause COVID-19. The vaccine is approved for use as two doses in the primary series, given 4-8 weeks apart. The efficacy of Spikevax is 94.1% [26].

3.
Convidecia (Ad5-nCoV), CanSino Biologics, Tianjin, China, (https://www.cansinotech. com, accessed on 7 July 2022) Convidecia is a recombinant viral vector vaccine for COVID-19 produced in China. The single-dose vaccine was developed on CanSino Biologics' adenovirus-based viral vector vaccine technology platform. The WHO's SAGE recommends the use of the vaccine as a single dose, in all age groups 18 and above. The efficacy of Convidecia is 63.7% [20].

4.
Sputnik V (Gam-COVID-Vac), Gamaleya Research Institute of Epidemiology and Microbiology, Moscow, Russia, (https://gamaleya.org/en, accessed on 7 July 2022) The COVID-19 vaccine Sputnik V is an adenoviral-based, two-part vaccine against the SARS-CoV-2 coronavirus. Initially produced in Russia in 2020, Sputnik V uses a weakened virus to deliver small parts of a pathogen and stimulate an immune response. The Sputnik V vaccine reduces the time taken for the actual development of immunity to SARS-CoV-2. The Sputnik V is a two-dose schedule vaccine that has been administered to people who are 18 years of age and above. The second dose should be taken after a 3-week gap from the first dose. The efficacy of Sputnik V is 95% [20].

9.
Vaxzevria (previously COVID-19 Vaccine AstraZeneca) (AZD1222), University of Oxford, Oxford, UK; AstraZeneca Cambridge, UK (https://www.astrazeneca.com, accessed on 7 July 2022) The Vaxzevria vaccine is developed from a virus, which is a weakened version of a common cold virus (adenovirus). In addition, genetic material has been added to make proteins from the coronavirus. After vaccination, the surface spike protein is produced, priming the immune system to attack SARS-CoV-2 if it later infects the body. The Vaxzevria primary vaccination course consists of two separate doses. The second dose should be administered between 4 and 12 weeks after the first dose. The efficacy of Vaxzevria is 79% [20]. 10. Nuvaxovid (NVX-CoV2373), Novavax, Gaithersburg, MD, USA (https://www.novavax. com/, accessed on 7 July 2022) Nuvaxovid is a subunit vaccine and contains a version of the spike protein, which has been produced in a laboratory. It also contains an "adjuvant", a substance to help strengthen the immune responses to the vaccine. The dose schedule is to give 2 doses 21 days apart. The efficacy of Nuvaxovid is 92.6% [29]. 11. Jcovden (previously COVID-19 Vaccine Janssen), Janssen Pharmaceutical, Beerse, Belgium (https://www.janssen.com, accessed on 7 July 2022) Jcovden is produced by another virus (of the adenovirus family) that has been modified to contain the gene for making a protein found on SARS-CoV-2. Jcovden does not contain SARS-CoV-2 itself and cannot cause COVID-19. The vaccine is authorized for emergency use as a one-dose series. The efficacy of Jcovden is 74.8% [30]. Covishield COVID-19 vaccine, formerly known as ChAdOx1 nCoV-19, is made from a weakened version of an adenovirus. In addition, genetic material has been added to the ChAdOx1 construct, which is used to make proteins from the SARS-CoV-2 spike protein.
CoviShield is the Serum Institute of India version of the AstraZeneca COVID-19 vaccine. The gap between the first and second doses of the Covishield vaccine was extended to 12−16 weeks. The efficacy of Covishield is 62% [20]. Table 1 contains data about manufacturer, type of vaccine, applicability, conditions for storage, dosing schedule and efficacy of above-mentioned COVID-19 vaccines. According to the collected data (Table 1), all the above-mentioned vaccines are safe and effective tools to prevent COVID-19 transmission, hospitalization, and death, but their characteristics vary depending on the particular vaccine considered. The analysis of the main characteristics of selected COVID-19 vaccines shows that the most commonly used vaccines belong to the three main vaccine types: Most COVID-19 vaccines require two doses because the second dose helps to better reinforce the immune response. Only two out of fifteen vaccines (CanSino Biologics and Janssen COVID-19 vaccines), both viral vector vaccines, require only one shot. In the rest of the cases, the interval between doses for two-dose vaccines should be three-or four-week. Moreover, three out of fifteen vaccines require ultra-low or fridge temperature conditions (Comirnaty, Spikevax, and Sputnik V). Overall, all COVID-19 vaccines have high efficacy against the original strain and the variants of concern and are well tolerated. Comirnaty, Spikevax, Sputnik V, EpiVacCorona, INO-4800, and Covifenz have the highest efficacy (more than 90%) after two doses in preventing symptomatic cases. The described vaccines rarely expose serious adverse effects. Some side effects of the vaccination are similar to the symptoms of COVID-19 (pain, redness, or swelling at the site where the shot was administered, tiredness, headache, muscle pain, chills, fever, or nausea throughout the rest of the body) [25].

Methodological Framework for Vaccine Selection
This section provides an overview of the theoretical foundations of contemporary MCDM methods and interval-valued Fermatean fuzzy numbers (IVFFNs). Then, we introduce a new TOPSIS modification via IVFFNs. Finally, we propose a new conceptual framework for the analysis of COVID-19 vaccine data.

Methodological Foundations of MCDM Methods
The multi-criteria decision methods are used to select the most suitable candidates among a given set of alternatives ranked by multiple criteria. MCDM methods with crisp and fuzzy numbers refer to the group of soft computing methods. The first MCDM method has been created in the 1970s. Some of the advantages of these methods are as follows: • They can be used in both modes-individual and group by decision-making experts. • They can easily be combined in pairs consisting of the relative weight determination method and method for alternative ranking. For solving the problem for COVID-19 vaccines selection, we propose to employ the classic Technique for Order of Preference by Similarity to Ideal Solution-TOPSIS (1981) [33] method and some recently developed MCMD models. The most widely used MCDA techniques, created after the first decade of the 21st century are as follows: Additive Ratio Assessment-ARAS (2010) [34], Weighted Aggregated Sum Product Assessment-WASPAS (2014) [35], Evaluation based on Distance from Average Solution-EDAS (2015) [36], Multi-Attribute Border approximation Area Comparison-MABAC (2015) [37], MAIRCA (2016) [38], Combinative Distance-based Assessment-CODAS (2016) [39] and Measurement of Alternatives and Ranking according to Compromise Solution-MARCOS (2020) [40]. TOPSIS (1981) is a distance-based multi-criteria method and calculates the distances between every alternative and the ideal and anti-ideal solutions, the best and the worst result on each criterion, respectively. The winner is the alternative with the highest coefficient of relative closeness to the ideal solution. In ARAS, the utility value of each alternative is divided by the value of the optimal alternative and the results are used as ranking values to select the best alternative. The utility function of the WASPAS method summarizes the values obtained by the Single Additive Weighting (SAW) and Weighted Product Method (WPM). EDAS is a distance-based multi-criteria method, and its evaluation of each alternative depends on the positive and negative distance to the average solution (average value of each criterion estimates). In MABAC, the evaluations of alternatives are functions of their distance to the border approximation area. MAIRCA calculates the gaps between ideal and empirical ratings. The best alternative in the ranking is the one with the lowest gap value. In CODAS, the ranking depends on the Euclidean and Manhattan distance to the negative ideal solution. For MARCOS, the value of each alternative depends on its relation to the ideal and anti-ideal solution.
The above-mentioned techniques belong to two main categories of multi-criteria methods-scoring and compromising methods. In the first category, the decision maker's preferences are expressed via the utility function. To this category belong ARAS and WASPAS methods. The second category includes methods that find a feasible solution for alternatives' ranking, which is the closest/farthest to the ideal/anti-ideal (the best/the worst compromise), and helps decision-makers to reach a final ranking. TOPSIS, EDAS, MABAC, MAIRCA, CODAS, and MARCOS are members of the second MCDM category.

Interval Value Fermatean Fuzzy Numbers-Some Basic Definitions and Operations
The implementation of interval-valued Fermatean fuzzy sets (IVFFSs) [41] for TOPSIS modification requires knowledge about their peculiarities and arithmetic operations. In this subsection, we present some fundamental ideas related to IVFFNs.
The theory of IVFFSs is an extension of FFS (2020). IVFFSs are three-dimensional and their belongingness grade (BG), non-belongingness grade (NG), and hesitation grade are represented by numbers from an interval within [0, 1]. The only constraint is that the cube sum of respective upper bounds of the interval-valued BG and interval-valued NG is less or equal to 1. Moreover, the BG and NG within an IVFFS are described by flexible interval values. Thus, compared with the FFSs, IVFFSs can present the uncertainty more precisely. Often the available data make it difficult for decision-makers and researchers to obtain crisp BG and NG for assessments of given alternatives. In such a situation, IVFFNs with flexible interval-valued BG and NG are suitable to address such concerns.
Here µ T (u i ) = µ lb T (u i ), µ ub T (u i ) and ν T (u i ) = ν lb T (u i ), ν ub T (u i ) represent the BG and NG of u i ∈ U, correspondingly, in terms of interval values.
The function π T (u i ) = π lb T (u i ), π ub T (u i ) denotes the hesitancy (indeterminacy) degree of u i to T, where For simplicity, an Interval-Valued Fermatean Fuzzy Number (IVFFN) could be signified by

Definition 2.
For any IVFFN λ = µ lb λ , µ ub λ , ν lb λ , ν ub λ , the score function S of λ is given by Definition 3. For any IVFFN λ = µ lb λ , µ ub λ , ν lb λ , ν ub λ , the accuracy function E of λ is given by Corresponding to the score and accuracy functions, a comparative scheme to compare any two IVFFNs λ 1 and λ 2 is given as: be three IVFFNs and γ ∈ R + . The operations on IVFFNs are given in the next formulas: In order to average IVFFNs, we employ a weighted averaging aggregation operator-intervalvalued Fermatean fuzzy weighted averaging (IVFFWA) operator.
The IVFFWA formula [41] is as follows: be IVFFNs. The Euclidean distance between IVFFNs λ 1 and λ 2 [42] is defined as follows: To summarize, the space of IVFFNs is greater compared with the space of intervalvalued intuitionistic fuzzy numbers (IVIFNs) and interval-valued Pythagorean fuzzy numbers (IVPFNs). Due to the relaxed constraint, IVFFSs are more accurate for handling complex uncertain MCDM problems than IVIFSs and IVPFSs.

TOPSIS in IVFFNs Environment
TOPSIS is one of the most widely used distance-based MCDM methods. It ranks the alternatives by measuring their closeness to the ideal solution and remoteness to the negative-ideal solution. To transform the method to work with IVFFNs, we propose measuring the distances between alternatives using Equation (11). The pseudocode of the new modified version of TOPSIS in IVFFNs environment is presented in Algorithm 1.

Algorithm 1. Pseudocode of IVFFNs TOPSIS.
Step 1: Formulation of DM problem: identify // Computation of the ideal A * and the negative ideal A − solution for beneficial (B) and cost criteria (C).

endfor endfor
Step 5: Calculation of Euclidean distances to the ideal and negative ideal solutions for each alternative for i in {1..N} // Computation of Euclidean distances from each alternative to the ideal and negative ideal solutions.
Step 6: for i in {1..N} RC i = D − D − +D + // Computation of the relative closeness of each alternative to the ideal solution Step 7: Output of alternatives' ranks in descending order of their assessment Unlike classic fuzzy TOPSIS, the proposed IVFFNs modification requires a larger number of computations. However, here the evaluations of alternatives are presented more precisely and in detail, and the resulting ranking is based on a more exhaustive comparison.

Theoretical Framework for COVID-19 Vaccine Selection
The new framework for unified analysis of COVID-19 vaccines data consists of eight stages (Figure 1). Stage 1. Analysis of the problem for COVID-19 vaccine selection In the first stage, decision-makers should answer the question about the needs and expectations of COVID-19 vaccine selection. Using a systematic literature review, they collect data about authorized or approved vaccines and the current state of the vaccination process. Data can be extracted directly from journal articles and other types of reports of studies (official COVID-19 datasets, regulatory reviews, trial registers, clinical studies reports, etc.). The goal is to clarify what vaccines are available, what share of the population is unvaccinated, and where the locations for vaccination are. If the result obtained for a particular situation confirms the need for COVID-19 vaccines, the selection process can continue to Stage 2. Otherwise, it should go to the end of the process.
Stage 2. Development of user requirements specification for a COVID-19 vaccine In this stage, the survey method can be used. The survey comprises a questionnaire that contains several question groups, corresponding to the different characteristics of vaccines and their use. At the end of this stage, the main parameters of the preferable COVID-19 vaccine are defined.
Stage 3. Construction of multi-criteria system for COVID-19 vaccines assessment In this stage, a multi-criteria index for vaccine comparison is established. The new index is built according to the user requirements and the importance of vaccine specifications for a given situation. Other evaluation measures may also be included in the construction of the assessment systems such as organizational characteristics of the vaccination strategy or individual preferences. The set of criteria can also be expanded with additional technical specifications and economic data from COVID-19 vaccine manufacturers, vaccination trackers, or users' reviews.
vanced multi-criteria methods will produce results that are more precise. This stage includes various methods for vaccine data collecting-medical experiments, medical information systems, open health data repositories, expert and user surveys, social media networks (reviews, likes, and follows/shares), etc.

Stage 4. Selection of data types and MCDM methods for relative weights and ranking of alternatives
The choice depends on the resources available to the decision maker and the data accumulated in Stage 3. In case of limited resources, the decision maker will probably prefer classic data types (real, interval real, fuzzy, interval fuzzy, etc.), and algorithms with low computational complexity. The implementation of advanced data types and advanced multi-criteria methods will produce results that are more precise. This stage includes various methods for vaccine data collecting-medical experiments, medical information systems, open health data repositories, expert and user surveys, social media networks (reviews, likes, and follows/shares), etc.
Stage 5. Data preprocessing and storage For each data type and algorithm from Stage 4, the specific coding rules are defined. All assessments except those expressed by real numbers (interval data, categorical data, linguistic terms) are transformed into numeric form (real numbers, classic fuzzy membership functions, or their contemporary extensions). The collected and converted data are imported into a relational database or in a single dataset. The coded data should be checked for duplicates, errors, or missing values. According to the data type, a decision should be made to remove duplicate observations or store them with appropriate substitutes in case of inconsistent values (errors or missing values). The most frequently used methods to handle missing values are as follows: replacing with mode, median, previous or next value, etc. Stage 6. Determination of relative weights of evaluation criteria Using data about vaccines and immunization progress, a multi-attribute evaluation system, and available datasets for vaccine comparison, the input values are filled in the decision matrix. The weight coefficients could be given in advance, or they could be calculated via weight determination methods (Section 3.1).
Stage 7. Multi-criteria data analysis The next stage calculates the COVID-19 vaccine ranking via crisp or fuzzy multicriteria decision-making algorithms (Section 3.1). Our proposal is employing several MCDM or different hybrid combinations from weight determination and MCDM methods.
Stage 8. Results analysis and interpretation Here, the decision-maker analyses revealed dependencies in vaccine ranking. If the highest ranked alternative is not accepted or more processing is needed, the researcher gathers additional data and goes to the next iteration of data processing (Stage 4). In the other case, this is the end of calculations, and the results should be interpreted. In this analysis, only COVID-19 vaccines that have been top-ranked with the various MCDM techniques are left. In this stage, decision makers select the most suitable vaccine.

A Case Study of Quality-Based Evaluation of COVID-19 Vaccines
Let S be an administrative authority faced with a COVID-19 vaccine selection problem. The benefits of vaccination for S are numerous. The problem is how to find the best COVID-19 vaccine for the particular subject.
The execution of Stage 1 of the proposed framework shows that there are several available vaccines, and the process of vaccine selection can start. In this illustrative example, we utilize a COVID-19 vaccine dataset, collected from Ozsahin et al. [20]. The dataset consists of five assessment criteria C 1 , C 2 , . . . , C 5 (Section 2.2), and fifteen COVID-19 vaccines A 1 , A 2 , . . . , A 15 (Section 2.3). The criteria are related to the following aspects of COVID-19 vaccines' features: C 1 -dose number, C 2 -dosing schedule, C 3 -storage advantage, C 4 -efficacy and C 5 -side effects. The COVID-19 vaccines are as follows: In Stage 2, experts from institution S fill in the questionnaire about their COVID-19 requirements. Respondents evaluate the vaccine's features via a five-point Likert scale ranging from "Extremely important" (corresponding to 5) to "Unimportant" (corresponding to 1).
In Stage 3, a multi-attribute criteria index is constructed. The evaluation index consists of variables C i , i = 1, 5.
In the next stage, we decide that the data type is IVFFNs and employ the proposed new IVFF TOPSIS modification. The values of the decision matrix are converted into a five-point Likert scale (Table 2). For transforming every linguistic variable into its corresponding IVFFNs, the correspondence table (Table 3) is applied.  The importance of weight coefficients is as follows: The obtained overall scores and rankings of given COVID-19 vaccines by using IVFF and crisp TOPSIS method are displayed in Table 4. The problem has also been solved using several other MCDM methods (Table 5). In order to show that the IVFF TOPSIS solution is feasible, we compare the obtained ranking with those obtained with crisp estimates. The final rankings are as follows: Spearman's rank correlation coefficient is applied as a measure between benchmark ranking (SAW) and rankings obtained using the other MCDM methods. The results have proven that the new method is reliable (Spearman's ρ IVFFNs TOPSIS = 0.754).
The high efficacy (C 4 ) assessments and relatively mild side effects (C 5 ) of Sputnik V, Epivac and Nuvaxovid allow them to occupy leading positions in the rankings and vice versa, Covishield is lagging behind in efficacy and ranking, respectively. The special cold chain (C 3 ) of Pfizer/BioNTech and Moderna cause their vaccines to fall into the last part of the rankings.
It can be concluded, that the proposed framework is reliable and properly reflects the requirements of administrative authority S.

A Case Study of Dynamic Attitude-Based Evaluation of COVID-19 Vaccines
Let the administrative authority S faced with a COVID-19 vaccine selection problem. The execution of Stage 1-Stage 4 of the proposed framework shows that the public attitudes to COVID-19 vaccines in social networks can be used for vaccine selection. In this illustrative example, we utilize a COVID-19 vaccine dataset, collected from Twitter using a text analysis add-on of Orange software (University of Ljubljana, Slovenia, https: //orangedatamining.com, accessed on 30 June 2022). The dataset consists of only one attitude assessment criteria C and six COVID-19 vaccines A 1 , A 2 , . . . , A 6 . The assessments of alternatives with the respect to the criterion are expressed in IVFFNs, in which BGs and NGs correspond to the lower and upper limits of positive and negative attitudes towards vaccines for a specific period (first day = 4 May 2021, last day = 19 May 2021). The COVID-19 vaccines are as follows: A 1 -Comirnaty, A 2 -Spikevax, A 3 -Sputnik V, A 4 -BBIBP-CorV, A 5 -Vaxzevria and A 6 -Jcovden.
In the next stage, we collect Twitter data (tweets) about the six vaccines, apply sentiment analysis, and find the user's emotions towards given vaccines (in percent of corresponding tweets' number). To convert data about users' emotions into IVFFNs, we apply the following rule: The BG is equal to the "Joy" value, while the NG is obtained as a sum of negative emotions' shares ("Anger", "Disgust", "Fear" and "Sadness") ( Table 6). Finally, to evaluate every alternative, we employ the score function (Equation (2)). The decision matrix, overall scores, and final vaccine ranks can be found in Table 7. The final ranking is as follows: The comparative analysis shows that all vaccines, except A 4 (BBIBP-CorV) retain their relative rankings from the first example. A possible reason for this high positive attitude towards BBIBP-CorV can be found in the fact that China was the first country affected by the coronavirus and the country's control strategies have successfully slowed the spread of the pandemic. Chinese Zero-COVID approach, as a mix of NPIs and vaccination programs, has quickly balanced economic growth and public health imperatives. The task for ranking COVID-19 vaccines based on users' attitudes can be solved periodically or in real time using online streaming data.
Vaccination is a powerful tool to prevent the spread of SARS-CoV-2, but there are still people who are reluctant to get vaccinated. To facilitate the selection process and clear the vaccination backlog, multi-faceted institutional activities promoting the benefits of vaccines are needed. The proposed approach provides an opportunity for experts to consider many technological, storage, and handling characteristics, establish requirement specifications, employ fuzzy estimates and objectively select the most suitable vaccine for a particular country. The decision-makers can further expand the evaluation system by adding factors such as the epidemiological situation (patterns and frequency), health system capacity, the cost per vaccine administration, etc.

Conclusions, Limitations, and Future Work
Recently, the tools for assessments of antiviral vaccines have become a research hotspot due to the expansion of the COVID-19 pandemic and the increasing role of vaccination. Many biotechnology and pharmaceutical companies have focused their efforts on the fast development of a variety of vaccines against SARS-CoV-2. Unfortunately, the availability and effectiveness of existing algorithms for the selection of COVID-19 vaccines are not high.
In this study, a new integrated framework for COVID-19 vaccine selection has been suggested. The proposed framework includes different multi-criteria decision-making methods and objectively evaluates COVID-19 vaccines. In addition, a new IVFFNs-based MCDM method has been developed and implemented for vaccine selection. Due to its fuzzy nature, the new method can cope with uncertainty and vagueness in experts' estimates.
The proposed fuzzy modification is based on TOPSIS, which is one of the most widely used distance-based multi-criteria methods. The advantage of the proposed IVFFNs TOPSIS is that the distances between compared alternatives are calculated by an improved formula for the IVFF environment:

•
In addition to interval-valued membership and non-membership grades, the intervalvalued hesitancy degree is also included.

•
The length of belongingness, non-belongingness, and hesitancy intervals also participates in distance calculation.
The effectiveness of new framework has been demonstrated using two practical examples for choosing among COVID-19 vaccines. The first one is concerned to finding the best ranking alternative among fifteen COVID-19 vaccines (Comirnaty (previously Pfizer-BioNTech), Spikevax (previously Moderna), Convidecia, Sputnik V, EpiVacCorona, BBIBP-CorV, WIBP-CorV, CoronaVac, Vaxzevria (previously AstraZeneca), Nuvaxovid, Jcovden (previously Janssen), INO-4800, Covaxin, Covifenz and Covishield) according to five evaluation criteria. The second example is concerned with ranking vaccines according to public attitudes toward them, expressed via tweets. The analysis of obtained results shows that the proposed methodology is reliable and correctly reflects vaccines' features in final rankings.
In the future, the conceptual framework will be enhanced by adding several recently developed multi-criteria methods. Additionally, the proposed mechanisms for ranking COVID-19 vaccines will be expanded to address the uncertainty of estimates with different types of classic and interval fuzzy sets (for example, type-2 fuzzy numbers and q-rung orthopair fuzzy numbers). We also plan on developing a new hybrid method for COVID-19 vaccines' evaluation combining new modifications of weights determination algorithms with modified multi-criteria decision-making methods.


extfieldsofstudy:
Computer Science
Mathematics
Engineering

text:
Online Convex Optimization Using Coordinate Descent Algorithms

This paper considers the problem of online optimization where the objective function is time-varying. In particular, we extend coordinate descent type algorithms to the online case, where the objective function varies after a finite number of iterations of the algorithm. Instead of solving the problem exactly at each time step, we only apply a finite number of iterations at each time step. Commonly used notions of regret are used to measure the performance of the online algorithm. Moreover, coordinate descent algorithms with different updating rules are considered, including both deterministic and stochastic rules that are developed in the literature of classical offline optimization. A thorough regret analysis is given for each case. Finally, numerical simulations are provided to illustrate the theoretical results.

1. Introduction. Online learning [22], resource allocation [7], demand response in power systems [14], and localization of moving targets [2] are just a few examples where online convex optimization (OCO) has been applied. In the problem setup of OCO, the objective functions are time-varying and are not available to the decision maker a priori. At each time instance, after an update of the decision variable, new information of the latest cost function is made available to the decision maker. The objective of the decision maker is to minimize the objective function over time. One commonly used performance measure of an online optimization algorithm is the notion of regret which measures the suboptimality of the algorithm compared to the outcome generated by the best decision at each time step.
In the seminal work of [30], the method of online gradient descent is proposed for OCO problems, where at each time step the decision maker performs one gradient descent step using the latest available information. A static regret upper bound that is sublinear in T is proved, where T is the length of the horizon. Under stronger assumptions on the cost functions such as strong convexity, an improved logarithmic regret bound can be achieved [10,18,9]. If future information is available, it can be used to further improve the performance of the online optimization algorithm in terms of regret bounds. The work [13] introduces an additional predictive step following the algorithm developed in [30], if certain conditions on the estimated gradient and descent direction are met. Similar algorithms have also been extended to cases where zeroth order [5,23,27] and second order [15] oracles are used instead of (sub)gradients. The works [5,27] on bandit feedback consider the situation where there are time-varying inequality constraints. In such cases the algorithms proposed in [30] will be hard to implement because of the high computational resource demand of the projection operation. This motivates recent research on online optimization algorithms with time-varying inequality constraints including the primal-dual algorithm proposed in [12], a modified saddle-point method given in [8]. Other algorithms are also proposed to handle stochastic constraints [28] and cover continuous-time applications [19]. In the case where only the values rather than the exact form of the cost function at are revealed to the decision maker, bandit feedback based online algorithms can be used to solve the problem, see [5,27] for example.
Although a lot of results on OCO have been obtained as listed above, most of the online algorithms are based on the idea of gradient descent and are centralized. The need for applications in large scale systems has led to extensive research on distributed OCO. Distributed online algorithms that achieve sublinear regret bound for convex optimization problems with static constraints can be found in [21,11,25]. For instance, [21] proposes a distributed version of the dynamic mirror descent algorithm which is a generalization of the classical gradient descent methods suitable for high-dimensional optimization problems. Furthermore, the work [29] extended the adaptive algorithm proposed in [12] to the distributed setting with a static inequality constraint. By introducing a regularized convex-concave function, the algorithm works without the knowledge of the total number of iterations. Finally, the work [16] proposes distributed online primal-dual algorithms for optimization problems with static coupled inequality constraints while the work [26] studies distributed online convex optimization with time-varying inequality constraints in the discrete-time setting.
To the best of our knowledge, Coordinate descent [24], as an important class of optimization algorithms, is left unanalysed by researchers in the online optimization community. Coordinate descent algorithms have great potential in applications where iteration with full gradient information is computationally expensive. Moreover, it can also be implemented in a parallel fashion as shown in [4]. In this paper, we aim to fill this gap by providing an in-depth regret analysis for different types of online coordinate descent algorithms applied to online convex optimization problems. Moreover, we believe that this work can also be extended to distributed dual iterations as well as those based on operator splitting method. This makes the results applicable to distributed problems.
The main contributions of the paper can be summarized as follows. First, we extend the coordinate descent algorithms considered in [24] to the online case and provide their regret analysis. To the best of our knowledge, this is the first attempt to look at possibilities of using coordinate descent methods to solve OCO problems. Second, we provide an in-depth regret analysis of various coordinate descent algorithms with different rules, such as cyclic updating rules and random updating rules. Specifically, we consider both random and deterministic online coordinate descent algorithms under assumptions commonly used in the literature. Additionally, we show that the regret bounds achieved by our online coordinate descent algorithms are comparable to those achieved by the literature on centralized full-gradient based online algorithms.
The paper is organized as follows. The problem formulation is presented in Section 2. The online coordinate descent algorithm considered in this paper is given in Section 3. Regret bounds for random online coordinate descent algorithms are given in Section 4 followed by regret bounds for deterministic online coordinate descent algorithms. The numerical simulation is given in Section 7. Finally the results presented in this paper is summarized in Section 8.
Notation: Let R be the set of real numbers and R n be the n-dimensional Euclidean space, R ≥0 (resp. R >0 ) be the set of non-negative (resp. positive) real numbers. For x, y ∈ R n , x, y denotes the inner product in R n . The set of natural numbers is denoted by N. The set of non-negative (resp. positive) integers is denoted by Z ≥0 (resp. Z >0 ). Furthermore, | · | denotes the Euclidean norm of a vector x ∈ R n . The matrix I n is used to denote the n-dimensional identity matrix and n will be omitted when the dimension is clear. For a given vector x, x (i) denotes the i-th component of x, x i denotes the value of x at time i, and x (i),j denotes the value of the i-th component of x at time j. All random variables considered in this paper are defined on a probability space (Ω, F , P), where Ω is the sample space, the σ-field F is the set of events and P is the probability measure defined on (Ω, F ).
2. Problem formulation. We consider the following optimization problem where f t : R n → R is the convex cost function at time t, x ∈ R n is the decision variable. For simplicity, we assume f t is continuously differentiable for any t ∈ N. Moreover, let the decision variable x t at any given time t be partitioned as The P components of the vector are assigned to P individual processors. For any integer p ∈ {1, . . . P }, the processor p is responsible for updating its own "local" decision variable x (p),t [4].
Denote the global minimizer of f t (x) at time t by x * t . We use a notion of regret to measure processors' ability to track x * t . Regret refers to a quantity that measures the overall difference between the cost incurred by an algorithm and the cost at the best possible point from an offline view up to a horizon T . Two notions of regret commonly considered in the literature are static regret and dynamic regret. The static regret is defined as: where x * := arg min T t=1 f t (x) for a given T , the subscript T is omitted for convenience. On the other hand, the dynamic regret is defined as: It can be seen from (2.2) and (2.3) that regret captures the accumulation of errors due to the fact that optimization problems are not solved exactly at each step. Moreover, regret keeps growing as the horizon T increases. However, if the regret is sublinear in T , then the average accumulated error R s T /T (or R d T /T ) will converge to zero as T → ∞. If stochastic algorithms are considered, similar notions of regrets can be defined via expectations.
With some abuse of notation, R s T and R d T are used for both random and deterministic cases. However, this would not lead to confusion since it should be clear whether an algorithm is stochastic or not.
3. Online coordinate descent algorithms. We construct our online block coordinate descent algorithms following the setup in [24]. At time t, we select a component of x t to update. The updating component at time t is denoted by i t . If the i-th component is updating, then updating equation for component i is given by where α t is the stepsize at time t and ∇ (i) f t (x t ) is the i-th component of the gradient of f evaluated at x t at time t. For any p = i t , we have Equivalently, we can define the matrix U t = diag(U (1),t , U (2),t , . . . , U (P ),t ). For any t ∈ N and 1 ≤ p ≤ P , U (p),t ∈ {I np , 0 np }, where I np and 0 np denote identity and zero matrices of dimension n p , respectively. Then the updates of the coordinate descent algorithm at time t can be written as In this paper, we consider the following three commonly used schemes of selecting the updating component i t .
• The random coordinate descent algorithm. In this case, i t is selected randomly with equal probability 1 , independently of the selections made at previous iterations. • The cyclic coordinate descent algorithm. In this case, the updating component i t is selected in a pre-determined cyclic fashion: i t+1 = (i t mod P ) + 1. • The coordinate descent algorithm with Gauss-Southwell Rule. In this case, the updating component i t is selected as i t = arg max i |∇ (i) f t (x t )|.

4.
Regret bounds for online coordinate descent algorithms with random coordinate selection rules. The online random coordinate descent algorithm considered in this section is given in Algorithm 4.1.
4.1. Static regret for convex functions. Before we state the main results, we first list the assumptions.
Assumption 4.1. For any given t ∈ Z >0 , x ∈ R n and x * := arg min T t=1 f t (x), the following inequalities hold uniformly in t and T for problem (2.1), Remark 4.2. By [22, Lemma 2.6], Assumption 4.1 (a) implies that f t is also Lipschitz continuous uniformly in t. These assumptions are quite standard in the literature on online optimization [5,6] and can be satisfied if at each step an additional projection step of the decision variable onto a compact constraint set is introduced. This will not limit the applicability of our main results since the exact values of constants G and R will not appear in the exponent of T in the regret bounds established in this paper.
For all i = i t : Before we state the first main result of the paper, we first present the so-called doubling trick scheme stepsize rule which is introduced in [ The following result states that, under . Given x t , denote the σ-field containing past data of Algorithm 4.1 up to time t by F t . Then, by convexity of f t , we have , taking total expectations, and rearranging (4.2) leads to Due to Assumption 4.1 the gradient of f t is uniformly bounded by G and |x t − x * | is upper bounded uniformly by R. Consequently, In the last inequality of (4.5), the property α T ≥ 1/ √ T is used, which is a direct consequence of the definition of the stepsize rule. On the other hand, the remaining term in (4.4) can be upper bounded as follows To derive the regret bound, we again use the properties of the doubling trick scheme. First, we set the horizon to be some known constant T * and the stepsize is chosen as the constant 1 √ T * . Then it is obvious that Since for q = 0, 1, . . . , ⌈log 2 T ⌉ + 1, α t = 1 √ 2 q in each period of 2 q iterations t = 2 q , 2 q + 1, . . . , 2 q+1 − 1. That is T * = 2 q . Then we can sum (4.6) up over any given T as Thus, the proof is complete.
Remark 4.5. In Theorem 4.4, the differentiability of f t is in fact never used. Thus the results apply to the case where subgradients are used when f t is not differentiable for some t as long as item 1 of Assumption 4.1 is satisfied by the subgradients used in the iterations. Moreover, the regret bound established in Theorem 4.4 is of the same order as the one established in [22] for online gradient descent under the same assumptions.
Remark 4.6. The doubling trick scheme of stepsize choices is particularly useful when stepsizes of type 1/T are needed to achieve a desirable regret bound. Since in applications it is often unrealistic to know the horizon T in advance, by using the doubling trick scheme regret bounds of the same order can be achieved without the knowledge of T .

4.2.
Static regret for strongly convex functions. In this part, we show that if the cost functions are strongly convex, then we can achieve an improved static regret bound for the online random coordinate descent algorithms.
Assumption 4.7. For any t, the function f t is uniformly µ-strongly convex, i.e., there exists µ > 0 such that the following inequality holds for any t ∈ N, x, y ∈ R n Proof. Similar to (4.2), given x t , we have the following relationship for any x ∈ R n , (4.10) By substituting x * to (4.10) and rearranging the terms, we have the following inequality Since the gradient of f t is uniformly bounded by G, the following inequality holds (4.11) By choosing α t = P µt , we have the following relationship where the second inequality follows by expanding the sum. Thus, the proof is complete.
By making the extra assumption of strong convexity, the sublinear static regret bound of order O( √ T ) established in Theorem 4.4 is improved to be of order O(log T ) which is consistent with the regret bound for online gradient descent algorithms under the same assumptions established in [10].

4.3.
Dynamic regret for convex functions. Now, we provide an upper bound of the dynamic regret of the online coordinate descent algorithm. First, we define the following measure of variations of the problem (2.1) which is commonly used in the literature [18,21] (4.13) where x * t is a solution to the optimization problem at time t and x * 0 can be arbitrary constant. The term C T captures the accumulated variations of optimal points at two consecutive time instances over time. If the cost functions are general convex functions and an upper bound of C T is known, the following results can be stated.
Proof. Substituting x * t in (4.2) for any t ≥ 2, yields (4.14) Then, Choosing the stepsize to be CT T leads to Remark 4.10. As discussed in Remark 4.6, the choice of stepsize CT T can be replaced by the doubling trick scheme (see Definition 4.3) to derive a regret bound of the same order. Moreover, the exact value of C T is also not necessary to derive the regret bound given in Theorem 4.9. If C T is not available, a stepsize of the same order of CT T can be used with constant factor errors. Lastly, as argued in [6], if C T is sublinear in T , then the overall dynamic regret bound in Theorem 4.9 will be sublinear in T , which is desired and consistent with the dynamic regret bounds established in [6] for full-gradient based online algorithms.

4.4.
Dynamic regret for strongly convex functions. Now, we consider the dynamic regret of the online random coordinate descent algorithm for strongly convex functions. As before, we consider µ-strongly convex functions. In addition, we will use the following result that shows the gradient of f t are Lipschitz uniformly in t.
Corollary 4.11. Suppose Assumption 4.1 (a) holds. For any t, the gradient of f t is uniformly Lipschitz continuous, i.e., there exists L > 0 such that the following inequality holds for any t ∈ N, x, y ∈ R n Proof. The result follows from Assumption 4.1 (a) and taking L = 2G.
It can be easily seen that [3] for a µ-strongly convex function having Lipschitz continuous gradient with constant L, we have µ ≤ L.
The main result regarding the dynamic regret bound of Algorithm 4.1 for strongly convex functions with Lipschitz gradients is stated as follows.
Proof. From (4.8) and (4.15), the following inequality holds [20,Lemma 11] for any t and any x, y ∈ R n Letting y = x * t yields Moreover, Assumption 4.1 (a) implies the following, which holds for any t and any Since the stepsize satisfies α t = α ≤ 2 P (µ+L) , we haveL : . Expanding it and using (4.17) leads to By Jensen's inequality, we have E|x t+1 − x * t | ≤ 1 − 2αµ P + α 2 µ 2 |x t − x * t |. Since P ≥ 1 and µ ≤ L, we have 1 − 2αµ Obviously, the dynamic regret is bounded as Now taking total expectations, using (4.20) and summing up both sides of (4.21) from t = 1 to t = T − 1 yields Note that by definition e = 1 − 2αµ P + α 2 µ 2 − (1 − αµ). Moreover, the condition α ≤ 2 P (µ+L) < 2 µP implies α 2 µ 2 < 2αµ P . Hence, αµ − e = 1 − 1 − 2αµ P + α 2 µ 2 > 0. Consequently, rearranging (4.22) leads to Remark 4.13. By assuming uniform strong convexity and uniform Lipschitz continuity of gradients of f t , Theorem 4.12 improves the order of the theoretical dynamic regret bound from O( √ C T T ) in Theorem 4.9 to O(C T ). This means if problem (2.1) does not change over time i.e. f t = f for any t, C T = 0 and the regret grows at a rate O(1) which is consistent with the convergence result of coordinate descent algorithms in the offline setting [24]. Moreover, if C T grows sublinearly, the dynamic regret bound in Theorem 4.12 is also sublinear in T which is consistent with results shown in [18] for full-gradient based online algorithms.

5.
Regret bounds for online coordinate descent algorithms with deterministic coordinate selection rules. We consider two deterministic online coordinate descent algorithms in this section and they are given in Algorithms 5.1 and 5.2, respectively.
For all i = i t : Note that both Algorithms 5.1 and 5.2 are deterministic and update a component of the decision variable. We can therefore relate the regrets achievable by Algorithms 5.1 and 5.2 to regret achievable by the online gradient descent algorithm which takes the form It can be easily seen that Algorithms 5.1 and 5.2 take the following form where the vector ν t :

Proof. By the definitions of regrets in (2.2) and (2.3), it is obvious that
Thus, if one of the two items is proved, so is the other item. Since Assumption 4.1 holds, from (2.2), we know that R s Thus the proof is complete. By using Proposition 5.1, we can establish regret bounds for Algorithms 5.1 and 5.2 using known regret bounds for online gradient descent algorithms. Moreover, if the regret bounds for online gradient descent are sublinear in T and T t=1 α t is also sublinear in T , then the established regret bounds for Algorithms 5.1 and 5.2 will be sublinear.
The following result on static regret bounds of Algorithms 5.1 and 5.2 is a direct corollary of Proposition 5.1 and Lemma 5.2.
The conclusion follows as a result of Proposition 5.1 and Lemma 5.2.
Proof. Since α t = 1 µt , we have The conclusion follows as a result of Proposition 5.1 and Lemma 5.4.

Dynamic regret for convex functions.
We can adapt the proof of Theorem 4.9 to the deterministic case to derive a dynamic regret bound for convex functions which is given in the following result.
Proof. From (5.1), we have for any Substituting x * t to (5.3) results in the following inequality for any t ≥ 2 Note that, the inequality (4.14) still holds in this case Thus, we havē If we set the stepsize to be CT T , we havē Using Propositions 5.1 and 5.6, we can state the following result on dynamic regret bounds of Algorithms 5.1 and 5.2.
Proof. Since α t = CT T , we have T t=1 α t = √ C T T . The conclusion follows as a result of Propositions 5.1 and 5.6.
As discussed in Remark 4.10, the stepsize choice α t = CT T can be made independent of T by using the doubling trick scheme.

Dynamic regret for strongly convex functions.
Note that when the cost functions are strongly convex and constant stepsizes are used, the result in Proposition 5.1 only gives a dynamic regret bound that is linear in T . Therefore, next we aim to establish the dynamic regret bounds for Algorithms 5.1 and 5.2. In this section we make the following assumption on the problem (2.1).
Assumption 5.8. For any t, the gradient of f t is uniformly block-wise Lipschitz continuous, i.e., for any 1 ≤ i ≤ P , there exists L i > 0 such that the following inequality holds for any t ∈ N, x ∈ R n , and u ∈ R ni where H i ∈ R n×ni is such that [H 1 H 2 · · · H P ] = I n .

The dynamic regret is bounded as
From (5.9), we have the following relationship by summing up both sides of (5.10) from t = 1 to t = T − 1, Since we have shown that L µ (1 − 2µĀ) < 1, Remark 5.10. Note that in Theorem 5.9, we introduce an upper bound that depends on the number of components P which increases to ∞ as B 3 decreases to 0. This is mainly a result of conservatism introduced in the derivation of (5.9) using (5.8). Regret bounds established in Theorems 5.11 and 5.12 that will be given later remove the need of requiring P being sufficiently small if additional updates are performed at each time.
The following two theorems give dynamic regret bounds without assuming an upper bound on the number of components P . However, at each time t, potentially multiple offline steps are needed to guarantee desirable regret bounds.
The modified algorithms are given below For all i = i κ , such that κ ≤ k: x (i),κ =x (i),κ−1 .
It can be seen that in Algorithms 5.3 and 5.4, at each time t, k updates are performed where k is an integer to be chosen. In Algorithms 5.1 and 5.2, however, only one step is performed at each time t. (1 + αL max ) P −1 < 1 holds, then the dynamic regret (2.5) achieved by Algorithm 5.4 Online coordinate descent algorithm with Gauss-Southwell Rule 1: Initialization: x 0 , κ and some integer k ≥ 1. 2: Update: At time t, κ = 1, For all i = i κ , such that κ ≤ k: x (i),κ =x (i),κ−1 .

Algorithm 5.3 satisfies
Proof. By the block descent lemma [1,Lemma 3.2] and the fact that Summing over all P blocks in a full round where all components have been updated exactly once leads to By the update equation and Lipschitz continuity of the gradient, we have |∇f Summing over P blocks leads to Therefore, (5.11) Then, by (5.11), we have (1 + αL max ) P −1 < 1 holds, then the dynamic regret (2.5) achieved by Algorithm 5.4 satisfies Proof. Following similar steps in the proof of Theorem 5.11 and using (5.7) and (5.13) yield    [21] 1 ≤ i ≤ 20, x (i) is a scalar. The horizon length is T = 5000, and the constant stepsize is chosen as α t = α = 0.001. Based on our experience, the exact value of α does not have significant impact on the performance of the algorithm, provided that it is small enough. In addition to the regrets (2.2) and (2.3) considered in the paper,  we also show how the time-average regrets R s T /T and R d T /T change with time in Figure 6.1. In all figures, Algorithms 1-3 refer to Algorithms with random, roundrobin and Gauss-Southwell rules respectively.
It can be seen from Figure 6.1 that when the constant stepsize is chosen sufficiently small, the regrets in all cases have a sublinear growth and therefore their time-averages go to 0 when T is sufficiently large. This is consistent with our results on strongly convex functions.
In order to see how the variation of the problem impact the performance of the algorithms. We add an extra term of 500I 20 such that the matrix Q t is diagonally dominant and therefore being less sensitive to t. We test the online algorithms in this case and the results are shown in Figure 7.1. It can be seen that when problem (7.1) varies slowly with respect to time, the curves of the regrets in Figure 7.1 have a lower growth rate compared to the regrets shown in Figure 6.1 where the diagonally dominant term is absent.
Next, we investigate the effect of the number of blocks P on the performance of the algorithm. We increase the amount of blocks from 20 to 100 and such that the while other settings remain unchanged. The result is shown in Figure 7.2. It can be seen from Figure 7.2 that when P increases, the regrets grow quicker as T increases compared to the results in Figure 6.1. This is to be expected since, it is now required at least 100 updates to ensure all components of the decision variable have been updated once. One interesting feature among Figures 6.1-7.2 is that in all cases for this numerical example, Algorithm 3 which corresponds to the Gauss-Southwell rule gives the best performance in terms of minimizing the regret. We believe one reason for this is that Algorithm 5.2 uses extra information of the norm of the gradients of all components to decide which component to update. An in-depth theoretical analysis of this problem is left for future work.
8. Summary. In this work, we have proposed an online coordinate descent algorithms to deal with optimization problems that may change over time. Three widely used update rules of coordinate descent are considered. Under different assumptions, we have provided different upper bounds on the regrets of these online algorithms. In particular, we have verified that the established regret bounds of these coordinate descent algorithms are of similar orders as those of online gradient descent methods under same settings. The regret bounds proved in this paper are summarized in Table  6.1. Lastly, a numerical example was given to illustrate our main result.