Timezone: »
Adversarial machines, where a learner competes against an adversary, have regained much recent interest in machine learning. They are naturally in the form of saddle-point optimization, often with separable structure but sometimes also with unmanageably large dimension. In this work we show that adversarial prediction under multivariate losses can be solved much faster than they used to be. We first reduce the problem size exponentially by using appropriate sufficient statistics, and then we adapt the new stochastic variance-reduced algorithm of Balamurugan & Bach (2016) to allow any Bregman divergence. We prove that the same linear rate of convergence is retained and we show that for adversarial prediction using KL-divergence we can further achieve a speedup of #example times compared with the Euclidean alternative. We verify the theoretical findings through extensive experiments on two example applications: adversarial prediction and LPboosting.
Author Information
Zhan Shi (University of Illinois at Chicago)
Xinhua Zhang (University of Illinois at Chicago (UIC))
Yaoliang Yu (University of Waterloo)
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Spotlight: Bregman Divergence for Stochastic Variance Reduction: Saddle-Point and Adversarial Prediction »
Wed. Dec 6th 01:45 -- 01:50 AM Room Hall C
More from the Same Authors
-
2022 Poster: Optimality and Stability in Non-Convex Smooth Games »
Guojun Zhang · Pascal Poupart · Yaoliang Yu -
2022 : Poisoning Generative Models to Promote Catastrophic Forgetting »
Siteng Kang · Xinhua Zhang -
2022 : Indiscriminate Data Poisoning Attacks on Neural Networks »
Yiwei Lu · Gautam Kamath · Yaoliang Yu -
2022 : Indiscriminate Data Poisoning Attacks on Neural Networks »
Yiwei Lu · Gautam Kamath · Yaoliang Yu -
2022 : Continual Poisoning of Generative Models to Promote Catastrophic Forgetting »
Siteng Kang · Xinhua Zhang -
2022 : Geometric attacks on batch normalization »
Amur Ghose · Apurv Gupta · Yaoliang Yu · Pascal Poupart -
2023 Poster: Robust Data Valuation with Weighted Banzhaf Values »
Weida Li · Yaoliang Yu -
2023 Poster: Batchnorm Allows Unsupervised Radial Attacks »
Amur Ghose · Apurv Gupta · Yaoliang Yu · Pascal Poupart -
2023 Poster: Understanding Neural Network Binarization with Forward and Backward Proximal Quantizers »
Yiwei Lu · Yaoliang Yu · Xinlin Li · Vahid Partovi Nia -
2023 Poster: Functional Renyi Differential Privacy for Generative Modeling »
Dihong Jiang · Sun Sun · Yaoliang Yu -
2022 Spotlight: Optimality and Stability in Non-Convex Smooth Games »
Guojun Zhang · Pascal Poupart · Yaoliang Yu -
2022 Poster: Moment Distributionally Robust Tree Structured Prediction »
Yeshu Li · Danyal Saeed · Xinhua Zhang · Brian Ziebart · Kevin Gimpel -
2022 Poster: Certifying Robust Graph Classification under Orthogonal Gromov-Wasserstein Threats »
Hongwei Jin · Zishun Yu · Xinhua Zhang -
2021 Poster: Distributionally Robust Imitation Learning »
Mohammad Ali Bashiri · Brian Ziebart · Xinhua Zhang -
2021 Poster: Implicit Task-Driven Probability Discrepancy Measure for Unsupervised Domain Adaptation »
Mao Li · Kaiqi Jiang · Xinhua Zhang -
2020 Poster: Certified Robustness of Graph Convolution Networks for Graph Classification under Topological Attacks »
Hongwei Jin · Zhan Shi · Venkata Jaya Shankar Ashish Peruri · Xinhua Zhang -
2020 Spotlight: Certified Robustness of Graph Convolution Networks for Graph Classification under Topological Attacks »
Hongwei Jin · Zhan Shi · Venkata Jaya Shankar Ashish Peruri · Xinhua Zhang -
2020 Poster: Proximal Mapping for Deep Regularization »
Mao Li · Yingyi Ma · Xinhua Zhang -
2020 Spotlight: Proximal Mapping for Deep Regularization »
Mao Li · Yingyi Ma · Xinhua Zhang -
2019 Poster: Multivariate Triangular Quantile Maps for Novelty Detection »
Jingjing Wang · Sun Sun · Yaoliang Yu -
2018 Poster: Deep Homogeneous Mixture Models: Representation, Separation, and Approximation »
Priyank Jaini · Pascal Poupart · Yaoliang Yu -
2018 Poster: Distributionally Robust Graphical Models »
Rizal Fathony · Ashkan Rezaei · Mohammad Ali Bashiri · Xinhua Zhang · Brian Ziebart -
2017 Poster: Decomposition-Invariant Conditional Gradient for General Polytopes with Line Search »
Mohammad Ali Bashiri · Xinhua Zhang -
2016 Poster: Convex Two-Layer Modeling with Latent Structure »
Vignesh Ganapathiraman · Xinhua Zhang · Yaoliang Yu · Junfeng Wen -
2014 Poster: Convex Deep Learning via Normalized Kernels »
Özlem Aslan · Xinhua Zhang · Dale Schuurmans -
2014 Poster: Robust Bayesian Max-Margin Clustering »
Changyou Chen · Jun Zhu · Xinhua Zhang -
2013 Poster: Learning with Invariance via Linear Functionals on Reproducing Kernel Hilbert Space »
Xinhua Zhang · Wee Sun Lee · Yee Whye Teh -
2013 Spotlight: Learning with Invariance via Linear Functionals on Reproducing Kernel Hilbert Space »
Xinhua Zhang · Wee Sun Lee · Yee Whye Teh -
2013 Poster: On Decomposing the Proximal Map »
Yao-Liang Yu -
2013 Poster: Convex Two-Layer Modeling »
Özlem Aslan · Hao Cheng · Xinhua Zhang · Dale Schuurmans -
2013 Spotlight: Convex Two-Layer Modeling »
Özlem Aslan · Hao Cheng · Xinhua Zhang · Dale Schuurmans -
2013 Oral: On Decomposing the Proximal Map »
Yao-Liang Yu -
2013 Poster: Polar Operators for Structured Sparse Estimation »
Xinhua Zhang · Yao-Liang Yu · Dale Schuurmans -
2013 Poster: Better Approximation and Faster Algorithm Using the Proximal Average »
Yao-Liang Yu -
2012 Poster: Convex Multi-view Subspace Learning »
Martha White · Yao-Liang Yu · Xinhua Zhang · Dale Schuurmans -
2012 Poster: Accelerated Training for Matrix-norm Regularization: A Boosting Approach »
Xinhua Zhang · Yao-Liang Yu · Dale Schuurmans -
2012 Poster: A Polynomial-time Form of Robust Regression »
Yao-Liang Yu · Özlem Aslan · Dale Schuurmans -
2010 Poster: Lower Bounds on Rate of Convergence of Cutting Plane Methods »
Xinhua Zhang · Ankan Saha · S.V.N. Vishwanathan -
2010 Poster: Relaxed Clipping: A Global Training Method for Robust Regression and Classification »
Yao-Liang Yu · Min Yang · Linli Xu · Martha White · Dale Schuurmans -
2009 Poster: A General Projection Property for Distribution Families »
Yao-Liang Yu · Yuxi Li · Dale Schuurmans · Csaba Szepesvari -
2008 Poster: Kernel Measures of Independence for non-iid Data »
Xinhua Zhang · Le Song · Arthur Gretton · Alexander Smola -
2008 Spotlight: Kernel Measures of Independence for non-iid Data »
Xinhua Zhang · Le Song · Arthur Gretton · Alexander Smola -
2006 Poster: Hyperparameter Learning for Graph Based Semi-supervised Learning Algorithms »
Xinhua Zhang · Wee Sun Lee