Microsoft Technology Licensing, LLC

Google Inc.

Kunal Talwar

Li Zhang

Kamal Jain

Ehud Wieder

Aleksandar Nikolov

Mark Steven Manasse

Rina Panigrahy

Daniel Ramage

Frank David McSherry

Hugh Brendan McMahan

Lincoln K Uyeda

Michael Isard

Vijayan Prabhakaran

Jonathan James Currey

Bernhard Haeupler

Moritz A W Hardt

Systems and methods for learning differentially private machine-learned models are provided. A computing system can include one or more server computing devices comprising one or more processors and one or more non-transitory computer-readable media that collectively store instructions that, when executed by the one or more processors cause the one or more server computing devices to perform operations. The operations can include selecting a subset of client computing devices from a pool of available client computing devices; providing a machine-learned model to the selected client computing devices; receiving, from each selected client computing device, a local update for the machine-learned model; determining a differentially private aggregate of the local updates; and determining an updated machine-learned model based at least in part on the data-weighted average of the local updates.

Training user-level differentially private machine-learned models

The privacy of linear queries on histograms is protected. A database containing private data is queried. Base decomposition is performed to recursively compute an orthonormal basis for the database space. Using correlated (or Gaussian) noise and/or least squares estimation, an answer having differential privacy is generated and provided in response to the query. In some implementations, the differential privacy is &#x3b5;-differential privacy (pure differential privacy) or is (&#x3b5;,&#x3b4;)-differential privacy (i.e., approximate differential privacy). In some implementations, the data in the database may be dense. Such implementations may use correlated noise without using least squares estimation. In other implementations, the data in the database may be sparse. Such implementations may use least squares estimation with or without using correlated noise.

Differentially private linear queries on histograms

Weighted features associated with a document are scaled using scales to generate a set of unweighted elements for each scale. A sketch is generated for each scale by sampling the unweighted elements generated for the scale. The scales are chosen based on a selected cutoff factor so that documents that have a similarity that is less than the cutoff factor might have no scales in common, while documents that have a similarity that is greater than the cutoff factor will have at sufficiently many but at least one scale in common. The similarity of these documents can be estimated using the sketches associated with each of the documents for the common scales.

Generating unweighted samples from weighted features

A method for packing virtual machines onto host devices may calculate scarcity values for several different parameters. A host's scarcity for a parameter may be determined by multiplying the host's capacity for a parameter with the overall scarcity of that parameter. The sum of a host's scarcity for all the parameters determines the host's overall scarcity. Hosts having the highest scarcity are attempted to be populated with a group of virtual machines selected for compatibility with the host. In many cases, several different scenarios may be evaluated and an optimal scenario implemented. The method gives a high priority to those virtual machines that consume scarce resources, with the scarcity being a function of the available hardware and the virtual machines that may be placed on them.

Virtual machine packing method using scarcity

A system for answering sets of queries on a set of private data while providing differential privacy protection is provided. The set of queries is received and applied to the set of private data to generate a set of results or answers. A geometric representation of the set of queries is generated. Example geometric representations include polytopes. Error values are generated for the set of queries using a K-norm mechanism based on values sampled from the geometric representation. The sampled values are added to the set of results to provide the differential privacy protection. By generating the error values based on the set of queries rather than the set of results or the set of private data, the amount of error added to the generated results to achieve a level of differential privacy protection is reduced.

Geometric mechanism for privacy-preserving answers

A job scheduler may schedule concurrent distributed jobs in a computer cluster by assigning tasks from the running jobs to compute nodes while balancing fairness with efficiency. Determining which tasks to assign to the compute nodes may be performed using a network flow graph. The weights on at least some of the edges of the graph encode data locality, and the capacities provide constraints that ensure fairness. A min-cost flow technique may be used to perform an assignment of the tasks represented by the network flow graph. Thus, online task scheduling with locality may be mapped onto a network flow graph, which in turn may be used to determine a scheduling assignment using min-cost flow techniques. The costs may encode data locality, fairness, and starvation-freedom.

Scheduling ready tasks by generating network flow graph using information receive from root task having affinities between ready task and computers for execution

A query log includes a list of queries and a count for each query representing the number of times that the query was received by a search engine. In order to provide differential privacy protection to the queries, noise is generated and added to each count, and queries that have counts that fall below a threshold are removed from the query log. A distribution associated with a function used to generate the noise is referenced to determine a distribution of a number of times that a hypothetical query having a zero count would have its count exceed the threshold after the addition of noise. Random queries of an amount equal to a sample from the distribution of number of times are added to the query log with a count that is greater than the threshold count.

Differentially private data release

To use market clearing methods to determine market equilibrium, a market clearing situation is established by determining a number of items to be sold at the market price and allotting a number of pseudo items assignable to bids below the market price. Once bids are received for the items, using the number of pseudo items and the actual items as the supply side, and the total funds bid as the demand side, a market clearing price is determinable using a market clearing equilibrium model. Funds assigned to pseudo items are returned or not charged. Further, by selling items only to bids exceeding the market clearing price, such as by setting the market price incrementally above the market clearing price, bidders are encouraged to submit bid prices bid reflecting what the items are worth to them instead of attempting to bid strategically to guess or set the market price.

Truth revealing market equilibrium

Auction prices for a quantity of items, the quantity of which is not determined prior to auction, are equilibrated among bidders to reflect supply and demand for the items. For example, in auctioning Internet advertising opportunities, the first available opportunities are auctioned to a high bidder. Later in the course of the auction period, once the high bidder's budget has been exhausted, the price for advertising opportunities is reduced. The difference in price paid by the high bidder and the reduced price for the quantity of advertising opportunities purchased is credited to the high bidder's account. Once the high bidder's account regains a level sufficient to acquire additional advertising opportunities, the high bidder may continue to acquire advertising opportunities. Other bidders similarly are credited the difference between prices previously paid and the current price. An equilibrium price is reached based on the recursive adjustment of prices paid by the bidders.

Online computation of market equilibrium price

In auctioning items, pseudo bids are determined based on the bid price and auction budget submitted by a bidder. The bid associated with the highest pseudo bid is identified as the winning bid. A consistent pseudo bid function is applied to determine the pseudo bids for each of the bids, or a variable pseudo bid function is selectively applied to some bids. The pseudo bid increases with increased bid prices and/or increased auction budgets. When a winning bid is identified, the winner's auction budget is debited the price of the item won, and the pseudo bid is recalculated using the remaining auction budget. Bidders submitting higher auction budgets are rewarded by being able to win more items because their auction budgets increase their pseudo bids. Recalculating pseudo bids based on remaining auction budgets allows different bidders to alternately win successive rounds as previous winners'auction budgets are reduced.

Growing community of inventors

San Francisco, CA, United States of America

Kunal Talwar