Abstract
For many applications in signal processing and machine learning, we are tasked with minimizing a large sum of convex functions subject to a large number of convex constraints. In this paper, we devise a new random projection method (RPM) to efficiently solve this problem. Compared with existing RPMs, our proposed algorithm features two useful algorithmic ideas. First, at each iteration, instead of projecting onto the subset defined by one of the constraints, our algorithm only requires projecting onto a half-space approximation of the subset, which significantly reduces the computational cost as it admits a closed-form formula. Second, to exploit the structure that the objective is a sum, variance reduction is incorporated into our algorithm to further improve the performance. As theoretical contributions, under a novel error bound condition and other standard assumptions, we prove that the proposed RPM converges to an optimal solution and that both optimality and feasibility gaps vanish at a sublinear rate. In particular, via a new analysis framework, we show that our RPM attains a faster convergence rate in optimality gap than existing RPMs when the objective function has a Lipschitz continuous gradient, capitalizing the benefit of the variance reduction. We also provide sufficient conditions for the error bound condition to hold. Experiments on a beamforming problem and a robust classification problem are also presented to demonstrate the superiority of our RPM over existing ones.
Introduction
Modern machine learning and signal processing tasks often involve minimizing a "finite-sum" objective function—where the total loss is the average of many individual data point losses—subject to a large number of convex constraints. Standard approaches like the Projected Gradient Method (PGM) become impractical when the number of summands ($n$) or constraints ($m$) is massive, or when individual constraints are complex and lack closed-form projection solutions.
To address these challenges, we introduce VR$^3$PM (Variance Reduced Random Relaxed Projection Method). By combining SVRG-style variance reduction with computationally cheap "relaxed" projections onto half-spaces, VR$^3$PM achieves faster theoretical convergence rates and superior practical performance compared to existing random projection methods.
Methods
VR$^3$PM integrates two key algorithmic innovations to overcome the computational bottlenecks of large-scale constrained optimization:
- Variance Reduction (SVRG): To handle the finite-sum objective, the algorithm uses the Stochastic Variance Reduced Gradient (SVRG) estimator. This technique periodically computes a full gradient to "anchor" stochastic estimates, significantly reducing the noise (variance) inherent in standard stochastic gradients.
- Relaxed Projections: Instead of projecting onto a complex constraint set $C_j$, VR$^3$PM projects onto a half-space approximation of that set. This "relaxed" projection is an outer approximation defined by a subgradient of the constraint function. Crucially, projecting onto a half-space has a simple, closed-form formula, making each iteration extremely fast.
Additionally, for practical performance, the algorithm supports grouping constraints into mini-batches. This "constraint analogue" to mini-batch gradients helps reduce the variance introduced by random constraint sampling. The algorithm operates in epochs, performing multiple inner iterations that combine variance-reduced stochastic gradients with random relaxed projections.
Experimental Evaluation
We evaluated VR$^3$PM on synthetic Quadratic Constrained Quadratic Programming (QCQP) benchmarks and real-world robust classification problems (using the a6a and a7a datasets from LIBSVM).
As shown in the experimental results, VR$^3$PM consistently outperforms state-of-the-art methods like RPM-NS and RPM-WB. In QCQP and beamforming tasks, VR$^3$PM reached higher accuracy significantly faster (in terms of CPU time) than variants using vanilla stochastic gradients. On large-scale robust classification problems, it demonstrated a much smoother and faster reduction in both the optimality gap and constraint violations.
Key Insights
- Synergy between SVRG and RPM: This work is the first to successfully integrate SVRG with random relaxed projections. We show that variance reduction allows for a faster $O(1/K^{2/3})$ convergence rate in the optimality gap, improving upon the standard $O(1/\sqrt{K})$ rate of previous RPMs.
- Efficiency of Relaxation: The results demonstrate that projecting onto simpler "outer" half-space approximations is sufficient for convergence and far more computationally efficient than exact projections.
- Novel Analysis Framework: To prove these results, we introduced a new "error bound-type" condition that relates the distance to the feasible set to the distance to randomly chosen half-spaces, providing a robust theoretical foundation for relaxed projection methods.
Conclusion and Future Work
VR$^3$PM provides a scalable and efficient solution for large-scale constrained finite-sum minimization. Future research directions include extending the framework to non-smooth objectives using proximal operators and developing automated methods for tuning parameters such as epoch length and step size.
Summary updated