2023/11/10 by Kai Jia, Martin Rinard, Jia, Kai +1
Computer Science · Engineering · #Complexity and Algorithms in Graphs #FOS: Mathematics #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2311.06205
openalex publication_date 2023/11/10 · openalex created_date 2023/11/14 · openalex updated_date 2026/07/28
We present the Trust Region Adversarial Functional Subdifferential (TRAFS) algorithm for constrained optimization of nonsmooth convex Lipschitz functions. Unlike previous methods that assume a subgradient oracle model, we work with the functional subdifferential defined as a set of subgradients that simultaneously captures sufficient local information for effective minimization while being easy to compute for a wide range of functions. In each iteration, TRAFS finds the best step vector in an ℓ2-bounded trust region by considering the worst bound given by the functional subdifferential. TRAFS finds an approximate solution with an absolute error up to ε in O( ε-1) or O(ε-0.5 ) iterations depending on whether the objective function is strongly convex, compared to the previously best-known bounds of O(ε-2) and O(ε-1) in these settings. TRAFS makes faster progress if the functional subdifferential satisfies a locally quadratic property; as a corollary, TRAFS achieves linear convergence (i.e., O(log ε-1)) for strongly convex smooth functions. In the numerical experiments, TRAFS is on average 39.1x faster and solves twice as many problems compared to the second-best method.