Variance Reduced Random Relaxed Projection Method for Constrained Finite-sum Minimization Problems

Zhichun Yang, Fu-quan Xia, Kai Tu, Man–Chung Yue

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:

  1. 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.
  2. 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).

Comprehensive performance comparison of VR$^3$PM against various RPM baselines (R$^2$PM variants, RPM-WB, and RPM-NS) across different problem scales. The plots track the optimality gap (left) and feasibility gap (right) against CPU time.

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

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.
BibTeX
@article{yang2024variance,
  author = {Zhichun Yang and Fu-quan Xia and Kai Tu and Man–Chung Yue},
  title = {{Variance Reduced Random Relaxed Projection Method for Constrained Finite-sum Minimization Problems}},
  journal = {IEEE TSP},
  year = {2024},
  doi = {10.1109/tsp.2024.3386388},
}
Figure