In the contextual bandit problem, a learner, for a series of rounds, observes a context, makes an action, and receives reward for this action, but does not see the potential reward for other possible actions. Consequently, the learner must negotiate an exploration-exploitation tradeoff, whereby it explores to understand good actions for each context, but also exploits so that it achieves high reward over the course of the interaction. In conte…

The approach of minimizing a function by successively fixing most of its variables and minimizing with respect to the others dates back many years, and has been applied in an enormous range of applications. Until recently, however, the approach did not command much respect among optimization researchers only a few prominent individuals took it seriously. Recent years have seen an explosion in applications, particularly in data analysis, which …

The recent success of tablets and depth cameras is a direct example of the importance of using natural interactions to interactively create simple and more interesting virtual experiences. On the other hand current interactive sketching media, shape modeling paradigms and tools remain non-intuitive and require significant training. They are often built on WIMP-based (windows-icons-menus-pointers) metaphors and interactions, thus binding the us…

Recently several methods were proposed for sparse optimization which make careful use of second-order information to improve local convergence rates. These methods construct a composite quadratic approximation using Hessian information, optimize this approximation using a first-order method, such as coordinate descent and employ a line search to ensure sufficient descent.

Here we propose a general framework, which includes slightly m…

We propose a variable metric framework for minimizing the sum of a self-concordant function and a possibly non-smooth convex function endowed with a computable proximal operator. We theoretically establish the convergence of our framework without relying on the usual Lipschitz gradient assumption on the smooth part. An important highlight of our work is a new set of analytic step-size selection and correction procedures based on the structure …