M.Sc Thesis
M.Sc Student Wagner Jonathan Andre Multiplicative Approximation Algorithms for Generalized Covering and Packing Problems Department of Computer Science Professor Elad Hazan

Abstract

Approximation of min-max problems is a common task in convex optimization which has many important uses in machine learning and combinatorial optimization.

Approximations of problems can be divided into two main categories - additive approximations and multiplicative approximations. Additive approximations are usually relevant to general settings, but have runtime that in many cases depends significantly on the magnitude of natural parameters of the problem. Multiplicative approximations on the other hand, are natural for non-negative settings, and unlike the additive case, allow in many cases algorithms that are independent of the magnitude, or width, of the input parameters. This property is also known as width-free running time.

Multiplicative approximation can also be useful if the optimum value of the problem is very small. In this case a multiplicative approximation of even 0.5, gives a very small additive approximation which may require much larger running time by additive approximation methods.

Recently, for the case of additive approximation, the use of sampling methods together with low-regret algorithms enabled the development of a general method for approximating an important class of min-max problems. This led to remarkably fast algorithms for several important problems in machine learning. This approach, however, did not address the task of multiplicative approximation.

In this work we present simple schemes based on low regret algorithms that give width-independent multiplicative approximation algorithms for two important classes of non-negative min-max problems -  generalized covering and generalized packing. Our main contribution is a novel sampling and speed-up technique that in certain cases can be incorporated into the schemes and lead to very fast algorithms. As an application, we describe the first near-linear time, width-free multiplicative approximation algorithms for Normalized Covering Semi-definite Programming, and for Non-negative Linear Classifier.