An anonymous inner class (AIC) can be used to create a subclass of an abstract class or a concrete class. An AIC can also provide a concrete implementation of an interface, including the addition of state (fields). An instance of an AIC can be referred to using this in its method bodies, so further methods can be called on it, its state can be mutated over time, etc. None of these apply to lambdas.

I'd guess that the majority of uses of AICs were to provide stateless implementations of single functions and so can be replaced with lambda expressions, but there are other uses of AICs for which lambdas cannot be used. AICs are here to stay.

UPDATE

Another difference between AICs and lambda expressions is that AICs introduce a new scope. That is, names are resolved from the AIC's superclasses and interfaces and can shadow names that occur in the lexically enclosing environment. For lambdas, all names are resolved lexically.

Oracle has posted a study comparing performance between Lambdas and anonymous classes

See JDK 8: Lambda Performance Study by Sergey Kuksenko, which is 74 slides long.

Summary: slow to warm up but when JIT inlines it worst case just as fast as anonymous class but can be faster.

UPDATE

A few comments wondering if my benchmark at the bottom was flawed - after introducing a lot of randomness (to prevent the JIT from optimising too much stuff), I still get similar results so I tend to think it is ok.

In the meantime, I have come across this presentation by the lambda implementation team. Page 16 shows some performance figures: inner classes and closures have similar performance / non-capturing lambda are up to 5x times faster.

And @StuartMarks posted this JVMLS 2013 talk from Sergey Kuksenko on lambda performance. The bottom line is that post JIT compilation, lambdas and anonymous classes perform similarly on current Hostpot JVM implementations.

YOUR BENCHMARK

I have also run your test, as you posted it. The problem is that it runs for as little as 20 ms for the first method and 2 ms for the second. Although that is a 10:1 ratio, it is in no way representative because the measurement time is way too small.

I have then taken modified your test to allow for more JIT warmup and I get similar results as with jmh (i.e. no difference between anonymous class and lambda).

public class Main {

    static interface ICallback {
        void payload();
    }
    static void measureAnonymousClass() {
        final int arr[] = {0};
        ICallback clb = new ICallback() {
            @Override
            public void payload() {
                arr[0]++;
            }
        };
        clb.payload();
    }
    static void measureLambda() {
        final int arr[] = {0};
        ICallback clb = () -> {
            arr[0]++;
        };
        clb.payload();
    }
    static void runTimed(String message, Runnable act) {
        long start = System.nanoTime();
        for (int i = 0; i < 10_000_000; i++) {
            act.run();
        }
        long end = System.nanoTime();
        System.out.println(message + ":" + (end - start));
    }
    public static void main(String[] args) {
        runTimed("as lambdas", Main::measureLambda);
        runTimed("anonymous class", Main::measureAnonymousClass);
        runTimed("as lambdas", Main::measureLambda);
        runTimed("anonymous class", Main::measureAnonymousClass);
        runTimed("as lambdas", Main::measureLambda);
        runTimed("anonymous class", Main::measureAnonymousClass);
        runTimed("as lambdas", Main::measureLambda);
        runTimed("anonymous class", Main::measureAnonymousClass);
    }
}

The last run takes about 28 seconds for both methods.

JMH MICRO BENCHMARK

I have run the same test with jmh and the bottom line is that the four methods take as much time as the equivalent:

void baseline() {
    arr[0]++;
}

In other words, the JIT inlines both the anonymous class and the lambda and they take exactly the same time.

Results summary:

Benchmark                Mean    Mean error    Units
empty_method             1.104        0.043  nsec/op
baseline                 2.105        0.038  nsec/op
anonymousWithArgs        2.107        0.028  nsec/op
anonymousWithoutArgs     2.120        0.044  nsec/op
lambdaWithArgs           2.116        0.027  nsec/op
lambdaWithoutArgs        2.103        0.017  nsec/op

Oracle has a presentation covering some of the performance differences. It appears that there are quite a few factors that impact performance of lambdas vs. anonymous classes.

http://www.oracle.com/technetwork/java/jvmls2013kuksen-2014088.pdf

You are obviously encountering the first-time initialization overhead of lambda expressions. As already mentioned in the comments, the classes for lambda expressions are generated at runtime rather than being loaded from your class path.

However, being generated isn’t the cause for the slowdown. After all, generating a class having a simple structure can be even faster than loading the same bytes from an external source. And the inner class has to be loaded too. But when the application hasn’t used lambda expressions before¹, even the framework for generating the lambda classes has to be loaded (Oracle’s current implementation uses ASM under the hood). This is the actual cause of the slowdown, loading and initialization of a dozen internally used classes, not the lambda expression itself².

You can easily verify this. In your current code using lambda expressions, you have two identical expressions (i1, i2) -> Integer.compare(i1.start, i2.start). The current implementation doesn’t recognize this (actually, the compiler doesn’t provide a hint neither). So here, two lambda instances, having even different classes, are generated. You can refactor the code to have only one comparator, similar to your inner class variant:

final Comparator<? super Interval> comparator
  = (i1, i2) -> Integer.compare(i1.start, i2.start);
int start = Collections.binarySearch(intervals, newInterval, comparator);
int skip = start >= 0 ? start : -start - 1;
int end = Collections.binarySearch(intervals.subList(skip, intervals.size()),
                                   new Interval(newInterval.end, 0),
                                   comparator);

You won’t notice any significant performance difference, as it’s not the number of lambda expressions that matters, but just the class loading and initialization of the framework, which happens exactly once.

You can even max it out by inserting additional lambda expressions like

final Comparator<? super Interval> comparator1
    = (i1, i2) -> Integer.compare(i1.start, i2.start);
final Comparator<? super Interval> comparator2
    = (i1, i2) -> Integer.compare(i1.start, i2.start);
final Comparator<? super Interval> comparator3
    = (i1, i2) -> Integer.compare(i1.start, i2.start);
final Comparator<? super Interval> comparator4
    = (i1, i2) -> Integer.compare(i1.start, i2.start);
final Comparator<? super Interval> comparator5
    = (i1, i2) -> Integer.compare(i1.start, i2.start);

without seeing any slowdown. It’s really the initial overhead of the very first lambda expression of the entire runtime you are noticing here. Since Leetcode itself apparently doesn’t use lambda expressions before entering your code, whose execution time gets measured, this overhead adds to your execution time here.

See also “How will Java lambda functions be compiled?” and “Does a lambda expression create an object on the heap every time it's executed?”

¹ This implies that JDK code that will be executed before handing control over to your application doesn’t use lambda expressions itself. Since this code stems from times before the introduction of lambda expressions, this is usually the case. With newer JDKs, modular software will be initialized by different, newer code, which seems to use lambda expressions, so the initialization of the runtime facility can’t be measured within the application anymore in these setups.

² The initialization time has been reduced significantly in newer JDKs. There are different possible causes, general performance improvements, dedicated lambda optimizations, or both. Improving initialization time in general, is an issue that the JDK developers did not forget.