Published in AAAI, 2024
We develop DGFM and DGFM+ for decentralized optimization of nonsmooth, nonconvex objectives using function evaluations. The methods combine randomized smoothing and gradient tracking, with variance reduction in DGFM+ improving the oracle complexity for reaching approximate Goldstein stationarity.
Published in ICML, 2024
Robust Markov Decision Processes (RMDPs) have recently been recognized as a valuable and promising approach to discovering a policy with creditable performance, particularly in the presence of a dynamic environment and estimation errors in the transition matrix due to limited data. Despite extensive exploration of dynamic programming algorithms for solving RMDPs, there has been a notable upswing in interest in developing efficient algorithms using the policy gradient method. In this paper, we propose the first single-loop robust policy gradient (SRPG) method with the global optimality guarantee for solving RMDPs through its minimax formulation. Moreover, we complement the convergence analysis of the nonconvex-nonconcave min-max optimization problem with the objective function’s gradient dominance property, which is not explored in the prior literature. Numerical experiments validate the efficacy of SRPG, demonstrating its faster and more robust convergence behavior compared to its nested-loop counterpart.
Published in NeurIPS, 2024
In this paper, we introduce faster accelerated primal-dual algorithms for minimizing a convex function subject to strongly convex function constraints. Prior to our work, the best complexity bound was O(ε⁻¹), regardless of the strong convexity of the constraint function. It is unclear whether the strong convexity assumption can enable even better convergence results. To address this issue, we have developed novel techniques to progressively estimate the strong convexity of the Lagrangian function. Our approach, for the first time, effectively leverages the constraint strong convexity, obtaining an improved complexity of O(ε⁻¹/²). This rate matches the complexity lower bound for strongly-convex-concave saddle point optimization and is therefore order-optimal. We show the superior performance of our methods in sparsity-inducing constrained optimization, notably Google’s personalized PageRank problem. Furthermore, we show that a restarted version of the proposed methods can effectively identify the optimal solution’s sparsity pattern within a finite number of steps, a result that appears to have independent significance.
Published in Preprint, 2025
PDCS and cuPDCS combine matrix-free primal-dual methods with GPU computation for large-scale conic programs. The solver uses sparse matrix-vector products rather than matrix factorizations, with adaptive step sizes, restarts, and diagonal preconditioning. Supported problems include linear, second-order cone, convex quadratic, and exponential cone programs.
Published in INFORMS Journal on Computing, 2025
We introduce a new first-order method for solving general semidefinite programming problems, based on the alternating direction method of multipliers (ADMM) and a matrix-splitting technique. Our algorithm has an advantage over the Burer-Monteiro approach as it only involves much easier quadratically regularized subproblems in each iteration. For a linear objective, the subproblems are well-conditioned quadratic programs that can be efficiently solved by the standard conjugate gradient method. We show that the ADMM algorithm achieves sublinear or linear convergence rates to the KKT solutions under different conditions. Building on this theoretical development, we present LoRADS, a new solver for linear SDP based on the Low-Rank ADMM Splitting approach. LoRADS incorporates several strategies that significantly increase its efficiency. Firstly, it initiates with a warm-start phase that uses the Burer-Monteiro approach. Moreover, motivated by the SDP low-rank theory [So et al., 2008], LoRADS chooses an initial rank of logarithmic order and then employs a dynamic approach to increase the rank. Numerical experiments indicate that LoRADS exhibits promising performance on various SDP problems. A noteworthy achievement of LoRADS is its successful solving of a matrix completion problem with 15, 694, 167 constraints and a matrix variable of size 40, 000 × 40, 000 in 351 seconds.
Published in Preprint, 2026
APEX adapts to unknown piecewise smoothness under quadratic growth, with improved oracle complexity and a verifiable termination certificate. The method is an accelerated bundle-level algorithm for convex objectives whose smooth regions are unknown. Its certificate provides an implementable stopping rule.
Published in INFORMS Journal on Computing, 2026
Optimal oracle complexity for convex function-constrained optimization, without requiring prior knowledge of smoothness parameters. The methods combine accelerated first-order algorithms with level-set formulations, adapting to Hölder smoothness without requiring its parameters in advance.
Published in Preprint, 2026
Restarted Penalty APEX handles unknown piecewise-smooth objectives and constraints, with certificates for both optimality and feasibility under quadratic growth.
Published in Preprint, 2026
Explaining how retaining sufficiently many cutting planes enables linear convergence for convex piecewise-smooth objectives under quadratic growth.
Published in Proceedings of the National Academy of Sciences (PNAS), 2026
GPU acceleration of low-rank semidefinite programming methods, implemented in cuLoRADS and evaluated on large-scale MaxCut and matrix completion problems.