Abstract
Large-scale constrained optimization problems are at the core of many tasks in control, signal processing, and machine learning. Notably, problems with functional constraints arise when, beyond a performance-centric goal (e.g., minimizing the empirical loss), one desires to satisfy other requirements such as robustness, fairness, etc. A simple method for such problems, which remarkably achieves optimal rates for non-smooth, convex, strongly convex, and weakly convex functions under first-order oracle, is Switching Gradient Method (SGM): in each iteration depending on a predetermined constraint violation tolerance, use the gradient of objective or the constraint as the update vector. While the performance of SGM is well-understood for non-smooth functions and in fact matches its unconstrained counterpart, i.e., Gradient Descent (GD), less is formally established about its convergence properties under the smoothness of loss and constraint functions. In this work, we aim to fill this gap. First, we show that SGM may not benefit from faster rates under smoothness, in contrast to improved rates for GD under smoothness. By taking a continuous-time limit perspective, we show the issue is fundamental to SGM's dynamics and not an artifact of our analysis. Our continuous-time limit perspective further provides insights towards alleviating SGM's shortcomings. Notably, we show that leveraging the idea of optimism, a well-explored concept in variational inequalities and min-max optimization, could lead to faster methods. This perspective further enables designing a new class of "soft" switching methods, for which we further analyze their iteration complexity under mild assumptions.
Introduction
In modern machine learning and control systems, optimization is rarely a matter of simple minimization. We often face functional constraints—requirements that ensure our models are not only accurate but also fair, robust, or safe. The Switching Gradient Method (SGM) has emerged as a popular tool for these problems due to its extreme simplicity. The algorithm operates on a binary logic: if the current state satisfies the constraints (within a certain tolerance), it takes a gradient step to minimize the objective; if the constraints are violated, it takes a gradient step to minimize the violation.
While SGM is known to be optimal for non-smooth functions, a significant theoretical gap exists regarding its behavior with smooth functions. In unconstrained optimization, smoothness allows Gradient Descent (GD) to accelerate from a complexity of $\mathcal{O}(\epsilon^{-2})$ to $\mathcal{O}(\epsilon^{-1})$. This paper investigates whether SGM enjoys a similar "smoothness speedup" and, finding that it does not, proposes new algorithmic frameworks to bridge this performance gap.
The Smoothness Paradox in SGM
Surprisingly, the research demonstrates that standard SGM remains trapped at the slower $\mathcal{O}(\epsilon^{-2})$ convergence rate even when both the objective and the constraints are perfectly smooth. This stands in stark contrast to standard GD.
To understand why, the authors analyze SGM through a continuous-time limit perspective, treating the optimization steps as a continuous flow. They discover that SGM can be viewed as Stochastic Gradient Descent (SGD) applied to a dual problem. The "hard" switching mechanism between the objective and the constraint introduces an inherent "variance" or "noise" into the optimization path. Much like how the variance in SGD prevents it from reaching the faster rates of full-batch GD on smooth functions, the chattering nature of SGM’s switches prevents it from exploiting the geometry of smooth functions.
Skew-Symmetric Dynamics and Optimism
The continuous-time analysis reveals a deeper structural issue: the dynamics of SGM are inherently skew-symmetric. In physical terms, the optimization path does not head directly toward the feasible minimum; instead, the Jacobian of the flow causes the system to rotate and oscillate around the boundary of the feasible region. This rotational behavior is mathematically analogous to the dynamics found in min-max games and the training of Generative Adversarial Networks (GANs).
To address these oscillations, the paper introduces two innovative approaches:
- Soft Switching Gradient Method (SSGM): Rather than a binary "if/else" switch, SSGM employs a "trimmed-hinge" function. This creates a smooth, weighted blend of the objective and constraint gradients based on the proximity to the constraint boundary, effectively dampening the "chattering" effect.
- Optimistic Discretization (SSPPM & SSPPM-E): Borrowing from variational inequality literature, the authors apply backward Euler (optimistic) discretization. These Proximal Point-style updates allow the algorithm to "anticipate" the next step, which stabilizes the rotational dynamics and leads to much smoother convergence paths.
Empirical Evaluation
The proposed methods were tested on synthetic, random convex quadratic objectives and constraints in $\mathbb{R}^{10}$. While the theoretical worst-case bounds for SSGM and SSPPM remain $\mathcal{O}(\epsilon^{-2})$, their empirical performance tells a different story.
By measuring the power-law decay ($Ct^{-\alpha}$) of the error, the authors found that SSGM achieved a decay rate of $\alpha=4.5$ for objective loss and $\alpha=10$ for constraint violation. In comparison, standard SGM lagged significantly with rates of $\alpha=1.8$ and $\alpha=6.7$, respectively. These results suggest that the "soft" and "optimistic" variants are far more effective at navigating the trade-offs between objective minimization and constraint satisfaction in practice.
Conclusion and Future Directions
This work clarifies why simple switching methods fail to accelerate under smoothness and provides a roadmap for fixing them. By smoothing the switching logic and incorporating optimistic updates, we can stabilize the skew-symmetric dynamics inherent in constrained optimization.
Future research will focus on refining the theoretical bounds for the smoothing parameters to make them less conservative and extending these methods to non-convex landscapes and stochastic settings. These advancements hold significant promise for real-world applications in safe reinforcement learning and distributed optimization where satisfying functional constraints is non-negotiable.
Summary updated