Robust Structured Statistical Estimation via Conditional Gradient Type Methods

• URL: http://arxiv.org/abs/2007.03572v1
• Date: Tue, 7 Jul 2020 15:49:31 GMT
• Title: Robust Structured Statistical Estimation via Conditional Gradient Type Methods
• Authors: Jiacheng Zhuo, Liu Liu, Constantine Caramanis
• Abstract summary: Conditional Gradient (CG) type methods are often used to solve structured statistical estimation problems. We propose to robustify CG type methods against Huber's corruption model and heavy-tailed data. We show that the two Pairwise CG methods are stable, i.e., do not accumulate error.
• Score: 25.816720329145102
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Structured statistical estimation problems are often solved by Conditional Gradient (CG) type methods to avoid the computationally expensive projection operation. However, the existing CG type methods are not robust to data corruption. To address this, we propose to robustify CG type methods against Huber's corruption model and heavy-tailed data. First, we show that the two Pairwise CG methods are stable, i.e., do not accumulate error. Combined with robust mean gradient estimation techniques, we can therefore guarantee robustness to a wide class of problems, but now in a projection-free algorithmic framework. Next, we consider high dimensional problems. Robust mean estimation based approaches may have an unacceptably high sample complexity. When the constraint set is a $\ell_0$ norm ball, Iterative-Hard-Thresholding-based methods have been developed recently. Yet extension is non-trivial even for general sets with $O(d)$ extreme points. For setting where the feasible set has $O(\text{poly}(d))$ extreme points, we develop a novel robustness method, based on a new condition we call the Robust Atom Selection Condition (RASC). When RASC is satisfied, our method converges linearly with a corresponding statistical error, with sample complexity that scales correctly in the sparsity of the problem, rather than the ambient dimension as would be required by any approach based on robust mean estimation.

Related papers

• Geometric Median (GM) Matching for Robust Data Pruning [29.458270105150564]
  Data pruning is crucial for mitigating the enormous computational costs associated with training data-hungry models at scale. In this work, we propose Geometric ($gm$) Matching that yields a $k$-subset such that the mean of the subset approximates the median of the (potentially) noisy dataset. Experiments across popular deep learning benchmarks indicate that $gm$ Matching consistently outperforms prior state-of-the-art.
  arXiv  Detail & Related papers  (2024-06-25T00:02:01Z)
• Large-Scale Non-convex Stochastic Constrained Distributionally Robust Optimization [23.029511473335145]
  This paper focuses on constrained DRO, which has an explicit characterization of the robustness of its performance. The complexity of our algorithm at each $chi2$-divergences point$ is independent overall dataset size, and thus is suitable for large-scale applications.
  arXiv  Detail & Related papers  (2024-04-01T15:56:58Z)
• Sobolev Space Regularised Pre Density Models [51.558848491038916]
  We propose a new approach to non-parametric density estimation that is based on regularizing a Sobolev norm of the density. This method is statistically consistent, and makes the inductive validation model clear and consistent.
  arXiv  Detail & Related papers  (2023-07-25T18:47:53Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  Many real-world problems have complicated non functional constraints and use a large number of data points. Our proposed method outperforms an existing method with the previously best-known result.
  arXiv  Detail & Related papers  (2022-12-19T14:48:54Z)
• Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes [59.61248760134937]
  We propose an efficient algorithm to achieve a regret of $tildeO(sqrtT+zeta)$. The proposed algorithm relies on the recently developed uncertainty-weighted least-squares regression from linear contextual bandit. We generalize our algorithm to the episodic MDP setting and first achieve an additive dependence on the corruption level $zeta$.
  arXiv  Detail & Related papers  (2022-12-12T15:04:56Z)
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent [69.47594803719333]
  Geometric median (textGm) is a classical method in statistics for achieving a robust estimation of the uncorrupted data. In this paper, we show that by that by applying textscGm to only a chosen block of coordinates at a time, one can retain a breakdown point of 0.5 judiciously for smooth nontext problems.
  arXiv  Detail & Related papers  (2021-06-16T15:55:50Z)
• Adversarial Robustness Guarantees for Gaussian Processes [22.403365399119107]
  Gaussian processes (GPs) enable principled computation of model uncertainty, making them attractive for safety-critical applications. We present a framework to analyse adversarial robustness of GPs, defined as invariance of the model's decision to bounded perturbations. We develop a branch-and-bound scheme to refine the bounds and show, for any $epsilon > 0$, that our algorithm is guaranteed to converge to values $epsilon$-close to the actual values in finitely many iterations.
  arXiv  Detail & Related papers  (2021-04-07T15:14:56Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  We prove that our algorithms require a number of evaluations gradient independent of training set size and number of parameters. Experiments on MNIST and ImageNet confirm the theoretical scaling of our algorithms, which are 9--36 times more efficient than full-batch methods.
  arXiv  Detail & Related papers  (2020-10-12T17:41:44Z)
• Kidney Exchange with Inhomogeneous Edge Existence Uncertainty [33.17472228570093]
  We aim to maximize a matched cycle and chain packing problem, where we aim to identify structures in a directed graph to the edge of failure. Our approaches on data from the United for Sharing (SUNO) provides better performance with the same weights as as an SAA-based method.
  arXiv  Detail & Related papers  (2020-07-07T04:08:39Z)
• High-Dimensional Robust Mean Estimation via Gradient Descent [73.61354272612752]
  We show that the problem of robust mean estimation in the presence of a constant adversarial fraction can be solved by gradient descent. Our work establishes an intriguing connection between the near non-lemma estimation and robust statistics.
  arXiv  Detail & Related papers  (2020-05-04T10:48:04Z)
• Entropy Regularized Power k-Means Clustering [21.013169939337583]
  We propose a scalable majorization-minimization algorithm that enjoys closed-form updates and convergence guarantees. Our method retains the same computational complexity of $k$-means and power $k$-means, but yields significant improvements over both.
  arXiv  Detail & Related papers  (2020-01-10T14:05:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.