Georgia Institute of Technology College of Sciences

We resolve an open question from (Christiano, 2014b) posed in COLT'14 regarding the optimal dependency of the regret achievable for online local learning on the size of the label set. In this framework the algorithm is shown a pair of items at each step, chosen from a set of n items. The learner then predicts a label for each item, from a label set of size L and receives a real valued payoff. This is a natural framework which captures many interesting scenarios such as collaborative filtering, online gambling, and online max cut among others. (Christiano, 2014a) designed an efficient online learning algorithm for this problem achieving a regret of O((nL^3T)^(1/2)), where T is the number of rounds. Information theoretically, one can achieve a regret of O((n log LT)^(1/2)). One of the main open questions left in this framework concerns closing the above gap. In this work, we provide a complete answer to the question above via two main results. We show, via a tighter analysis, that the semi-definite programming based algorithm of (Christiano, 2014a), in fact achieves a regret of O((nLT)^(1/2)). Second, we show a matching computational lower bound. Namely, we show that a polynomial time algorithm for online local learning with lower regret would imply a polynomial time algorithm for the planted clique problem which is widely believed to be hard. We prove a similar hardness result under a related conjecture concerning planted dense subgraphs that we put forth. Unlike planted clique, the planted dense subgraph problem does not have any known quasi-polynomial time algorithms. Computational lower bounds for online learning are relatively rare, and we hope that the ideas developed in this work will lead to lower bounds for other online learning scenarios as well. Joint work with Pranjal Awasthi, Moses Charikar, and Andrej Risteski at Princeton.

We consider a Benney-type system modeling short wave-long wave interactions in compressible viscous fluids under the influence of a magnetic field. Accordingly, this large system now consists of the compressible MHD equations coupled with a nonlinear Schodinger equation along particle paths. We study the global existence of smooth solutions to the Cauchy problem in R^3 when the initial data are small smooth perturbations of an equilibrium state. An important point here is that, instead of the simpler case having zero as the equilibrium state for the magnetic field, we consider an arbitrary non-zero equilibrium state B for the magnetic field. This is motivated by applications, e.g., Earth's magnetic field, and the lack of invariance of the MHD system with respect to either translations or rotations of the magnetic field. The usual time decay investigation through spectral analysis in this non-zero equilibrium case meets serious difficulties, for the eigenvalues in the frequency space are no longer spherically symmetric. Instead, we employ a recently developed technique of energy estimates involving evolution in negative Besov spaces, and combine it with the particular interplay here between Eulerian and Lagrangian coordinates. This is a joint work with Junxiong Jia and Ronghua Pan.

In recent years, small-time asymptotic methods have attracted much attention in mathematical finance. Such asymptotics are especially crucial for jump-diffusion models due to the lack of closed- form formulas and efficient valuation procedures. These methods have been widely developed and applied to diverse areas such as short-time approximations of option prices and implied volatilities, and non-parametric estimations based on high-frequency data. In this talk, I will discuss some results on the small-time asymptotic behavior of some Levy functionals with applications in finance.

In elementary calculus, we learn that (1+z/n)^n has limit exp(z) as n approaches infinity. This type of scaling limit arises in many contexts - from approximation theory to universality limits in random matrices. We discuss some examples.