Adaptive Rejection Sampler

Adaptive Rejection Sampler

Overview

This skill provides guidance for implementing Adaptive Rejection Sampling (ARS) algorithms. ARS is a method for generating samples from log-concave probability distributions by constructing piecewise linear upper and lower envelopes of the log-density function. The skill focuses on procedural approaches, performance optimization, and verification strategies rather than providing implementation code.

When to Use This Skill

Use this skill when:

• Implementing adaptive rejection sampling from scratch
• Working with log-concave distribution samplers
• Building statistical sampling algorithms that require envelope construction
• Debugging or optimizing existing ARS implementations
• The task involves R, Python, or other statistical computing environments

Implementation Approach

Phase 1: Algorithm Design Before Coding

Before writing any code:

1. Understand the mathematical foundations

   • Review the ARS algorithm requirements for log-concave functions
   • Understand how piecewise linear envelopes are constructed from tangent lines
   • Identify the squeeze function optimization

2. Design with performance in mind

   • Plan iteration limits and safeguards from the start
   • Consider worst-case computational complexity of the sampling loop
   • Design for timeout constraints that may be stricter than development testing

3. Plan the module structure

   • Log-concavity verification module
   • Envelope construction and update module
   • Sampling loop with rejection logic
   • Initialization point selection

Phase 2: Critical Implementation Considerations

Log-Concavity Checking

When implementing log-concavity verification:

• Use appropriate tolerance values for numerical comparison
• Consider that some valid distributions have constant second derivatives (e.g., exponential distribution)
• Use <= tolerance instead of strict < comparisons when checking for non-positive second derivatives
• Test with edge cases like exponential, normal, and gamma distributions

Initialization Points

Proper initialization significantly affects sampling quality and performance:

• Handle shifted distributions by adjusting initialization points relative to the mode
• Consider the support bounds when selecting initial points
• Use multiple initial points to ensure good envelope coverage
• Test with distributions that have modes far from the origin

Iteration Limits and Safeguards

Critical for preventing infinite loops and timeouts:

• Implement maximum iteration limits in all sampling loops
• Add progress indicators or logging for long-running computations
• Include timeout protection mechanisms
• Design early exit conditions for convergence

Phase 3: Performance-First Development

Timeout Considerations

• External test frameworks may use shorter timeouts than development testing
• If development tests use 180-second timeouts, production may use 60 seconds
• Profile performance early to catch issues before they become blocking
• Test with varying timeout constraints to ensure robustness

Computational Efficiency

• Analyze the computational complexity of the sampling loop
• Optimize envelope updates to minimize recalculation
• Consider caching frequently computed values
• Profile with realistic sample sizes

Verification Strategies

Unit Testing Approach

1. Test each module independently

   • Log-concavity checker with known log-concave and non-log-concave functions
   • Envelope construction with simple distributions
   • Sampling loop with controlled random seeds

2. Test known distributions

   • Standard normal distribution
   • Exponential distribution (constant second derivative edge case)
   • Truncated normal distributions
   • Gamma distributions with various parameters

3. Test edge cases explicitly

   • Non-function inputs
   • Negative sample counts
   • Invalid bounds (lower > upper)
   • Very small and very large sample sizes

Performance Testing

• Match testing timeouts to expected production constraints
• Test worst-case behavior, not just average case
• Profile with different random seeds to catch stochastic failures
• Measure time per sample to identify performance degradation

Integration Testing

• Test the complete pipeline from input to samples
• Verify statistical properties of generated samples (mean, variance, distribution shape)
• Use statistical tests (KS test, chi-square) to verify sample quality
• Test with distributions that have known analytical moments

Common Pitfalls and Mistakes

Critical Mistakes to Avoid

1. Missing iteration limits

   • Always include maximum iteration safeguards in rejection sampling loops
   • An unbounded rejection loop will cause timeouts on difficult distributions

2. Inadequate performance testing

   • Development tests passing does not guarantee production success
   • Test with the same timeout constraints as the target environment

3. Tolerance issues in log-concavity checking

   • Strict inequality checks (< 0) may incorrectly reject valid distributions
   • Use tolerant comparisons (<= tolerance) for numerical stability

4. Poor initialization for shifted distributions

   • Hard-coded initialization points fail for distributions with non-zero modes
   • Always compute initialization relative to the distribution's characteristics

5. Incomplete file verification

   • After writing large code blocks, verify the complete content was written
   • Truncated files can cause subtle bugs

Debugging Approach

When tests fail or timeout:

1. Systematic debugging over trial-and-error

   • Understand root causes before implementing fixes
   • Use logging to identify where time is being spent

2. Isolate the problematic component

   • Test log-concavity checking separately
   • Test envelope construction separately
   • Test sampling loop with mock envelopes

3. Check for infinite loops

   • Add iteration counters to all loops
   • Log when iteration limits are approached
   • Verify exit conditions are reachable

Quality Checklist

Before considering the implementation complete:

• All sampling loops have maximum iteration limits
• Log-concavity checking uses appropriate tolerances
• Initialization points adapt to distribution characteristics
• Performance tested with target timeout constraints
• Edge cases for invalid inputs are handled
• Statistical properties of samples verified
• Code verified to be completely written (no truncation)
• Tested with multiple random seeds