# Author Archives: Sebastien Bubeck

## Embeddings of finite metric spaces in Hilbert space

In this post we discuss the following notion: Let and be two metric spaces, one says that embeds into with distortion if there exists and such that for any , We write this as . Note that if … Continue reading

## The aftermath of ORF523 and the final

It has been two weeks since my last post on the blog, and I have to admit that it felt really good to take a break from my 2-posts-per-week regime of the previous months. Now that ORF523 is over the … Continue reading

## ORF523: Optimization with bandit feedback

In this last lecture we consider the case where one can only access the function with a noisy -order oracle (see this lecture for a definition). This assumption models the ‘physical reality’ of many practical problems (on the contrary to … Continue reading

## ORF523: Acceleration by randomization for a sum of smooth and strongly convex functions

In this lecture we are interested in the following problem: where each is -smooth and strongly-convex. We denote by the condition number of these functions (which is also the condition number of the average). Using a gradient descent … Continue reading

## ORF523: Noisy oracles

Today we start the third (and last) part of our class titled: ‘Optimization and Randomness’. An important setting that we will explore is the one of optimization with noisy oracles: Noisy -order oracle: given it outputs such that . Noisy … Continue reading

## ORF523: Mirror Prox

Today I’m going to talk about a variant of Mirror Descent invented by Nemirovski in 2004 (see this paper). This new algorithm is called Mirror Prox and it is designed to minimize a smooth convex function over a compact convex … Continue reading

## COLT 2013 accepted papers

The accepted papers for COLT 2013 have just been revealed. You can also find the list below with a link to the arxiv version when I could find one (if you want me to add a link just send me … Continue reading

## ORF523: Mirror Descent, part II/II

We start with some of the standard setups for the Mirror Descent algorithm we described in the previous post. Standard setups for Mirror Descent ‘Ball’ setup. The simplest version of Mirror Descent is obtained by taking on The function is … Continue reading

## ORF523: Mirror Descent, part I/II

In this post we are interested in minimizing a convex function over a compact convex set under the assumption that is -Lipschitz on with respect to some arbitrary norm (precisely we assume that ). As we have seen in this … Continue reading

## ORF523: ISTA and FISTA

As we said in the previous lecture it seems stupid to consider that we are in a black-box situation when in fact we know entirely the function to be optimized. Consider for instance the LASSO objective where one wants to minimize over . By … Continue reading