In the world of machine learning and operations research, we often face a trade-off: we want to minimize an objective function (like error) while strictly adhering to "hard" constraints (like fairness requirements or resource budgets). While stochastic methods have become the gold standard for large-scale optimization, they often struggle with these hard constraints, typically only guaranteeing that constraints are satisfied on average.
A new paper by Zhaosong Lu and Yifeng Xiao, titled "An inexact stochastic variance-reduced gradient method for constrained convex finite-sum optimization," introduces a novel algorithm that bridges this gap, offering a much faster way to find solutions that are guaranteed to be "surely feasible."
TL;DR
The authors propose an inexact Stochastic Variance-Reduced Gradient (SVRG) method that significantly improves the efficiency of finding solutions for constrained convex problems. By using a proximal Augmented Lagrangian approach to solve subproblems inexactly, they achieve a much better "oracle complexity" (fewer gradient calculations) for solutions that strictly satisfy constraints compared to previous state-of-the-art penalty methods.
What Problem Does This Paper Address?
Most modern large-scale optimization problems take the form of a "finite-sum": you are minimizing the average of many individual functions (like the loss over thousands of data points). When you add constraints to this, things get tricky.
Existing stochastic methods usually aim for $\epsilon$-expected feasibility, meaning the constraint violation is small on average. However, in many real-world "imperative" applications—such as ensuring a model doesn't exceed a strict memory limit or a fairness threshold—we need $\epsilon$-sure feasibility. This means the constraint violation must be deterministically bounded by $\epsilon$.
Until now, the best-known method for reaching this stricter "surely feasible" state (SVRFP) had a significant performance gap. It required $O(\epsilon^{-3/2})$ gradient evaluations, whereas finding an "expectedly feasible" solution only required $O(\epsilon^{-1})$. This paper aims to close that complexity gap.
Methods
The authors move away from traditional "exterior" penalty methods, which approach the feasible region slowly from the outside. Instead, they propose a "feasible" framework:
- Inexact SVRG (Algorithm 2): They adapt the popular SVRG algorithm—which uses periodic full gradient calculations to reduce the "noise" of stochastic steps—to handle constraints.
- The "Inexact" Proximal Step: Standard SVRG requires an exact "proximal operator" (essentially a projection onto the constraint set), which is often impossible to compute for complex cones. The authors show that you only need an inexact solution—specifically, an $\epsilon$-KKT (Karush-Kuhn-Tucker) solution.
- Subproblem Solver (Algorithm 1): To find this inexact solution, they employ a first-order proximal Augmented Lagrangian (AL) method. This allows the algorithm to handle complex conic constraints efficiently.
- Deterministic Reduction: Interestingly, when the problem involves only a single function (not a sum), the method reduces to a new deterministic first-order method that outperforms standard benchmarks like the Extra Anchored Gradient (EAG) method.
Datasets
The authors evaluated their method on three distinct problems:
- Fairness-constrained Logistic Regression: Using the
a1adataset from LIBSVM (67% male, 33% female samples). The goal was to minimize loss while ensuring equal performance across subgroups. - Quadratically Constrained Least Squares: Using synthetic data to simulate signal processing problems with power budget constraints.
- Linearly Constrained LASSO: Using synthetic data to test the deterministic version of the algorithm against standard solvers.
Key Insights and Ideas
- Feasibility Matters: By focusing on staying "nearly feasible" throughout the iterations rather than just at the end, the algorithm avoids the slow convergence typical of penalty-based methods.
- Complexity Breakthrough: The method improves the objective gradient evaluation complexity from $O(\epsilon^{-3/2})$ to $O(\epsilon^{-1/2})$. In the world of optimization, moving from a power of 1.5 to 0.5 is a massive leap in efficiency.
- Exploiting "Cheap" Constraints: A major "aha" moment is that if calculating the gradient of the constraints is cheaper than calculating the gradient of the objective, this method becomes exceptionally powerful. It effectively shifts the computational burden toward the cheaper operations.
Key Results
- Superior Convergence: In the fairness-constrained logistic regression tests, the proposed method converged significantly faster than both the SVRFP penalty method and the deterministic EAG method.
- Low Violation: Unlike other methods that see an initial spike in constraint violation before slowly decreasing, this inexact SVRG method maintains a consistently low level of violation from the very first iterations.
- Efficiency in LASSO: For the linearly constrained LASSO problem, the method achieved a rapid reduction in both objective value and constraint violation, outperforming established benchmarks by a wide margin in terms of total gradient evaluations.
Limitations and Future Work
- Parameter Tuning: Like many variance-reduction methods, the performance relies on choosing the right inner-loop length ($T_k$) and step sizes. While the paper provides theoretical values, practical performance often requires some tuning.
- Strong Convexity: While the main paper focuses on general convex functions, the authors briefly note in the conclusion that the method can be extended to strongly convex objectives for even better results ($O(\log \epsilon^{-1})$ complexity).
- Non-Conic Constraints: The current framework is built around closed convex cones. Extending this to more general non-convex constraints remains an open challenge.
For those interested in the mathematical proofs and specific parameter settings, the full paper is available on arXiv:2611.23221v1.
Summary updated