Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userConsistent $k$-Median: Simpler, Better and Robust
103
0
0.0
(
0
)
Added by
Xiangyu Guo
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper we introduce and study the online consistent $k$-clustering with outliers problem, generalizing the non-outlier version of the problem studied in [Lattanzi-Vassilvitskii, ICML17]. We show that a simple local-search based online algorithm can give a bicriteria constant approximation for the problem with $O(k^2 log^2 (nD))$ swaps of medians (recourse) in total, where $D$ is the diameter of the metric. When restricted to the problem without outliers, our algorithm is simpler, deterministic and gives better approximation ratio and recourse, compared to that of [Lattanzi-Vassilvitskii, ICML17].
rate research
Read More
The $k$-Facility Location problem is a generalization of the classical problems $k$-Median and Facility Location. The goal is to select a subset of at most $k$ facilities that minimizes the total cost of opened facilities and established connections between clients and opened facilities. We consider the hard-capacitated version of the problem, where a single facility may only serve a limited number of clients and creating multiple copies of a facility is not allowed. We construct approximation algorithms slightly violating the capacities based on rounding a fractional solution to the standard LP. It is well known that the standard LP (even in the case of uniform capacities and opening costs) has unbounded integrality gap if we only allow violating capacities by a factor smaller than $2$, or if we only allow violating the number of facilities by a factor smaller than $2$. In this paper, we present the first constant-factor approximation algorithms for the hard-capacitated variants of the problem. For uniform capacities, we obtain a $(2+varepsilon)$-capacity violating algorithm with approximation ratio $O(1/varepsilon^2)$; our result has not yet been improved. Then, for non-uniform capacities, we consider the case of $k$-Median, which is equivalent to $k$-Facility Location with uniform opening cost of the facilities. Here, we obtain a $(3+varepsilon)$-capacity violating algorithm with approximation ratio $O(1/varepsilon)$.
We study the Capacitated k-Median problem, for which all the known constant factor approximation algorithms violate either the number of facilities or the capacities. While the standard LP-relaxation can only be used for algorithms violating one of the two by a factor of at least two, Shi Li [SODA15, SODA16] gave algorithms violating the number of facilities by a factor of 1+{epsilon} exploring properties of extended relaxations. In this paper we develop a constant factor approximation algorithm for Uniform Capacitated k-Median violating only the capacities by a factor of 1+{epsilon}. The algorithm is based on a configuration LP. Unlike in the algorithms violating the number of facilities, we cannot simply open extra few facilities at selected locations. Instead, our algorithm decides about the facility openings in a carefully designed dependent rounding process.
Adversarial training (AT) has been demonstrated as one of the most promising defense methods against various adversarial attacks. To our knowledge, existing AT-based methods usually train with the locally most adversarial perturbed points and treat all the perturbed points equally, which may lead to considerably weaker adversarial robust generalization on test data. In this work, we introduce a new adversarial training framework that considers the diversity as well as characteristics of the perturbed points in the vicinity of benign samples. To realize the framework, we propose a Regional Adversarial Training (RAT) defense method that first utilizes the attack path generated by the typical iterative attack method of projected gradient descent (PGD), and constructs an adversarial region based on the attack path. Then, RAT samples diverse perturbed training points efficiently inside this region, and utilizes a distance-aware label smoothing mechanism to capture our intuition that perturbed points at different locations should have different impact on the model performance. Extensive experiments on several benchmark datasets show that RAT consistently makes significant improvement on standard adversarial training (SAT), and exhibits better robust generalization.
Transfer learning is a widely-used paradigm in deep learning, where models pre-trained on standard datasets can be efficiently adapted to downstream tasks. Typically, better pre-trained models yield better transfer results, suggesting that initial accuracy is a key aspect of transfer learning performance. In this work, we identify another such aspect: we find that adversarially robust models, while less accurate, often perform better than their standard-trained counterparts when used for transfer learning. Specifically, we focus on adversarially robust ImageNet classifiers, and show that they yield improved accuracy on a standard suite of downstream classification tasks. Further analysis uncovers more differences between robust and standard models in the context of transfer learning. Our results are consistent with (and in fact, add to) recent hypotheses stating that robustness leads to improved feature representations. Our code and models are available at https://github.com/Microsoft/robust-models-transfer .
In the decremental $(1+epsilon)$-approximate Single-Source Shortest Path (SSSP) problem, we are given a graph $G=(V,E)$ with $n = |V|, m = |E|$, undergoing edge deletions, and a distinguished source $s in V$, and we are asked to process edge deletions efficiently and answer queries for distance estimates $widetilde{mathbf{dist}}_G(s,v)$ for each $v in V$, at any stage, such that $mathbf{dist}_G(s,v) leq widetilde{mathbf{dist}}_G(s,v) leq (1+ epsilon)mathbf{dist}_G(s,v)$. In the decremental $(1+epsilon)$-approximate All-Pairs Shortest Path (APSP) problem, we are asked to answer queries for distance estimates $widetilde{mathbf{dist}}_G(u,v)$ for every $u,v in V$. In this article, we consider the problems for undirected, unweighted graphs. We present a new emph{deterministic} algorithm for the decremental $(1+epsilon)$-approximate SSSP problem that takes total update time $O(mn^{0.5 + o(1)})$. Our algorithm improves on the currently best algorithm for dense graphs by Chechik and Bernstein [STOC 2016] with total update time $tilde{O}(n^2)$ and the best existing algorithm for sparse graphs with running time $tilde{O}(n^{1.25}sqrt{m})$ [SODA 2017] whenever $m = O(n^{1.5 - o(1)})$. In order to obtain this new algorithm, we develop several new techniques including improved decremental cover data structures for graphs, a more efficient notion of the heavy/light decomposition framework introduced by Chechik and Bernstein and the first clustering technique to maintain a dynamic emph{sparse} emulator in the deterministic setting. As a by-product, we also obtain a new simple deterministic algorithm for the decremental $(1+epsilon)$-approximate APSP problem with near-optimal total running time $tilde{O}(mn /epsilon)$ matching the time complexity of the sophisticated but rather involved algorithm by Henzinger, Forster and Nanongkai [FOCS 2013].
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
