2023/05/28 by Renbo Zhao, Zhao, Renbo
Computer Science · Engineering · Mathematics · #FOS: Mathematics #Optimization and Control (math.OC) #Point processes and geometric inequalities #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2305.17808
openalex publication_date 2023/05/28 · openalex created_date 2023/05/31 · openalex updated_date 2026/08/01
We present and analyze an away-step Frank-Wolfe method for the convex optimization problem minx\inX f(A x) + ⟨c,x⟩, where f is a θ-logarithmically-homogeneous self-concordant barrier, A is a linear operator that may be non-invertible, ⟨c,⋅⟩ is a linear function and X is a nonempty polytope. The applications of primary interest include D-optimal design, inference of multivariate Hawkes processes, and TV-regularized Poisson image de-blurring. We establish affine-invariant and norm-independent global linear convergence rates of our method, in terms of both the objective gap and the Frank-Wolfe gap. When specialized to the D-optimal design problem, our results settle a question left open since Ahipasaoglu, Sun and Todd (2008). We also show that the iterates generated by our method will land on and remain in a face of X within a bounded number of iterations, which can lead to improved local linear convergence rates (for both the objective gap and the Frank-Wolfe gap). We conduct numerical experiments on D-optimal design and inference of multivariate Hawkes processes, and our results not only demonstrate the efficiency and effectiveness of our method compared to other principled first-order methods, but also corroborate our theoretical results quite well.