  In this two-part work, we propose an algorithmic framework for solving
non-convex problems whose objective function is the sum of a number of smooth
component functions plus a convex (possibly non-smooth) or/and smooth (possibly
non-convex) regularization function. The proposed algorithm incorporates ideas
from several existing approaches such as alternate direction method of
multipliers (ADMM), successive convex approximation (SCA), distributed and
asynchronous algorithms, and inexact gradient methods. Different from a number
of existing approaches, however, the proposed framework is flexible enough to
incorporate a class of non-convex objective functions, allow distributed
operation with and without a fusion center, and include variance reduced
methods as special cases. Remarkably, the proposed algorithms are robust to
uncertainties arising from random, deterministic, and adversarial sources. The
part I of the paper develops two variants of the algorithm under very mild
assumptions and establishes first-order convergence rate guarantees. The proof
developed here allows for generic errors and delays, paving the way for
different variance-reduced, asynchronous, and stochastic implementations,
outlined and evaluated in part II.
