Comparing online Hyper-parameter tuning variants.

Benchmarking performance of various hyper-parameter tuning algorithms

Assume Rewards are user click reciprocal ranks (continous real reward).

Table of Contents

• Comparing online Hyper-parameter tuning variants.
• Table of Contents
  • Criteria for Implementation
  • Algorithm Variants
  • Variants / Research for Prototyping
  • Testing
  • Results Preview

Criteria for Implementation

• Sample efficiency
• Latency
• Ease of implementation

Algorithm Variants

• Thompson Sampler with Guassian posterior and Normal-Inverse Gamma priors.
• Random Asynchronous Successive Halving Algorithm
• Factorized Thompson Sampling which assumes hyper-params are low co-variance, use Guassian Process if interactions are expected.
• Top-Two Thompson Sampling
• Population Based Search

Variants / Research for Prototyping

• CMA-ES with margin
  • And Other variants
• Streaming Sparse Gaussian Process Approximations
• Limited-Memory Matrix Adaptation for Large Scale Black-box Optimization
• Illuminating search spaces by mapping elites

Testing

$ python test.py

Results Preview

Number of arms: 750
Real known best arm: 318
Best combination: [30.   0.2  4.   4. ]
CTR: 0.1765
Thread CTR: 0.1213


                                 PopulationBasedSearch
┏━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━┳━━━━━━━━━━━━━━┓                                                                                                    
┃ #samples ┃ Predicted Best arm ┃ Rank of predicted best arm ┃ Top %ile ┃ Total Regret ┃                                                                                                    
┡━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━╇━━━━━━━━━━━━━━┩                                                                                                    
│ 100      │ 11                 │ 314                        │ 41.8667  │ -0.9993      │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 1000     │ 531                │ 309                        │ 41.2000  │ 28.0397      │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 5000     │ 560                │ 497                        │ 66.2667  │ 75.7364      │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 10000    │ 515                │ 111                        │ 14.8000  │ 258.6546     │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 50000    │ 707                │ 42                         │ 5.6000   │ 1068.1392    │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 100000   │ 128                │ 188                        │ 25.0667  │ 2314.0023    │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 500000   │ 382                │ 156                        │ 20.8000  │ 10207.3045   │                                                                                                    
└──────────┴────────────────────┴────────────────────────────┴──────────┴──────────────┘                                                                                                    
                      RandomAsynchronousSuccessiveHalvingAlgorithm
┏━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━┳━━━━━━━━━━━━━━┓                                                                                                    
┃ #samples ┃ Predicted Best arm ┃ Rank of predicted best arm ┃ Top %ile ┃ Total Regret ┃                                                                                                    
┡━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━╇━━━━━━━━━━━━━━┩                                                                                                    
│ 100      │ 78                 │ 574                        │ 76.5333  │ 4.4953       │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 1000     │ 635                │ 291                        │ 38.8000  │ 26.2129      │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 5000     │ 514                │ 60                         │ 8.0000   │ 105.5652     │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 10000    │ 589                │ 212                        │ 28.2667  │ 257.8797     │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 50000    │ 103                │ 13                         │ 1.7333   │ 1168.7754    │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 100000   │ 316                │ 130                        │ 17.3333  │ 2345.0638    │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 500000   │ 64                 │ 3                          │ 0.4000   │ 12650.9991   │                                                                                                    
└──────────┴────────────────────┴────────────────────────────┴──────────┴──────────────┘                                                                                                    
                                      UCB1Sampler     
┏━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━┳━━━━━━━━━━━━━━┓                                                                                                    
┃ #samples ┃ Predicted Best arm ┃ Rank of predicted best arm ┃ Top %ile ┃ Total Regret ┃                                                                                                    
┡━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━╇━━━━━━━━━━━━━━┩                                                                                                    
│ 100      │ 56                 │ 146                        │ 19.4667  │ 2.7814       │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 1000     │ 126                │ 79                         │ 10.5333  │ 24.2011      │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 5000     │ 421                │ 241                        │ 32.1333  │ 114.5895     │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 10000    │ 270                │ 51                         │ 6.8000   │ 224.8316     │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 50000    │ 88                 │ 40                         │ 5.3333   │ 1203.3186    │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 100000   │ 196                │ 36                         │ 4.8000   │ 2483.5763    │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 500000   │ 244                │ 12                         │ 1.6000   │ 11322.4899   │                                                                                                    
└──────────┴────────────────────┴────────────────────────────┴──────────┴──────────────┘                                                                                                    
                               FactorizedThompsonSampler          
┏━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━┳━━━━━━━━━━━━━━┓                                                                                                    
┃ #samples ┃ Predicted Best arm ┃ Rank of predicted best arm ┃ Top %ile ┃ Total Regret ┃                                                                                                    
┡━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━╇━━━━━━━━━━━━━━┩                                                                                                    
│ 100      │ 640                │ 25                         │ 3.3333   │ 5.9946       │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 1000     │ 649                │ 297                        │ 39.6000  │ 22.6687      │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 5000     │ 371                │ 44                         │ 5.8667   │ 66.3130      │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 10000    │ 682                │ 192                        │ 25.6000  │ 249.6314     │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 50000    │ 512                │ 7                          │ 0.9333   │ 653.9620     │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 100000   │ 512                │ 7                          │ 0.9333   │ 728.0627     │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 500000   │ 676                │ 68                         │ 9.0667   │ 3182.1269    │                                                                                                    
└──────────┴────────────────────┴────────────────────────────┴──────────┴──────────────┘                                                                                                    
                           NormalInverseGammaThompsonSampler      
┏━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━┳━━━━━━━━━━━━━━┓                                                                                                    
┃ #samples ┃ Predicted Best arm ┃ Rank of predicted best arm ┃ Top %ile ┃ Total Regret ┃                                                                                                    
┡━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━╇━━━━━━━━━━━━━━┩                                                                                                    
│ 100      │ 381                │ 171                        │ 22.8000  │ -3.3944      │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 1000     │ 687                │ 459                        │ 61.2000  │ 37.7738      │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 5000     │ 133                │ 120                        │ 16.0000  │ 171.6365     │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 10000    │ 439                │ 52                         │ 6.9333   │ 139.6900     │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 50000    │ 704                │ 123                        │ 16.4000  │ 968.4361     │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 100000   │ 511                │ 84                         │ 11.2000  │ 2090.4056    │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 500000   │ 64                 │ 3                          │ 0.4000   │ 7188.7645    │                                                                                                    
└──────────┴────────────────────┴────────────────────────────┴──────────┴──────────────┘                                                                                                    
                        TopTwoNormalInverseGammaThompsonSampler   
┏━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━┳━━━━━━━━━━━━━━┓                                                                                                    
┃ #samples ┃ Predicted Best arm ┃ Rank of predicted best arm ┃ Top %ile ┃ Total Regret ┃                                                                                                    
┡━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━╇━━━━━━━━━━━━━━┩                                                                                                    
│ 100      │ 102                │ 119                        │ 15.8667  │ 6.4490       │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 1000     │ 695                │ 738                        │ 98.4000  │ 41.5832      │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 5000     │ 44                 │ 380                        │ 50.6667  │ 167.3407     │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 10000    │ 288                │ 684                        │ 91.2000  │ 310.8385     │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 50000    │ 655                │ 113                        │ 15.0667  │ 1188.3919    │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 100000   │ 124                │ 38                         │ 5.0667   │ 2129.6981    │                                                                                                    
├──────────┼────────────────────┼────────────────────────────┼──────────┼──────────────┤                                                                                                    
│ 500000   │ 304                │ 9                          │ 1.2000   │ 7507.7635    │                                                                                                    
└──────────┴────────────────────┴────────────────────────────┴──────────┴──────────────┘