2019/09/20 by Fei Li, Li, Fei, Zheng Qu +1 · 1 citation
Computer Science · Engineering · Mathematics · #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1909.09582
openalex publication_date 2019/09/20 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
We propose an inexact proximal augmented Lagrangian framework with explicit\ninner problem termination rule for composite convex optimization problems. We\nconsider arbitrary linearly convergent inner solver including in particular\nstochastic algorithms, making the resulting framework more scalable facing the\never-increasing problem dimension. Each subproblem is solved inexactly with an\nexplicit and self-adaptive stopping criterion, without requiring to set an a\npriori target accuracy. When the primal and dual domain are bounded, our method\nachieves O(1/\√(\ε)) and O(1/\ε) complexity bound in terms\nof number of inner solver iterations, respectively for the strongly convex and\nnon-strongly convex case. Without the boundedness assumption, only logarithm\nterms need to be added and the above two complexity bounds increase\nrespectively to O(1/\√(\ε)) and O(1/\ε),\nwhich hold both for obtaining \ε-optimal and \ε-KKT solution.\nWithin the general framework that we propose, we also obtain nO(1/\ε) and O(1/\ε2) complexity bounds under\nrelative smoothness assumption on the differentiable component of the objective\nfunction. We show through theoretical analysis as well as numerical experiments\nthe computational speedup possibly achieved by the use of randomized inner\nsolvers for large-scale problems.\n