How can I fit an oversize retaining wall base adjacent to sidewalk?
I think you're asking about width, and not depth. I'd simply excavate an inch or three under the sidewalk and fill it with your substrate, then set the wall tight to the sidewalk. 

If this is not possible, build the base as wide as is practically feasible and compact it well. It's unlikely that you'll have problems with a three-course wall.