Data-driven Algorithm Selection and Parameter Tuning: Two Case studies in Optimization and Signal Processing

Jesús A. De Loera, Jamie Haddock, Anna Ma, Deanna NeedellarXiv 2019 · arXiv

Abstract

This paper explores the application of simple neural networks to the "Algorithm Selection Problem" in signal processing and optimization. Instead of using optimization to train models, we use shallow neural networks to choose the best optimization algorithms and parameters for a given task. By treating algorithm selection as a classification problem, we demonstrate that "meta-learning" can significantly outperform "one-size-fits-all" heuristics in compressed sensing and stochastic gradient descent.

1. Introduction

In signal processing and mathematical optimization, there is rarely a single "best" algorithm. The performance of a method often depends heavily on the specific characteristics of the input data—a phenomenon known as the "no free lunch" theorem. Currently, practitioners rely on human expertise or computationally expensive brute-force searches to tune parameters. This work addresses the "Algorithm Selection Problem": can we train a machine learning model to automatically recommend the most effective tool or parameter setting for a given problem instance?

2. Methodology

We present two case studies using shallow Neural Networks (NNs) to perform "meta-optimization."

2.1 Case Study I: Compressed Sensing Algorithm Selection

Compressed sensing aims to recover a sparse signal from relatively few measurements. We evaluate three greedy algorithms: HTP, NIHT, and CSMPSP. The task is to predict whether a specific algorithm will successfully recover a signal based on the problem's "phase transition" parameters: $\delta$ (sampling rate) and $\rho$ (sparsity rate). We employ a tiny neural network with two hidden layers (3 and 9 nodes). The first layer identifies the matrix type, and the second classifies success vs. failure.

2.2 Case Study II: SGD Learning Rate Selection

For Stochastic Gradient Descent (SGD), we aim to determine the optimal learning rate schedule—either constant or epoch-based decaying—for a given linear system. A neural network with one hidden layer (30 nodes) takes the measurement vector $y$ as input and predicts the optimal schedule.

3. Datasets and Experimental Setup

The study utilizes both synthetic and real-world datasets:

  • Compressed Sensing: 2,241 samples using Gaussian, Sparse, and Discrete Cosine Transform (DCT) measurement matrices.
  • Synthetic Linear Systems: 3,000 systems designed to favor different learning rate schedules.
  • CT/MNIST: A real-world dataset where measurement matrices represent CT scans and signals are images from the MNIST database.

4. Results and Discussion

The neural networks achieved high accuracy (96.3% to 96.9%) in predicting recovery success for compressed sensing. As illustrated in Figures 1 and 2, the meta-learners effectively capture the geometry of the phase transition boundaries (the "breaking points" of the algorithms) with high precision across different matrix types.

Figure 1: Comparison of ground truth success regions (top) and neural network classification results (bottom) for three measurement matrix types in compressed sensing.
Figure 2: Phase transition prediction results for an alternative greedy algorithm, demonstrating the robustness of the meta-learning approach.

In the SGD experiments, the "NN Predicted" learning rate consistently resulted in lower average recovery errors compared to fixed heuristics. Visual validation on the CT/MNIST task confirmed that the network correctly identifies system inconsistency and applies the appropriate schedule, leading to clearer reconstructions.

5. Conclusion

This research demonstrates that algorithm selection does not require massive computational overhead; simple neural networks can learn "bespoke" heuristics tailored to specific data distributions. While future work must address the estimation of unknown meta-features and scalability to non-convex objectives, this approach offers a promising path toward self-improving optimization software.

Summary updated

Abstract

Machine learning algorithms typically rely on optimization subroutines and are well-known to provide very effective outcomes for many types of problems. Here, we flip the reliance and ask the reverse question: can machine learning algorithms lead to more effective outcomes for optimization problems? Our goal is to train machine learning methods to automatically improve the performance of optimization and signal processing algorithms. As a proof of concept, we use our approach to improve two popular data processing subroutines in data science: stochastic gradient descent and greedy methods in compressed sensing. We provide experimental results that demonstrate the answer is ``yes'', machine learning algorithms do lead to more effective outcomes for optimization problems, and show the future potential for this research direction.
BibTeX
@misc{loera2019data,
  author = {Jesús A. De Loera and Jamie Haddock and Anna Ma and Deanna Needell},
  title = {{Data-driven Algorithm Selection and Parameter Tuning: Two Case studies in Optimization and Signal Processing}},
  year = {2019},
  eprint = {1905.13404},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1905.13404},
}
Figure