We address a classical problem in finance of constructing mean reverting portfolios. A new proxy for mean reversion is proposed. As our proxy for mean reversion is not convex, we define a semi-definite relaxation along with an online algorithm tailored for the relaxation with provable performance guarantees compared to the non-convex optimum. As part of our investigation, we consider the general framework of online learning with memory, for which we give a the first efficient algorithm with optimal performance guarantees.