  In this paper we consider large-scale smooth optimization problems with
multiple linear coupled constraints. Due to the non-separability of the
constraints, arbitrary random sketching would not be guaranteed to work. Thus,
we first investigate necessary and sufficient conditions for the sketch
sampling to have well-defined algorithms. Based on these sampling conditions we
developed new sketch descent methods for solving general smooth linearly
constrained problems, in particular, random sketch descent and accelerated
random sketch descent methods. From our knowledge, this is the first
convergence analysis of random sketch descent algorithms for optimization
problems with multiple non-separable linear constraints. For the general case,
when the objective function is smooth and non-convex, we prove for the
non-accelerated variant sublinear rate in expectation for an appropriate
optimality measure. In the smooth convex case, we derive for both algorithms,
non-accelerated and accelerated random sketch descent, sublinear convergence
rates in the expected values of the objective function. Additionally, if the
objective function satisfies a strong convexity type condition, both algorithms
converge linearly in expectation. In special cases, where complexity bounds are
known for some particular sketching algorithms, such as coordinate descent
methods for optimization problems with a single linear coupled constraint, our
theory recovers the best-known bounds. We also show that when random sketch is
sketching the coordinate directions randomly produces better results than the
fixed selection rule. Finally, we present some numerical examples to illustrate
the performances of our new algorithms.
