  We present the framework of slowly varying regression under sparsity,
allowing sparse regression models to exhibit slow and sparse variations. The
problem of parameter estimation is formulated as a mixed-integer optimization
problem. We demonstrate that it can be precisely reformulated as a binary
convex optimization problem through a novel relaxation technique. This
relaxation involves a new equality on Moore-Penrose inverses, convexifying the
non-convex objective function while matching the original objective on all
feasible binary points. This enables us to efficiently solve the problem to
provable optimality using a cutting plane-type algorithm. We develop a highly
optimized implementation of this algorithm, substantially improving upon the
asymptotic computational complexity of a straightforward implementation.
Additionally, we propose a fast heuristic method that guarantees a feasible
solution and, as empirically illustrated, produces high-quality warm-start
solutions for the binary optimization problem. To tune the framework's
hyperparameters, we suggest a practical procedure relying on binary search
that, under certain assumptions, is guaranteed to recover the true model
parameters. On both synthetic and real-world datasets, we demonstrate that the
resulting algorithm outperforms competing formulations in comparable times
across various metrics, including estimation accuracy, predictive power, and
computational time. The algorithm is highly scalable, allowing us to train
models with thousands of parameters. Our implementation is available
open-source at https://github.com/vvdigalakis/SSVRegression.git.
