Distributed Self-Paced Learning in Alternating Direction Method of Multipliers

1 Introduction

Inspired by the learning processes used by humans and animals [Bengio et al., 2009], Self-Paced Learning (SPL) [Kumar et al., 2010] considers training data in a meaningful order, from easy to hard, to facilitate the learning process. Unlike standard curriculum learning [Bengio et al., 2009], which learns the data in a predefined curriculum design based on prior knowledge, SPL learns the training data in an order that is dynamically determined by feedback from the individual learner, which means it can be more extensively utilized in practice. In self-paced learning, given a set of training samples along with their labels, a parameter λ is used to represents the "age" of the SPL in order to control the learning pace. When λ is small, "easy" samples with small losses are considered. As λ grows, "harder" samples with larger losses are gradually added to the training set. This type of learning process is modeled on the way human education and cognition functions. For instance, students will start by learning easier concepts (e.g., Linear Equations) before moving on to more complex ones (e.g., Differential Equations) in the mathematics curriculum. Self-paced learning can also be finely explained in a robust learning manner, where uncorrupted data samples are likely to be used for training earlier in the process than corrupted data.

In recent years, self-paced learning [Kumar et al., 2010] has received widespread attention for various applications in machine learning, such as image classification [Jiang et al., 2015], event detection [Jiang et al., 2014a; Zhang et al., 2017c] and object tracking [Supancic and Ramanan, 2013; Zhang et al., 2016]. A wide assortment of SPL-based methods [Pi et al., 2016; Ma et al., 2017a] have been developed, including self-paced curriculum learning [Jiang et al., 2015], self-paced learning with diversity [Jiang et al., 2014b], multi-view [Xu et al., 2015] and multi-task [Li et al., 2017; Keerthiram Murugesan, 2017] self-paced learning. In addition, several researchers have conducted theoretical analyses of self-paced learning. [Meng et al., 2015] provides a theoretical analysis of the robustness of SPL, revealing that the implicit objective function of SPL has a similar configuration to a non-convex regularized penalty. Such regularization restricts the contributions of noisy examples to the objective, and thus enhances the learning robustness. [Ma et al., 2017b] proved that the learning process of SPL always converges to critical points of its implicit objective under mild conditions, while [Fan et al., 2017] studied a group of new regularizers, named self-paced implicit regularizers that are derived from convex conjugacy.

Existing self-paced learning approaches typically focus on modeling the entire dataset at once; however, this may introduce a bottleneck in terms of memory and computation, as today's fast-growing datasets are becoming too large to be handled integrally. For those seeking to address this issue, the main challenges can be summarized as follows: 1) Computational infeasibility of handling the entire dataset at once. Traditional self-paced learning approaches gradually grow the training set according to their learning pace. However, this strategy fails when the training set grows too large to be handled due to the limited capacity of the physical machines. Therefore, a scalable algorithm is required to extend the existing self-paced learning algorithm for massive datasets. 2) Existence of heterogeneously distributed "easy" data. Due to the unpredictability of data distributions, the "easy" data samples can be arbitrarily distributed across the whole dataset. Considering the entire dataset as a combination of multiple batches, some batches may contain large amount of "hard" samples. Thus, simply applying self-paced learning to each batch and averaging across the trained models is not an ideal approach, as some models will only focus on the "hard" samples and thus degrade the overall performance. 3) Dependency decoupling across different data batches. In self-paced learning, the instance weights depend on the model trained on the entire dataset. Also, the trained model depends on the weights assigned to each data instance. If we consider each data batch independently, a model trained in a "hard" batch can mistakenly mark some "hard" samples as "easy" ones. For example, in robust learning, the corrupted data samples are typically considered as "hard" samples, then more corrupted samples will therefore tend to be involved into the training process when we train data batches independently.

In order to simultaneously address all these technical challenges, this paper presents a novel Distributed Self-Paced Learning (DSPL) algorithm. The main contributions of this paper can be summarized as follows: 1) We reformulate the self-paced problem into a distributed setting. Specifically, an auxiliary variable is introduced to decouple the dependency of the model parameters for each data batch. 2) A distributed self-paced learning algorithm based on consensus ADMM is proposed to solve the SPL problem in a distributed setting. The algorithm optimizes the model parameters for each batch in parallel and consolidates their values in each iteration. 3) A theoretical analysis is provided for the convergence of our proposed DSPL algorithm. The proof shows that our new algorithm will converge under mild assumptions, e.g., the loss function can be non-convex. 4) Extensive experiments have been conducted utilizing both synthetic and real-world data based on a robust regression task. The results demonstrate that the proposed approaches consistently outperform existing methods for multiple data settings. To the best of our knowledge, this is the first work to extend self-paced learning to a distributed setting, making it possible to handle largescale datasets.

The reminder of this paper is organized as follows. Section 2 gives a formal problem formulation. The proposed distributed self-paced learning algorithm is presented in Section 3 and Section 4 presents a theoretical analysis of the convergence of the proposed method. In Section 5, the experimental results are analyzed and the paper concludes with a summary of our work in Section 6.

2 ProblemFormulation

In the context of distributed self-paced learning, we consider the samples to be provided in a sequence of mini batches as {(X(1) , y(1) ), . . . , (X(m) , y(m) )}, where X(i) ∈ Rp×ni represents the sample data for the ith batch, y(i) is the corresponding response vector, and ni is the instance number of the ith batch.

The goal of self-paced learning problem is to infer the model parameter w ∈ Rp for the entire dataset, which can be formally defined as follows:

where ‖w‖22 is the regularization term for model parameters w. Variable vi represents the instance weight vector for the ith batch and vij is the weight of the j th instance in the ith batch. The objective function fi(w, vi) for each mini-batch is defined as follows:

We denote xij ∈ Rp and yij ∈ R as the feature vector and its corresponding label for the j th instance in the ith batch. The loss function L is used to measure the error between label yij and the estimated value from model g. The term -λ ∑ni j=1 vij is the regularization term for instance weights vi, where parameter λ controls the learning pace. The notations used in this paper are summarized in Table 1.

The problem defined above is very challenging in the following three aspects. First, data instances for all m batches can be too large to be handled simultaneously in their entirety, thus requiring the use of a scalable algorithm for large datasets. Second, the instance weight variable vi of each batch depends on the optimization result for w shared by all the data, which means all the batches are inter-dependent and it is thus not feasible to run them in parallel. Third, the objective function of variables wi and vi are jointly non-convex and it is an NP-hard problem to retrieve the global optimal solution [Gorski et al., 2007]. In next section, we present a distributed self-paced learning algorithm based on consensus ADMM to address all these challenges.

3 The ProposedMethodology

In this section, we propose a distributed self-paced learning algorithm based on the alternating direction method of multipliers (ADMM) to solve the problem defined in Section 2.

The problem defined in Equation (1) cannot be solved in parallel because the model parameter w is shared in each batch and the result of w will impact on the instance weight variable vi for each batch. In order to decouple the relationships among all the batches, we introduce different model parameters wi for each batch and use an auxiliary variable z to ensure the uniformity of all the model parameters. The problem can now be reformulated as follows:

where the function fi(wi, vi) is defined as follows.

Unlike the original problem defined in Equation (1), here each batch has its own model parameter wi and the constraint wi - z = 0 for ∀i = 1, . . . ,m ensures the model parameter wi has the same value as the auxiliary variable z. The purpose of the problem reformulation is to optimize the model parameters wi in parallel for each batch. It is important to note that the reformulation is tight because our new problem is equivalent to the original problem when the constraint is strictly satisfied.

In the new problem, Equation (3) is a bi-convex optimization problem over vi and wi for each batch with fixed z, which can be efficiently solved using the Alternate Convex Search (ACS) method [Gorski et al., 2007]. With the variable v fixed, the remaining variables {wi}, z and α can be solved by consensus ADMM [Boyd et al., 2011]. As the problem is an NP-hard problem, in which the global optimum requires polynomial time complexity, we propose an alternating algorithm DSPL based on ADMM to handle the problem efficiently.

The augmented Lagrangian format of optimization in Equation (3) can be represented as follows:

where {αi}mi=1 are the Lagrangian multipliers and ρ is the step size of the dual step.

The process used to update model parameter wi for the ith batch with the other variables fixed is as follows:

Specifically, if we choose the loss function L to be a squared loss and model g(w, xij) to be a linear regression g(w, xij) = wT xij, we have the following analytical solution for wi:

The auxiliary variable z and Lagrangian multipliers αi can be updated as follows:

The stop condition of consensus ADMM is determined by the (squared) norm of the primal and dual residuals of the kth iteration, which are calculated as follows:

After the weight parameter wi for each batch has been updated, the instance weight vector vi for each batch will be updated based on the fixed wi by solving the following problem:

For the above problem in Equation (10), we always obtain the following closed-form solution:

where ∞(·) is the indicator function whose value equals to one when the condition L(yij, g(wt+1 i , xij)) < λ is satisfied; otherwise, its value is zero.

The details of algorithm DSPL are presented in Algorithm 1. In Lines 1-2, the variables and parameters are initialized. With the variables vi fixed, the other variables are optimized in Lines 5-13 based on the result of consensus ADMM, in which both the model weights wi and Lagrangian multipliers αi can be updated in parallel for each batch. Note that if no closed-form can be found for Equation (6), the updating of wi is the most time-consuming operation in the algorithm. Therefore, updating wi in parallel can significantly improve the efficiency of the algorithm. The variable vi for each batch is updated in Line 14, with the variable wi fixed. In Lines 1518, the parameter λ is enlarged to include more data instances into the training set. τλ is the maximum threshold for λ and µ is the step size. The algorithm will be stopped when the Lagrangian is converged in Line 20. The following two alternative methods can be applied to improve the efficiency of the algorithm: 1) dynamically update the penalty parameter ρ after Line 11. When r > 10s, we can update ρ ← 2ρ. When 10r < s, we have ρ ← ρ/2. 2) Move the update of variable vi into the consensus ADMM step after Line 9. This ensures that the instance weights are updated every time the model is updated, so that the algorithm quickly converges. However, no theoretical convergence guarantee can be made for the two solutions, although in practice they do always converge.

Algorithm 1: DSPL ALGORITHM

Input: X ∈ Rp×n , y ∈ Rn , λ0 ∈ R, τλ ∈ R, µ ∈ R Output: solution w(t+1) , v(t+1) 1 Initialize w0 i = 1, v0 i = 1 2 Choose εL > 0, εr > 0, εs > 0, λ ← λ0, t ← 0 3 repeat 4 k ← 0 5 repeat 6 zk+1 ← 1m ∑mi=1 (wk+1 i + 1ρ αki ) 7 Update variables wk+1 i in parallel, for ∀i = 1 . . .m 8 wk+1 i ← argminfi(wi, vi)+ 9 [αki ]T (wi - zk ) + ρ2 ‖wi - zk ‖22 10 Update dual αk+1 i ←αki +ρ(wk+1 i -zk+1 ) in parallel 11 Update primal and dual residuals rk+1 and sk+1 . 12 k ← k + 1 13 until ‖rk+1 ‖22 < εr and ‖sk+1 ‖22 < εs 14 vt+1 i ←∞(L(yij, g(wt+1 i , xij)) < λ), for ∀i = 1 . . .m 15 if λ < τλ then 16 λ ← λ ∗ µ 17 else 18 λ ← τλ 19 t ← t + 1 20 until ‖Lt+1 -Lt ‖2 < εL 21 return zt+1 , vt+1

4 Theoretical Analysis

In this section, we will prove the convergence of the proposed algorithm. Before we start to prove the convergence of Algorithm 1, we make the following assumptions regarding our objective function and penalty parameter ρ:

Assumption 1 (Gradient Lipchitz Continuity). There exists a positive constant ϕi for objective function fi(wi) of each batch with the following properties:

Assumption 2 (Lower Bound). The objective function in problem (3) has a lower bound B as follows:

Assumption 3 (Penalty Parameter Constraints). For ∀i = 1 . . .m, the penalty parameter ρi for each batch is chosen in accord with the following constraints:

• For ∀i, the subproblem (6) of variable wi is strongly convex with modulus γi(ρi).
• For ∀i, we have ρiγi(ρi) > 2ϕ2i and ρi ≥ ϕi.

Note that when ρi increases, subproblem (6) will be eventually become strongly convex with respect to variable wi. For simplicity, we will choose the same penalty parameter ρ for all the batches with ρ = maxi(ρi). Based on these assumptions, we can draw the following conclusions.

Lemma 1. Assume the augmented Lagrangian format of optimization problem (3) satisfies Assumption 1, the augmented Lagrangian L has the following property:

Proof. Since the the objective function fi(wi) for each batch is gradient Lipchitz continuous with a positive constant ϕi, the Lagrangian in Equation (5) has the following property according to Lemma 2.2 in [Hong et al., 2016]:

where γ = mρ > 0. The inequality (a) follows from Assumption 2, namely that ργi(ρ) > 2ϕ2i , so we have ( ϕ2i ρ - γi(ρ) 2 ) < 0.

Lemma 2. Assume the augmented Lagrangian of problem (3) satisfies Assumptions 1-3, the augmented Lagrangian L is lower bounded as follows:

where B is the lower bound of the objective function in problem (3).

The proof details of 2 can be found in the paper's extended version 1 .

Theorem 3. The Algorithm 1 converges when Assumptions 1-3 are all satisfied.

Proof. In Lemmas 1 and 2, we proved that the Lagrangian is monotonically decreasing and has a lower bound during the iterations of ADMM. Now we will prove that the same properties hold for the entire algorithm after updating variable v and parameter λ.

Inequality (a) follows Lemma 1 and inequality (b) follows the optimization step in Line 14 in Algorithm 1. Inequality (c) follows from the fact that λ increases monotonically so that λt ≤ λt+1 . As L({wt+1 }, zt+1 ,αt+1 ) for some constant values of v and λ has a lower bound B, we can easily prove that L({wt+1 }, vt+1 , zt+1 , αt+1 ; λt+1 ) ≥ B + C - τλn, where C is a constant and n is the size of the entire dataset. Therefore, the Lagrangian L is convergent. According to the stop condition for Algorithm 1, the algorithm converges when the Lagrangian L is converged.

1 https://xuczhang.github.io/papers/ijcai18 dspl extend.pdf

5 Experimental Results

In this section, the performance of the proposed algorithm DSPL is evaluated for both synthetic and real-world datasets in robust regression task. After the experimental setup has been introduced in Section 5.1, we present the results for the regression coefficient recovery performance with different settings using synthetic data in Section 5.2. Due to the space limitation, the real-world data evaluation based on house rental price prediction is presented in the extended version 2 . All the experiments were performed on a 64bit machine with an Intel(R) Core(TM) quad-core processor (i7CPU@3.6GHz) and 32.0GB memory. Details of both the source code and the datasets used in the experiment can be downloaded here 3 .

5.1 Experimental Setup

Datasets and Labels

The datasets used for the experimental verification were composed of synthetic and real-world data. The simulation samples were randomly generated according to the model y(i) = [X(i) ]T w∗ + u(i) + ε(i) for each mini-batch, where w∗ represents the ground truth coefficients and u(i) the adversarial corruption vector. ε(i) represents the additive dense noise for the ith batch, where ε(i) j ∼ N(0, σ2 ). We sampled the regression coefficients w∗ ∈ Rp as a random unit norm vector. The covariance data X(i) for each mini-batch was drawn independently and identically distributed from xi ∼ N(0, Ip) and the uncorrupted response variables were generated as y(i) ∗ = [X(i) ]T w∗ + ε(i) . The corrupted response vector for each mini-batch was generated as y(i) = y(i) ∗ + u(i) , where the corruption vector u(i) was sampled from the uniform distribution [-5‖y(i) ∗ ‖∞, 5‖y(i) ∗ ‖∞]. The set of uncorrupted points was selected as a uniformly random subset of [ni] for each batch.

The real-world datasets utilized consisted of house rental transaction data from two cities, New York City and Los Angeles listed on the Airbnb 4 website from January 2015 to October 2016. These datasets can be publicly downloaded 5 . For the New York City dataset, the first 321,530 data samples from January 2015 to December 2015 were used as the training data and the remaining 329,187 samples from January to October 2016 as the test data. For the Los Angeles dataset, the first 106,438 samples from May 2015 to May 2016 were used as training data, and the remaining 103,711 samples as test data. In each dataset, there were 21 features after data preprocessing, including the number of beds and bathrooms, location, and average price in the area.

Evaluation Metrics

For the synthetic data, we measured the performance of the regression coefficient recovery using the averaged L2 error e = ‖ ˆw - w∗‖2 , where ˆw represents the recovered coefficients for each method and w∗ represents the ground truth regression coefficients. For the real-world dataset, we used the mean absolute error (MAE) to evaluate the performance for rental price prediction. Defining ˆ y and y as the predicted price and ground truth price, respectively, the mean absolute error between ˆ y and y can be presented as MAE(ˆ y, y) = 1n ∑ni=1 ∣∣ ˆ yi -yi ∣∣, where yi represents the label of the ith data sample.

2 https://xuczhang.github.io/papers/ijcai18 dspl extend.pdf

3 https://goo.gl/cis7tK

4 https://www.airbnb.com/

5 http://insideairbnb.com/get-the-data.html

Comparison Methods

We used the following methods to compare the performance of the robust regression task: Torrent (Abbr. TORR) [Bhatia et al., 2015], which is a hard-thresholding based method that includes a parameter for the corruption ratio. As this parameter is hard to estimate in practice, we opted to use a variant, TORR25, which represents a corruption parameter that is uniformly distributed across a range of ±25% off the true value. We also used RLHH [Zhang et al., 2017b] for the comparison, which applies a recently proposed robust regression method based on heuristic hard thresholding with no additional parameters. This method computes the regression coefficients for each batch, and averages them all. The DRLR [Zhang et al., 2017a] algorithm, which is a distributed robust learning method specifically designed to handle large scale data with a distributed robust consolidation. The traditional self-paced learning algorithm (SPL) [Kumar et al., 2010] with the parameter λ = 1 and the step size µ = 1.1 was also compared in our experiment. For DSPL, we used the same settings as for SPL with the initial λ0 = 0.1 and τλ = 1. All the results from each of these comparison methods were averaged over 10 runs.

5.2 Robust Regression in Synthetic Data Recovery Coefficients Recovery

Figure 1 shows the coefficient recovery performance for different corruption ratios in uniform distribution. Specifically, Figures 1(a) and 1(b) show the results for a different number of features with a fixed data size. Looking at the results, we can conclude: 1) Of the six methods tested, the DSPL method outperformed all the competing methods, including TORR, whose corruption ratio parameter uses the ground truth value. 2) Although DRLR turned in a competitive performance when the data corruption level was low. However, when the corruption ratio rose to over 40%, the recovery error is increased dramatically. 3) The TORR method is highly dependent on the corruption ratio parameter. When the parameter is 25% different from the ground truth, the error for TORR25 was over 50% compared to TORR, which uses the ground truth corruption ratio. 4) When the feature number is increased, the average error for the SPL algorithm increased by a factor of four. However, the results obtained for the DSPL algorithm varied consistently with the corruption ratio and feature number. The results presented in Figures 1(a) and 1(c) conform that the DSPL method consistently outperformed the other methods for larger datasets, while still achieving a close recovery of the ground truth coefficient.

Performance on Different Corrupted Batches

The regression coefficient recovery performance for different numbers of corrupted batches is shown in Table 2, ranging from four to nine corrupted batches out of the total of 10 batches. Each corrupted batch used in the experiment contains 90% corrupted samples and each uncorrupted batch has 10% corrupted samples. The results are shown for the averaged L2 error in 10 different synthetic datasets with randomly ordered batches. Looking at the results shown in Table 2, we can conclude: 1) When the ratio of corrupted batches exceeds 50%, DSPL outperforms all the competing methods with a consistent recovery error. 2) DRLR performs the best when the mini-batch is 40% corrupted, although its recovery error increases dramatically when the number of corrupted batch increases. 3) SPL turns in a competitive performance for different levels of corrupted batches, but its error almost doubles when the number of corrupted batches increases from four to nine.

Analysis of Parameter λ

Figure 2 show the relationship between the parameter λ and the coefficient recovery error, along with the corresponding Lagrangian L. This result is based on the robust coefficient recovery task for a 90% data corruption setting. Examining the blue line, as the parameter λ increases, the recovery error continues to decrease until it reaches a critical point, after which it increases. These results indicate that the training process will keep improving the model until the parameter λ becomes so large that some corrupted samples become incorporated into the training data. In the case shown here, the critical point is around 1.0. The red line shows the value of the Lagrangian L in terms of different values of the parameter λ, leading us to conclude that: 1) the Lagrangian monotonically decreases as λ increases. 2) The Lagrangian decreases much faster once λ reaches a critical point, following the same pattern as the recovery error shown in blue line.

6 Conclusion

In this paper, a distributed self-paced learning algorithm (DSPL) is proposed to extend the traditional SPL algorithm to its distributed version for large scale datasets. To achieve this, we reformulated the original SPL problem into a distributed setting and optimized the problem of treating different mini-batches in parallel based on consensus ADMM. We also proved that our algorithm can be convergent under mild assumptions. Extensive experiments on both synthetic data and real-world rental price data demonstrated that the proposed algorithms are very effective, outperforming the other comparable methods over a range of different data settings.