Technical Summary: Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizes

Problem Formulation

The paper addresses the constrained optimization problem:
$$\min_{x} f(x) \quad \text{subject to} \quad x \in X \cap Y$$
where $Y \subseteq \mathbb{R}^n$ is a closed, convex set that is "easy to project on" (e.g., balls or boxes), and $X$ is defined as the intersection of $m$ lower-level sets of convex functions:
$$X := \bigcap_{i=1}^m \{x \in \mathbb{R}^n \mid g_i(x) \leq 0\}$$
The primary challenge arises when $m$ is large and projecting onto the intersection $X$ is computationally intractable. The authors consider two distinct regimes for the objective function $f$:

1. Strongly convex and Lipschitz-smooth: $f$ has a unique minimizer and smooth gradients.
2. Convex and possibly nonsmooth: $f$ may lack smoothness and strong convexity.

The goal is to develop algorithms that minimize $f$ while ensuring feasibility with respect to $X$ without requiring full projection onto $X$ at every iteration.

Methodology

The proposed approach decouples objective minimization from constraint satisfaction using a two-step iterative framework:

1. Randomized Feasibility Updates (Algorithm 1)

To handle the complex constraints $X$, the authors employ a randomized feasibility algorithm based on Polyak's steps. Instead of projecting onto the full set $X$, the algorithm:

• Samples a single constraint index $\omega_k$ uniformly from $\{1, \dots, m\}$.
• Computes a subgradient of the sampled constraint violation function $g^+_{\omega_k}(x) = \max\{0, g_{\omega_k}(x)\}$.
• Performs a subgradient step with a Polyak step size scaled by a parameter $\beta \in (0, 2)$.
• Projects the result back onto the "easy" set $Y$.
• Repeats this process $N_k$ times per outer iteration, where $N_k$ can be deterministic or random.

The output of this inner loop, $x_k$, serves as a feasibility update that reduces the distance to the feasible set $X \cap Y$ geometrically.

2. Objective Minimization with Adaptive Steps

The outer loop minimizes $f(x)$ using the output of the feasibility updates. The paper proposes two specific strategies based on the properties of $f$:

• Case (i): Strongly Convex & Smooth (Algorithm 2)
  The method combines gradient descent steps with the randomized feasibility updates. The authors introduce an adaptive step size scheme that does not require prior knowledge of the strong convexity constant $\mu$ or the Lipschitz constant $L$. The step size is adjusted based on the gradient norm and a target tolerance $\epsilon$.

• Case (ii): Convex & Nonsmooth (Algorithms 3 & 4)
  For nonsmooth objectives, the paper introduces a fully parameter-free adaptive scheme based on Distance over Weighted Subgradients (DoWS), a variant of the DoWG method.

  • Algorithm 3 (DoWS): Assumes the feasible set $Y$ is bounded. It tracks the maximum distance of iterates from an initial point and accumulates weighted subgradient norms to determine the step size.
  • Algorithm 4 (T-DoWS): A "tamed" variant designed for unbounded sets (e.g., $Y = \mathbb{R}^n$). It modifies the step size scaling to ensure the iterates remain bounded under a sub-level set assumption on $f$, removing the need for a priori boundedness of $Y$.

Key Contributions

1. Theoretical Connection of Error Bounds and Dual Multipliers:
   The authors establish a connection between global error bounds and Lagrangian dual multipliers under the Strong Slater condition. They prove that a uniform upper bound on dual multipliers exists without assuming the compactness of $Y$, a result derived from prior works (Lewis & Pang, 1998; Bertsekas, 1999; Mangasarian, 1998) but explicitly linked here to the specific constraint structure.

2. Linear Convergence for Strongly Convex Problems:
   For strongly convex and smooth objectives, the paper proves linear convergence in expectation of the objective function values to any prescribed tolerance $\epsilon$. This is achieved using adaptive step sizes and a specific condition on the number of feasibility samples $N_k$. Unlike prior work, this result does not assume bounded subgradients of the constraint functions a priori but proves they are bounded almost surely.

3. Fully Parameter-Free Methods for Nonsmooth Problems:
   The paper presents the first fully parameter-free method for solving problem (P) without projections, combining DoWS with randomized feasibility updates.

   • It achieves an $O(1/\sqrt{T})$ worst-case rate in expectation for convex, possibly nonsmooth objectives.
   • It introduces T-DoWS (Algorithm 4), which guarantees bounded iterates and optimal convergence rates even when the constraint set $Y$ is unbounded, provided the sub-level sets of $f$ are bounded.

4. Analysis of Random Sampling Strategies:
   The authors analyze the impact of the number of feasibility samples $N_k$ per iteration. They show that the infeasibility of iterates decreases geometrically almost surely. They provide theoretical guidance on choosing the distribution of $N_k$ (e.g., Poisson, Binomial, or deterministic growth) to achieve optimal convergence rates, demonstrating that optimal rates can be achieved with specific sample-size growth schedules.

Results and Empirical Evaluation

Theoretical Guarantees

• Strongly Convex Case: The algorithm reaches $\epsilon$-accuracy in $O(\ln(1/\epsilon))$ iterations. The infeasibility gap decays geometrically with the number of samples $N_k$.
• Convex Nonsmooth Case: The averaged iterates achieve an expected error bound of $O(1/\sqrt{T})$ (up to logarithmic factors depending on the ratio of the set diameter to the initial estimate). The infeasibility bound depends on the sampling distribution and decreases at a rate of $O(1/T)$ under specific sampling conditions.

Simulations

The authors validate their methods on three problem types:

1. Quadratically Constrained Quadratic Programming (QCQP): Demonstrates linear convergence for the strongly convex case and competitive performance for the nonsmooth case compared to Arrow-Hurwicz, Alt-GDA, and ACVI.
2. Support Vector Machines (SVM): Shows that the proposed parameter-free methods converge without requiring cross-validation for step-size tuning, unlike primal-dual methods which suffer from high computational overhead in online settings.
3. Logistic Regression with Group Fairness Constraints: Illustrates the ability to handle complex fairness constraints (modeled as intersections of lower-level sets) while achieving zero feasibility violation and converging to the optimal objective value.

In all simulations, the proposed algorithms (Algorithms 2, 3, and 4) demonstrate computational efficiency, particularly in scenarios with a large number of constraints where full projection is infeasible. The methods outperform or match state-of-the-art baselines (ACVI, Arrow-Hurwicz) while avoiding the need for hyperparameter tuning or solving subproblems at each iteration.

Significance and Claims

The paper claims to advance the field of constrained optimization by providing computationally efficient, theoretically grounded, and fully parameter-free algorithms for problems with a large number of constraints.

• Novelty: The authors state this is the first time a combination of DoWG (or its tamed variant) with randomized feasibility updates has been studied for constrained optimization without projections.
• Robustness: The methods do not require knowledge of problem-specific parameters (strong convexity constants, Lipschitz constants, or optimal values), making them suitable for practical applications where such information is unavailable.
• Scalability: By using randomized feasibility updates, the algorithms avoid the computational bottleneck of projecting onto the intersection of many constraints, scaling effectively to high-dimensional problems with thousands of constraints.

The work bridges the gap between randomized feasibility methods and adaptive gradient methods, offering a unified framework that adapts to both smooth and nonsmooth objectives while ensuring feasibility with geometric decay.