Computing proximal points of convex functions with inexact subgradients

Locating proximal points is a component of numerous minimization algorithms. This work focuses on developing a method to find the proximal point of a convex function at a point, given an inexact oracle. Our method assumes that exact function values are at hand, but exact subgradients are either not available or not useful. We use approximate subgradients to build a model of the objective function, and prove that the method converges to the true prox-point within acceptable tolerance. The subgradient g_k used at each step k is such that the distance from g_k to the true subdifferential of the objective function at the current iteration point is bounded by some fixed epsilon>0. The algorithm includes a novel tilt-correct step applied to the approximate subgradient.