I have a dirty secret. Well, I actually have many. But one of them is that I never understood the basic algorithms behind reinforcement learning. So I plan to remedy this with a series of blog posts, where I will cover foundational RL algorithms, from REINFORCE to the frontier. Here's …
Differentiating through optimization is a fundamental problem in hyperparameter optimization, dataset distillation, meta-learning and optimization as a layer, to name a few. In this blog post we'll look into one of the main approaches to differentiate through optimization: unrolled differentiation. With the help of polynomials, we'll be able to derive …
This blog post discusses the convergence rate of the Stochastic Gradient Descent with Stochastic Polyak Step-size (SGD-SPS) algorithm for minimizing a finite sum objective. Building upon the proof of the previous post, we show that the convergence rate can be improved to O(1/t) under the additional assumption that …
The stochastic Polyak step-size (SPS) is a practical variant of the Polyak step-size for stochastic optimization. In this blog post, we'll discuss the algorithm and provide a simple analysis for convex objectives with bounded gradients.
The Langevin algorithm is a simple and powerful method to sample from a probability distribution. It's a key ingredient of some machine learning methods such as diffusion models and differentially private learning. In this post, I'll derive a simple convergence analysis of this method in the special case when the …
The idea for what was later called Monte Carlo method occurred to me when I was playing solitaire during my illness. Stanislaw Ulam, Adventures of a Mathematician The Russian Roulette offers a simple way to construct an unbiased estimator for the limit of a sequence. It allows for example to …
Backtracking step-size strategies (also known as adaptive step-size or approximate line-search) that set the step-size based on a sufficient decrease condition are the standard way to set the step-size on gradient descent and quasi-Newton methods. However, these techniques are much less common for Frank-Wolfe-like algorithms. In this blog post I …
Six : All of this has happened before. Baltar : But the question remains, does all of this have to happen again? Six : This time I bet no. Baltar : You know, I've never known you to play the optimist. Why the change of heart? Six : Mathematics. Law of averages. Let a complex …
When an optimization problem has multiple global minima, different algorithms can find different solutions, a phenomenon often referred to as the implicit bias of optimization algorithms. In this post we'll characterize the implicit bias of gradient-based methods on a class of regression problems that includes linear least squares and Huber …
This is the first of a series of blog posts on short and beautiful proofs in optimization (let me know what you think in the comments!). For this first post in the series I'll show that stochastic gradient descent (SGD) converges exponentially fast to a neighborhood of the solution.
While the most common accelerated methods like Polyak and Nesterov incorporate a momentum term, a little known fact is that simple gradient descent –no momentum– can achieve the same rate through only a well-chosen sequence of step-sizes. In this post we'll derive this method and through simulations discuss its practical …
I've seen things you people wouldn't believe. Valleys sculpted by trigonometric functions. Rates on fire off the shoulder of divergence. Beams glitter in the dark near the Polyak gate. All those landscapes will be lost in time, like tears in rain. Time to halt. A momentum optimizer *
We can tighten the analysis of gradient descent with momentum through a cobination of Chebyshev polynomials of the first and second kind. Following this connection, we'll derive one of the most iconic methods in optimization: Polyak momentum.
There's a fascinating link between minimization of quadratic functions and polynomials. A link that goes deep and allows to phrase optimization problems in the language of polynomials and vice versa. Using this connection, we can tap into centuries of research in the theory of polynomials and shed new light on …
A naive implementation of the logistic regression loss can results in numerical indeterminacy even for moderate values. This post takes a closer look into the source of these instabilities and discusses more robust Python implementations.
This blog post extends the convergence theory from the first part of these notes on the Frank-Wolfe (FW) algorithm with convergence guarantees on the primal-dual gap which generalize and strengthen the convergence guarantees obtained in the first part.
I discuss a recently proposed optimization algorithm: the Davis-Yin three operator splitting.
This blog post is the first in a series discussing different theoretical and practical aspects of the Frank-Wolfe algorithm. $$ \def\xx{\boldsymbol x} \def\yy{\boldsymbol y} \def\ss{\boldsymbol s} \def\dd …
Most proofs in optimization consist in using inequalities for a particular function class in some creative way. This is a cheatsheet with inequalities that I use most often. It considers class of functions that are convex, strongly convex and $L$-smooth.
My friend Rémi Leblond has recently uploaded to ArXiv our preprint on an asynchronous version of the SAGA optimization algorithm . The main contribution is to develop a parallel (fully asynchronous, no locks) variant of the SAGA algorighm . This is a stochastic variance-reduced method for general optimization, specially adapted for problems …
TL;DR: I describe a method for hyperparameter optimization by gradient descent. Most machine …
Announce: first public release of lightning !, a library for large-scale linear classification, regression and ranking in Python. The library was started a couple of years ago by Mathieu Blondel who also contributed the vast majority of source code. I joined recently its development and decided it was about time for …
Together with other scikit-learn developers we've created an umbrella organization for scikit-learn-related projects named scikit-learn-contrib . The idea is for this organization to host projects that are deemed too specific or too experimental to be included in the scikit-learn codebase but still offer an API which is compatible with scikit-learn and …
Recently I've implemented, together with Arnaud Rachez , the SAGA[ 1 ] algorithm in the lightning machine learning library (which by the way, has been recently moved to the new scikit-learn-contrib project). The lightning library uses the same API as scikit-learn but is particularly adapted to online learning. As for the SAGA …
My latests work (with Francis Bach and Alexandre Gramfort ) is on the consistency of ordinal regression methods. It has the wildly imaginative …
Cross-validation iterators in scikit-learn are simply generator objects, that is, Python objects that implement the __iter__ method and that for each call to this method return (or more precisely, yield ) the indices or a boolean mask for the train and test set. Hence, implementing new cross-validation iterators that behave as …
Due to lack of time and interest, I'm no longer maintaining this project. Feel free to grab the sources from https://github.com/fabianp/nbgallery and fork the project. TL;DR I created a gallery for IPython/Jupyter notebooks. Check it out :-) A couple of months ago I put online …
Last Friday was PyData Paris , in words of the organizers, ''a gathering of users and developers of data analysis tools in Python''. The organizers did a great job in putting together and the event started already with a full room for Gael's keynote My take-away message from the talks is …
My latest research paper [ 1 ] deals with the estimation of the hemodynamic response function (HRF) from fMRI data. This is an important topic since the knowledge of a hemodynamic response function is what makes it possible to extract the brain activation maps that are used in most of the impressive …
:og_image: http://fa.bianp.net/blog/images/2014/mprof_example.png One of the lesser known features of the memory_profiler package is its ability to plot memory consumption as a function of time. This was implemented by my friend Philippe Gervais, previously a colleague at INRIA and now at Google. With …
Sir R. A. Fisher. Source: Wikipedia --> TL; DR These are some notes on calibration of surrogate loss functions in the context of machine learning. But mostly it is …
As part of the development of memory_profiler I've tried several ways to get memory usage of a program from within Python. In this post I'll describe the different alternatives I've tested. The psutil library psutil is a python library that provides an interface for retrieving information on running processes. It …
In this post I compar several implementations of Logistic Regression. The task was to implement a Logistic Regression model using standard optimization …
TL;DR: I've implemented a logistic ordinal regression or proportional odds model. Here is the Python code The logistic ordinal regression model …
My latest contribution for scikit-learn is an implementation of the isotonic regression model that I coded with Nelle Varoquaux and Alexandre Gramfort …
Householder matrices are square matrices of the form $$ P = I - \beta v v^T$$ where $\beta$ is a scalar and $v$ is …
** Note: this post contains a fair amount of LaTeX, if you don't visualize the math correctly come to its original location ** In …
Besides performing a line-by-line analysis of memory consumption, memory_profiler exposes some functions that allow to retrieve the memory consumption of a function in real-time, allowing e.g. to visualize the memory consumption of a given function over time. The function to be used is memory_usage . The first argument specifies what …
SciPy contains two methods to compute the singular value decomposition (SVD) of a matrix: scipy.linalg.svd and scipy.sparse.linalg.svds . In this post I'll compare both methods for the task of computing the full SVD of a large dense matrix. The first method, scipy.linalg.svd , is perhaps …
This tutorial introduces the concept of pairwise preference used in most ranking problems . I'll use scikit-learn and for learning and matplotlib for …
My newest project is a Python library for monitoring memory consumption of arbitrary process, and one of its most useful features is the line-by-line analysis of memory usage for Python code. I wrote a basic prototype six months ago after being surprised by the lack of related tools. I wanted …
A little experiment to see what low rank approximation looks like. These are the best rank-k approximations (in the Frobenius norm) to the a natural image for increasing values of k and an original image of rank 512. Python code can be found here . GIF animation made using ImageMagic's convert …
In scipy's development version there's a new function closely related to the QR-decomposition of a matrix and to the least-squares solution of a linear system. What this function does is to compute the QR-decomposition of a matrix and then multiply the resulting orthogonal factor by another arbitrary matrix. In pseudocode …
Last week we released a new version of scikit-learn. The Changelog is particularly impressive , yet personally this release is important for other reasons. This will probably be my last release as a paid engineer. I'm starting a PhD next month, and although I plan to continue contributing to the project …
I've been working lately in improving the scikit-learn example gallery to show also a small thumbnail of the plotted result. Here is what the gallery looks like now: And the real thing should be already displayed in the development-documentation . The next thing is to add a static image to those …
Today's coding sprint was a bit more crowded, with some notable scipy hackers such as Ralph Gommers, Stefan van der Walt , David Cournapeau or Fernando Perez from Ipython joining in. On what got done: - We merged Jake 's new BallTree code. This is a pure Cython implementation of a nearest-neighbor …
As a warm-up for the upcoming EuroScipy-conference , some of the scikit-learn developers decided to gather and work together for a couple of days. Today was the first day and there was only a handfull of us, as the real kickoff is expected tomorrow. Some interesting coding happened, although most of …
Ridge coefficients for multiple values of the regularization parameter can be elegantly computed by updating the thin SVD decomposition of the design matrix: import numpy as np from scipy import linalg def ridge ( A , b , alphas ): """ Return coefficients for regularized least squares min ||A x - b||^2 + alpha ||x||^2 …
I haven't worked in the manifold module since last time , yet thanks to Jake VanderPlas there are some cool features I can talk about. First of, the ARPACK backend is finally working and gives factor one speedup over the lobcpg + PyAMG approach . The key is to use ARPACK's shift-invert mode …
The manifold module in scikit-learn is slowly progressing: the locally linear embedding implementation was finally merged along with some documentation . At about the same time but in a different timezone, Jake VanderPlas began coding other manifold learning methods and back in Paris Olivier Grisel made my digits example a lot …