The monotone linear complementarity problem (LCP) unifies the primal and dual aspects of linear and convex quadratic programs. These optimization problems occur often in machine learning and optimal control. For example, training support vector machines (SVMs) and finding optimal policies in Markov decision processes (MDPs) can be cast as monotone LCPs. LCP instances are commonly too large to solve exactly in applications like MDP planning. This thesis will focus on fast but approximate LCP algorithms that carry approximation bounds–bounds on the distance between an approximate solution and the set of actual solutions. We have already developed several fixed point algorithms that carry bounds. These algorithms are based on Galerkin approximations. Many LCP instances are estimated from data, so we also want to bound how far a solution of an estimated LCP can be from the true set of solutions. The reasoning and theoretical tools associated with bounding approximation error can also be used to bound the error introduced by estimation and other perturbations. These bounds can be combine with probabilistic perturbation models to get tail bounds on how extreme error can be; we provide examples of the kind of perturbation bounds that we want. We also intend to run a number of experiments based on applications drawn from real world problems including large SVMs and a large MDP based on the one used in the Airborne Collision Avoidance System (ACAS). These experiments will allow us to compare our general-purpose LCP algorithms to problem-specific algorithms and characterize their relative performances. The data will also allow us to determine how tight our approximation and perturbation bounds are in practice.
Geoff Gordon (Co-chair)
André Platzer (Co-chair)
Ron Parr (Duke University)
deb [atsymbol] cs ~replace-with-a-dot~ cmu ~replace-with-a-dot~ edu