The facial reduction algorithm plays an important role in regularizing any conic convex program and establishing the extended duals that enjoy strong duality without requiring any constraint qualifications. When the cone is nice, the extended dual has a relatively simpler formula. In this work, we generalize both the facial reduction algorithm and the concept of niceness from closed convex cones to closed convex sets. Different from the classical facial reduction algorithm that only considers a linear objective function and an intersection of a closed convex cone and an affine subspace, our convex facial reduction algorithm has the flexibility to handle a nonlinear objective function and an intersection of two closed convex sets, and so is able to deal with problems that are inefficiently SDP representable. Based on the convex facial reduction algorithm we establish a class of extended duals that covers the extended duals in conic cases. Similarly, when both the two sets are nice, the formula of the extended dual is relatively simpler.

In this paper, we present an accelerated preconditioned ADMM (pADMM) to efficiently solve large-scale optimal transport (OT) problems. Specifically, to address the challenges posed by solving large-scale linear equations in ADMM sub-problems, we propose a pADMM with a specialized proximal term that enables fast solutions to the subproblems. Furthermore, to further improve the efficiency of pADMM, we propose an accelerated pADMM, which enjoys an $o(1/k)$ non-ergodic iteration complexity with respect to the Karush–Kuhn–Tucker (KKT) residual. Moreover, we implement the proposed accelerated pADMM on GPU. Numerical results demonstrate the outstanding performance of the accelerated pADMM algorithm in solving large-scale OT problems.

We investigate certified robustness for GNNs under graph injection attacks. Existing research only provides sample-wise certificates by verifying each node independently, leading to very limited certifying performance. In this paper, we present the first collective certificate, which certifies a set of target nodes simultaneously. To achieve it, we formulate the problem as a binary integer quadratic constrained linear programming (BQCLP). We further develop a customized linearization technique that allows us to relax the BQCLP into linear programming (LP) that can be efficiently solved. Through comprehensive experiments, we demonstrate that our collective certification scheme significantly improves certification performance with minimal computational overhead. For instance, by solving the LP within 1 minute on the Citeseer dataset, we achieve a significant increase in the certified ratio from 0.0 to 81.2 when the injected node number is 5 of the graph size. Our step marks a crucial step towards making provable defense more practical.

We propose an efficient sieving based secant method to address the computational challenges of solving sparse optimization problems with least-squares constraints. A level-set method has been introduced in [X. Li, D.F. Sun, and K.-C. Toh, SIAM J. Optim., 28 (2018), pp. 1842--1866] that solves these problems by using the bisection method to find a root of a univariate nonsmooth equation $\phi(\lambda) = \rho$ for some $\rho >0$, where $\phi(.)$ is the value function computed by a solution of the corresponding regularized least-squares optimization problem. When the objective function in the constrained problem is a polyhedral gauge function, we prove that (i) for any positive integer $k$, $\phi(.)$ is piecewise $C^k$ in an open interval containing the solution $\lambda^*$ to the equation $\phi(\lambda) = \rho$; (ii) the Clarke Jacobian of $\phi(.)$ is always positive. These results allow us to establish the essential ingredients of the fast convergence rates of the secant method. Moreover, an adaptive sieving technique is incorporated into the secant method to effectively reduce the dimension of the level-set subproblems for computing the value of $\phi(.)$. The high efficiency of the proposed algorithm is demonstrated by extensive numerical results.