The monotone Variational Inequality (VI) is an important problem in machine
learning. In numerous instances, the VI problems are accompanied by function
constraints which can possibly be data-driven, making the projection operator
challenging to compute. In this paper, we present novel first-order methods for
function constrained VI (FCVI) problem under various settings, including smooth
or nonsmooth problems with a stochastic operator and/or stochastic constraints.
First, we introduce the~{\texttt{OpConEx}} method and its stochastic variants,
which employ extrapolation of the operator and constraint evaluations to update
the variables and the Lagrangian multipliers. These methods achieve optimal
operator or sample complexities when the FCVI problem is either (i)
deterministic nonsmooth, or (ii) stochastic, including smooth or nonsmooth
stochastic constraints. Notably, our algorithms are simple single-loop
procedures and do not require the knowledge of Lagrange multipliers to attain
these complexities. Second, to obtain the optimal operator complexity for
smooth deterministic problems, we present a novel single-loop Adaptive
Lagrangian Extrapolation~(\texttt{AdLagEx}) method that can adaptively search
for and explicitly bound the Lagrange multipliers. Furthermore, we show that
all of our algorithms can be easily extended to saddle point problems with
coupled function constraints, hence achieving similar complexity results for
the aforementioned cases. To our best knowledge, many of these complexities are
obtained for the first time in the literature.

本文提出了适用于具有各种设置的函数约束 VI 问题的新型一阶方法，包括具有随机算子和 / 或随机约束的平滑或非平滑问题。通过使用算子和约束的外推来更新变量和 Lagrange 乘子，我们的算法能够实现最优操作员或样本复杂度。对于平滑的确定性问题，我们还提出了一种新的单循环自适应 Lagrangian 外推方法，可以自适应地搜索和显式地绑定 Lagrange 乘子。此外，我们的算法可以轻松地扩展到具有耦合函数约束的鞍点问题。