Study on proper learning under relaxed worst-case robust loss for VC classes.
problem Proper adversarially robust PAC learning under relaxed worst-case robust loss.
method Introduced a family of robust loss relaxations and showed their effectiveness for proper learnability.
result VC classes are properly PAC learnable with sample complexity close to standard PAC learning setup.
Despite their impressive performance on diverse tasks, neural networks fail catastrophically in the presence of adversarial inputs---imperceptibly but adversarially perturbed versions of natural inputs. We have witnessed an arms race between defenders who attempt to train robust networks and attackers who try to constr…
New algorithms achieve better regret bounds for online classification with relaxed benchmarks.
problem Competing with worst-case optimal binary loss in online classification.
method Comparing against predictors robust to small input perturbations, performing well under Gaussian smoothing, or maintaining a prescribed output margin.
result Regret guarantees depend only on VC dimension and instance space complexity, with an O(log(1/γ)) dependence on the generalized margin. SAM improves deep learning by relaxing Bayes objective.
problem Improving generalization in deep learning models.
method SAM as a relaxation of Bayes objective using Fenchel biconjugate.
result SAM connects adversarial and Bayesian methods for robustness.
This paper studies noisy low-rank matrix completion: given partial and noisy entries of a large low-rank matrix, the goal is to estimate the underlying matrix faithfully and efficiently. Arguably one of the most popular paradigms to tackle this problem is convex relaxation, which achieves remarkable efficacy in practic…
Paper relaxes SGD privacy and generalization guarantees for non-smooth convex losses.
problem Privacy and generalization in SGD for non-smooth convex losses.
method Relaxes Lipschitz and strong smoothness assumptions to Hölder smoothness, proving (ε,δ)-DP and optimal excess risk. result Noisy SGD with α-Hölder smooth losses achieves optimal excess risk with linear gradient complexity for α≥1/2. New regularizers tighten convex relaxation bounds for neural networks.
problem Large gap between certifiable and empirical robustness in neural networks.
method Two regularizers to train neural networks yielding tighter convex relaxation bounds.
result Higher certified accuracy with proposed regularizers.
Improved neural network robustness certification through tighter convex relaxations.
problem Certifying neural network robustness to perturbed and adversarial inputs.
method Exploiting ReLU network structure, novel partition-based certification procedure.
result Tightens existing linear programming relaxations to achieve zero relaxation error asymptotically.
New method improves adversarial training robustness.
problem Lack of tight upper bounds for adversarial training.
method Holistic expansion of the network for upper bound minimization.
result RUB and aRUB methods are more robust than state-of-the-art methods.
Paper proposes robust tensor regression method for tensor data analysis.
problem Outliers in tensor data analysis can make existing methods sensitive.
method Nonconvex relaxation of tensor tubal rank in optimization framework.
result Global convergence of proposed estimation algorithm under mild assumptions.
Renet improves Elastic Net by dynamically selecting between convex blending and refitting, enhancing prediction accuracy.
problem Elastic Net's shrinkage bias limits its prediction accuracy in high-dimensional settings.
method Adaptive relaxation procedure that dynamically dispatches between convex blending and efficient sub-path refitting.
result Renet consistently outperforms standard Elastic Net and Adaptive Elastic Net in high-dimensional, low signal-to-noise ratio, and high-multicollinearity scenarios.
Proposes new convex relaxations for certifying spatial robustness of neural networks.
problem Lack of provable guarantees for robustness against vector field transformations.
method Novel convex relaxations for certifying robustness against vector field transformations.
result First time providing a certificate of robustness against vector field transformations.
Paper improves robust PCA for noisy, outlier, and missing data.
problem Robust PCA with noise, outliers, and missing data.
method Bridging convex and nonconvex optimization.
result Near-optimal statistical accuracy for robust PCA.
Bayesian analysis reveals asymmetry in financial data.
problem Quantifying asymmetry in financial time series data.
method Bayesian approach, t-Test generalization, two data distribution models, sensitivity analysis.
result Statistical significance of gain/loss asymmetry amounts.
This paper tackles robust control of noisy systems with uncertain distributions.
problem Optimal control of sampled-data stochastic systems with multiplicative noise and distributional ambiguity.
method Develops a convex relaxation to handle the ``concave-max'' geometry and derives a probabilistic performance guarantee.
result Derives an explicit, non-asymptotic bound on the duality gap and proves robust viability conditions.
Covariate shift relaxes the widely-employed independent and identically distributed (IID) assumption by allowing different training and testing input distributions. Unfortunately, common methods for addressing covariate shift by trying to remove the bias between training and testing distributions using importance weigh…
Geometric technique determines exactness of SDP robustness certificate.
problem Certifying robustness of neural networks to adversarial examples.
method Geometric projection onto hyperbola, SDP relaxation of ReLU activation.
result SDP certificate is exact for a single hidden layer under mild assumptions.
Verification of neural networks enables us to gauge their robustness against adversarial attacks. Verification algorithms fall into two categories: exact verifiers that run in exponential time and relaxed verifiers that are efficient but incomplete. In this paper, we unify all existing LP-relaxed verifiers, to the best…
This work improves certifiably robust models by distilling knowledge from adversarially robust teachers.
problem Certifiably robust models suffer from poor standard performance.
method Knowledge distillation from adversarially robust teachers to improve standard performance.
result Distillation from adversarially robust teachers consistently improves certified training performance.
The paper tackles robust domain generalization by accounting for unobserved confounders.
problem Learning robust, generalizable models from multiple datasets in the presence of unobserved confounders.
method Defines a new invariance property for causal solutions, connects it to distributionally robust optimization, and incorporates regularization to encourage partial equality of error derivatives.
result Demonstrates the empirical effectiveness of the approach on healthcare data from various modalities.
New bound relaxes uniform gradient norm assumptions for PAC-Bayesian bounds.
problem Generalization bounds with strict assumptions like uniformly bounded loss.
method Relax uniform bounds assumptions to on-average bounded loss and gradient norm.
result Proposes a new generalization bound with a surrogate of model complexity.
New analysis improves SGD for robust and quantile regression with sub-quadratic convergence.
problem Improving SGD for robust and quantile regression with sub-quadratic convergence.
method Piecewise Lyapunov function for first-order differentiable functions.
result First geometrical convergence result for sub-quadratic SGD.
Develops a robust multiclass classification method for deep image classifiers.
problem Tackles data contamination and robustness to outliers in deep image classifiers.
method Uses Distributionally Robust Optimization (DRO) with Wasserstein metric ambiguity sets and regularized learning.
result Reduces test error rate by up to 83.5% and loss by up to 91.3% in image classification tasks.
Polynomial-time private algorithm for robust estimation of mean and covariance in the presence of outliers.
problem Estimating mean and covariance in the presence of adversarial outliers.
method Stabilizing convex relaxations using a new estimate-dependent noise injection mechanism.
result First efficient private robust estimation algorithm for covariance without condition-number assumptions.
Training neural networks with verifiable robustness guarantees is challenging. Several existing approaches utilize linear relaxation based neural network output bounds under perturbation, but they can slow down training by a factor of hundreds depending on the underlying network architectures. Meanwhile, interval bound…
New method closes certification gap for adversarially trained models.
problem Certifying robustness of adversarially trained neural networks.
method Nonconvex low-rank SDP relaxation with polynomial-time optimization.
result Strong certifications comparable to SDP methods, but with fewer variables.
Improved training boosts certified robustness of L-infinity distance nets.
problem Certified robustness of L-infinity distance nets is not as strong as conventional networks.
method Improved training process combining scaled cross-entropy and clipped hinge loss with a decaying mixing coefficient.
result Certified accuracy of L-infinity distance nets improved from 33.30% to 40.06% on CIFAR-10.
In recent years, the softmax model and its fast approximations have become the de-facto loss functions for deep neural networks when dealing with multi-class prediction. This loss has been extended to language modeling and recommendation, two fields that fall into the framework of learning from Positive and Unlabeled d…
Graph based clustering is one of the major clustering methods. Most of it work in three separate steps: similarity graph construction, clustering label relaxing and label discretization with k-means. Such common practice has three disadvantages: 1) the predefined similarity graph is often fixed and may not be optimal f…
Paper relaxes stability and generalization assumptions for SGD.
problem Stability and generalization for SGD under restrictive assumptions.
method Introduces on-average model stability and develops novel bounds.
result First-ever-known fast bounds in low-noise setting using stability approach.
New method solves subspace optimization problems efficiently.
problem Finding a k-dimensional subspace in high dimensions.
method Local linear convergence of gradient methods under strict complementarity.
result Gradient method converges linearly in high dimensions.
Bayesian adversaries can outsmart traditional adversarial attacks.
problem Bayesian adversaries can manipulate machine learning models through small perturbations.
method Developed a continuous-time particle system (Abram) to approximate the gradient flow of the Bayesian adversarial robustness problem.
result Abram approximates the minimizer of the Bayesian adversarial robustness problem under certain assumptions.
This work interprets SFA through variational inference, relaxing linearity constraints.
problem Recover non-linear SFA from variational inference.
method Probabilistic interpretation of SFA through variational inference, relaxing linearity constraints.
result Reinterprets SFA as a variational framework, allowing slowness as a regularizer to reconstruction loss.
Enhanced H-consistency bounds derived under relaxed conditions.
problem Quantifying the relationship between zero-one estimation error and surrogate loss estimation error.
method Relaxing the condition on the surrogate loss conditional regret and presenting a general framework for establishing enhanced H-consistency bounds. result Derivation of more favorable H-consistency bounds in various scenarios. Automates perturbation analysis for neural networks, enabling certified robustness on complex architectures.
problem Limited applicability of existing perturbation analysis methods to complex neural network architectures.
method Developed an automatic framework to generalize LiRPA algorithms to any neural network structure, enabling loss fusion and state-of-the-art certified defense results.
result Demonstrated LiRPA based certified defense on Tiny ImageNet and Downscaled ImageNet.
Compressed sensing (CS) shows that a signal having a sparse or compressible representation can be recovered from a small set of linear measurements. In classical CS theory, the sampling matrix and representation matrix are assumed to be known exactly in advance. However, uncertainties exist due to sampling distortion, …
This paper improves loss functions for deep learning with noisy labels.
problem Training deep neural networks with noisy labels.
method The paper introduces a normalization technique to make any loss function robust to noisy labels and proposes a framework called Active Passive Loss (APL) to combine robust loss functions.
result The proposed APL framework consistently outperforms state-of-the-art methods, especially under high noise rates.
A new Branch-and-Bound solver tackles L0-penalized problems with flexible loss functions.
problem Solving L0-penalized optimization problems with a broader class of loss functions.
method Generic Branch-and-Bound procedure with closed-form expressions for key quantities.
result El0ps solver achieves state-of-the-art performance and extends computational feasibility.
Differentiable Architecture Search (DARTS) has attracted a lot of attention due to its simplicity and small search costs achieved by a continuous relaxation and an approximation of the resulting bi-level optimization problem. However, DARTS does not work robustly for new problems: we identify a wide range of search spa…
Paper simplifies balancing weights by relaxing outcome assumptions.
problem Estimating missing outcomes in a target population.
method Relaxes outcome assumptions to simplify balancing weights.
result Balancing weights can be simplified with convex loss and minimum worst-case bias.
We demonstrate that almost all non-parametric dimensionality reduction methods can be expressed by a simple procedure: regularized loss minimization plus singular value truncation. By distinguishing the role of the loss and regularizer in such a process, we recover a factored perspective that reveals some gaps in the c…
New algorithm learns mixtures of any constant number of Gaussians robustly.
problem Learning mixtures of Gaussians with robustness guarantees.
method New method using differential operations on generating functions to prove polynomial identifiability.
result First provably robust algorithm for mixtures of any constant number of Gaussians.
Optimal transport simplifies machine learning by comparing probability measures.
problem Comparing and manipulating probability distributions in machine learning.
method Uses optimal transport to compare and manipulate probability distributions, combining statistical and geometric perspectives.
result Optimal transport provides a unified framework for various machine learning tasks.
New research shows flat minima in robust loss landscapes correlate with good adversarial robustness.
problem Adversarial training leads to robust overfitting, poor robust generalization.
method Average- and worst-case metrics to measure flatness in robust loss landscapes.
result Flatness in robust loss landscapes correlates with good adversarial robustness.
The paper proves deep learning can be robust with certain loss functions.
problem The robustness of deep learning models under flawed data.
method Empirical-risk minimization with unbounded, Lipschitz-continuous loss functions.
result These loss functions provide efficient prediction under minimal data assumptions.
Bayesian learning is often hampered by large computational expense. As a powerful generalization of popular belief propagation, expectation propagation (EP) efficiently approximates the exact Bayesian computation. Nevertheless, EP can be sensitive to outliers and suffer from divergence for difficult cases. To address t…
The paper sets lower bounds for adversarial robustness in multiclass classification.
problem Adversarial robustness in multiclass classification with arbitrary loss functions.
method Dual and barycentric reformulations for robust risk minimization.
result Sharp lower bounds for adversarial risks are computed efficiently.
Paper relaxes factor analysis for noisy data, improving robustness.
problem Challenges in finding robust low dimensional approximations for data with heteroskedastic noise.
method Introduces a relaxed version of Minimum Trace Factor Analysis (MTFA) as a convex optimization method.
result Effective at not overfitting to heteroskedastic perturbations and addressing common issues in factor analysis.