After some investigation, the following code works:
Register provider as a service:
// src/Application/Sonata/MediaBundle/Resources/config/services.yml
parameters:
    application_sonata_media.custom_class: Application\Sonata\MediaBundle\Provider\CustomProvider
services:
    sonata.media.provider.custom:
          class: %application_sonata_media.custom_class%
          tags:
              - { name: sonata.media.provider }
          arguments:
              - sonata.media.provider.custom
              - @sonata.media.filesystem.local
              - @sonata.media.cdn.server
              - @sonata.media.generator.default
              - @sonata.media.thumbnail.format
Custom Provider code:
// src/Application/Sonata/MediaBundle/Provider/CustomProvider.php
<?php
namespace Application\Sonata\MediaBundle\Provider;
use Sonata\MediaBundle\Model\MediaInterface;
use Sonata\MediaBundle\Provider\FileProvider;
use Symfony\Component\Form\FormBuilder;
use Symfony\Component\HttpFoundation\File\File;
/**
 * Class CustomProvider
 * @package Application\Sonata\MediaBundle\Provider
 */
class CustomProvider extends FileProvider
{
    /**
     * @param MediaInterface $media
     */
    protected function doTransform(MediaInterface $media)
    {
         // ...
    }
    /**
     * {@inheritdoc}
     */
    public function generatePublicUrl(MediaInterface $media, $format)
    {
        // new logic
    }
    /**
     * {@inheritdoc}
     */
    public function postPersist(MediaInterface $media)
    {
    }
    /**
     * {@inheritdoc}
     */
    public function postUpdate(MediaInterface $media)
    {
    }
}
Updated sonata configuration:
// app/config/sonata/sonata_media.yml
sonata_media:
        ...
        product:
            providers:
                - sonata.media.provider.image
                - sonata.media.provider.custom
            formats:
                small: { width: 40 , quality: 100}
        ...
And I've also setup DI extension to autoload services.yml
I made a PR to update outdated documentation.