Everyone is welcome to attend the next N&O seminar with Sophie Huiberts under the title ‘Self-Adjusting Networks’.
The conference will take place in L017 at the CWI, with zoom support for remote participants. For more information and to register for the Zoom link via email, please contact Willem Feijen (willem.feijen on cwi.nl), Samarth Tiwari (samarth.tiwari on cwi.nl) or Sven Polak ( sven.polak on cwi.nl).
Abstract: We consider the problem of maximizing a linear functional on a general convex body K given by a separation oracle. While the standard cut plane algorithm works well in practice, no limit 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 which works 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 one assumes that K contains a ball of radius r and is contained inside the ball of radius R centered at the origin. If the inner ball r is centered at the origin, we give a simplified variant that produces a multiplicative approximate solution (1 + eps) using O(R^ 2/(r^2 eps^ 2)) oracle calls. We evaluate our method on instances from combinatorial optimization, semi-definite programming and machine learning. In terms of oracle calls, we observe that it is comparable to the standard cut plane method and often even faster. It is a joint work with Daniel Dadush, Christopher Hojny and Stefan Weltge.