Source-linked AI summary
A PAC Approach to Application-Specific Algorithm Selection
Rishi Gupta, Tim Roughgarden
TL;DR
Algorithm choice depends on application-specific inputs that may be hard to formalize, yet theoretical analysis of selection has lagged behind empirical work. The paper applies statistical and online learning frameworks to this problem, showing that many algorithm classes have small pseudo-dimension and that online no-regret learning has both worst-case barriers and positive results under smoothed assumptions.
Problem
Application-relevant inputs can have domain-specific features that defy formalization, while theoretical analysis of algorithm selection has lagged behind empirical work.
Source: §1 · pp. 1–2Method
The paper models application-specific algorithm selection using statistical learning and online regret-minimization frameworks.
Source: §1 · p. 2Results
Many useful algorithm families have small pseudo-dimension and low generalization error; worst-case no-regret online learning is precluded for natural non-Lipschitz classes, with positive results under smoothed-analysis-type assumptions.
Source: §1 · p. 2Takeaways & Limitations
Learning-theory dimension notions apply to algorithm families beyond prediction-function classes and help formalize their simplicity.
Source: §1 · p. 2Pseudo-dimension is not unconditionally a simplicity measure: even the optimal-only class has dimension 1; its relevance is qualified to NP-hard problems with polynomial-time algorithms, assuming P≠NP.
Source: §3.3.3 · p. 10
Abstract
from arXiv · showhide
The best algorithm for a computational problem generally depends on the "relevant inputs," a concept that depends on the application domain and often defies formal articulation. While there is a large literature on empirical approaches to selecting the best algorithm for a given application domain, there has been surprisingly little theoretical analysis of the problem. This paper adapts concepts from statistical and online learning theory to reason about application-specific algorithm selection. Our models capture several state-of-the-art empirical and theoretical approaches to the problem, ranging from self-improving algorithms to empirical performance models, and our results identify conditions under which these approaches are guaranteed to perform well. We present one framework that models algorithm selection as a statistical learning problem, and our work here shows that dimension notions from statistical learning theory, historically used to measure the complexity of classes of binary- and real-valued functions, are relevant in a much broader algorithmic context. We also study the online version of the algorithm selection problem, and give possibility and impossibility results for the existence of no-regret learning algorithms.
1 Introduction
Algorithm performance can be incomparable across inputs, while application-relevant instances often have domain-specific features that are difficult to formalize. The paper uses learning theory to analyze application-specific algorithm selection, including statistical and online approaches.
1 Introduction
- Algorithm performance can be incomparable across inputs, so a single worst-case or average-case summary is often used to advocate one algorithm over another.Source: §1 · p. 1
- Application-specific selection targets instances of interest whose domain-specific features often defy formal articulation, despite extensive empirical work and limited theoretical analysis.Worst-case analysis is deliberately application-agnostic, one possible explanation for the theoretical gap.Source: §1 · pp. 1–2
- The paper models application-specific algorithm selection as learning and captures existing approaches from self-improving algorithms to empirical performance models.Source: §1 · p. 2
- Small pseudo-dimension for many useful algorithm families, including broad greedy and local-search classes, implies low generalization error and extends learning-theory dimensions beyond prediction functions.The paper also presents this as a way to formalize the often-mentioned notion of algorithm-family simplicity.Source: §1 · p. 2
- Worst-case no-regret online learning is precluded by non-Lipschitz behavior in natural algorithm classes, while smoothed-analysis-type assumptions yield positive results.Source: §1 · p. 2
2 Motivating Scenarios
The motivating scenarios span domain-specific heuristic choice, algorithms that adapt to an input distribution, parameter tuning, and per-instance selection using performance models.
2 Motivating Scenarios
- The framework interprets approaches to learning good algorithms from data across disparate application domains, alongside a few prior uses of learning-theory dimensions beyond prediction functions.Source: §2 · p. 2
2.1 Example #1: Greedy Heuristic Selection
- The FCC spectrum reverse auction uses a greedy heuristic to order station removals, with its specific implementation justified by experiments on synthetic instances thought representative.The auction’s repacking constraints resemble independent-set and graph-coloring problems, and the paper’s results can provide a post hoc justification for exhaustive selection among sufficiently simple heuristic classes.Source: §2.1 · p. 3
2.2 Example #2: Self-Improving Algorithms
- Self-improving algorithms learn from i.i.d. samples of an unknown instance distribution and aim to converge to its optimal algorithm using little auxiliary space.For sorting, the cited approach has expected running time within a constant factor of an information-theoretically optimal algorithm after polynomially many samples.Source: §2.2 · p. 3
2.3 Example #3: Parameter Tuning in Optimization and Machine Learning
- Choosing optimization and machine-learning parameters is challenging; the paper’s gradient-descent analysis can be interpreted as a sample-complexity analysis of grid search over step sizes.The motivating examples include gradient descent’s step size and error tolerance and CPLEX’s 135 parameters.Source: §2.3 · p. 4
2.4 Example #4: Empirical Performance Models for SAT Algorithms
- For SAT, empirical performance models predict each solver’s running time from instance features, enabling selection of the solver with the smallest predicted time.The cited SATzilla approach used labeled training data and regression models, and won numerous medals at the 2007 SAT Competition.Source: §2.4 · p. 4
3 PAC Learning an Application-Specific Algorithm
This section frames application-specific algorithm choice as learning an optimal algorithm for an unknown instance distribution and develops the framework across several algorithm-selection settings.
3 PAC Learning an Application-Specific Algorithm
- The section formulates selecting the best algorithm for a poorly understood domain as learning an optimal algorithm under an unknown instance distribution.Source: §3 · p. 5
- It bounds pseudo-dimension for classes of greedy and local-search heuristics.Source: §3 · p. 5
- Applications include reinterpreting self-improving algorithms, modeling empirical performance models and feature-based selection, and studying gradient-descent step-size selection.Source: §3 · p. 5
3.1 The Basic Model
The basic model represents application-specific algorithm selection as learning from samples drawn from an unknown input distribution, with performance measured by a chosen cost function.
3.1 The Basic Model
- The model specifies a computational or optimization problem, a set of algorithms for it, and a performance cost bounded in [0, H].Cost can measure running time or, for optimization, the objective value of the produced solution.Source: §3.1 · p. 5
- An unknown input distribution encodes application-specific information, and the optimal algorithm minimizes or maximizes expected cost as appropriate.Source: §3.1 · p. 5
- The learning algorithm receives i.i.d. input samples and their algorithm costs, then selects an algorithm for future inputs from the same distribution.Source: §3.1 · p. 5
- An algorithm (ε, δ)-learns the optimum if, for every input distribution, it outputs an algorithm with error at most ε with probability at least 1−δ.Source: §3.1 · p. 5
3.2 Pseudo-Dimension and Uniform Convergence
Section 3.2 treats each algorithm as a real-valued performance function and uses pseudo-dimension to connect learning the best algorithm to estimating performance from samples.
3.2 Pseudo-Dimension and Uniform Convergence
- Pseudo-dimension measures how many input samples a real-valued function class can shatter using thresholds, extending VC dimension beyond binary-valued functions.Bounding it is sufficient to bound sample complexity for estimating the expectation of every function in the class.Source: §3.2 · p. 6
- Each algorithm is represented by its cost function over instances, and an ERM procedure returns an algorithm with the best average performance on a finite sample.For a finite algorithm class, brute force provides a straightforward ERM procedure.Source: §3.2 · p. 6
- For a class with pseudo-dimension d, any ERM (2ϵ, δ)-learns its optimal algorithm from the sample count specified by the paper’s bound.The bound applies to fixed instances and performance measure.Source: §3.2 · p. 7
- The paper emphasizes sample complexity rather than ERM’s computational efficiency, though its examples admit ERM under mild assumptions.An infinite class need not have an ERM algorithm a priori.Source: §3.2 · p. 7
3.3 Application: Greedy Heuristics and Extensions
The section formalizes parameterized greedy heuristics and bounds their pseudo-dimension, then extends the analysis to multiple choices, multiple parameters, and local search.
3.3.1 Definitions and Examples
- The model treats inputs as objects with attributes and feasible assignments, while parameterized scoring rules rank unassigned objects for greedy assignment.κ-crossing bounds score ties across parameter values, and β-bounded assignment rules limit each object's distinct attribute values.Source: §3.3.1 · pp. 8–9
3.3.2 Upper Bound on Pseudo-Dimension
- A (κ, β)-single-parameter family of greedy heuristics has pseudo-dimension O(log(κβn)); the running examples have pseudo-dimension O(log n).This applies to broad classes of greedy heuristics, including the section’s object-assignment examples.Source: §3.3.2 · p. 9
3.3.3 Computational Considerations
- For polynomial κ and β, comparison-induced intervals yield a polynomial-time ERM when each algorithm in the family runs in polynomial time.The proof enumerates relevant comparisons and searches over representative algorithms from the resulting intervals.Source: §3.3.3 · p. 10
3.3.4 Extensions: Multiple Algorithms, Multiple Parameters, and Local Search
- Choosing the best of q family members gives pseudo-dimension O(q log(κβn)), while multi-parameter families use a multivariate crossing bound.The crossing parameter is tied to connected components of the co-zero set of score differences.Source: §3.3.4 · p. 11
- For a four-vertex MWIS swap score, the family is 3-crossing and the natural assignment rule is n^4-bounded.The degree term may use original degree or specified residual-degree variants.Source: §3.3.4 · p. 12
- A (κ, β)-single-parameter family of k-swap local search heuristics has pseudo-dimension O(k log(κβn)).The analysis extends greedy scoring and assignment rules to subsets of up to k objects.Source: §3.3.4 · p. 12
3.4 Application: Self-Improving Algorithms Revisited
The section reinterprets self-improving sorting through PAC learning of bucket-based algorithms, bounding the class complexity and the samples needed to learn a near-optimal sorter.
3.4 Application: Self-Improving Algorithms Revisited
- The reinterpretation combines low representation error for independent entries with small pseudo-dimension, while general correlated-input distributions fall outside the low-representation-error guarantee.The paper contrasts its ˜O(n^(1+c)) bound for arbitrary distributions, including correlated entries, with the ˜O(n^c) bound in for independent entries.Source: §3.4 · pp. 12–14
- For independently distributed array elements, a bucket-based sorter achieves expected running time within a constant factor of the optimal sorter for their product distribution.The construction uses n buckets, InsertionSort within each bucket, and compact search trees for bucket placement.Source: §3.4 · p. 13
- Bucket-based sorting algorithms with search trees of size O(n^c) have pseudo-dimension O(n^(1+c)).The bound follows by counting the distinct sample labelings induced by bucket boundaries and search-tree choices.Source: §3.4 · p. 13
- The resulting sample complexity is ˜O(n^(1+c)) for learning the optimal algorithm in the class, with H taken as the ratio of maximum to minimum running time.The analysis assumes a maximum running time of O(n log n), with MergeSort as a safe fallback if an algorithm exceeds that bound.Source: §3.4 · pp. 13–14
3.5 Application: Feature-Based Algorithm Selection
The section extends algorithm selection from one algorithm per domain to choices based on instance features. It bounds the complexity of selection maps and performance predictors, while taking feature and predictor choices as given.
3.5 Application: Feature-Based Algorithm Selection
- When array elements are dependent, the sorting theorem fails, and the best bucket-based algorithm may be more than a constant factor worse than optimal.Source: §3.5 · p. 14
- The model takes the feature set and feature map as given, and expected predictor loss depends on the chosen predictor, features, and map.Defining a good feature set is described as challenging and outside the model.Source: §3.5 · pp. 14–15
- For finite F, guarantees extend with linear |F| degradation, and selection-map pseudo-dimension is at most |F|d when algorithms have pseudo-dimension d.Bounding this dimension bounds sample complexity; for finite G, a general upper bound is log2 |G|.Source: §3.5 · pp. 14–15
- With large or infinite F, the model can learn a performance predictor for each algorithm, reducing each task to regression over instance features.The predictor is chosen from P to minimize a specified loss; squared error is a common choice.Source: §3.5 · p. 15
- Linear predictors over d-dimensional instance features have pseudo-dimension at most d.The stated sample-complexity bound for bounded linear predictors is ˜O(H^4 d/ϵ^2).Source: §3.5 · pp. 15–16
- Regression trees with at most ℓ nodes over d-dimensional features have pseudo-dimension O(ℓlog(ℓd)), supporting near-optimal predictor learning with small sample complexity.Each tree node tests an inequality on one feature.Source: §3.5 · p. 16
- For many possible algorithms, predictors can use both algorithm and instance features; linear predictors then have pseudo-dimension d + d′.Here d and d′ are the dimensions of the instance-feature and algorithm-feature sets.Source: §3.5 · p. 16
3.6 Application: Choosing the Step Size in Gradient Descent
The section studies learning a gradient-descent step size that minimizes expected iteration count. Under stated function and initial-point conditions, discretization yields a finite-sample guarantee for a nearly optimal step size.
3.6 Application: Choosing the Step Size in Gradient Descent
- Step-size selection minimizes expected iteration count: larger ρ may progress faster but risks overshooting, and the analysis interprets the result as a sample-complexity guarantee for grid search.Source: §3.6.1 · p. 17
3.6.1 Gradient Descent Preliminaries
- The guarantee assumes convex, L-smooth functions, bounded initial-point norms, and guaranteed progress for every allowed step size.Under these restrictions, the paper states that a nearly optimal step size can be computed from a reasonable number of samples.Source: §3.6.1 · p. 17
- L-smoothness makes a fixed-step gradient update Lipschitz in its current point, even when ρ exceeds 2/L.The bound is ∥g(w, ρ) − g(y, ρ)∥ ≤ D(ρ)∥w − y∥.Source: §3.6.1 · pp. 17–18
3.6.3 Learning the Best Step Size
- m = ˜O(H^3/ϵ^2) samples suffice to (1 + ϵ, δ)-learn the optimal step-size algorithm.Source: §3.6.3 · p. 19
4 Online Learning of Application-Specific Algorithms
The section studies online application-specific algorithm selection, where algorithms are chosen sequentially against an unknown instance sequence. It shows that worst-case no-regret learning can fail for MWIS heuristics, while smoothed instances admit an efficient low-regret learner.
4.1 The Online Learning Model
- The online model chooses an algorithm using only past instances and measures average performance loss against the best fixed algorithm in hindsight.Unlike the batch setup, it uses an instance sequence rather than an unknown distribution; finite algorithm sets already have standard no-regret methods.Source: §4 · p. 19, §4.1 · p. 20
4.2.1 A Hard Example for MWIS
- For any constants 0 < r < s < 1, there is an MWIS instance x on at most n vertices with cost(Aρ, x) = 1 for ρ ∈ (r, s), and cost(Aρ, x) = o_n(1) when ρ < r or ρ > s.Source: §4.2.1 · p. 21
4.2 An Impossibility Result for Worst-Case Instances
- For worst-case MWIS sequences, every online algorithm has expected regret 1 − o_n(1) under a distribution on input sequences.The lower bound applies to the parameterized family of MWIS heuristics, which lacks a Lipschitz condition for controlling performance of nearby algorithms.Source: §4.2 · p. 20, §4.2.1 · p. 22
4.3 A Smoothed Analysis
- The smoothed setting keeps arbitrary MWIS graphs but draws each vertex weight from a distribution with density at most σ^-1 on [0, 1].As σ approaches zero, the model returns to the worst-case setting; the paper considers σ bounded below by an inverse polynomial in n.Source: §4.3 · p. 22
4.3.1 A Low-Regret Algorithm for σ-Smooth MWIS
- A finite q-net of heuristic parameters supports learning because, with high probability, each heuristic matches a net member on the observed smoothed instances.The strategy applies a finite-action no-regret algorithm to the net; the proof controls how closely transition points can occur.Source: §4.3 · p. 22, §4.3.1 · pp. 23–24
- For σ-smooth MWIS sequences, an online learner runs in poly(n, σ^-1) time and achieves expected regret at most poly(n^-1).This is low regret in n, not the no-regret condition requiring regret to vanish as T grows.Source: §4.3 · p. 22, §4.3.1 · p. 24
5 Conclusions and Future Directions
The conclusion frames the work as an initial theoretical step on application-specific algorithm selection. It identifies open questions about learnable algorithm classes, computation, complexity measures, and instance features.
5 Conclusions and Future Directions
- The paper formulates algorithm selection as learning an algorithm or algorithm sequence from an unknown distribution or input sequence, and reports small pseudo-dimension for many studied algorithm classes.It concludes that near-optimal algorithms can be learned from relatively modest data, while worst-case no-regret online guarantees are impossible and good online learning exists in a natural smoothed model.Source: §5 · p. 25
- An open question is which problems have algorithm classes with both low representation error and small pseudo-dimension.The conclusion also asks how to choose instance features to minimize representation error.Source: §5 · p. 25
- The conclusion asks which algorithm classes are learnable online and when near-optimal algorithms can be learned with polynomial computation rather than brute-force search.It also raises possible conditional lower bounds for when brute-force search is necessary.Source: §5 · p. 25
- The relationship between statistical learning measures of algorithm-class complexity and traditional computational complexity remains open.Source: §5 · p. 25
A A Bad Example for Gradient Descent
The appendix constructs gradient-descent instances whose performance varies with the step-size parameter. This yields a function class with infinite pseudo-dimension, even under smoothness conditions.
A A Bad Example for Gradient Descent
- The construction parameterizes functions by finite subsets of [0, 1] and fixes a common initial point for gradient descent.The first step places the iterate in either a flat black area or a sloped blue area.Source: A A Bad Example for Gradient Descent · p. 28
- Landing in the flat black area makes gradient descent stop immediately with cost 1, while landing in the sloped blue area yields cost ≫1.Source: A A Bad Example for Gradient Descent · p. 28
- The resulting function class can shatter any finite subset of (ρℓ, ρu), so it has infinite pseudo-dimension, including after modifications making its functions continuously differentiable and L-smooth.Source: A A Bad Example for Gradient Descent · p. 28