2018/08/07 by Ion Necoara, Necoara, Ion, Martin Takáč +1
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #optimization
paper · pdf · doi:10.48550/arxiv.1808.02530
openalex publication_date 2018/08/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we consider large-scale smooth optimization problems with\nmultiple linear coupled constraints. Due to the non-separability of the\nconstraints, arbitrary random sketching would not be guaranteed to work. Thus,\nwe first investigate necessary and sufficient conditions for the sketch\nsampling to have well-defined algorithms. Based on these sampling conditions we\ndeveloped new sketch descent methods for solving general smooth linearly\nconstrained problems, in particular, random sketch descent and accelerated\nrandom sketch descent methods. From our knowledge, this is the first\nconvergence analysis of random sketch descent algorithms for optimization\nproblems with multiple non-separable linear constraints. For the general case,\nwhen the objective function is smooth and non-convex, we prove for the\nnon-accelerated variant sublinear rate in expectation for an appropriate\noptimality measure. In the smooth convex case, we derive for both algorithms,\nnon-accelerated and accelerated random sketch descent, sublinear convergence\nrates in the expected values of the objective function. Additionally, if the\nobjective function satisfies a strong convexity type condition, both algorithms\nconverge linearly in expectation. In special cases, where complexity bounds are\nknown for some particular sketching algorithms, such as coordinate descent\nmethods for optimization problems with a single linear coupled constraint, our\ntheory recovers the best-known bounds. We also show that when random sketch is\nsketching the coordinate directions randomly produces better results than the\nfixed selection rule. Finally, we present some numerical examples to illustrate\nthe performances of our new algorithms.\n