Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizes

We consider minimizing an objective function subject to constraints defined by the intersection of lower-level sets of convex functions. We study two cases: (i) strongly convex and Lipschitz-smooth objective function and (ii) convex but possibly nonsmooth objective function. To deal with the constraints that are not easy to project on, we use a randomized feasibility algorithm with Polyak steps and a random number of sampled constraints per iteration, while taking (sub)gradient steps to minimize the objective function. For case (i), we prove linear convergence in expectation of the objective function values to any prescribed tolerance using an adaptive stepsize. For case (ii), we develop a fully problem parameter-free and adaptive stepsize scheme that yields an $O(1/\sqrt{T})$ worst-case rate in expectation. The infeasibility of the iterates decreases geometrically with the number of feasibility updates almost surely, while for the averaged iterates, we establish an expected lower bound on the function values relative to the optimal value that depends on the distribution for the random number of sampled constraints. For certain choices of sample-size growth, optimal rates are achieved. Finally, simulations on a Quadratically Constrained Quadratic Programming (QCQP) problem, Support Vector Machines (SVM), and logistic regression with group fairness constraints demonstrate the computational efficiency of our algorithm compared to other state-of-the-art methods.

Modern machine learning systems are often required to satisfy many constraints, such as fairness, safety, robustness, or resource limitations. Solving these constrained optimization problems is difficult when the constrained set is not easy to project on or computing the closed form expression of projection is difficult. Existing methods either require expensive projection operations, careful hyperparameter or regularizer tuning for penalizing the constraints, or processing all constraints at every iteration. These issues become more severe when the number of constraints is very large. In this work, we develop new optimization algorithms that handle constraints using randomized feasibility updates. Instead of checking all constraints at every step, our methods randomly sample a small subset of constraints and gradually move the solution toward feasibility while also improving the objective function. We combine this idea with adaptive step-size rules that automatically adjust the learning rate during optimization, removing the need for manual parameter tuning. Additionally, we also studied a fully parameter-free line-search free distance adaptive method for solving such a problem. We provide theoretical guarantees showing that our methods converge efficiently. We also study how the number of sampled constraints affects feasibility and convergence. Experiments on Quadratically Constrained Quadratic Programming (QCQP), Support Vector Machines (SVM), and logistic regression with group fairness constraints show that our methods achieve competitive performance while being computationally efficient and fully adaptive.