  Zero-One Composite Optimization (0/1-COP) is a prototype of nonsmooth,
nonconvex optimization problems and it has attracted much attention recently.
The augmented Lagrangian Method (ALM) has stood out as a leading methodology
for such problems. The main purpose of this paper is to extend the classical
theory of ALM from smooth problems to 0/1-COP. We propose, for the first time,
second-order optimality conditions for 0/1-COP. In particular, under a
second-order sufficient condition (SOSC), we prove the R-linear convergence
rate of the proposed ALM. In order to identify the subspace used in SOSC, we
employ the proximal operator of the 0/1-loss function, leading to an active-set
identification technique. Built around this identification process, we design
practical stopping criteria for any algorithm to be used for the subproblem of
ALM. We justify that Newton's method is an ideal candidate for the subproblem
and it enjoys both global and local quadratic convergence. Those considerations
result in an inexact Newton ALM (iNALM). The method of iNALM is unique in the
sense that it is active-set based, it is inexact (hence more practical), and
SOSC plays an important role in its R-linear convergence analysis. The
numerical results on both simulated and real datasets show the fast running
speed and high accuracy of iNALM when compared with several leading solvers.
