Prof. Shalabh Bhatnagar (Indian Institute of Science)

Prof. Shalabh Bhatnagar (Indian Institute of Science)

Title: Zeroth-Order Optimization Under Noise: Taming Bias and Non-smoothness

Abstract: Many engineering and learning problems have objective functions that must be optimized without access to the gradient — we can only evaluate the objective, often with noise. Gradient-free methods estimate the slope from such evaluations, but every estimate is biased, and many objectives, such as absolute-value losses or ReLU networks, have kinks where the gradient is not defined.

This talk presents two ways of handling these difficulties, linked by one viewpoint: the algorithm is a stochastic approximation whose long-run behaviour is read off from a deterministic limiting dynamics. In the first part, for smooth objectives, bias is a design choice. A few more function measurements per step, combined through a shift-operator expansion, reduce the bias to arbitrarily high order in the perturbation size. Since the bias is not zero, the limiting dynamics is a differential inclusion, a set-valued perturbation of gradient descent, and the iterates converge to a neighbourhood of the minimizers that shrinks with the bias.

In the second part, we drop smoothness. The gradient is replaced by the set-valued Clarke generalized gradient. Two noisy evaluations along a random Gaussian direction estimate the gradient of a smoothed objective, which approaches the generalized gradient as the smoothing is reduced. A two-timescale projected scheme averages this estimate on the fast scale and descends along it on the slow scale. In outline, the iterates track a projected differential inclusion, compared with the smoothed dynamics by a Grönwall argument, and converge almost surely to a neighbourhood of the Clarke stationary points, the candidates for a minimum.