# Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizes

arXiv: https://arxiv.org/abs/2601.20076 · HTML: https://mlsanity.com/paper/2601.20076/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 77 references that are in the map.
- First posted on arXiv 27 Jan 2026.

## Builds on (most cited first, 30 of 46)

- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [A Lyapunov-based Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/1805.07708/) (2018)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Learning-Rate-Free Learning by D-Adaptation](https://mlsanity.com/paper/2301.07733/) (2023)
- [Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals](https://mlsanity.com/paper/1809.04198/) (2018)
- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [Adaptive Gradient Descent without Descent](https://mlsanity.com/paper/1910.09529/) (2019)
- [UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization](https://mlsanity.com/paper/1910.13857/) (2019)
- [Online Adaptive Methods, Universality and Acceleration](https://mlsanity.com/paper/1809.02864/) (2018)
- [Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets](https://mlsanity.com/paper/1406.1305/) (2014)
- [Online to Offline Conversions, Universality and Adaptive Minibatch Sizes](https://mlsanity.com/paper/1705.10499/) (2017)
- [DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method](https://mlsanity.com/paper/2305.16284/) (2023)
- [Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization](https://mlsanity.com/paper/2102.09468/) (2021)
- [Adaptive Proximal Gradient Method for Convex Optimization](https://mlsanity.com/paper/2308.02261/) (2023)
- [Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithm](https://mlsanity.com/paper/2206.05850/) (2022)
- [Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation](https://mlsanity.com/paper/2303.12277/) (2023)
- [Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity](https://mlsanity.com/paper/1712.04104/) (2017)
- [Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization](https://mlsanity.com/paper/2212.09513/) (2022)
- [Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient](https://mlsanity.com/paper/2301.04431/) (2023)
- [Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities](https://mlsanity.com/paper/2007.08840/) (2020)
- [New Analysis and Results for the Frank-Wolfe Method](https://mlsanity.com/paper/1307.0873/) (2013)
- [Accelerated Parameter-Free Stochastic Optimization](https://mlsanity.com/paper/2404.00666/) (2024)
- [Tuning-Free Stochastic Optimization](https://mlsanity.com/paper/2402.07793/) (2024)
- [Log Barriers for Safe Black-box Optimization with Application to Safe Reinforcement Learning](https://mlsanity.com/paper/2207.10415/) (2022)
- [A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guarantees](https://mlsanity.com/paper/1904.03563/) (2019)
- [Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features](https://mlsanity.com/paper/2304.11737/) (2023)
- [Sequential convergence of AdaGrad algorithm for smooth convex optimization](https://mlsanity.com/paper/2011.12341/) (2020)

## Built on by (most cited first, 1 of 1)

- [Distance-Aware Muon: Adaptive Step Scaling for Normalized Optimization](https://mlsanity.com/paper/2605.18999/) (2026)

## Abstract (arXiv)

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/√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.