Paper tackles ranking items with a semi-random comparison graph and a monotone adversary.
problem Ranking items based on pairwise comparisons from a semi-random comparison graph with a monotone adversary.
method Developed a weighted maximum likelihood estimator (MLE) and an SDP-based approach to reweight the semi-random graph.
result Achieves near-optimal sample complexity, up to a log^2(n) factor, for identifying the top-K preferred items.
New algorithm tackles non-convex matrix completion in semi-random settings.
problem Matrix completion in semi-random environments with varying observation probabilities.
method Proposes a pre-processing step to re-weight semi-random input, followed by a nearly-linear time algorithm.
result Recovering ground-truth matrix using non-convex local minima after pre-processing.
Spectral ranking methods are improved against semi-random graph sampling.
problem Improving spectral ranking methods in semi-random graph sampling.
method Investigating entry-wise error of spectral algorithms against a semi-random adversary.
result Asymptotic performance can be recovered by reweighting observed edges.
New method robust to semi-random sparse recovery, nearly-linear time.
problem Brittleness of fast sparse recovery algorithms under generative model changes.
method Designing a new iterative method robust to semi-random model.
result Proves robustness of new method to semi-random generative models.
We propose semi-random features for nonlinear function approximation. The flexibility of semi-random feature lies between the fully adjustable units in deep learning and the random features used in kernel methods. For one hidden layer models with semi-random features, we prove with no unrealistic assumptions that the m…
SDP relaxation for Sub-Gaussian Mixture Model achieves optimal error bound and robustness.
problem Estimating discrete clustering structures in Sub-Gaussian Mixture Model.
method Hidden integrality property of SDP relaxation and semi-random robustness analysis.
result SDP relaxation achieves optimal error bound and robustness in semi-random setting.
Several recent works have shown that state-of-the-art classifiers are vulnerable to worst-case (i.e., adversarial) perturbations of the datapoints. On the other hand, it has been empirically observed that these same classifiers are relatively robust to random noise. In this paper, we propose to study a \textit{semi-ran…
Improved SGD for robust linear and ReLU regression with adversarial corruptions.
problem Robust regression with adversarial corruptions in streaming data.
method Stochastic gradient descent (SGD-exp) with exponentially decaying step size.
result Nearly linear convergence to true parameter with up to 50% Massart corruption rate.
Efficient algorithm detects communities in noisy graphs with robustness.
problem Community detection in stochastic block models with adversarial corruptions.
method Efficient algorithm using semidefinite programming for robust clustering.
result Achieves error O(ε)+e−2C(1±o(1)) for ε-fraction of corruptions. Study on ReLU regression with Massart noise, achieving exact parameter recovery.
problem Efficiently fitting ReLUs to data in the presence of Massart noise.
method Developed an efficient algorithm for exact parameter recovery under mild assumptions.
result Achieved exact parameter recovery in ReLU regression with Massart noise.
KSS method converges and recovers correct clustering under certain conditions.
problem Subspace clustering for semi-randomly sampled data.
method Local convergence analysis and recovery guarantee for KSS method.
result KSS method converges superlinearly and finds correct clustering within loglog N iterations.
A fast, non-iterative method for missing value imputation using random trees.
problem Missing value imputation in large and high-dimensional datasets.
method Recursive semi-random hyperplane cuts to assign observations to buckets and calculate weighted averages as imputations.
result Significantly faster than chained equations and scales well to large datasets.
MAX uses ensemble models to efficiently explore novel situations in reinforcement learning.
problem Efficient exploration in reinforcement learning.
method Model-based active exploration using ensemble forward models and Bayesian disagreement.
result MAX is at least an order of magnitude more efficient than baselines in semi-random environments.
New formula refutes random CSPs with fewer constraints.
problem Refuting random constraint satisfaction problems efficiently.
method Introduced a non-backtracking matrix and proved an Ihara-Bass formula.
result Efficiently refutes random CSPs with fewer constraints.
Graph clustering involves the task of dividing nodes into clusters, so that the edge density is higher within clusters as opposed to across clusters. A natural, classic and popular statistical setting for evaluating solutions to this problem is the stochastic block model, also referred to as the planted partition model…
Metric learning is a key problem for many data mining and machine learning applications, and has long been dominated by Mahalanobis methods. Recent advances in nonlinear metric learning have demonstrated the potential power of non-Mahalanobis distance functions, particularly tree-based functions. We propose a novel non…
Paper improves ℓ0-SSC for noisy data by proving SDP and proposing Noisy-DR-ℓ0-SSC.
problem Noisy data and less restrictive subspace affinity in sparse subspace clustering.
method Proposes Noisy-DR-ℓ0-SSC, which projects data onto a lower dimensional space and then applies noisy ℓ0-SSC. result Theoretical guarantee on the correctness of noisy ℓ0-SSC in terms of SDP on noisy data. This paper improves linear system solving by optimizing matrix diagonal scaling.
problem Improving the condition number of a matrix for faster iterative methods.
method Left or right diagonal rescaling of the matrix A, with new bounds and algorithms.
result Jacobi preconditioning reduces A's condition number to within a quadratic factor of the best possible scaling.
Proposes a new adversarial model to avoid accuracy vs. adversarial accuracy tradeoff.
problem Inherent tradeoff between accuracy and adversarial accuracy in existing adversarial robustness definitions.
method Introduces Voronoi-epsilon adversary that balances perturbation constraints.
result Voronoi-epsilon adversary avoids accuracy vs. adversarial accuracy tradeoff even with large ε. Adversarial consistency depends on the uniqueness of adversarial Bayes classifiers.
problem Consistency of adversarial surrogate losses is not guaranteed.
method Connected consistency of adversarial surrogate losses to the uniqueness of adversarial Bayes classifiers.
result A convex surrogate loss is statistically consistent for adversarial learning if and only if the adversarial Bayes classifier is unique.
New method makes neural networks more resilient to location-optimized adversarial patches.
problem Neural networks' vulnerability to adversarial patches that are visible but still effective.
method Developed a practical approach to optimize patch locations and applied adversarial training.
result Significantly improved robustness against adversarial patches on CIFAR10 and GTSRB.
Adversarial training achieves optimal test error for shallow networks.
problem Achieving optimal adversarial test error for general data distributions.
method Applying new Rademacher complexity bounds and properties of optimal adversarial predictors.
result Adversarial training can achieve optimal adversarial test error for general data distributions.
SPAT improves adversarial robustness by preserving semantics in adversarial training.
problem Adversarial examples often have different semantics than original data, introducing unintended biases.
method Semantics-preserving adversarial training (SPAT) that encourages pixel perturbation shared among all classes.
result SPAT improves adversarial robustness and achieves state-of-the-art results in CIFAR-10 and CIFAR-100.
Improves adversarial training generalization with domain adaptation.
problem Weak generalization of adversarial training due to lack of representative adversarial samples.
method Adversarial Training with Domain Adaptation (ATDA) method.
result ATDA greatly improves adversarial training generalization and model smoothness.
New approach improves adversarial robustness without sacrificing natural generalization.
problem Balancing adversarial robustness and natural generalization in machine learning.
method Friendly adversarial training (FAT) using early-stopped PGD to find least adversarial data.
result Early-stopped PGD achieves adversarial robustness without compromising natural generalization.
Adversarial training adds dynamic perturbations to neural networks for robustness.
problem Accuracy trade-off and lack of diversity in adversarial examples.
method Dynamic adversarial perturbations in the parameter space of neural networks, updating perturbation biases during training.
result Adversarial training with negligible cost and reduced accuracy trade-off.
Simple regularization methods mimic adversarial training's robustness.
problem Expensive adversarial training for robustness.
method Label smoothing and logit squeezing.
result Achieves strong adversarial robustness without adversarial examples.
Optimal control theory applied to machine learning adversarial attacks.
problem Adversarial machine learning threats and detection challenges.
method Optimal control theory applied to machine learning systems.
result Advances in control theory and reinforcement learning can enhance adversarial machine learning research.
Aims to make neural networks robust to small, imperceptible perturbations.
problem Neural networks can be fooled by small, imperceptible changes.
method Proposes a Generative Adversarial Networks (GAN) framework to learn robust classifiers.
result Our method outperforms adversarial training in robustness.
Paper analyzes adversarial risk using optimal transport.
problem Poor performance of machine learning on adversarial data.
method Optimal transport perspective, optimal transport plans (couplings), convexity, smoothness assumptions.
result Fundamental limits on adversarial risk calculated for various datasets.
New method makes neural networks more secure by protecting latent layers from adversarial attacks.
problem Vulnerability of latent layers in adversarially trained models to small perturbations.
method Latent Adversarial Training (LAT) and Latent Attack (LA) algorithms.
result Improves adversarial accuracy by 1-2% on MNIST, CIFAR-10, CIFAR-100 datasets.
Paper bounds convergence rate of adversarial surrogate risk.
problem Vulnerability of binary classification models to adversarial attacks.
method Characterizes conditions for adversarial consistency and provides surrogate risk bounds.
result Surrogate risk bounds quantify the rate of convergence of adversarial classification risk.
Study on robustness in linear regression models, focusing on adversarial perturbations.
problem Understanding and improving robustness in linear regression models to adversarial perturbations.
method Developed a two-stage adversarial learning framework that incorporates model structure information.
result Proved the consistency and developed the Bahadur representation of the adversarially robust estimator.
Free adversarial training improves robustness without generating adversarial examples.
problem Training robust models against adversarial attacks is costly and impractical for large-scale datasets.
method Recycles gradient information from parameter updates to generate adversarial examples.
result Free adversarial training achieves comparable robustness to PGD training at negligible cost.
Localized adversarial training improves image classifiers' robustness.
problem State-of-the-art image classifiers fail on carefully manipulated adversarial images.
method Developed a localized adversarial attack and used it to train a robust classifier.
result Localized adversarial training increases robustness against adversarial inputs.
Adversarial training improves gradient interpretability, reducing misinterpretations.
problem Improving gradient interpretability in adversarially trained deep networks.
method Identified and demonstrated that adversarial training restricts gradients closer to the image manifold, making them more interpretable.
result Adversarial training leads to more meaningful loss gradients, aligning better with human perception.
Paper tackles adversarial attacks on A3C path finding, proposing Gradient Band-based Adversarial Training.
problem Adversarial attacks on A3C path finding.
method Gradient Band-based Adversarial Training with CDG method.
result Gradient Band-based Adversarial Training achieves high attack immunity.
A two-step defense method generates strong adversarial examples at low cost.
problem Vulnerability of deep neural networks to adversarial attacks.
method Develops a two-step defense approach that generates strong adversarial examples using FGSM at a lower computational cost compared to traditional multi-step adversarial training.
result Demonstrates effectiveness of the two-step defense approach against various attack methods with comparable robustness to traditional multi-step adversarial training.
New method improves model robustness against adversarial attacks.
problem Models trained with adversarial samples can be vulnerable to simple attacks.
method Graybox Adversarial Training using intermediate models to seed adversaries.
result Models trained with Graybox Adversarial Training are more robust to simple attacks.
Improves deep neural networks' robustness against adversarial attacks.
problem Deep neural networks' vulnerability to adversarial perturbations.
method Joint training with a discriminator to filter adversarial noise.
result Preliminary experiments show improved adversarial robustness.
A Bayesian framework models adversarial uncertainty for robust machine learning.
problem Vulnerability of machine learning models to adversarial attacks.
method Formal Bayesian framework that models adversarial uncertainty through a stochastic channel, articulating probabilistic assumptions.
result Explicitly modeling adversarial uncertainty leads to improved robustification strategies.
Study evaluates adversarial attacks on speech emotion recognition systems.
problem Adversarial examples challenge the robustness of speech emotion recognition systems.
method Proposes adversarial training and GAN as defenses.
result Demonstrates effective use of adversarial examples for robustness.
Generative Adversarial Privacy (GAP) learns privacy mechanisms from data.
problem Learning optimal privacy mechanisms from data.
method Formulates privacy as a constrained minimax game between privatizer and adversary.
result GAP provides privacy guarantees against strong adversaries.
Adversarial training improves audio classifier robustness.
problem Improving robustness of audio classifiers against adversarial attacks.
method Adversarial training of deep neural networks on audio data.
result Adversarially trained models can resist higher perturbations and fooling rates.
Paper tackles robustness in adversarial noise with a meta-optimizer.
problem Sensitivity to adversarial noise hinders machine learning deployment.
method Meta-optimizer learns to robustly optimize models using adversarial examples.
result Meta-optimizer transfers adversarial knowledge to new models without generating new examples.
New adversarial examples with structured distortion sets improve robustness and perceptibility.
problem Improving adversarial robustness and perceptibility of images.
method Exploring and constraining adversarial search with trace-norms and other norms.
result Structured adversarial perturbations allow larger distortions and control over generation.
Survey of adversarial examples in visual machine learning models.
problem Vulnerability of machine learning models to adversarial examples.
method Exploration of various adversarial attack and defense methods.
result Understanding of adversarial attack and defense mechanisms.
Robust RL with learned optimal adversary improves agent performance under adversarial state observations.
problem Ensuring reinforcement learning agents' robustness against adversarial perturbations of state observations.
method Proposed a framework of alternating training with learned adversaries (ATLA) to find optimal adversarial policies and enhance agent robustness.
result ATLA achieves state-of-the-art performance under strong adversaries in continuous control environments.