Problem 486207 · medium · Level 04 Non-Linear Data Structures

Mini-Batches in a Reproducible Order

stochastic gradient descent · mini-batches · epochs · seeded shuffle · linear regression

A building's energy use is modelled as w·x + b from two daily features, and the model is trained by mini-batch gradient descent on the mean squared error: every step uses only a few days, which is cheaper than using all of them and still heads downhill on average. Every run must give exactly the same model, so the random order is fixed by a seed.

Write minibatch_sgd(X, y, lr, batch_size, epochs, seed) that returns (w, b, loss):

  1. Create rng = random.Random(seed) once. Start with all weights 0.0 and b = 0.0.
  2. For every epoch: make order = list(range(n)) and call rng.shuffle(order). Cut order into consecutive batches of batch_size indices (the last batch may be smaller).
  3. For every batch, in that order: compute the gradient of the mean squared error over the batch only (2·mean(e·x_j) and 2·mean(e) over the batch's examples, with e = w·x + b - y), then update all parameters with learning rate lr.
  4. After the last epoch, loss is the mean squared error of the final model over all of X.

The helper meter_readings(n, seed) returns (X, y) for n days, X[i] = [temperature, occupancy].

Examples

Input:  X = [[1], [2], [3], [4], [5]], y = [3, 5, 7, 9, 11], lr = 0.05, batch_size = 2, epochs = 1, seed = 0
Output: ([1.9369999999999998], 0.6955000000000001, 0.2514802500000001)
Explanation: random.Random(0) shuffles [0, 1, 2, 3, 4] into [2, 1, 0, 4, 3], so the batches are
the examples [2, 1], then [0, 4], then [3] on its own: three steps in one epoch.

Input:  the same data, batch_size = 5, epochs = 3, seed = 0
Output: ([2.122], 0.6100000000000001, 0.030343999999999833)
Explanation: one batch holds every example, so this is plain gradient descent and the seed does not matter.

Constraints

  • 1 <= n = len(X) <= 500, 1 <= d <= 5, 1 <= batch_size <= n, 0 <= epochs <= 50, 0 < lr <= 0.2
  • shuffle a fresh list(range(n)) once per epoch with the one rng, and use rng for nothing else
  • floats are compared with a tolerance of 1e-6

Goals

  • Split each epoch into mini-batches following a seeded random order
  • Take one gradient step per mini-batch, using only that batch's examples
  • Make a random training procedure exactly reproducible
Starting Python…