DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 5 and 14 recites the limitation " wherein ". There is insufficient antecedent basis for this limitation.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claim(s) 1-9, 11-16, 18, 19 are rejected under 35 U.S.C. 103 as being unpatentable over Philippenko (Preserved central model for faster bidirectional compression in distributed settings) in view of Nguyen (Federated Learning with Buffered Asynchronous Aggregation).
Regarding claim 1, Philippenko teaches sampling, by a server device, at least one client device, wherein the sampling includes a request to update a local model of the client device using a hidden state model (Section 2.1, Eq(3), We introduce a downlink memory term (Hk)k, which is available on both workers and central server. The difference Ωk+1 between the model and this memory is compressed and exchanged, then the local model is reconstructed from this information, the hidden state model is the memory H, which is used to update the local model); receiving, by the server device, a quantized difference for the local model of the at least one client device (Section 2.1 Eq(3), quantized difference is shown in the uplink step as Cup(∆i k)); updating, by the server device, the hidden state model using the server model; and transmitting, by the server device, a hidden state model update to the at least one client device (Section 2.1 Eq(3), in the downlink step (information being sent from the server to the clients) the hidden state model is updated using the server model here Hk+1 = Hk +αdwnCdwn(Ωk+1), where Ωk+1 = wk+1 −Hk and wk+1 is the global model).
Philippenko fails to teach aggregating, by the server device, model updates in a buffer; performing, by the server, a global update on a server model using the model updates in the buffer.
Nguyen teaches aggregating, by the server device, model updates in a buffer; performing, by the server, a global update on a server model using the model updates in the buffer (Section 1, Unlike other asynchronous methods, the server aggregates K client updates in a secure buffer before performing a server update.)
Nguyen and Philippenko are analogous to the claimed invention because they are both in the field of federated learning. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have used the FedBuff system in Nguyen alongside the bidirectional compression system in Philippenko to scale aggregation efficiently while being compatible with secure aggregation to maintain the privacy of the system (Nguyen Abs, We empirically demonstrate that FedBuff is 3.3× more efficient than synchronous FL and up to 2.5× more efficient than asynchronous FL, while being compatible with privacy-preserving technologies such as Secure Aggregation and differential privacy).
Regarding claim 2, Philippenko teaches wherein sampling the at least one client device includes a request for local updates to the hidden state model from the at least one client device, and wherein the local updates are determined following training by the at least one client device (Section 2.1 Eq(3), local updates to the hidden state model: hi k+1 = hi k + αupCup(∆i k) based on the gradient from the client: ∆i k = gi k+1(wk)−hi).
Regarding claim 3, Philippenko teaches Quantized Federated Learning Model (Title, Preserved central model for faster bidirectional compression in distributed settings) but fails to teach Buffered Aggregation. Nguyen teaches Buffered Aggregation (Title, Federated Learning with Buffered Asynchronous Aggregation). The rationale for combining the two systems is stated in the rejection for claim 1.
Regarding claim 4, Philippenko teaches wherein the quantized difference includes a compressed set of hidden state model updates determined by the at least one client device (Section 2.1 Eq(3), quantized difference Cup(∆i k) includes the compressed memory/hidden state model: ∆i k = gi k+1(wk)−hi k).
Regarding claim 5, Philippenko teaches wherein the quantizer compresses updates to the hidden state model including a function with a compression parameter (Section 2.1, We use two different compression operators, respectively Cup and Cdwn to compress the message in each direction), and an internal randomness parameter (Assumption 1, There exists constants ωup ,ωdwn ∈ R∗ +, such that the compression operators Cup and Cdwn satisfy the two following properties for all w in Rd: E[Cup/dwn(w)] = w, and E[ Cup/dwn(w) − w2] ≤ ωup/dwnw2. The higher is ω, the more aggressive the compression is, expectation implies randomness, Section 1, First, we show that it is possible to improve the convergence rate by sending different randomized models to the different workers, internal randomness in the model that is compressed), the function configured to reduce trained dataset updates to a quantized set of data updates (Section 5, Each experiment has been run with N = 20 workers using stochastic scalar quantization [3], w.r.t. 2-norm. To maximize compression, we always quantize on a single level (s = 20), unless for PP (s = 21) and neural network (the value of s depends on the dataset, implies randomness as well given the word “stochastic”).
Regarding claim 6, Philippenko teaches determining quantized model updates, the quantized model updates providing training feedback for the local model (Section 2.1 Eq(3), the local model is updated using the quantized model updates wk+1 = Hk +Cdwn(Ωk+1)) and hidden state model (Section 2.1 Eq(3), the hidden model is updated using the quantized model updates Hk+1 = Hk+αdwnCdwn(Ωk+1)).
Regarding claim 7, Philippenko teaches wherein the global update includes updating a server model on the server device based on aggregated training updates received for the hidden state model from at least one client device (Section 2.1 Eq(3), wk+1 = wk – γ/N∑ N i=1 Cup(∆i k)+hi global model updated using hidden state model and gradient from local model).
Regarding claim 8, Philippenko teaches wherein updating the hidden state model includes modifying a hidden state model using an updated server model on the server device (Section 2.1 Eq(3), hidden state model updated using wk+1 (the updated server model): Hk+1 = Hk +αdwnCdwn(Ωk+1)).
Regarding claim 9, Philippenko teaches wherein transmitting the hidden state model update includes broadcasting a modified hidden state model to the at least one client device (Section 2.1 Eq(3), hidden state model updated using wk+1 (the updated server model) during the uplink stage (from server to client): Hk+1 = Hk +αdwnCdwn(Ωk+1)).
Regarding claim 11, the claim cites limitations essentially the same as claim 1 but a system including a server and at least one client device which is taught by Philippenko (Abs, uplink (from the local workers to the central server)) and is therefore rejected for at least the same reasons.
Regarding claim 12, the claim cites essentially the same limitations as claim 3 and is rejected for at least the same reasons.
Regarding claim 13, Philippenko teaches wherein the client device includes an unbiased quantizer (Section 2.1, We only consider unbiased operators, that encompass sparsification, quantization and sketching) configured to generate a quantized difference for the local model of the at least one client device and the hidden state model (Section 2.1 Eq(3), quantized difference is shown in the uplink step as Cup(∆i k), where ∆i k = gi k+1(wk)−hi, wk is the local model and hk the hidden state model).
Regarding claim 14, the claim recites essentially the same limitations as claim 5 and is rejected for at least the same reasons.
Regarding claim 15, the claim recites essentially the same limitations as claim 6 and is rejected for at least the same reasons.
Regarding claim 16, the claim recites essentially the same limitations as claim 7 and is rejected for at least the same reasons.
Regarding claim 18, Philippenko teaches receiving, by a client device, a hidden state model, the hidden state model based on a server device model (Section 2.1, Eq(3), We introduce a downlink memory term (Hk)k, which is available on both workers and central server. The difference Ωk+1 between the model and this memory is compressed and exchanged, then the local model is reconstructed from this information, the hidden state model is the memory H, which is used to update the local model and sent during the downlink portion); training, by the client device, a local model to determine updates for the local model (Section 2.1 Eq(3), difference involves gradient of the local model: ∆i k = gi k+1(wk)−hi k); receiving, by client device, a request to transmit updates determined for the local model of the client device; generating, by the client device, a quantized difference for the local model and the hidden state model; transmitting, by the client device, a quantized difference to the server device (Section 2.1 Eq(3), in the uplink step (information being sent from the client to the server) the quantized difference Cup(∆i k) where ∆i k = gi k+1(wk)−hi k, is calculated).
Nguyen teaches, which Philippenko fails to teach, buffered aggregation (Section 1, Unlike other asynchronous methods, the server aggregates K client updates in a secure buffer before performing a server update.)
Nguyen and Philippenko are analogous to the claimed invention because they are both in the field of federated learning. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have used the FedBuff system in Nguyen alongside the bidirectional compression system in Philippenko to scale aggregation efficiently while being compatible with secure aggregation to maintain the privacy of the system (Nguyen Abs, We empirically demonstrate that FedBuff is 3.3× more efficient than synchronous FL and up to 2.5× more efficient than asynchronous FL, while being compatible with privacy-preserving technologies such as Secure Aggregation and differential privacy).
Regarding claim 19, Philippenko teaches Quantized Federated Learning Model (Title, Preserved central model for faster bidirectional compression in distributed settings) but fails to teach Buffered Aggregation. Nguyen teaches Buffered Aggregation (Title, Federated Learning with Buffered Asynchronous Aggregation). The rationale for combining the two systems is stated in the rejection for claim 18.
Claim(s) 10, 17, 20 are rejected under 35 U.S.C. 103 as being unpatentable over Philippenko and Nguyen as applied to claims 1, 11, and 18 above, and further in view of Tang (GossipFL: A Decentralized Federated Learning Framework With Sparsified and Adaptive Communication).
Regarding claim 10, Philippenko in view of Nguyen teaches the method of claim 1 and Philippenko teaches wherein the at least one client device performs (Section 2.1 Eq(3), uplink and down link of hidden state model updates (Hk).
The combination of Philippenko and Nguyen fails to teach wherein the at least one client device performs a gossiped
Tang teaches wherein the at least one client device performs a gossiped and quantized communication(Section 1, Each client only needs to exchange a highly compressed model with a single peer at every communication round).
Tang is analogous to the claimed invention because it is in the field of federated learning. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have added the system of GossipFL from Tang to the combination of Philippenko and Nguyen to “reduce both the up-link and down-link communication traffic” (Tang Section 1).
Regarding claim 17, the claim recites essentially the same limitations as claim 10 and is rejected for at least the same reasons.
Regarding claim 20, the claim recites essentially the same limitations as claims 13 and 17 combined and is rejected for at least the same reasons.
Claim(s) 21 is rejected under 35 U.S.C. 103 as being unpatentable over Koloskova (Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication) in view of Ozkasap (Stepwise fair-share buffering for gossip-based peer-to-peer data dissemination).
Regarding claim 21, Koloskova teaches sampling, by a client device, at least one neighboring client device, wherein sampling includes a request for the at least one neighboring client device to update a local model of the at least one neighboring client device using a hidden state model (Algorithm 1, line 2 updates the local model using a hidden state model x ̂(t), Section 3.4, Every worker i∈[n] stores and updates its own local variable xi as well as the variables xˆj for all neighbors (including itself)); receiving, by the client device, a quantized difference for the local model of the at least one neighboring client device (Algorithm 1, line 3 and 5 q(t) is the quantized difference, Section 3.3, Informally, we can think of Q as either a sparsification operator (that enforces sparsity of Q(g)) or a quantization operator that reduces the number of bits required to represent Q(g)); aggregating, by the client device, model updates (Algorithm 1, line 2, shows updating and aggregating model updates); updating, by the client device, the hidden state model of the client device using the client model (Algorithm 1, line 6 shows updating the hidden state model using qt which includes the client model); and transmitting, by the client device, a hidden state model update to the at least one neighboring client device, wherein the client device performs a gossiped and quantized communication of hidden state model updates to the at least one neighboring client device (Algorithm 1, line 5, quantized communication of differences involving hidden state models between neighbors).
Koloskova fails to teach a buffer. Ozkasap teaches a buffer (Abs, We consider buffer management in support of large-scale gossip-based peer-to-peer data dissemination protocols).
Ozkasap and Koloskova are analogous to the claimed invention because they are both in the field of gossip-based distributed systems. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have added the buffer system in Ozkasap designed for gossip-based peer-to-peer data dissemination to the gossip-based neighbor-to-neighbor communication system of Koloskova to reduce the memory usage (Ozkasap section 2.2).
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to NATNAEL A ASEGDEW whose telephone number is (571)270-0407. The examiner can normally be reached 7:30-5.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Kakali Chaki can be reached at (571) 272-3719. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/NATNAEL A ASEGDEW/Examiner, Art Unit 2122
/MICHAEL H HOANG/PRIMARY EXAMINER, Art Unit 2122
