Zeroth-Order Stochastic Compositional Gradient Descent: Towards Black-Box Sparse AUC Maximization

Wenkang Wang, Dongxu Liu, Bin Gu
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:3268-3276, 2026.

Abstract

The area under the ROC curve (AUC) is a key metric for classification tasks, valued for its robustness to class imbalance. Sparse models trained with $\ell_0$ constraints further enhance interpretability and generalization. Building on prior work that reformulates nonlinear AUC maximization as a pointwise compositional optimization problem, we revisit this formulation as the basis for addressing the black-box setting, where only function evaluations are available. A central challenge arises from integrating zeroth-order gradient estimation with hard-thresholding operators in the compositional framework, which has remained unresolved. To overcome this difficulty, we propose the Zeroth-Order Stochastic Compositional Hard-Thresholding (ZO-SCHT) algorithm, which, to the best of our knowledge, is the first method for black-box sparse AUC maximization. We establish that ZO-SCHT achieves linear convergence up to a tolerance bound under a fixed step size. Extensive experiments on both black-box sparse AUC maximization and black-box adversarial attack tasks demonstrate the effectiveness and versatility of our approach.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-wang26g, title = { Zeroth-Order Stochastic Compositional Gradient Descent: Towards Black-Box Sparse AUC Maximization }, author = {Wang, Wenkang and Liu, Dongxu and Gu, Bin}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {3268--3276}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/wang26g/wang26g.pdf}, url = {https://proceedings.mlr.press/v300/wang26g.html}, abstract = { The area under the ROC curve (AUC) is a key metric for classification tasks, valued for its robustness to class imbalance. Sparse models trained with $\ell_0$ constraints further enhance interpretability and generalization. Building on prior work that reformulates nonlinear AUC maximization as a pointwise compositional optimization problem, we revisit this formulation as the basis for addressing the black-box setting, where only function evaluations are available. A central challenge arises from integrating zeroth-order gradient estimation with hard-thresholding operators in the compositional framework, which has remained unresolved. To overcome this difficulty, we propose the Zeroth-Order Stochastic Compositional Hard-Thresholding (ZO-SCHT) algorithm, which, to the best of our knowledge, is the first method for black-box sparse AUC maximization. We establish that ZO-SCHT achieves linear convergence up to a tolerance bound under a fixed step size. Extensive experiments on both black-box sparse AUC maximization and black-box adversarial attack tasks demonstrate the effectiveness and versatility of our approach. } }
Endnote
%0 Conference Paper %T Zeroth-Order Stochastic Compositional Gradient Descent: Towards Black-Box Sparse AUC Maximization %A Wenkang Wang %A Dongxu Liu %A Bin Gu %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-wang26g %I PMLR %P 3268--3276 %U https://proceedings.mlr.press/v300/wang26g.html %V 300 %X The area under the ROC curve (AUC) is a key metric for classification tasks, valued for its robustness to class imbalance. Sparse models trained with $\ell_0$ constraints further enhance interpretability and generalization. Building on prior work that reformulates nonlinear AUC maximization as a pointwise compositional optimization problem, we revisit this formulation as the basis for addressing the black-box setting, where only function evaluations are available. A central challenge arises from integrating zeroth-order gradient estimation with hard-thresholding operators in the compositional framework, which has remained unresolved. To overcome this difficulty, we propose the Zeroth-Order Stochastic Compositional Hard-Thresholding (ZO-SCHT) algorithm, which, to the best of our knowledge, is the first method for black-box sparse AUC maximization. We establish that ZO-SCHT achieves linear convergence up to a tolerance bound under a fixed step size. Extensive experiments on both black-box sparse AUC maximization and black-box adversarial attack tasks demonstrate the effectiveness and versatility of our approach.
APA
Wang, W., Liu, D. & Gu, B.. (2026). Zeroth-Order Stochastic Compositional Gradient Descent: Towards Black-Box Sparse AUC Maximization . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:3268-3276 Available from https://proceedings.mlr.press/v300/wang26g.html.

Related Material