Modern statistical problems often involve minimizing objective functions that are not necessarily convex or smooth. This paper proposes and investigates a broad surrogate framework, defined by generalized Bregman divergence functions, for developing scalable algorithms. Local linear approximation, mirror descent, iterative thresholding, and DC programming can all be viewed as particular instances. The Bregman re-characterization enables us to choose suitable measures of computational error to establish global convergence rate results even for nonconvex problems in high-dimensional settings. Moreover, under some regularity conditions, the sequence of iterates in the general Bregman surrogate optimization can be shown to approach the statistical truth within the desired accuracy geometrically fast. The paper also reveals that these algorithms can be accelerated with a careful control of relaxation and stepsize parameters. Simulation studies are performed to support the theoretical results.