Can anyone direct me to any algorithms or theorems that describe the difficulty of solving a nonsmooth convex optimization problem for the special case where the full subdifferential is available? All of the results that I can find are designed for the case where one has an oracle that can generate a single subgradient.

3$\begingroup$ If you have the full subdifferential and can extract a subgradient of minimal norm, you have a descent direction which can therefore be used in place of the usual gradient in firstorder methods. You could also take a look at Lewis' and Overton's works on nonsmooth quasiNewton methods. $\endgroup$ – Christian Clason Jun 27 '15 at 9:09

$\begingroup$ @ChristianClason, that sure looks like an answer to me! $\endgroup$ – Tom Solberg Jun 27 '15 at 18:44
The difficulty with nondifferentiable convex functions in optimization stems from the fact that an arbitrary subgradient need not be a descent direction, and hence classical firstorder methods cannot be guaranteed to work. (But see Lewis' and Overton's works on nonsmooth quasiNewton methods, e.g., http://people.orie.cornell.edu/aslewis/publications/13nonsmooth.pdf, where an appropriate linesearch strategy is used to mitigate that difficulty.)
If you have access to the full subdifferential, you could try to compute (analytically or algorithmically) a minimumnorm subgradient $$ p^k = \arg\min_{\xi\in\partial f(x^k)}\\xi\,$$ which is a descent direction (and can be used to measure stationarity) and can be used in place of the standard gradient in any algorithm built on descent directions (e.g., gradient descent with Armijo line search). A proof (and a counterexample for arbitrary subgradients) can be found in Andrzej Ruszczyński's book Nonlinear Optimization.
A related approach is to compute (again, analytically or algorithmically) instead proximal points $$ \mathrm{prox_f(v)} = \arg\min_{w} \frac12 \vw\^2 + f(w) = (\mathrm{Id} + \partial f)^{1}(v)$$ which can be used directly in place of gradient steps when applied to a suitable $v^k$ (think implicit vs. explicit Euler method for ODEs). Most current firstorder methods for convex optimization are based on this approach, such as Nesterov's optimal firstorder method which uses a specially chosen sequence of step sizes. A good introduction to these methods can be found in Lieven Vandenberghe's lecture notes.
Regarding difficulty results (i.e., lower bounds) for iterative methods, worstcase complexity results in the oracle model hold regardless of whether you provide the full subgradient to the algorithm. What happens is that lower bounds for nonsmooth convex optimization are obtained by piecewise linear functions, and the adversary can always (consistently) adapt the instance so that at all query points the function is locally linear, thus the subdifferential is a singleton. You can see the proof at page 120 in the following notes http://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf
If you care about averagecase analysis (where the adversary is not allowed to adapt) then the question is much more delicate, and I think there is no answer in the literature up to date.