An Efficient Traffic Incident Detection and Classification Framework by Leveraging the Efficacy of Model Stacking

Automatic incident detection (AID) plays a vital role among all the safety-critical applications under the parasol of Intelligent Transportation Systems (ITSs) to provide timely information to passengers and other stakeholders (hospitals and rescue, police, and insurance departments) in smart cities. Moreover, accurate classification of these incidents with respect to type and severity assists the Traffic Incident Management Systems (TIMSs) and stakeholders in devising better plans for incident site management and avoiding secondary incidents. Most of the AID systems presented in the literature are incident type-specific, i.e., either they are designed for the detection of accident or congestion. While traveling along the road, one may come across different types of traffic incidents, such as accidents, congestion, and reckless driving..is necessitates that the AID system detects and classifies not only all the popular traffic incident types, but severity as well that is associated with these incidents. .erefore, this study aims to propose an efficient incident detection and classification (E-IDC) framework for smart cities, by incorporating the efficacy of model stacking, to classify the incidents with respect to their types and severity levels. .e experimental results showed that the proposed E-IDC framework achieved performance gains of 5%–56% in terms of incident severity classification and 1%–14% in terms of incident type classification when applied with different classifiers. We have also applied the Wilcoxon test to benchmark the performance of our proposed framework that reflects the significance of our approach over existing individual incident predictors in terms of severity and type classification. Moreover, it has been observed that the proposed E-IDC framework outperforms the existing ensemble technique, such as XGBoost used for the classification of incidents.

Introduction
e worldwide urban and highway transportation comes across several traffic incidents in every single moment with the increase in the number of on-road vehicles, and a single irregularity may disturb daily transportation and logistics operations [1]. e Road Traffic Incidents (RTIs), referred to as incidents, are defined as the unexpected scenarios that occur on the road network, often in potentially dangerous situations, and disrupt the normal traffic flow. e interrupted flow of road traffic can be majorly categorized into three types, i.e., (1) stoppage/hurdle on the road, (2) recurrent/nonrecurrent congestion, and (3) traffic violations. Derived from these categories, accidents, congestion, and reckless driving are the most common types of road incidents [2] and are highly interlinked with each other, as stated by the U.S. Department of Transportation (DOT) in [3]. According to the World Health Organization (WHO) report published in [4], road accidents are the major category of traffic incidents and are considered as the ninth leading cause of death globally. Moreover, it was also highlighted that the major cause of accidents is reckless driving that is often defined as a mental state in which the driver displays a wanton disregard for the rules of the road; the drivers misjudge common driving procedures, e.g., overspeeding, driving under the influence of drugs, and nonuse of helmets and seat belts. According to report [5], reckless driving causes 33% of all deaths involving major car accidents, which are more than 13,000 each year. Another challenging type of on-road traffic incident is congestion that relates to an excess of vehicles on a portion of a roadway at a time resulting in slower speeds, sometimes much slower than normal or "free flow" speeds, the Federal Highway Administration (FHWA) [6]. Congestion can be categorized into two types: recurrent which happened due to insufficient road resources and nonrecurrent which occurred due to another primary incident. According to a report by the Texas Transportation Institute (TTI), [7] on urban transportation, congestion is a reason for 8.8 billion extra hours in travel time and wastage of 3.3 billion gallons of fuel, and on average, the autocommuter has to spend extra 54 hours traveling compared to normal traveling time [8]. Authors in [9] worked to identify the correlation between the co-occurrence of colocated traffic incidents and eventually categorized them into primary and secondary incidents. It is also observed that 20%-50% of traffic incidents occur due to primary incidents and 50% of secondary incidents occur within 10 minutes of the primary incident. Similarly, an additional minute collapse in the clearance of the incident site increases the chances of near future incidents by 2.8% [10]. Moreover, the interdependency of these RTIs makes the boundary of incident classification blurred, which increases false alarm rate (FAR) and misclassification of the incident type (IT), and makes it hard to guess the risk factor (RF) also known as incident severity (IS) associated with the RTIs. e risk of secondary incidents can be reduced by deploying an incident management system (IMS) to timely and accurately detect the primary incident type (accident, congestion, and reckless driving) and its associated severity (low, medium, and high) and reporting the RTI with its details to appropriate rescue departments for timely clearance.
Existing IMS for smart cities can be classified into preincident management systems and postincident management systems [11]. Preincident management involves the study of incident prediction and prevention. ese systems are designed to generate alerts for vehicles before they get involved in any incident. e International Transport Forum (ITF) [12] reports the assumptions for these systems in achieving "zero-incident." A zero-incident situation is a symbol of perfection that is hard to achieve as it requires each component of the system to be perfect and working all the time in a synchronized manner. On the other hand, postincident management systems include an entire Traffic Incident Management System (TIMS) [13]. It comprises three major modules including incident detection, reporting, and clearance. e incident detection module includes the systems that evolved from nonautomatic incident detection systems via mobile telephone calls by eye-witnesses to automatic incident detection (AID) systems [14] that utilize parametric data gathered from on-road and in-vehicle sensing devices. e data are then analyzed using comparative, statistical, time-series, and ML algorithms to extract traffic patterns that are used to classify incidents [15]. e reporting module reports the detected incident to the appropriate stakeholders, e.g., hospitals, insurance agencies, traffic control room (TCR), law enforcement agencies, and neighboring vehicles. In the clearance module, actionable activities are arranged to clear the incident sight, e.g., ambulances, response teams, and changeable message signs (CMSs) [16,17].
is paper focuses on ML-based AID systems for smart cities that can be further classified into two categories with respect to (a) incident context and (b) classification: a context-aware AID system is designed to classify a single type of incident only, such as accident or congestion. e context-free systems are more generic and can classify among different types of traffic incidents, such as accident, congestion, and reckless driving. For example, a context-free AID system is proposed [18] in which accidents, road debris, and road works are considered as incidents and are detected using restricted Boltzmann machine (RBM). However, the system lacks in providing real-time support due to very high detection time. On contrary, most of the ML-based AID systems available in the literature, such as [19,20], are context-aware. ese systems have a very high probability of incident misclassification because these are designed to classify only a specific type of incident, e.g., an AID deployed to classify accident from traffic data may classify a stalled vehicle due to congestion to an accident. In addition, the ML-based AID system can be characterized as a singlefeature classification (SFC) which classifies the single feature or one aspect of the underlying scenario while multifeature classification (MFC) can classify or predict multiple features or multiple aspects about the underlying problem. erefore, a context-free AID system equipped with MFC can extract multiple aspects of the incident, such as type and severity.
Hence, the main aim of this research is to design an efficient incident detection and classification (E-IDC) framework for smart cities by leveraging the efficacy of model stacking to classify the incidents accurately with respect to incident type (accident, congestion, and reckless driving) and severity level (low, medium, and high). Following research questions (RQs) are listed to evaluate the performance of the proposed E-IDC framework: RQ-1: is the proposed framework effective to classify the incidents at their severity levels? RQ-2: is the proposed framework effective to classify the incidents into appropriate categories/contexts? RQ-3: does the proposed framework outperform the existing state-of-the-art ensemble learning approach used for incident prediction? e rest of the paper is structured as follows: Section 2 discusses the related work, Section 3 presents the proposed E-IDC framework, Section 4 describes the dataset creation mechanism and the evaluation model, Section 5 discusses the experiments and results, Section 6 describes the threat to validity, and Section 7 concludes the discussion of the article.

Related Work
ML-based AID systems can be categorized into two classes: (1) individual algorithm, a standalone algorithm usually based on a single classifier having classification and detection logic, and (2) fusion algorithms, integration of multiple 2 Complexity algorithms through ensemble learning to improve and enhance the performance of individual classifiers. Multiple systems consider incident classification as a multiclass problem in which the target/dependent variable has more than two outcomes; that is, if the severity of the accident is a target class/label then fatal, severe, slight, and injurious are the possible outcomes that may lead towards misclassification. e following subsections discuss briefly the individual and fusion-based AID systems.

Individual
Algorithm-Based AID Systems. e native ML-based AID systems were based on individual algorithms that take incident classification as a binary or multiclass problem. e binary classification represents two possible outcomes in the target variable, i.e., "1" if an incident occurs and "0" otherwise, while the multiclass also selects the target variable with multiple labels but selects one label at a time. In this section, existing ML-based incident detection and classification systems are discussed with respect to the context of the investigated incidents, parameters used in the incident predictor, and machine learning technique along with their support for multifeature classification or singlefeature classification.

Accident Detection Systems.
ML-based accident detection systems are deployed to detect accidents and their relevant details, i.e., crash severity, injury severity, driver behavior, weather condition, road conditions, type of vehicles involved in accidents, location of the vehicle, peak hours, and nonpeak hours. e study [18] proposed a spatiotemporal pattern network (STPN) and restricted Boltzmann machine (RBM)-based system that can find the presence of incident along with its root-cause analysis, but due to lack of data to train the model, the case study in this paper does not differentiate secondary incidents from all incidents and it focuses on accident only. Authors in [21] proposed an accident injury classification by using hierarchical clustering and artificial neural networks. e classification is restricted to a limited number of resources, large overhead, and lack of precision for a large number of clusters. e literature [22] proposes a traffic accident detection system using the random forest in which vehicles share their microscopic vehicular parameters with neighbor vehicles. Incidents are considered as outliers, which limits it to take binary classification decisions. A copula-based approach is employed in [23] with a multivariate temporal ordered probit model to simultaneously predict injury and damage severity.
ough it provides MFC support in classification, its functionality is limited within the same context. Authors in [24] find the weightage of attributes by using rough set theory and support vector machine (SVM) to predict the severity of accidents. In the literature, a semisupervised model is proposed that detects vehicle incident trajectories coming from the cameras using a deeplearning-based You Look Only Once (YOLOv3) classifier was projected [25]. In another study, [26] presented a system to investigate accident likelihood and severity by manipulating real-time traffic and weather data. e results presented in this paper are based on data from two urban arterials. In [27], a parametric sensitivity analysis method is proposed to shape an algorithm accident detection using SVM for rural roads. e development of automatic severity classification of accidents using advanced machine learning algorithms was carried out in the traffic accident literature [28]. e discussion on accident detection and classification systems is summarized in Table 1.

Congestion Detection Systems.
In the literature, researchers have focused on another important issue of traffic congestion that costs billions of dollars around the globe. e SFC-based ML approaches are currently being used to detect the presence, severity, and causal of congestion. e study [29] used the speed performance index to measure present congestion levels on urban roads. A procedure based on a piecewise switched linear (PWSL) macroscopic traffic model and an exponentially weighted moving average (EWMA) monitoring chart for the detection of traffic congestion was carried out in [30] which suffers from a lack of precision. In the literature [31], congestion levels are estimated by using clustering and find out the road area per capita along with the ownership of vehicles per thousand people, which affects the ratio of congestion. In [32], a novel traffic congestion detection algorithm is designed from two aspects. One is the offline traffic data processing, and the other is congestion mode judgment by online monitoring, but the system has very low support for real-time implementation.
e study [33] presented an integrated and computable definition of congestion in which a congestion dataset that contains multiple traffic scenes is constructed, and an algorithm is developed based on inverse perspective mapping (IPM). e deep-learning method does not work well, and a stronger label including the position of vehicles and a carefully designed deep network shall be exploited. In another study [34], a congestion detection algorithm is proposed using multilayer perceptron (MLP) and convolutional neural networks (CNNs), but there is a lack of incident type and severity. e study [35] presented a system for automated congestion detection on a road segment based on lane-changing properties. e literature [36] also proposed a Tree-Augmented Naïve Bayesian (TAN) classifierbased algorithm to estimate congestion. Due to lack of suitable datasets and transferability of information, the TAN-based algorithms are not evaluated in this paper. Table 2 summarizes the congestion detection systems.

Reckless Driving Detection Systems.
Reckless driving is an obvious reason for traffic accidents that also leads to congestion as well. In the literature [37], the authors presented the detection of centerline crossing in abnormal driving using a deep convolutional neural network, but the system lacks in providing precision and effectiveness. A study [38] proposed a five-layer architecture with the context-aware property that can collect the driving situation and detect bad driving patterns. A system to detect bad driving by training and testing a model with real-world vehicle data was also proposed [39]. e abnormal driving pattern of vehicles using multiple view geometry in space and time, e.g., transverse motion, acceleration/deceleration, and meandering, is proposed [40]. Another work [41] proposed a real-time GPS-based abnormal driving detection for intelligent vehicles, but there is a lack of precision due to insufficient training data. e authors in [42] proposed an innovative driver behavior monitoring system in real-time, because of vehicle dynamics, road design values, and passenger comfort. To identify and detect the abnormal driving behavior, e.g., lane changing, weaving, and sudden braking by using pattern matching techniques were carried out in [43]. e study did not consider various road types, vehicles and placement positions of the phone, and variable sampling rates, and their effect on the pattern. In the literature [44], an anomaly detection system is proposed, namely, D&R Sense to enrich smart transportation and making road journeys safe and comfortable. Table 3 summarizes various aspects of reckless driving detection systems.

Fusion
Algorithm-Based AID Systems. Fusion algorithms are commonly implemented through ensemble learning technique which is one type of ML technique in which multiple classifiers are combined to improve the performance and accuracy of the classification. Stacking is an ensemble learning that is used to explore a space of different models for the same problem. e logic is to take a learning problem with different types of models that are capable to learn some part of the problem, but not the whole space of the problem. Hence, multiple different learners could be built and further used to build an intermediate prediction, one prediction for each learned model. en, a new model could be added which learns from the intermediate predictions for the same target. Traffic incident detection systems use the ensemble learning approach to achieve accuracy and minimize the false alarm rate.
Authors in the literature [45] proposed a model for injury severity analysis by using two-layer stacking but the effectiveness of the model is achieved by setting the values of various parameters as fixed (e.g., values in the ideal environment). e literature [46] proposed a freeway accident detection by using a two-stage approach that optimally sums up the data generated from sensors using Bayesian quickest change detection framework, but lack of MFC support and intertype classification was found. An ensemble learning technique is used in which SVM and KNN models are used for traffic incident detection [19], but there is no support for incident type classification. An incident detection and management system are proposed for traffic signals comprising of urban traffic networks [47], but the system requires extra hardware for proper functioning, hence providing a costly solution to the incident detection. ere is a methodology in which traffic signals are extracted from video and converted as spatial-temporal (ST) signals to find the normal and abnormal driving patterns by using SVM and adaptive boosting on these ST signals [48]. In [49], it is studied that the causes of traffic congestion using collaboration between connected vehicles and used voting procedure (VP) and belief function (BF) methods for congestion estimation, but it has very low support for real-time implementation due to lack of validity. A framework was designed for real-time distributed congestion classification on a diverse urban road network using a decision tree and probabilistic Naïve Bayes classifier [50]. In a study [20], an  AID algorithm is developed based on standard SVM with the bagging method but the system lacks providing real-time implementation support, and boosting may outperform bagging. In the study [51] (XGBoost), the ML technique is used to detect the occurrence of accidents using a set of realtime data comprised of traffic, network, demographic, land use, and weather features but the performance of this system is limited to highway-based accident detection. e literature on fusion algorithms shows that multiexpert and multistage systems are currently being used to improve the performance of individual algorithm-based incident detection and classification systems. However, all these systems are context-aware in nature and do not support multitarget classification. Table 4 summarizes various aspects of fusion algorithm-based AID systems.
To summarize the entire discussion on existing AID systems, it could be said that existing systems support univariate or multivariate target variable but within the same incident context (either it detects the presence of incident or it classifies its severity) and these are not compatible for realtime deployment due to the imprecise training based on offline features (collected from the police department or hospitals after the incident is rescued). So, in the context of TIMS, it requires a full understanding of several aspects of the incident (incident type and severity, type of vehicles collapsed, peak or off-peak hours and location, etc.) that help in devising more efficient incident clearance plans that may help in minimizing the occurrence of secondary incidents in smart city paradigm. us, an effective incident detection and classification framework is needed to reduce the clearance delay in any circumstances (accident, congestion, reckless driving, and other environmental conditions such as weather and time). In each dimension of TIMS, the quick and valid response based on maximum information relevant to the incident could be more beneficial for all stakeholders in devising appropriate decision making as well as to avoid the near future incidents.

Efficient Incident Detection and Classification (E-IDC) Framework
We propose an efficient incident detection and classification framework based on enhanced TIMS architecture as well as incident detection and classification algorithm to effectively detect and classify the incident type and severity for smart cities.

Enhanced TIMS.
Similar to the existing TIMS architecture, the proposed enhanced TIMS architecture also comprises three major components: (1) on-road networks, (2) intelligent roadside units, and (3) traffic control room. However, the enhancements have been proposed in all the abovementioned components to improve the operations of the TIMS as depicted in Figure 1 and discussed as follows: (1) On-road network: it comprises various sensing resources (e.g., loop detectors and radar sensors) that can be used to collect the desired on-road parameters of interest from a smart city environment, such as traffic flow information, weather information, and vehicle specific information. (2) Intelligent roadside unit (I-RSU): traditionally, the RSUs were used as access points (APs) to collect the data from the road network and forward it to the traffic control room. We propose to enhance the capabilities of RSUs by deploying a pretrained incident detection and classification algorithm on them. e resulting RSU is named intelligent roadside units (I-RSUs), as they are now capable of processing the data received from the on-road network and classify incidents based on type (accident, congestion, or reckless driving) and severity. Figure 1 depicts the I-RSU and its two components, (1) transceiver, which receives real-time data from onroad sensors and forwards it to TCR along with processed incident-specific information, and (2) incident detection and classification algorithm.
(3) Traffic control room (TCR): TCR is a centralized traffic control room dedicated to managing the traffic flow of a city. In this study, TCRs are used for offline  training of the incident detection and classification algorithm that is deployed on the I-RSU.

Incident Detection and Classification
Algorithm. e proposed E-IDC framework utilizes model stacking to detect and classify road traffic incidents based on type and severity.
ough the model stacking has been used in various studies [52] to provide a solution for the classification problems, its performance is restricted to SFC as it considers only one target variable for decision making. In this study, we have enhanced the capability of the model stacking approach to provide MFC and make it context-free. e model stacking comprises of two levels: the "level 1 (L1)" classifies the incident severity and "level 2 (L2)" is to classify the incident type. As a result, the classification of the incident (type) with its associated impact (severity) can be classified in a single iteration. Moreover, since the incident type and severity classification are interdependent problems, therefore, incident severity prediction at L1 can help to improve the classification (accuracy and performance) of incident type at L2.
e entire classification procedure of the proposed E-IDC framework is logically presented in Figure 2 as a block diagram.
We have considered three incident types, i.e., accident (A), congestion (C), and reckless driving (R) with their associated severity in three levels, i.e., low (L), medium (M), and high (H), which results in a total of nine (type and severity) pairs. At L1, nine models (M1 to M9) are trained using raw data X (obtained from the on-road network), to classify one of the nine (type and severity) pairs, e.g., M1 is trained to classify (type (accident) and severity (low)). Each model will give its output as either 0 or 1 according to the belonging of the (type and severity) pair.
e output vector X′ of L1 (comprising of nine outputs from the L1 models) is then passed as input to the L2 that has three models (N1 to N3) that are trained to classify the three incident types (A, C, and R). Figure 3 further elaborates the details of the proposed E-IDC framework in terms of the structure and the procedure for training and testing. Firstly, the raw dataset (X) is taken having the order "i × j," where "i" represents the number of instances (incident records) and "j" represents the features (traffic attributes) with severity as a target variable "T sev ". e dataset is then split into nine data segments (A_L, A_M, and so on) with respect to the (type and severity) pairs. ese data segments are used to train the nine L1 models, i.e., M1 (A, L), M2 (A, M), M3 (A, H), . . ., M9 (R, H) for (type and severity) pair classification. After training of L1 models, the severity predictions for "i" records are taken using k-fold cross-validation, e.g., all the nine models predict the severity label as 1 or 0; that is, "1" will be predicted if the instance belongs to the model and "0" will be predicted if it does not belong. Afterward, the predictions from nine L1 models "PM1, PM2, . . ., PM9" for "i" records are taken as features for creating the training dataset (termed as X′) for L2. e target variable "T type " is assigned the ground truth values/labels that are known during the training procedure. X′ is then split into three data segments each for a specific incident type classification (A, C, and R). ese data segments are used to train three L2 models, such as N1 (accident), N2 (congestion), and N3 (reckless driving) using k-fold crossvalidation; that is, all the models predict the incident type label as 0 or 1. After training the model stacking-based E-IDC algorithm, the unlabeled testing data (T) having the order "i × j" without target variable "T sev " (i.e., "?" in Figure 3 shows the emptiness of the target variable) are passed to the nine trained models of L1. All nine models will predict the incident severity label for "i" instances of "T" and create a dataset (T′) from these predictions. e dataset T′ with empty target variable "T type " is passed into  6 Complexity three trained models of L2 that will predict the incident type labels for all the test instances. Hence, the predictions of both levels give the final incident severity and type predictions and make the "E-IDC framework" compatible with the MFC support.

Dataset Description.
e dataset description presented in this section comprises three activities including dataset extraction, preprocessing, and sensitivity analysis.

Dataset Extraction.
ere is no single public dataset that collectively contains information about the three major road traffic incidents (accident, congestion, and reckless driving). erefore, the accident dataset (D1) was retrieved from the link (smoosavi.org/datasets/us_accidents) which was spans over 49 states of the US from February 2016 to onwards. e D1 is used in the literature [53] for accident risk prediction. e dataset on congestion and reckless driving was collected from the United States (US) Government dataset repository (data.gov). e congestion dataset (D2) contains the past data on congestion of 1270 Chicago's arterial roads from August 2011. e data at Chicago Traffic Tracker are continuously collected through GPS traces received from Chicago Transit Authority (CTA) buses. irdly, the dataset for reckless driving (D3) is collected which spans the historic data of the motorists who exceed the safe speed limit of Chicago City by at least 12 miles per hour (mph), and based on these data, citations/ penalties could be generated. Since the datasets on congestion and reckless driving were relevant to only one state, i.e., Chicago; therefore, we have only selected the data of Chicago out of 49 states of D1, and the timespan for D1 was in-line with the time frame of D2 and D3 to maintain the uniformity. e retrieved datasets independently provide labeled data for a specific type (i.e., accident or congestion) along with their severity.

Data Preprocessing.
In order to create a single dataset containing incidents of three types (accident, congestion, and reckless driving) with their three associated severity levels (low, medium, and high), the collected datasets (D1, D2, and D3) are integrated to create a single dataset. e integration of the data is done based on the common demographic (location) and temporal (time and date) attributes from all three datasets to align in a single file. Eleven attributes (start latitude, start longitude, road segment number, temperature (F), humidity (%), pressure (in), visibility (mi), wind speed (mph), weather condition, traffic signal, and sunrise/sunset) are selected from the D1 dataset, and five attributes (start latitude, start longitude, road segment number, date, and time) were selected from D2 and D3 datasets. e weather conditions can also play a vital role in transportation behavior, and it was missing in D2 and D3 datasets which were extracted from the online weather data sources by using date, time, latitude, and longitude. By merging these attributes, a total of eleven attributes were combined in a single file, and labels were assigned to each instance as given in the original dataset. e created dataset was then analyzed, and it was observed that the selected attributes were not enough to classify multiple incident types along with their severity. e reason for this deficiency was the lack of vehicle-related attributes that would better describe the traffic condition to differentiate the type of incidents that occur on the road. erefore, we have used the Simulation of Urban Mobility (SUMO) simulator to impersonate the incidents that are already present in the historical datasets by using the location (latitude and longitude) and environmental situations. A road traffic scenario was generated in SUMO in which we export the Chicago City maps from OpenStreetMap (OSM) website. Random trips were generated on various areas of the map, and various detectors were applied to multiple places on the map. As SUMO is a collision-free simulator, we have forcefully simulated accidents by implementing stops in vehicles at random places and random lanes. Congestions are simulated at various lanes, and speed is increased three times to simulate drivers' aggressive driving behavior. e final dataset after integration holds thirty-two attributes of which thirty (historical and simulator-based attributes) are serving as independent and two as dependent variables. e description of dependent variables, i.e., incident severity and incident type, is given in Table 5.
To improve the effectiveness of the created dataset in terms of accuracy in incident classification, the undersampling technique is applied on the integrated data in which all the instances with missing values were excluded to remove the ambiguities, and all the classes are balanced with an equal number of instances.

Dataset Sensitivity Analysis.
To identify the validity and contribution of each feature of the created dataset to the classification results of the E-IDC framework, we have extracted the weights corresponding to each feature by applying information gain attribute evaluation [54]. Figures 4 and 5 show the contribution of each factor in the classification of incidents at its types and severity levels, respectively. All the features are classified into two categories, i.e., historical data and simulated data. e features of the simulated data have high significance over most of the variables from the historical data category which shows that selected simulated attributes are imported to be available for real-time incident detection and classification. Moreover, it is clarified from the sensitivity analysis that the accuracy of incident classification results majorly depends on the presence of road, vehicular, and traffic flow-related attributes contribute about 70%-73% in the case of incident type and severity classification.

Evaluation Model for Framework.
e performance evaluation of the proposed framework is done in two steps. In the first step, we have extracted various model evaluation metrics for the implemented E-IDC framework. As our proposed approach falls under the classification problem, therefore, we considered five performance evaluation metrics to evaluate our algorithm. ese five metrics include true positive rate (TP), false positive rate (FP), precision (P), recall (R), and F-measure. ough we have calculated all the values of evaluation metrics, to simplify the presentation of results and considering the significance of F-measure, we have used it as a primary investigating factor. 8 Complexity In the second step, the Wilcoxon test is conducted, and boxplots are drawn to benchmark the performance of the proposed E-IDC framework. ough there are several statistical tests (e.g., McNemar's, Friedman's, and Nemenyi tests) to benchmark the significance of one algorithm over the other but based on the nature and domain of our problem, we have used the Wilcoxon test. e Wilcoxon test is conducted to determine if two or more sets of pairs are different from one another in a statistically significant manner [55]. In this study, we have two groups of algorithms to be judged, i.e., individual classifiers and classifier integrated with the proposed E-IDC framework over a single dataset. e results of the Wilcoxon test are interpreted in terms of significance values and are discussed in the next section. Afterward, the boxplots are drawn to visualize and compare the F-measures of existing (individual) and proposed (E-IDC) incident classification framework. e F-measures of both groups (individual and E-IDC framework) are taken as sample populations. e boxplots are interpreted using the lower, median, and upper quartile notations, i.e., Q 1 , Q 2 , and Q 3 of the sample data, respectively. ese notations help us to determine the size of the boxes (i.e., interquartile range (IQR)), the position of median, and whisker in the boxplot. Finally, through these     Complexity parameters, we have interpreted the difference between the two groups. Following rules are considered for the interpretation of boxplots [56]: Rule 1. F-measure comparison between two groups is considered different when boxplots do not overlap each other. Consequently, the difference between the two sample distributions can be endorsed if the following equation holds: (1) Rule 2. F-measure comparison between two groups will be the same when their boxplots overlap each other via medians and the following equation holds: Rule 3. F-measure comparison between two groups will be the considered uncertain when their boxplots overlap each other without medians. In this case, the subrules are derived as follows.
Subrule 3A. F-measure comparison between two groups of classes will be the same when their IQR is the same, defined using However, it could not define that the underlying F-measure distribution is symmetric.
Subrule 3B. e underlying F-measure distribution will be symmetric if the difference of Q 1 and Q 3 with Q 2 (median) is the same, shown in equation (4). e same assumption can be done between whiskers and Q 2 : Furthermore, we have considered the distance between medians (DBMs) and overall visible spread (OVS) measures to significantly distinguish among the distributions of [57]. According to the fractional percentage (i.e., DBM/ OVS × 100), the significant difference between groups can be defined in terms of sample size. For example, when the sample size is up to 30, then the fractional percentage >33% indicates the significant difference between groups. Subsequently, the fractional percentages of 20% and 10% are recommended when the sample size is ≥100 and 1000 observations, respectively. e sample size of the system under study is fewer than 30; therefore, the results are benchmarked according to a fractional percentage of 33%.

Experiments and Results Analysis
In this section, we have presented an experimental procedure along with the algorithm followed by the results. e main aim is to describe the procedure that how the proposed E-IDC framework can be employed to (1) incident severity classification, (2) incident type classification, and (3) comparison of the proposed technique with state-of-the-art ensemble technique in terms of incident type and severity classification.

Experimental Procedure.
We have performed several experiments and grouped them into three phases. In the proposed E-IDC technique training of the incident classification module is periodically improved based on the incident detection and classification received from the I-RSUs. erefore, the classifiers with low training overhead are preferred. Moreover, due to real-time incident classification requirements, the proposed incident classification module should have a minimum response time. After conducting the experiments with a total of 14 classifiers, we have selected nine classifiers that fulfill the above requirements to be fused with the proposed E-IDC technique. While in the second phase experiments, we employed the proposed E-IDC framework described in Algorithm 1 by incorporating all the nine classifiers of the first phase (such as NB) and analyzed the improvement in the classification decision.
In the algorithm, steps 1-2 describe level 1 and predict the incident severity labels, whereas steps 3-4 are responsible for incident type classification and hence describe level 2 of model stacking. To refer to experiments of the second phase, we have used the notation "E-IDC + NB" for the NB to analyze in [58] and compare the improvement in the performance of individual incident predictors (i.e., NB) with the proposed framework (i.e., E-IDC + NB). e same notation is used for the rest of the individual incident predictors. e experiment of the third phase is performed to compare the performance of the proposed E-IDC with the existing stateof-the-art ensemble technique (i.e., XGBoost). e experiments of all phases are performed with k-fold (i.e., k � 10) cross-validation to assess the effectiveness of incident predictors. Besides, we performed all experiments using WEKA and R tool. Finally, to benchmark the performance of the proposed E-IDC compared to the existing incident predictors, we have applied various nonparametric tests. e first and second phase experiments aim to respond to the RQ-1 and RQ-2, respectively, while experiments of the third phase aim to respond to the RQ-3.

Response to RQ-1.
e aim of RQ-1 is to assess the effectiveness of E-IDC as compared to individual incident predictors in terms of identification of severity level of incidents. Consequently, in this regard, we performed experiments of the first and second phases by calling Algorithm 1. e effectiveness of individual incident predictors and their incorporation with the proposed ensemble framework (i.e., E-IDC) in terms of F-measure is shown in Figure 6. e major findings of experimental results are as follows: (i) A significant increase (5%-56%) in the performance of individual incident predictors when exploiting through E-IDC except for NB (ii) 48% improvement in the effectiveness of individual incident predictor, namely, H-Tree when it is incorporated with E-IDC (i.e., E-IDC + H-Tree) (iii) Improvement in the performance of NB (1%), RF (5%), and J48 (6%) when incorporated with E-IDC as compared to their performance at the individual level (iv) E-IDC + J48 (F-measure � 99%) and E-IDC + LMT (F-measure � 99%) outperformed other incident predictors for correct estimation of the severity levels of an incident From Figure 6, it can be observed that the improvements for the individual incident predictors may vary.
Consequently, there is a need to benchmark the significance of improvement for individual incident predictors when incorporated with E-IDC. In this regard, we applied a nonparametric test, namely, a two-tailed Wilcoxon signedrank test to rank the significant improvement in classification decision of incident predictors when incorporated with E-IDC. e F-measure values of incident predictors with and without E-IDC are considered as two sample populations. e null hypothesis (H0: the performance of individual incident predictors with and without incorporation with E-IDC is the same for the prediction of incident severity levels). e observed value of the Wilcoxon signedrank test (i.e., 0.004) with p value <0.05 indicates the rejection of null hypothesis. Consequently, we can conclude that the performance of individual predictors is not the same when incorporated with E-IDC.
Moreover, to evaluate the boxplot drawn for incident severity classification shown in Figure 7, we apply the rules defined earlier. It can be observed that the IQR of both groups overlaps without medians; hence, first and second rules are rejected. In the case of individual and E-IDC incident predictor groups for incident severity classification presented in Figure 7, the IQR of both incident predictors slightly overlaps and it can be observed that the Q 2 and Q 3 of E-IDC incident predictors are greater than Q 2 of individual incident predictors. Moreover, it can be concluded from the values of whiskers and medians that the performance of E-IDC incident predictors is better than individual predictors, which makes rule 3 vague. Hence, we will apply the DBM and OVS fractional percentage test to benchmark the performance of our approach. e Q 2 value of the individual incident predictor (0.871) is less than the value of the E-IDC incident predictor (0.971). Hence, the value of DBM for this case is 0.1, and the value of OVS is 0.27. erefore, their fractional percentage calculated through the formula is 37% that is greater than 33% (significant value for this study) significance of E-IDC over individual incident predictors for incident severity classification.

Response to RQ-2.
RQ-2 aims to assess the effectiveness of E-IDC as compared to individual incident predictors in terms of type identification of traffic incidents. Consequently, in this regard, we performed experiments of the first and second phases, but this time, we consider the incident type rather than incident severity levels by using Algorithm 1.
e effectiveness of individual incident predictors and their incorporation with Input: 1. "X" = S[i][j] is a matrix of training dataset with "i" instances and "j" independent variables 2. "C" � {Set of individual classifiers selected under study i.e., Naïve Bayes, Decision Table. . .. J48} Procedure Begin 1. Split "X" to "m" datasets 1.1. Assign binary labels for each severity class in "X m " 2. FOR "m" � 1 to 9 2.1. Apply classification algorithm from "C" on "X m " 2.1.1. Predict severity labels for "i" rows of "X" 2.1.2. Write predicted severity labels in "X′" 3. Split "X′" to "l" datasets 3.1. Assign binary labels for each incident type class in "X l " 4. FOR l � 1 to 3 4.1. Apply classification algorithm from "C" on "X l " 4.1.1. Predict type labels for "i" rows of "X′" 4.1.2. Apply evaluation criteria to assess the F-measure of the classifier Procedure End Output: e outperform incident predictor with best F-measure along with severity and type labels  Figure 8, we can observe that the significant improvement in individual incident predictors varies. Consequently, there is a need to benchmark the significant improvement of individual incident predictors when incorporated with E-IDC.
In this regard, like severity level prediction, we also applied a nonparametric test, namely, the two-tailed Wilcoxon signed-rank test to rank the significant improvement in classification decision (i.e., identification of incident types) of incident predictors when incorporated with E-IDC. e null hypothesis (H0: the performance of individual incident predictors with and without incorporation with E-IDC is the same for the prediction of incident types). e observed value of the Wilcoxon signed-rank test (i.e., 0.03) with p value <0.05 indicates the rejection of null hypothesis. Consequently, we can conclude that the performance of individual incident predictors is not the same when incorporated with E-IDC. Afterward, we draw a boxplot-based comparison in Figure 9 to benchmark the    significant improvement in the performance of the proposed incident predictor for the identification of incident types. e IQRs of both groups slightly overlap (without Q 2 ) from the bottom of E-IDC with the top of individual incident predictors which rejects rules 1 and 2.
Moreover, it can be observed that Q 2 and Q 3 of E-IDC are greater than Q 2 of individual incident predictors which implies E-IDC incident predictors are better as compared to individual incident predictors in terms of incident type classification. Moreover, it can also be concluded that the groups are not symmetric and rule 3 is weak to make any clear decision about the groups. Hence, to benchmark the performance, we will calculate the percentage of DBM and OVS.
e Q 2 value of the individual incident predictor (0.987) is less than the value of the E-IDC incident predictor (1). Hence, the value of DBM for this case is 0.013 and the value of OVS is 0.037. erefore, their fractional percentage calculated through the formula is 35% (>33% significant value) which shows the significance of E-IDC over individual incident predictors.  In the context of incident detection, recently, [51] has reported the implication of an ensemble technique XGBoost by leveraging the capabilities of a decision tree classifier. In order to respond to the RQ-3, we performed a comparative analysis of outperformed proposed incident type predictors (such as E-IDC + LMT) with XGBoost. e results are shown in terms of F-measure in Figure 10. In the case of incident severity level prediction, the proposed ensemble framework has improved the classification decision up to 8% of the proposed E-IDC incident predictor (i.e., E-IDC + LMT) as compared to XGBoost. Similarly, in the case of incident type prediction, the proposed E-IDC framework has improved the classification decision up to 1% of the individual incident predictor (i.e.,   Complexity 13 E-IDC + LMT) as compared to XGBoost. ough the low improvement in the classification decision of LMT through E-IDC has been observed, it will be true for the rest of the cases when XGBoost is ensembled with another individual classifier.

Results Evaluation
Summary. e following discussion evaluates the experimental results: (1) e performance of an individual incident predictor can be enhanced through the proposed ensemble framework, namely, E-IDC in terms of F-measure and accuracy. In the case of severity level prediction, we observe a 5%-56% improvement for prediction of severity level while a 1%-14% improvement for the type of prediction of incidents through E-IDC. (2) e experimental results indicate the effectiveness of E-IDC to identify the type and its associated severity level of an incident simultaneously in a single iteration rather than identification of a specific incident type or severity level done by existing incident predictors. (3) We observe that E-IDC performs better compared to existing ensemble techniques, such as XGBoost used for the prediction of incidents. (4) e proposed model stacking approach shows improvements in both severity classification based on specialized incident severity predictors at level 1 and incident type classification based on intermediary predictions at level 2 that narrow down the domain of incident type. Level 2, thus, predicts incident type more accurately with a very low misclassification rate. (5) It could be observed from the experiments that the model stacking approach could be utilized for MFCbased applications in which multiple aspects of the same problem/event are to be classified. As traffic incident type and severity classification is a multivariate problem and both the target variables are highly interdependent, therefore, both the target variables could be classified simultaneously by stacking them at various levels of model stacking. (6) Existing MFC-based approaches [18,23] train the classifiers using the entire training dataset for each target variable independently and thus involve high training overhead whereas the proposed model stacking approach reduces the training overhead by exploiting the predictions of intermediate levels to obtain the final predictions. (7) e results of the proposed approach could be enhanced near to reality by deploying various real vehicular features in the datasets extracted from the smart vehicle, smart road infrastructure, and smart city environment as the traffic parameters show a high dynamicity in real-time.

Threats to Validity
In this study, we have identified the following four threats to validity: I. e first threat is related to the generalization of data preprocessing techniques. We have performed experiments and concluded the results with balanced incidental instances/records. An unbalanced and continuous stream of real-time data could present the modified results. II. e second threat is related to the use of an integrated dataset and the selection of independent parameters specific to vehicles and weather conditions. e reported results could be altered if more features are added and tuning is done. III. e third threat is related to the consideration of few incident predictors to assess the efficacy of the E-IDC framework. e benchmark result could be varied either if the number of incident predictors is increased or incident predictors of other families are considered. IV. e fourth threat is relevant to the use of selected performance measures to assess the effectiveness of the proposed approach. We used only F-measure, while  other performance metrics could be considered to assess class-level accuracy of the E-IDC framework.

Conclusion
E-IDC framework is based on incident classification via model stacking, an ensemble learning approach aid to provide a promising base for classifying various incident types and their severity levels simultaneously. We conclude several important consequences with respect to the experimental results. First, no individual algorithm could be specified to be stacked in the model stacking approach and varies across MFC-supported incident classification problems. All the individual algorithms provide SFC support, but their performance capabilities are enhanced by integrating them with our proposed E-IDC framework. e performance of the proposed E-IDC framework is enhanced by 5%-56% in terms of incident severity classification and 1%-14% improvement is observed in incident type classification. Second, the performance of a classifier degrades with the increase in the number of classes in the target variable, e.g., the F-measure for incident type classification is far more pleasant than severity classification as it has more classes in the target variable. Moreover, in order to determine more than two aspects of the incident simultaneously, more levels in stacking should be added as we have considered only the type and severity of the incident; therefore, we have defined only two levels in the model stacking approach. ird, to benchmark the performance of our proposed approach, we have used the Wilcoxon nonparametric test for incident severity (i.e., 0.004) and type classification (i.e. 0.03) which shows lesser values than the significant value (i.e. 0.05) and hence rejects the null hypothesis. Moreover, we observe that the E-IDC framework outperforms (8% for the case of incident severity and 1% in case of type classification) the existing ensemble framework such as XGBoost used for the prediction of incidents.

Data Availability
e data used to support the findings of this study are available from the corresponding author upon request.

Conflicts of Interest
e authors declare that they have no conflicts of interest to report regarding the present study.


extfieldsofstudy:
Computer Science
Mathematics

s2fieldsofstudy:
Computer Science
Mathematics

text:
Faster Rates of Private Stochastic Convex Optimization

In this paper, we revisit the problem of Differentially Private Stochastic Convex Optimization (DP-SCO) and provide excess population risks for some special classes of functions that are faster than the previous results of general convex and strongly convex functions. In the first part of the paper, we study the case where the population risk function satisfies the Tysbakov Noise Condition (TNC) with some parameter $\theta>1$. Specifically, we first show that under some mild assumptions on the loss functions, there is an algorithm whose output could achieve an upper bound of $\tilde{O}((\frac{1}{\sqrt{n}}+\frac{\sqrt{d\log \frac{1}{\delta}}}{n\epsilon})^\frac{\theta}{\theta-1})$ for $(\epsilon, \delta)$-DP when $\theta\geq 2$, here $n$ is the sample size and $d$ is the dimension of the space. Then we address the inefficiency issue, improve the upper bounds by $\text{Poly}(\log n)$ factors and extend to the case where $\theta\geq \bar{\theta}>1$ for some known $\bar{\theta}$. Next we show that the excess population risk of population functions satisfying TNC with parameter $\theta\geq 2$ is always lower bounded by $\Omega((\frac{d}{n\epsilon})^\frac{\theta}{\theta-1}) $ and $\Omega((\frac{\sqrt{d\log \frac{1}{\delta}}}{n\epsilon})^\frac{\theta}{\theta-1})$ for $\epsilon$-DP and $(\epsilon, \delta)$-DP, respectively. In the second part, we focus on a special case where the population risk function is strongly convex. Unlike the previous studies, here we assume the loss function is {\em non-negative} and {\em the optimal value of population risk is sufficiently small}. With these additional assumptions, we propose a new method whose output could achieve an upper bound of $O(\frac{d\log\frac{1}{\delta}}{n^2\epsilon^2}+\frac{1}{n^{\tau}})$ for any $\tau\geq 1$ in $(\epsilon,\delta)$-DP model if the sample size $n$ is sufficiently large.

for -DP and ( , δ)-DP, respectively when θ ≥ 2, here n is the sample size and d is the dimension of the space. Then we address the inefficiency issue, improve the upper bounds by Poly(log n) factors and extend to the case where θ ≥θ > 1 for some knownθ. Next we show that the excess population risk of population functions satisfying TNC with parameter θ ≥ 2 is always lower bounded by Ω(( d n ) θ θ−1 ) and Ω(( √ d log(1/δ) n ) θ θ−1 ) for -DP and ( , δ)-DP, respectively, which matches our upper bounds. In the second part, we focus on a special case where the population risk function is strongly convex. Unlike the previous studies, here we assume the loss function is non-negative and the optimal value of population risk is sufficiently small. With these additional assumptions, we propose a new method whose output could achieve an upper bound of O( d log(1/δ)

Introduction
Preserving the privacy of training data has become an important consideration and now is a challenging task for machine learning algorithms. To address the privacy issue, Differential Privacy (DP) (Dwork et al., 2006), which roots in cryptography, is a strong mathematical scheme for privacy preserving. It allows for rich statistical and machine learning analysis, and is now becoming a de facto notation for private data analysis. Methods to guarantee differential privacy have been widely studied, and recently adopted in industry (Tang et al., 2017;Ding et al., 2017).
As one of the most important problems in Machine Learning and Differential Privacy community, the Empirical Risk Minimization problem in the DP model, i.e., DP-ERM, has been studied quite well in the last decade, starting from (Chaudhuri et al., 2011), such as (Bassily et al., 2014;Wang et al., 2017Wang et al., , 2019aWu et al., 2017;Kasiviswanathan and Jin, 2016;Kifer et al., 2012;Smith et al., 2017;Wang et al., 2018aWang et al., , 2019bAsi et al., 2021a). Besides DP-ERM, its population (or expected) version, namely Differentially Private Stochastic Convex Optimization (DP-SCO), has received much attention in recent years, starting from (Bassily et al., 2014). Specifically, (Bassily et al., 2019) first provides the optimal rate of DP-SCO with general convex loss functions in ( , δ)-DP, which is quite different from the optimal rate in DP-ERM. Later, (Feldman et al., 2020) extends this problem to strongly convex and (or) non-smooth cases by providing a general localization technique. Moreover, their methods have linear time complexity if the loss functions are smooth. For non-smooth loss functions, (Kulkarni et al., 2021) recently proposes a new method which only need subquadratic gradient complexity. While there are already a large number of studies on DP-SCO, the problem is still far from well understood. A key observation is that, all of the previous works only focus on the the case where the loss functions are either general convex or strongly convex. However, there are also many problems that are even stronger than strongly convex functions, or fall between convex and strongly convex functions. In the non-private counterpart, various studies have attempted to get faster rates by imposing additional assumptions on the loss functions. And it has been shown that it is indeed possible to achieve rates that are faster than the rates of general convex loss functions (Yang et al., 2018;Koren and Levy, 2015;van Erven et al., 2015), or it could even achieve the same rate as in the strongly convex case even if the function is not strongly convex (Karimi et al., 2016;Liu et al., 2018;Xu et al., 2017). Motivated by this, our question is, For the problem of DP-SCO with special classes of population risk functions, is it possible to achieve faster rates of the excess population risk than the optimal ones of general convex and (or) strongly convex cases?
In this paper, we provide an affirmative answer by studying some classes of population risk functions. Particularly, we will mainly focus on the case where the population risk satisfies the Tysbakov Noise Condition (TNC) 1 , which includes strongly convex functions, SVM and linear regression as special cases. Our contributions can be summarized as follows.
• In the first part of the paper, we study the problem where the population risk satisfying TNC with parameter θ and propose three methods. When θ ≥ 2, we first propose a method that could achieve an excess population risk of O(( 1 √ n + d n ) θ θ−1 ) and O(( 1 √ n + √ d log(1/δ) n ) θ θ−1 ) in -DP and ( , δ)-DP model respectively under the assumption that the loss function is smooth and Lipschitz, where n is the sample size of the data and d is the dimension of the space. We then propose another method to resolve the inefficiency issue under the assumption that θ is known. Moreover, we propose an improved method. Compared with previous two methods, it improves the upper bounds of error by Poly(log n) factors. And it only needs a relaxed assumption of θ ≥θ > 1 for some knownθ instead of θ being known or θ ≥ 2. Moreover, it outperforms the previous methods practically. Next, we focus on the lower bounds of the excess population risk. Specifically, for any θ ≥ 2, we show that there is a population risk function satisfying TNC with parameter θ such that for any -DP (( , δ)-DP) algorithm, its output achieves an excess risk of Ω(( d n ) θ θ−1 ) ( Ω(( √ d log(1/δ) n ) θ θ−1 )) with high probability.
• In the second part of the paper, we will focus on the problem where the population risk function is strongly convex, which is a special case of TNC functions with θ = 2. Unlike the previous studies, here we assume the loss function is non-negative and the optimal value of the population is sufficiently small. With these additional assumptions, we propose a new method whose output could achieve an upper bound of O( d log(1/δ) n 2 2 + 1 n τ ) and O( d 2 n 2 2 + 1 n τ ) for any τ > 1 in ( , δ)-DP and -DP model respectively if the sample size n is sufficiently large. These rates circumvent their corresponding lower bounds for general strong convex functions in (Feldman et al., 2020), i.e., Θ( d 2 n 2 2 + 1 n ) for -DP and Θ( d log(1/δ) n 2 2 + 1 n ) for ( , δ)-DP.
Due to the space limit, all the experiments (Appendix B) and proofs are included in Appendix.

Related Work
Starting from (Chaudhuri et al., 2011), a long list of works have attacked the problems of DP-ERM from different perspectives: (Bassily et al., 2014;Iyengar et al., 2019;Zhou et al., 2020;Song et al., 2020;Wang et al., 2017;Zhang et al., 2017) studied the problems in the low dimensional case and the central model, (Kasiviswanathan and Jin, 2016;Kifer et al., 2012;Talwar et al., 2015;Wang and Gu, 2020;Cai et al., 2020) considered the problems in the high dimensional sparse case and the central model, (Smith et al., 2017;Duchi et al., 2013;Wang et al., 2020a;Duchi et al., 2018) focused on the problems in the local model. However, almost all of these works only focus the case where the empirical risk function is either general convex or strongly convex. For special class of functions, (Wang et al., 2017) studies the empirical risk functions satisfying Polyak-Lojasiewicz (PL) condition, which is weaker than strongly convexity and show that it is possible to achieve an excess empirical risk of O( d log(1/δ) n 2 2 ), which is the same as the strongly convex loss. As we will mention in Remark 16, the PL condition is equivalent to TNC with parameter θ = 2. Thus, in this paper we extend the result from the empirical risk to the population risk function.
For DP-SCO, besides the related work we mentioned in the previous section, there is another direction which studies some special cases of DP-SCO. For example, (Bassily et al., 2021) and (Asi et al., 2021a) consider the case where the underlying constraint set W has specific geometric structures, such as polyhedron. (Guzmán et al., 2021) studies the (non)smooth and (non)convex generalized linear loss. (Wang et al., 2020b) and(Kamath et al., 2021) focus on the case where the distribution of the data or the gradient of the loss function is heavy-tailed. However, none of these works study the case where the population risk satisfies TNC. (Liu et al., 2021) recently studies the theoretical guarantees of the PATE model (Papernot et al., 2016) under the assumption that the population risk function satisfies TNC and shows that it is possible to achieve faster rates than in the convex case (Bassily et al., 2018). However, since here we focus on a different problem, their results cannot be used to DP-SCO.
Concurrent Work: We notice that (Asi et al., 2021b) also studies DP-SCO with TNC population risk functions concurrently. However, compared with its results there are several critical differences.
1) The idea of Algorithm 2 in (Asi et al., 2021b) is similar to Algorithm 2 in our paper. However, the idea of proof and the choice of parameters are quite different.
2) The same as Algorithm 2, Algorithm 2 in (Asi et al., 2021b) is also inefficient and has poor performance in practice. To resolve the issue, we also develop two other algorithms (Algorithm 3 and 5).
3) For ( , δ)-DP model, (Asi et al., 2021b) only shows the worst-case lower bound of Ω(( √ d log(1/δ) n ) θ θ−1 ) under the assumption θ ≥ 1 + c for some constant c > 0 while in this paper we also extend the result to θ ≥ 2. Although the hard instance in (Asi et al., 2021b) is similar to ours, the proofs of lower bounds are different. 4) In this paper, we also provide experimental results on the problem which has not been studied in (Asi et al., 2021b). 5) Besides TNC population risk functions, in this paper we also provide faster rates of DP-SCO with strongly convex loss function with additional assumptions which also has not been studied in (Asi et al., 2021b).

Preliminaries
Definition 1 (Differential Privacy (Dwork et al., 2006)) Given a data universe X , we say that two datasets S, S ⊆ X are neighbors if they differ by only one entry, which is denoted as S ∼ S . A randomized algorithm A is ( , δ)-differentially private (DP) if for all neighboring datasets S, S and for all events E in the output space of A, the following holds Pr(A(S) ∈ E) ≤ e Pr(A(S ) ∈ E)+δ.
Definition 4 (DP-SCO (Bassily et al., 2014)) Given a dataset S = {x 1 , · · · , x n } from a data universe X where x i are i.i.d. samples from some unknown distribution D, a convex loss function f (·, ·), and a convex constraint set W ⊆ R d , Differentially Private Stochastic Convex Optimization (DP-SCO) is to find w priv so as to minimize the population risk, i.e., F (w) = E x∼D [f (w, x)] with the guarantee of being differentially private. The utility of the algorithm is measured by the (expected) excess population risk, that is E A [F (w priv )] − min w∈W F (w), where the expectation of A is taken over all the randomness of the algorithm. Besides the population risk, we can also measure the empirical risk of dataset S: Definition 7 A function F : W → R is λ-strongly convex over the domain W if, for all w, w ∈ W,F (w) + ∇F (w), w − w + λ 2 ||w − w|| 2 2 ≤ F (w ). Let w * = arg min w∈W F (w) be the minimizer, strongly convexity implies (Hazan and Kale, 2011): Previous work on DP-SCO only focused on case where the loss function is either convex or strongly convex (Bassily et al., 2019;Feldman et al., 2020). In this paper, we will mainly study the case where the population risk satisfies the Tysbakov Noise Condition (TNC) (Ramdas and Singh, 2012;Liu et al., 2018), which has been studied quite well and has been shown that it could achieve faster rates than the optimal one of general convex loss functions in the non-private case. Below we provide the definition of TNC.
Definition 8 For a convex function F (·), let W * = arg min w∈W F (w) denote the optimal set and for any w ∈ W, let w * = arg min u∈W * u − w 2 denote the projection of w onto the optimal set W * . Function F satisfies (θ, λ)-TNC for some θ > 1 and λ > 0 if for any w ∈ W the following inequality holds From the definition of TNC and (1) we can see that for a λ-strong convex function it is (2, λ 2 )-TNC. Moreover, if a function is (θ, λ)-TNC, then it is also (θ , λ)-TNC for any θ < θ . Throughout the whole paper we will assume that θ is a constant and thus we will omit the term of c θ in the Big-O notation if c is a constant.

Upper Bounds of Excess Population Risk
In this section, we will concentrate on the case where the population risk function is (θ, λ)-TNC and provide some upper bounds of its excess population risk. To provide a clear intuition of our methods, we will first assume that the loss functions are smooth. Later we will extend to the non-smooth case.
We first consider an easier case, where the TNC parameter θ satisfies θ ≥ 2. Our algorithm is based on the localization technique proposed by (Feldman et al., 2020), which provides an algorithm, namely Phased-SGD (Algorithm 1) for DP-SCO with general convex loss functions and shows that the algorithm could achieve the optimal rate of excess population risk. } and if η ≤ 1 β (i.e., n is sufficiently large), then Algorithm 1 will be ( , δ)-DP for all ≤ 2 log(1/δ).

The output satisfies
β , then Algorithm 1 will be -DP. Moreover, the output satisfies Algorithm 1: Phased-SGD(w 0 , η, n, W) algorithm (Feldman et al., 2020) Input: Dataset S = {x 1 , · · · , x n }, convex function f : W × X → R, initial point w 0 ∈ W, step size η (will be specified later), privacy parameter and (or) δ. Set k = log 2 n . Partite the whole dataset S into k subsets {S 1 , · · · , S k }. Denote n i as the number of samples in S i , i.e., |S i | = n i , where n i = 2 −i n .
We propose our adaptive stochastic approximation algorithm, which is presented in Algorithm 2. The updates are divided into m stages. At each stage, the Phased-SGD algorithm is applied with n 0 samples. Each employment of the Phased-SGD algorithm is warm-started by the initial point that is returned from the last stage.
with centerŵ k−1 and radius R k−1 . The Phased-SGD runs on the k-th subset S i . end returnŵ m The following theorem states that, the output of Algorithm 2 achieve an excess population risk for -DP and ( , δ)-DP, respectively, if the population risk function satisfies TNC with θ ≥ 2.
Theorem 11 Assume that F (·) satisfies (θ, λ)-TNC and f (·, x) is convex, β-smooth and L-Lipschitz for each x. Then Algorithm 2 is -DP or ( , δ)-DP based on different stepsizes {γ k } m k=1 and noises if γ k ≤ 1 β . Moreover, if n is sufficiently large such that n ≥ 256, for ( , δ)-DP we have In practice, the main difficulty on implementing Algorithm 2 is the projection onto the ball W ∩ B(ŵ k−1 , R k−1 ) in each iteration of the Phased-SGD in each phase. In practice, this could be solved by using the Dykstra's algorithm (Dykstra, 1983;Boyle and Dykstra, 1986), which studied the best approximation problem: given m closed and convex sets W 1 , · · · , W m ⊆ R d and a point y ∈ R d , we seek the point in W 1 · · · W m (assumed nonempty) closest to y, and solve min u∈W 1 ··· Wm u−y 2 . However, in theory, the theoretical guarantee of Theorem 11 may not be held if we use the Dykstra's algorithm under the privacy constraint. The main reason is that, Dykstra's algorithm can only provide an approximate solution of the projection step. However, the approximate solution may not have the same 2 (or 1 )-norm sensitivity as the exact solution. Thus, from this view, Algorithm 2 lacks of efficiency. Instead of using the Dykstra's algorithm, motivated by (Xu et al., Algorithm 3: Phased-SGD-SC(w 0 , γ, , δ) Input: Dataset S = {x 1 , · · · , x n }, convex function f : W × X → R, initial point w 0 ∈ W, privacy parameter and (or) δ. D is a constant satisfying D ≥ w 0 − w * 2 . Partite the data S into k disjoint subsets {S 1 , · · · , S k }, where k = log log n and for each i ∈ [k], |S i | = n i = 2 i−2 n/ log n . for t = 1, · · · , k do Let w t = Phased-SGD(w t−1 , η t , n t , W), where the Phased-SGD runs on the t-th subset S i with loss function f (w, , in the following, we present a new algorithm which only needs the projection onto W. Briefly speaking, instead of considering the original stochastic function, we focus on the problem with an additional strongly convex regularization, i.e., min w∈W F (w) + 1 2γ w − w 1 2 2 , where w 1 ∈ W is some reference point and γ is some parameter. Specifically, the same as in Algorithm 2, we first divide the whole algorithm into m stages. In each stage we hope to find a private estimator w k such that w k ≈ arg min w∈W F (w) + 1 2γ k w − w k−1 2 2 with γ k changing with k. Specifically, we use Algorithm 3 to get such private estimator. Note that due to the additional 2 regularization, now the function is strongly convex. Thus, instead of using the original Phased-SGD (Algorithm 1) for general convex loss, here we use a strongly convex version of Phased-SGD, which is adopted from (Feldman et al., 2020). Moreover, since now we have an additional 2 -norm regularization, here we do not need the projection onto the balls W ∩ B(ŵ k−1 , R k−1 ) during updates compared with Algorithm 2.
Theorem 12 Assume that F (·) satisfies (θ, λ)-TNC and f (·, x) is convex, β-smooth and L-Lipschitz for each x. If n is sufficiently large such thatθ ≥ 2 log log n log n , then Algorithm 4 is -DP or ( , δ)-DP Algorithm 4: Private Stochastic Approximation-II(w 0 , n, R 0 ) Input: Dataset S = {x 1 , · · · , x n }, convex function f : W × X → R, initial point w 0 ∈ W, privacy parameter and (or) δ. χ 0 is a constant such that . So far we have proposed two algorithms. However, there are still several issues: First, both of the previous methods need strong assumption on θ. Algorithm 4 needs θ to be known in advance while Algorithm 2 needs to assume θ ≥ 2. Thus, can we develop a method that only needs a weaker assumption on θ? Secondly, both of the previous two algorithms could achieve rates for -DP and ( , δ)-DP, respectively. Can we further improve these bounds? Thirdly, the two methods are either impractical or inefficient. Specifically, for Algorithm 4, as we can see from our theoretical analysis, we need to exactly set γ 0 )) in the ( , δ)-DP model, which is quite large and is difficult to get. And we can see that in Theorem 12 we can only guarantee there exists a w k that achieves the upper bound of error, it is still unknown how to find such w k privately with the same theoretical guarantees. For Algorithm 2, as we will see in the experiment part, it even does not outperform the previous Phased-SGD method (Algorithm 1), which means that its performance is quite poor. Thus, how to design improved methods both theoretically and practically? In the following we will focus on these three issues by developing a new method.
The idea of our algorithm is as the following: assuming that the value of θ is unknown, but θ is lower bounded by some known constantθ > 1, namely θ ≥θ > 1. We first divide the whole dataset into k = (logθ 2) · log log n disjoint subsets, where the i-th subset has n i = 2 i−1 n/(log n) logθ 2 samples; then we repeat the Algorithm 1 for k times where each phase runs on the i-th subset and is initialized at the output of the previous phase. See Algorithm 5 for details.
Remark 13 Although both Algorithm 5 and 2 partite the data into several parts and perform the Phased-SGD several times. There are several differences: First, the sizes of subsets in Algorithm Algorithm 5: Iterated Phased-SGD(w 1 , n, W,θ) end return w k 2 are equal, while we partite the data aggressively in Algorithm 5. Secondly, in each phase of Algorithm 5, the convex set to be projected is invariant while in Algorithm 2 we constantly replace it to W ∩ B(ŵ k−1 , R k−1 ), which is necessary based on our theoretical analysis.
Theorem 14 Assume that F (·) is (θ, λ)-TNC with θ ≥θ > 1 for some known constantθ, and f (·, x) is convex, β-smooth and L-Lipschitz for each x. If the sample size n is sufficiently large such thatθ ≥ 2 log log n (log n)−1 , then Algorithm 5 is either -DP or ( , δ)-DP for any ≤ 2 log(1/δ), based on different step sizes and noises under the assumption that η t ≤ 1 β . Moreover, for ( , δ)-DP, the output Remark 15 Compared with the previous results, we can see the upper bounds in Theorem 14 improve factors of Poly(log n) in both -DP and ( , δ)-DP models. Moreover, instead of θ ≥ 2, we only need the assumption of θ ≥θ for some knownθ > 1 in Theorem 14. And as we will see in the experimental part, Algorithm 5 outperforms all previous methods.
Remark 16 We can see that it is possible to get faster rates than the rates of strongly convex loss if θ < 2. For example, when θ = 3 2 , the upper bound of error becomes ) 3 ) in the ( , δ)-DP model. Moreover, when θ > 1, then the bounds will be always higher than the optimal rate for general convex loss as θ θ−1 > 1. When θ = 2, we have an excess population risk for -DP and ( , δ)-DP respectively, which matches the optimal rate of DP-SCO with strongly convex function (Feldman et al., 2020). Besides strongly convex functions, there are other problems that satisfy (2, λ)-TNC, such as the functions satisfying Weak Strong Convexity, Restricted Secant Inequality (RSI), Error Bound (EB) and Polyak-Lojasiewicz (PL) conditions (see Section 2.1 in (Karimi et al., 2016) for details). Thus, Theorem 14 with θ = 2 could be seen as a generalization of the strongly convex case. For Polyak-Lojasiewicz (PL) functions, (Wang et al., 2018b) shows an upper bound of O( d log(1/δ) n 2 2 ) for the empirical risk. However, their method cannot be extended to the population risk. In the following we provide some examples that satisfy TNC with θ = 2.
Lemma 17 (Quadratic Problem (Liu et al., 2018)) Consider the quadratic problem (1)) and W is a bounded polyhedron (e.g., 1 -norm or ∞ -norm ball), then the population risk function will be TNC with θ = 2 and the problem will satisfy the assumptions in Theorem 14.
By Lemma 17 we can see that for the linear regression problem where F (w) = E(x T w − y) 2 over a bounded polyhedron W. It is possible to achieve an upper bound of O( 1 n + d log(1/δ) n 2 2 ) and O( 1 n + d 2 n 2 2 ) for the excess population risk in the ( , δ)-DP and -DP model, respectively. Lemma 18 (SCO over 2 -norm ball (Liu et al., 2018)) Consider the problem of SCO over 2 -norm ball min is convex, smooth and Lipschitz, and min w∈R d F (w) < min w 2 ≤B F (w). Then the population risk is TNC with θ = 2 and satisfies the assumptions in Theorem 14.
So far, we provided several methods for TNC population risk functions under the assumption that the loss function is smooth. We can extend the previous methods to the non-smooth case, see Appendix A for details.

Lower Bounds of Excess Population Risk
In the previous section, we provide an algorithm whose output could achieve an excess population for -DP and ( , δ)-DP respectively. The question is, can we further improve these bounds? In this section, we show that for all θ ≥ 2, the θ θ−1 ) cannot be further improved. We consider the following loss function. Define Theorem 19 (Lower bound of ( , δ)-DP ) Let n, d ∈ N, θ ≥ 2, > 0 and δ = o( 1 n ) such that n ≥ Ω( √ d } d such that with probability at least 1 3 over the randomness of the algorithm, its output w priv satisfies where loss function is given by (3)  Theorem 20 (Lower bound of -DP ) Let n, d ∈ N, θ ≥ 2 and > 0 such that n ≥ Ω( √ d } d such that with probability at least 1 3 over the randomness of the algorithm, its output w priv satisfies where loss function is given by (3) which is O(1)-Lipschitz, and the population risk satisfies (θ, O(1))-TNC.
Remark 21 From the above theorems, we can see that for the case where θ = 2, the loss function in (3) is reduced to the squared loss, which was used to the lower bound proof of strongly convex loss in (Bassily et al., 2014).

Improved Rates for Strongly Convex Loss
In the previous section, we showed upper and lower bounds of the excess population risk for general TNC population risk functions. Moreover, from Theorem 26 we can see that we get asymptotically the same bound for smooth and non-smooth loss functions in the ( , δ)-DP model. However, in the non-private case, it has been shown that for the strongly convex loss functions, it is possible to get an improved rate compared with the non-smooth ones (Zhang and Zhou, 2019). Thus, our question is, can we get improved rates if the loss functions have additional properties? In the following we will study the strongly convex loss case. Specifically, we will show that when the loss function f (·, x) has additional assumptions on non-negativity and if the optimal value F (w * ) is sufficiently small, it is possible to achieve an upper bound of O( d log(1/δ) n 2 2 + 1 n τ ) for any τ > 1 if the sample size n is sufficiently large.
There are two parts in the algorithm. In the first part, we perform the original Iterated Phased-SGD (Algorithm 5) on the first half of the data to get a good solution to the optimal parameter w * . After that we perform a new method, namely Epoch-DP-SGD (Algorithm 6) on the second half of the data, which may also be used in other problems. We note that although Algorithm 6 and Algorithm 1 both perform the original DP-SGD algorithm in (Bassily et al., 2014) for several phases or epochs.
They are quite different: First, as the phase/epoch increases, we decrease the size of the subset (or the number of iterations) in Algorithm 1. While in Algorithm 6 we will increase the size of the subset (or the number of iterations). As we will see in the proof, this increase is necessary. Secondly, the initial size of the subset in Algorithm 1 is n 2 while it is 2 2τ +3 κ in Algorithm 6, where κ is the condition number κ = β/λ of the population risk functions.
For -DP, the output returned by algorithm 7 satisfies We note that recently (Wang et al., 2020b) also showed that when the loss function is non-negative and the optimal value of the population risk is small, it is possible to get a non-trivial upper bound for DP-SCO. However, there are some differences: Firstly, (Wang et al., 2020b) only studied the case of DP-SCO with heavy-tailed data while here we study DP-SCO with strongly convex functions. Thus, the problems are different. Moreover, their method is based on the sample-and-aggregate framework, which is impractical, and their result is O( d 3 F (w * ) n 4 ) under the assumption that ∇F (w * ) = 0, which may not hold in the case where W is a close set. Compared with their work, we do not need such strong assumption and in general our bound is much smaller than theirs for F (w * ) = O(1).
Remark 24 Theorem 23 implies that when n = Ω(κ τ ), the output of Algorithm 7 achieves excess population risks of O( d log(1/δ) n 2 2 + F (w * ) n + 1 n τ ) and O( d 2 n 2 2 + F (w * ) n + 1 n τ ) for ( , δ)-DP and -DP, respectively, which are faster than the optimal rates of O( 1 n + d log(1/δ) n 2 2 ) and O( d 2 n 2 2 + 1 n ) for general strongly convex loss functions, under the assumption that the optimal risk F (w * ) is relatively small. It is also notable that the bounds in Theorem 23 have exponential dependence on the parameter τ , which means τ also cannot be very large. Moreover, due to the large (hidden) constant in the upper bound, the practical performance of Theorem 23 is poor. We leave the problem of designing more practical algorithms for future research.

Conclusion
In this paper, we studied DP-SCO with special classes of population functions. In the first part of the paper, we study the case where the population function satisfies TNC with the parameter θ > 1. Specifically, we first provided several methods which could achieve upper bounds of for -DP and ( , δ)-DP, respectively. Then we showed that for any θ > 1, there is a population risk function satisfies TNC with θ such that for any -DP (( , δ)-DP) algorithm, the excess population risk of its output is lower bounded by Ω(( d n ) θ θ−1 ) and Ω(( for -DP and ( , δ)-DP, respectively. In the second part of the paper, we revisited DP-SCO with strongly convex loss functions. We claimed that when the loss function is non-negative and the optimal value of the population function is small enough, it is possible to achieve an upper bound of O( d log(1/δ) n 2 2 + 1 n τ ) and O( d 2 n 2 2 + 1 n τ ) for any τ > 1 in ( , δ)-DP and -DP model respectively if the sample size n is sufficiently large.
Besides the open problems we mentioned in the previous parts, there are other unsolved problems: 1) From the theoretical results in this paper, we can see there is still a gap of O( 1 n θ 2(θ−1) ) between upper bounds and lower bounds in both -DP and ( , δ)-DP models. Thus, the optimal rates of excess population risk is still unknown. 2) In this paper we provide faster rates of DP-SCO with special class of functions, especially for TNC population functions. However, besides TNC, there are other special classes of functions which have faster rates in the non-private case, such as exponential concave loss (Koren and Levy, 2015). It is still unknown whether we can get faster rates under the differential privacy constraint. We will leave these problems for future research.

Appendix A. Extension to Non-smooth Loss
In the previous section, we provided several methods for TNC population risk functions under the assumption that the loss function is smooth. However, we constantly meet the case where the loss is non-smooth. In this section, we will extend the previous methods to the non-smooth case. The observation is that, in both Algorithm 5 and Algorithm 2, we use the Phased-SGD (Algorithm 1) as a sub-routine for several phases. And we need the smoothness condition in Phased-SGD to get the upper bounds in Lemma 10. Thus, to extend to the non-smooth case, the most direct way is to change Phased-SGD to a non-smooth version in both Algorithm 5 and Algorithm 2. (Feldman et al., 2020) provided non-smooth version of Phased-SGD based on proximal mapping for ( , δ)-DP model, namely Phased-ERM, which is shown in Algorithm 8.
Algorithm 8: Phased-ERM(w 0 , η, n, W) algorithm (Feldman et al., 2020) Input: Dataset S = {x 1 , · · · , x n }, convex function f : W × X → R, initial point w 0 ∈ W, step size η (will be specified later), privacy parameters , δ. Set k = log 2 n . Partite the whole dataset into k subsets By using Algorithm 8 as subroutine in Algorithm 5 and 2 we have the following result, which is similar to Theorem 14 and 11.
Theorem 26 Assume that F (·) is (θ, λ)-TNC and f (·, x) is convex and L-Lipschitz for each x. For any 0 < , δ < 1, if we replace the Phased-SGD with Phased-ERM in Algorithm 5 and 2 (we also change the stepsizes), then the two algorithms are ( , δ)-DP. Moreover, in Algorithm 5, the output satisfies If n is sufficiently large such that n ≥ 256, in Algorithm 2, the output satisfies In the following we provide some examples that satisfy TNC with θ = 2 and with non-smooth loss.
Lemma 27 (Hinge Loss (Xu et al., 2017)) Consider the SVM problem with hinge loss where W is an 1 -norm or ∞ -norm ball and | w, x | ≤ 1 for all x and w ∈ W. Then F (·) satisfies TNC with θ = 2.

Appendix B. Experiments
In this section, we provide some experimental studies to compare the effectiveness of the proposed methods for population risk functions satisfying TNC.

Experimental Settings and Baseline Methods
For the problems satisfying TNC, we first consider the population risk with squared loss, which is mentioned in Lemma 17, min As we mentioned in the previous section, this problem satisfies TNC with parameter θ = 2. For this problem, we use Phased-SGD (Algorithm 1) as our baseline method, which could be seen as the state-of-the-art method (Feldman et al., 2020). We will use PSA (Algorithm 2) and iterated SGD (Algorithm 5) withθ = 1.5 and 2 for comparisons. Note that here we will not compare with Algorithm 4. As we can see that, theoretically it involves quite large constants which impedes the algorithm to be practical. Moreover, since strongly convex functions satisfy (2, λ)-TNC, we also perform our methods on strongly convex function. Here we will use Phased-SGD-SC (Algorithm 3) (Feldman et al., 2020), which is known to have the optimal rate of error, as the baseline method. For this case, we will consider the population risk function with squared logistic loss and an additional l 2 -norm regularization: which is λ-strongly convex and satisfies (2, λ)-TNC. We set the parameter λ = 0.001. For the compared methods, as we could see from Figure 1 and 3, the performance of PSA (Algorithm 2) is quite poor. Moreover, we find that the error of Faster-DPSGD-SC (Algorithm 7) is also quite large. Thus, to have a better comparison with Phased-SGD-SC, here we will not show the results of PSA and Faster-DPSGD-SC for the regularized logistic regression problem.

Dataset and Parameter Settings
We will implement our methods on four real-world datasets from the libsvm website 3 , namely a8a, a9a, ijcnn1 and w7a. For ijcnn1 dataset, although the training set and test set are explicitly provided, the training set is relatively small while test set is relatively too large. Thus, we randomly select 8 × 10 4 samples in the test data and combine them to the training data, i.e., we will leave 11,701 samples for testing while 115,000 samples for training.
Since it is difficult to get the exact value of the population risk function, here we will use the testing error to approximate it, which is the value of the empirical risk on test data. In the experimental part, we study the above mentioned two TNC problems (5), (6) and their corresponding testing errors with various sample sizes and privacy budgets . When performing the results for different sample sizes, we will fix 2 √ log(1/δ) = 2. When performing the results for different privacy budgets , we will use n = 10 4 samples. We will set δ = 1 n 1.1 for all experiments. Note that all the algorithms presented in the experiments are conducted for 20 random runs and we take the their averaged testing error over the 20 runs.  Figure 2 and 4 are for the 2 -norm regularized squared logistic regression. As we can see the from these results: 1) The previous method Phased-SGD outperforms our first method PSA in all the cases, which contradicts to our previous theoretical results. We conjecture that this may be due to that we use the Dykstra's algorithm in PSA to get an approximate solution of the projection step, which may destroy our theoretical guarantees, another reason may be that the sample size is still not large enough, as we can see when the sample size gets larger the two methods get closer. 2) We can see that, unlike PSA, our third method, Iterated SGD, outperforms Phased-SGD in all the experiments. Moreover, either the sample size or the privacy parameter gets larger, the testing error of Iterated SGD decreases faster, which supports our previous theoretical analysis. 3) From Iterated SGD withθ = 2 andθ = 1.5 we can see that the method is quite flexible. This is due to that we showed that Theorem 14 will hold as long as θ ≥θ > 1. However, we note that the performance could still be different forθ = 1.5 andθ = 2, and we find thatθ = 1.5 is better thanθ = 2. We conjecture it is because the hidden constant in the upper bound of Theorem 14 in the case ofθ = 1.5 is relatively smaller than the case ofθ = 2.

Appendix C. Omitted Proofs
Proof [Proof of Theorem 11] For convenience here we only show the proof of ( , δ)-DP. The proof of -DP is almost the same by replacing the term ( 1 The guarantee of ( , δ)-DP is just followed by Lemma 10 and the parallel theorem of Differential Privacy. In the following we will focus on the utility.
where the third inequality is given by throwing away the √ d log(1/δ) · n m term and substituting m in term 1 √ n m with 1 2 log 2 2n log 2 n − 2. Below, we consider the following two cases.
Assume (8) is true for some k > 1, then we have Which is (9). By the definition of TNC, we have Thus (8) is true for k + 1. Now we prove (10). Referring to Lemma 10, we know that Here completes the proof of the lemma.
Now we proceed to prove theorem 11 in this case.
Case 2 If λ < µ 0 , then By a similar argument process as in Case 1, we have Combining the two cases, we conclude that Theorem 12] Before our proof, we provide some notations. We denote F * = min w∈W F (w). For a given error ρ, we denote L ρ the ρ-level set of function F (W ) and S ρ the ρ-sublevel set F (w), respectively, i.e., L ρ = {w ∈ W : F (w) = F * + ρ}, S ρ = {w ∈ W : F (w) ≤ F * + ρ}. For any w ∈ W, we denote w + ρ as the closet point in the ρ-sublevel set to w, i.e., Using the KKT condition, it is easy to check that when w ∈ S ρ then w + ρ ∈ L ρ . We first recall the following lemma, given by (Yang and Lin, 2018).
Lemma 30 (Lemma 1 in (Yang and Lin, 2018)) For any w ∈ W and ρ > 0 we have where W * = {w : w ∈ arg min w∈W F (w)} and dist(w + ρ , W * ) is the distance from the point w + ρ to the set W * .
Lemma 31 If f (·, x) is convex, β-smooth and L-Lipschitz for each x and γ ≥ W 2 L , where W 2 is the diameter of the set W, i.e., W 2 = max w,w ∈W w − w 2 . Based on different noises and stepsizes in Algorithm 3, Algorithm 3 is ( , δ) or -DP if η ≤ 1 β . Given w 0 ∈ W, for the output w k in Algorithm 3. In the case of ( , δ)-DP, we have In the case of -DP, we have whereF (w) = F (w) + 1 2γ ||w − w 0 || 2 2 and w 0 is the initial point.
Next we start our proof. For convenience here we only focus on ( , δ)-DP, the proof of -DP is almost the same. The guarantee of ( , δ)-DP is simply followed by Lemma 31. We also note that Lemma 31 implies that for any w ∈ W, We assume that for all Otherwise we have proved the theorem.
We will show by induction that If this is true then when w = m we have . In the following we will show (17). For k = 0, by the definition of χ, it is true. Now, consider the k-th phase. By (15) we have Thus, where the last equality is due to (16).
For term B, we have where the first equality is due to (16). Thus, in total we have Proof [Proof of Theorem 14] In the following we only consider the ( , δ)-DP case. It is almost the same for -DP. The guarantee of ( , δ)-DP is just followed by Lemma 10 and the parallel theorem of Differential Privacy. In the following we will focus on the utility.
Since k = (logθ 2) · log log n , then k ≤ (logθ 2) · log log n, namely 2 k ≤ (log n) logθ 2 and 2 k −1 (log n) logθ 2 ≤ 1. Observe that the total sample number used in the algorithm is when we take expectations at both sides, namely Thus, we have where the first inequality comes from Lemma 10 and the second inequality uses (18). Denote Then (19) can be simplified as Notice that n i /n i−1 = 2, then E i−1 E i ≤ ( n i n i−1 ) θ = 2 θ , namely: Then we can rearrange the above inequality as where the first inequality uses (20) and the second inequality applies (21).
Thus we have θ θ−1 log n − log c 1 ≤ θ k−1 log C 1 , which is equivalent to our object n θ θ−1 As a result, we hold a solution with error: where we use the fact that n k = 2 k−1 (log n) logθ 2 ≥ 1 2 n and (a + b) 2 ≤ 2(a 2 + b 2 ).
Remark 32 To perform valid Phased SGD (Subroutine of Iterated Phased-SGD) for k times, it should satisfy n i = 2 i−1 n (log n) logθ 2 ≥ 2 for any i ∈ [k]. Otherwise, the Phased SGD cannot function properly to get the bound in Lemma 10. As a result, n should be sufficiently large such that θ ≥ 2 log log n (log n)−1 .

Proof [Proof of Theorem 19]
Based on the fact that a lower bound on excess empirical risk implies nearly the same lower bound on the excess population risk (Bassily et al., 2019), here we consider the empirical risk, then we can use the boosting technique to the population loss. See (Bassily et al., 2019) for details.
For any dataset S = {x 1 , · · · , x n } with data point drawn from √ d } d , and any w ∈ W, we define the empirical risk function as the following, In the following, we first show that there is a point w * satisfying ||w * || 2 ≤ 1, s.t. ∇F (w * ; S) = 0.
If (24) holds, then Recall the following lemma. such that for every ( , δ)- For the sake of contradiction, we consider such S described in the above lemma, with probability more than 2 3 , (24) holds. Let A be an ( , δ)-differentially private algorithm that first runs A on the data and then outputs ||Z|| θ−2 θ−1 2 w priv , and let n be sufficiently large that n ≥ √ By the boosting technique in (Bassily et al., 2019), we have with probability at least 1 3 , Proof [Proof of Theorem 20] The proof of Theorem 20 is almost the same as the proof of Theorem 19. Instead of using Lemma 33 we use the following lemma: Lemma 34 (Lemma 5.1 in (Bassily et al., 2014)) Let n, d ∈ N, > 0 such that n ≥ Ω( d ). There is a number M = Ω min n, d such that for every ( , δ)-differentially private algorithm A, there is a dataset S = {x 1 , · · · , x n } ⊆ x i || 2 = Ω min 1, d n .
Proof [Proof of Theorem 22] For simplicity, here we only focus on ( , δ)-DP. It is almost the same for -DP.
In the first step we perform Algorithm 1, which is ( , δ)-DP. Thus, it is sufficient to show that Algorithm 6 is also ( , δ)-DP, i.e., each epoch is ( , δ)-DP. To prove this, we first revoke the stability of One -Pass Projected SGD for strongly convex loss functions, which is given by (Hardt et al., 2015).
Lemma 35 [Theorem 3.9 in (Hardt et al., 2015)] Assume the loss function f (·, x) is λ-strongly convex and β-smooth with respect to w ∈ W for all x. Let S i and S i be two samples of size n i differing in only a single element. Denote w t i and w t i as the outputs of the projected stochastic gradient method (4) on datasets S i and S i respectively, then if η ≤ 1 β we have Recall that in each epoch we perform projected gradient descent for n i steps using n i samples, according to Lemma 35, we can bound the sensitivity of w t i for each t and we have ||w t i − w t i || ≤ 2L 2 λn i for all t, where w t i and w t i correspond to the solution of two neighboring dataset S i and S i that differs in one sample.
Thus, the sensitivity of w i = 1 n i n i t=1 w t i is also 2L 2 λn i . By the Gaussian mechanism, adding Gaussian noise with σ i = 8L 2 √ log(1/δ) n i λ will preserve ( , δ)-DP.
Proof [Proof of Theorem 23] For convenience here we only focus on ( , δ)-DP, the proof is almost the same as for -DP.
Lemma 36 (Lemma 1 in (Zhang and Zhou, 2019)) Assume f (·, x) is non-negative and β-smooth for all x and F (·) is convex. Apply n i iterations of (4), i.e., w t+1 i = W (w t i − η i ∇ w f (w t i , x t i )) with η i < 1/(2β). Then for any w ∈ W, we have Since f (·, x) is β-smooth for all x, we have Take expectations on both sides w.r.t the data and ξ i we get Combining with Lemma 36, we have Based on the above result, we establish the following result of excess population risk of each epoch in Epoch-DP-SGD (Algorithm 6).
Thus the lemma holds for e + 1 which completes the proof. Now we go back to our proof. The number of epochs made is given by the largest e which satisfies e i=1 n i ≤ n 2 , i.e., e i=1 n i = n 1 (1 + 2 + · · · + 2 e−1 ) = n 1 (2 e − 1) ≤ n 2 which means the largest value is E = log 2 ( n 2n 1 + 1) and the final solution is w = w E .