{"id":424,"date":"2018-04-26T07:11:10","date_gmt":"2018-04-26T07:11:10","guid":{"rendered":"http:\/\/wordpress.cs.vt.edu\/optml\/?p=424"},"modified":"2018-04-26T07:11:10","modified_gmt":"2018-04-26T07:11:10","slug":"federated-optimization-distributed-machine-learning-for-on-device-intelligence","status":"publish","type":"post","link":"https:\/\/wordpress.cs.vt.edu\/optml\/2018\/04\/26\/federated-optimization-distributed-machine-learning-for-on-device-intelligence\/","title":{"rendered":"Federated Optimization: Distributed Machine Learning for On-Device Intelligence"},"content":{"rendered":"

Introduction<\/strong><\/p>\n

Standard machine learning approaches require centralizing the training data on one machine or in a datacenter. This work\u00a0introduces\u00a0an additional approach: Federated Learning, which\u00a0leaves the training data distributed on the mobile devices, and learns a shared model by aggregating locally computed updates via\u00a0a central coordinating server.<\/p>\n

State-of-the-art optimization algorithms are typically inherently sequential. Moreover, they usually rely on performing a large number of very fast iterations. However, the round of communication is much more time-consuming than a single iteration of the algorithm, which lead to the development of novel algorithms specialized for distributed optimization.<\/p>\n

Problem Formulation<\/p>\n

This model proposed in this paper are considering the problem of minimizing an objection function that has the form of a sum, which is like this:<\/p>\n

\"\"<\/p>\n

The examples for this kind of problem structure covers:<\/p>\n

\"\"<\/p>\n

The Setting of Federated Optimization<\/p>\n

Since communication efficiency is of utmost importance, algorithm for federated optimization follow the following characteristics.<\/p>\n

Massively Distributed:<\/p>\n

Data points are stored across a large number of nodes K. In particular, the number of nodes can be much bigger than the average number of training examples stored on a given node (n\/K).<\/p>\n

Non-IID:<\/p>\n

Data on each node may be drawn from a different distribution; that is, the data points available locally are far from being a representative sample of the overall distribution.<\/p>\n

Unbalanced:<\/p>\n

Different nodes may vary by orders of magnitude in the number of training examples they hold.<\/p>\n

Federated Learning<\/strong><\/p>\n

Federated Learning enables mobile phones to collaboratively learn a shared prediction model while keeping all the training data on device, decoupling the ability to do machine learning from the need to store the data in the cloud. This goes beyond the use of local models that make predictions on mobile devices by bringing model training to the device as well.<\/p>\n

It works like this: your device downloads the current model, improves it by learning from data on your phone, and then summarizes the changes as a small focused update. Only this update to the model is sent to the cloud, using encrypted communication, where it is immediately averaged with other user updates to improve the shared model. All the training data remains on your device, and no individual updates are stored in the cloud.<\/p>\n

Distributed settings and desirable\u00a0algorithmic properties<\/strong><\/p>\n

We consider two distributed settings in this work. On a single machine, we compute the execution time as<\/p>\n

\"\"<\/p>\n

where\u00a0\"\"\u00a0is\u00a0the number of iterations algorithm A needs to converge to some fixed \u03b5 accuracy.\"\"is\u00a0the time needed for a single iteration.<\/p>\n

On natural distributed machines, the execution time includes the communication overhead\u00a0\u00a0in a single iteration; c >> \"\".<\/p>\n

\"\"<\/p>\n

Desirable algorithmic properties for the non-IID, unbalanced, and massively-distributed setting are:<\/p>\n

\"\"<\/p>\n

\n
\n
\n

Property (A) is valuable in any optimization setting. Properties (B) and (C) are extreme cases of the federated optimization setting (non-IID, unbalanced, and sparse), whereas (D) is an extreme case of the classic distributed optimization setting (large amounts of IID data per machine). Thus, (D) is the least important property for algorithms in the federated optimization setting.<\/p>\n

SVRG algorithm on a single node<\/strong><\/p>\n

\"\"<\/p>\n

The Central idea<\/b><\/u> is\u00a0<\/b>the algorithm evaluates two stochastic gradients,\u2207fi(w) and \u2207fi(wt) to estimate the change of the gradient of the entire function between points wt and w, namely \u2207f(w)\u2212 \u2207f(wt).<\/p>\n

Under a distributed setting, we modify the objective as below:<\/p>\n

The original problem formulation is\u00a0\"\"\u00a0If we define\u00a0\"\"\u00a0then\u00a0\"\"<\/p>\n

Therefore, the objective is changed to\"\"<\/p>\n

Distributed Approximate Newton algorithm (DANE)<\/strong><\/p>\n<\/div>\n<\/div>\n<\/div>\n

\"\"<\/p>\n

The main idea of DANE is to form a local subproblem, dependent only on local data, and gradient of the entire function \u2014 which can be computed in a single round of communication.<\/p>\n

Naive Federated SVRG<\/strong><\/p>\n

\"\"<\/p>\n

\"\"<\/p>\n

This proposition proves the effectiveness of the naive federated SVRG algorithm. However, this algorithm is inherently stochastic, and is\u00a0valid under identical sequence of samples. This work further improves this algorithm to get the federated SVRG.<\/p>\n

The Federated SVRG<\/strong><\/p>\n

The notations used in this work are summarized below:<\/p>\n

\"\"<\/p>\n

Federated SVRG improves from naive federated SVRG from four parameters:<\/p>\n

\"\"<\/p>\n

\"\"<\/p>\n

Since the local data sizes, nk, are not identical, so setting the stepsize hk inversely proportional to nk, making sure each node makes progress of roughly the same magnitude overall.<\/p>\n

\"\"<\/p>\n

\n
\n
\n

If K is\u00a0more than 1, the values of Gk are in general biased estimates of \u2207f(wt).<\/p>\n

\"\"<\/p>\n

\n
\n
\n

This motivates the aggregation of updates from nodes proportional to nk, the number of data points available locally.<\/p>\n

\"\"<\/p>\n

\n
\n
\n

Because of the un-even distribution of nonzeros for a particular feature,<\/p>\n

\n
\n
\n

repeatedly sampling and overshooting the magnitude of the gradient will likely cause the iterative process to diverge quickly. So we scale stochastic gradients by diagonal matrix Sk.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

\"\"<\/p>\n

\n
\n
\n

If a variable appears in data on each node, we are going to take average. However, the less nodes a particular variable appear on, the more we want to trust those few nodes in informing us about the meaningful update to this variable \u2014 or alternatively, take a longer step. Hence the per-variable scaling of aggregated updates.<\/p>\n

Experiments<\/strong><\/p>\n

They provide results on a dataset based on public Google+ posts, clustered by user \u2014 simulating each user as a independent node.<\/p>\n

The following figure shows the frequency of\u00a0 different features across nodes. In particular, over 88%
\nof features are present on fewer than 1000 nodes, which simulate the structure of distribution of the sparsity pattern.<\/p>\n

\"\"<\/p>\n

Figure 1: Features vs. appearance on nodes. The x-axis is a feature index, and they-axis represents the number of nodes where a given feature is present.<\/p>\n<\/div>\n<\/div>\n

\"\"<\/p>\n

Figure 2: Rounds of communication vs. objective function (left) and test prediction error (right).<\/p>\n<\/div>\n

Figure2 show that FSVRG, converges to optimal test classification accuracy in just 30 iterations.\u00a0Since the core reason other methods fail to converge is the non-IID data distribution, the experiment test the FSVRGR algorithm with data randomly reshuffled among the same number of nodes, which illustrate the algorithm is robust\u00a0to challenges present in federated optimization.<\/p>\n","protected":false},"excerpt":{"rendered":"

Introduction Standard machine learning approaches require centralizing the training data on one machine or in a datacenter. This work\u00a0introduces\u00a0an additional approach: Federated Learning, which\u00a0leaves the training data distributed on the mobile devices, and learns a shared model by aggregating locally computed updates via\u00a0a central coordinating server. State-of-the-art optimization algorithms are typically inherently sequential. Moreover, they … Continue reading Federated Optimization: Distributed Machine Learning for On-Device Intelligence<\/span><\/a><\/p>\n","protected":false},"author":169,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[1],"tags":[],"class_list":["post-424","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9CQAE-6Q","_links":{"self":[{"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/posts\/424","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/users\/169"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/comments?post=424"}],"version-history":[{"count":12,"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/posts\/424\/revisions"}],"predecessor-version":[{"id":491,"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/posts\/424\/revisions\/491"}],"wp:attachment":[{"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/media?parent=424"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/categories?post=424"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/tags?post=424"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}