Randomized Optimization on Discrete Landscapes and Neural Networks

Introduction

There is a whole world of optimization that begins where gradients fail. Rugged objectives, deceptive local maxima, noisy evaluations—these are the domains where simple calculus runs out of road and heuristic search takes over. This post is a concept-first look at how three randomized methods navigate those landscapes and when each shines in practice.

I focus on the underlying ideas covered in the second assignment for Georgia Tech’s Machine Learning course. These cover what shapes of search spaces favor simulated annealing over hill climbing, why genetic algorithms thrive on recombinable structure, and how any of these can stand in for backprop when tuning a small neural network.

Overview

Randomized optimization provides practical strategies for navigating rugged objective functions when gradients are unavailable or unhelpful. This piece compares three local/heuristic search methods:

• Randomized Hill Climbing (RHC)
• Simulated Annealing (SA)
• Genetic Algorithm (GA)

Looking at how these behave on common landscape archetypes and consider how they can stand in for gradient methods when searching continuous neural network weight spaces.

Canonical Problem Archetypes

1. Discrete landscape with deceptive local structure: A rugged objective with many local maxima and a single narrow global basin. This stresses exploitation vs. controlled exploration.

2. Discrete landscape with compositional substructures: A building-block objective where good partial solutions can be recombined. This emphasizes recombination and population diversity.

3. Neural network weight optimization: Replace backprop with RHC/SA/GA to minimize classification loss on a small task. Evaluate training loss, validation accuracy, wall-clock time, and sample efficiency.