Everyone is welcome to attend the next N&O seminar with Sophie Huiberts with the title 'Self-Adjusting Networks'.
The talk will take place in L017 at CWI, along with zoom support for remote participants. For more information and registration to get the Zoom link via e-mail, please contact Willem Feijen (willem.feijen at cwi.nl), Samarth Tiwari (samarth.tiwari at cwi.nl) or Sven Polak (sven.polak at cwi.nl).
Abstract: We consider the problem of maximizing a linear functional over a general convex body K given by a separation oracle. While the standard cutting plane algorithm performs well in practice, no bounds on the number of oracle calls can be given. In contrast, methods with strong theoretical guarantees, such as the ellipsoid method, are often impractical. We give a new simple method with weaker theoretical bounds but that performs considerably better in practice.
It is based on classical Von Neumann and Frank-Wolfe algorithms, and requires O(R^4/(r^ 2 eps^2)) calls to the oracle to find an additive -approximate solution, where it is assumed that K contains a ball of radius r and is contained inside the origin centered ball of radius R. If the inner r-ball is centered at the origin, we give a simplified variant that outputs a multiplicative (1 + eps)-approximate solution using O(R^2/(r^2 eps^ 2)) oracle calls. We evaluate our method on instances from combinatorial optimization, semidefinite programming, and machine learning. In terms of oracle calls, we observe that it is comparable to the standard cutting plane method and often even faster. This is joint work with Daniel Dadush, Christopher Hojny, and Stefan Weltge.
