Abstract
Minimizing finite sums of functions is a central problem in optimization, arising in numerous practical applications. Such problems are commonly addressed using first-order optimization methods. However, these procedures cannot be used in settings where gradient information is unavailable. Finite-difference methods provide an alternative by approximating gradients through function evaluations along a set of directions. For finite-sum minimization problems, it was shown that incorporating variance-reduction techniques into finite-difference methods can improve convergence rates. Additionally, recent studies showed that imposing structure on the directions (e.g., orthogonality) enhances performance. However, the impact of structured directions on variance-reduced finite-difference methods remains unexplored. In this work, we close this gap by proposing a structured variance-reduced finite-difference algorithm for non-smooth finite-sum minimization. We analyze the proposed method, establishing convergence rates for non-convex functions and those satisfying the Polyak-Łojasiewicz condition. Our results show that our algorithm achieves state-of-the-art convergence rates while incurring lower per-iteration costs. Finally, numerical experiments highlight the strong practical performance of our method.
Introduction
In many modern machine learning scenarios, the objective is to minimize a "finite sum" of functions, typically representing a loss function averaged over a dataset. While first-order methods like Stochastic Gradient Descent (SGD) are standard, they are inapplicable in "black-box" scenarios where gradients are unavailable. Examples include adversarial attacks on classifiers with inaccessible weights, fine-tuning massive models where backpropagation is memory-prohibitive, and optimizing complex simulations that only provide scalar outputs.
Zeroth-Order (ZO) optimization addresses these challenges by estimating gradients using finite differences. However, these estimates are often noisy or computationally expensive. While variance reduction and structured directions (e.g., orthogonality) have been studied independently, their combination for non-smooth, non-convex problems has remained unexplored until now.
The VR-SZD Algorithm
We propose VR-SZD (Variance Reduced Structured Zeroth-order Descent), a novel algorithm that integrates variance reduction with structured, orthogonal sampling directions. VR-SZD employs a two-loop structure inspired by SVRG:
- Outer Loop: Computes an accurate gradient surrogate using all $d$ coordinate directions, serving as a stable anchor.
- Inner Loop: Executes $m$ stochastic updates. Crucially, instead of random sampling, VR-SZD utilizes a set of $\ell \le d$ orthogonal directions. This geometric structure minimizes redundant information, yielding higher-quality gradient estimates.
- Efficiency: By using forward differences instead of central differences, VR-SZD requires only $\ell+1$ evaluations per inner iteration, nearly halving the cost compared to many existing methods.
- Proximal Handling: To accommodate non-smooth components (e.g., $L_1$ regularization), the algorithm incorporates a proximal operator.
Comparison with Existing Methods
The theoretical strength of VR-SZD lies in its ability to match the best-known complexity for non-smooth, non-convex finite-sum problems while maintaining lower per-iteration costs through structured approximation.
As shown in the table above, VR-SZD achieves a complexity of $\mathcal{O}(n^{2/3}d\epsilon^{-1})$, placing it at the state-of-the-art for algorithms capable of handling non-smooth functions ($h$ non-smooth). Its use of structured (STR) gradient approximation distinguishes it from methods relying on un-structured (UST) or coordinate-wise (COO) sampling, allowing for larger step sizes and faster convergence.
Experimental Evaluation
The performance of VR-SZD was validated through experiments on synthetic and real-world tasks:
- LASSO Minimization: On a synthetic $d=50$ dimensional problem, VR-SZD demonstrated significantly faster convergence to the minimum compared to variance-reduced baselines like ZO-ProxSVRG and ZO-PSpider+.
- Black-box Binary Classification: Using datasets from the LIBSVM repository (Mushrooms, Phishing, Splice, Australian), VR-SZD consistently achieved lower objective values within a fixed budget of $10^7$ function evaluations.
The results indicate that imposing orthogonality allows for more stable gradient estimates, leading to superior practical performance and smoother descent curves compared to random sampling methods.
Conclusion and Future Work
VR-SZD represents a significant advancement in zeroth-order optimization by effectively combining variance reduction with structured sampling. While generating orthogonal matrices introduces a minor $\mathcal{O}(d\ell^2)$ overhead, the gains in convergence speed and evaluation efficiency are substantial. Future research will focus on adaptive procedures to automatically select parameters like the step size $\gamma$ and the number of directions $\ell$ during the optimization process.
Summary updated