  We address the problem of minimizing a class of energy functions consisting
of data and smoothness terms that commonly occur in machine learning, computer
vision, and pattern recognition. While discrete optimization methods are able
to give theoretical optimality guarantees, they can only handle a finite number
of labels and therefore suffer from label discretization bias. Existing
continuous optimization methods can find sublabel-accurate solutions, but they
are not efficient for large label spaces. In this work, we propose an efficient
sublabel-accurate method that utilizes the best properties of both continuous
and discrete models. We separate the problem into two sequential steps: (i)
global discrete optimization for selecting the label range, and (ii) efficient
continuous sublabel-accurate local refinement of a convex approximation of the
energy function in the chosen range. Doing so allows us to achieve a boost in
time and memory efficiency while practically keeping the accuracy at the same
level as continuous convex relaxation methods, and in addition, providing
theoretical optimality guarantees at the level of discrete methods. Finally, we
show the flexibility of the proposed approach to general pairwise smoothness
terms, so that it is applicable to a wide range of regularizations. Experiments
on the illustrating example of the image denoising problem demonstrate the
properties of the proposed method. The code reproducing experiments is
available at
\url{https://github.com/nurlanov-zh/sublabel-accurate-alpha-expansion}.
