Efficient Algorithms for Online Convex Optimization and Their Applications (thesis)

Abstract:

In this thesis we study algorithms for online convex optimization
and their relation to approximate optimization.

In the first part, we propose a new algorithm for a general online
optimization framework called online convex optimization.
Whereas previous efficient algorithms are mostly gradient-descent
based, the new algorithm is inspired by the Newton-Raphson method
for convex optimization, and hence called Online Newton Step. We prove that in
certain scenarios Online Newton Step guarantees logarithmic regret, as opposed
to polynomial bounds achieved by previous algorithms. The analysis
is based on new insights concerning the natural
``follow-the-leader" (FTL) method for online optimization, and
answers some open problems regarding FTL.

One application is for the portfolio management problem, for which we describe
experimental results over real market data.

In the second part of the thesis, we describe a general scheme of
utilizing online game playing algorithms to obtain efficient
algorithms for offline optimization. Using new and old online
convex optimization algorithms we show how to derive the
following:

1. Approximation algorithms for convex programming with linear
dependence on the approximation guarantee.

2. Efficient algorithms for haplotype frequency estimation.

3. Fast algorithms for approximate semidefinite programming