This paper explores numerical methods for solving a convex-concave semi-infinite program (SIP). SIP has been systematically discussed by optimization community for many years with many real-world applications. Most numerical algorithms for optimization with finitely many constraints can be somehow extended for SIP. The examples include the penalty method, the interior-point method, the Lagrangian method, and the trust-region method. However, most of these works only show an asymptotic convergence property or a local convergence rate. On the contrary, we establish the global non-asymptotic convergence rate for our algorithm and characterize its iteration complexity for finding an $\epsilon$-optimal solution. We introduce a primal-dual gradient method which performs three updates iteratively: a momentum gradient ascend step to update the constraint parameters, a momentum gradient ascend step to update the dual variables, and a gradient descend step to update the primal variables. Our approach also extends to scenarios where gradients and function values are accessible solely through stochastic oracles. We show the iteration complexity under different smoothness, convexity and concavity assumptions on the functions. In addition, we explore the application of the proposed algorithms on training machine learning models with fairness constraints.

Constrained optimization problems where both the objective and constraints may be nonsmooth and nonconvex arise across many learning and data science settings. In this talk, we discuss a simple first-order method that for any Lipschitz, weakly convex objectives and constraints, it finds a feasible, epsilon-stationary point at a convergence rate of $O(epsilon^{−4})$ without relying on compactness or Constraint Qualification (CQ). When CQ holds, this convergence is measured by approximately satisfying the Karush-Kuhn-Tucker conditions. When CQ fails, we guarantee the attainment of weaker Fritz-John conditions. As an illustrative example, our method stably converges on piecewise quadratic SCAD regularized problems despite frequent violations of constraint qualification. The considered algorithm is similar to those of "Quadratically regularized subgradient methods for weakly convex optimization with weakly convex constraints" by Ma et al. and "Stochastic first-order methods for convex and nonconvex functional constrained optimization" by Boob et al. (whose guarantees further assume compactness and CQ), iteratively taking inexact proximal steps, computed via an inner loop applying a switching subgradient method to a strongly convex constrained subproblem. Our non-Lipschitz analysis of the switching subgradient method appears to be new and may be of independent interest.

This talk will consider finite-sum monotone inclusion problems, which is a generalized framework for min-max optimization and variational inequalities. We will focus on guarantees on residual and operator norm. These optimality measures generalize a the notion of "gradient norm" from minimization to more general problems we consider. We will cover algorithms incorporating variance reduction on Halpern iteration that achieve optimal complexity guarantees not only in terms of the desired accuracy, but also number of functions involved in the finite-sum and Lipschitz constant. We will discuss further consequences of the result and open problems.