  A basic problem in the design of privacy-preserving algorithms is the private
maximization problem: the goal is to pick an item from a universe that
(approximately) maximizes a data-dependent function, all under the constraint
of differential privacy. This problem has been used as a sub-routine in many
privacy-preserving algorithms for statistics and machine-learning.
  Previous algorithms for this problem are either range-dependent---i.e., their
utility diminishes with the size of the universe---or only apply to very
restricted function classes. This work provides the first general-purpose,
range-independent algorithm for private maximization that guarantees
approximate differential privacy. Its applicability is demonstrated on two
fundamental tasks in data mining and machine learning.
