亚洲男人的天堂2018av,欧美草比,久久久久久免费视频精选,国色天香在线看免费,久久久久亚洲av成人片仓井空

Principal component analysis (PCA) is a widely used dimension reduction technique in machine learning and multivariate statistics. To improve the interpretability of PCA, various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis (SPCA). In this paper, we present thresholding as a provably accurate, polynomial time, approximation algorithm for the SPCA problem, without imposing any restrictive assumptions on the input covariance matrix. Our first thresholding algorithm using the Singular Value Decomposition is conceptually simple; is faster than current state-of-the-art; and performs well in practice. On the negative side, our (novel) theoretical bounds do not accurately predict the strong practical performance of this approach. The second algorithm solves a well-known semidefinite programming relaxation and then uses a novel, two step, deterministic thresholding scheme to compute a sparse principal vector. It works very well in practice and, remarkably, this solid practical performance is accurately predicted by our theoretical bounds, which bridge the theory-practice gap better than current state-of-the-art.

Several learning problems involve solving min-max problems, e.g., empirical distributional robust learning or learning with non-standard aggregated losses. More specifically, these problems are convex-linear problems where the minimization is carried out over the model parameters $w\in\mathcal{W}$ and the maximization over the empirical distribution $p\in\mathcal{K}$ of the training set indexes, where $\mathcal{K}$ is the simplex or a subset of it. To design efficient methods, we let an online learning algorithm play against a (combinatorial) bandit algorithm. We argue that the efficiency of such approaches critically depends on the structure of $\mathcal{K}$ and propose two properties of $\mathcal{K}$ that facilitate designing efficient algorithms. We focus on a specific family of sets $\mathcal{S}_{n,k}$ encompassing various learning applications and provide high-probability convergence guarantees to the minimax values.

Recently, Balliu, Brandt, and Olivetti [FOCS '20] showed the first $\omega(\log^* n)$ lower bound for the maximal independent set (MIS) problem in trees. In this work we prove lower bounds for a much more relaxed family of distributed symmetry breaking problems. As a by-product, we obtain improved lower bounds for the distributed MIS problem in trees. For a parameter $k$ and an orientation of the edges of a graph $G$, we say that a subset $S$ of the nodes of $G$ is a $k$-outdegree dominating set if $S$ is a dominating set of $G$ and if in the induced subgraph $G[S]$, every node in $S$ has outdegree at most $k$. Note that for $k=0$, this definition coincides with the definition of an MIS. For a given $k$, we consider the problem of computing a $k$-outdegree dominating set. We show that, even in regular trees of degree at most $\Delta$, in the standard \LOCAL model, there exists a constant $\epsilon>0$ such that for $k\leq \Delta^\epsilon$, for the problem of computing a $k$-outdegree dominating set, any randomized algorithm requires at least $\Omega(\min\{\log\Delta,\sqrt{\log\log n}\})$ rounds and any deterministic algorithm requires at least $\Omega(\min\{\log\Delta,\sqrt{\log n}\})$ rounds. The proof of our lower bounds is based on the recently highly successful round elimination technique. We provide a novel way to do simplifications for round elimination, which we expect to be of independent interest. Our new proof is considerably simpler than the lower bound proof in [FOCS '20]. In particular, our round elimination proof uses a family of problems that can be described by only a constant number of labels. The existence of such a proof for the MIS problem was believed impossible by the authors of [FOCS '20].

We study Tikhonov regularization for possibly nonlinear inverse problems with weighted $\ell^1$-penalization. The forward operator, mapping from a sequence space to an arbitrary Banach space, typically an $L^2$-space, is assumed to satisfy a two-sided Lipschitz condition with respect to a weighted $\ell^2$-norm and the norm of the image space. We show that in this setting approximation rates of arbitrarily high H\"older-type order in the regularization parameter can be achieved, and we characterize maximal subspaces of sequences on which these rates are attained. On these subspaces the method also converges with optimal rates in terms of the noise level with the discrepancy principle as parameter choice rule. Our analysis includes the case that the penalty term is not finite at the exact solution ('oversmoothing'). As a standard example we discuss wavelet regularization in Besov spaces $B^r_{1,1}$. In this setting we demonstrate in numerical simulations for a parameter identification problem in a differential equation that our theoretical results correctly predict improved rates of convergence for piecewise smooth unknown coefficients.

The min-distance between two nodes $u, v$ is defined as the minimum of the distance from $v$ to $u$ or from $u$ to $v$, and is a natural distance metric in DAGs. As with the standard distance problems, the Strong Exponential Time Hypothesis [Impagliazzo-Paturi-Zane 2001, Calabro-Impagliazzo-Paturi 2009] leaves little hope for computing min-distance problems faster than computing All Pairs Shortest Paths, which can be solved in $\tilde{O}(mn)$ time. So it is natural to resort to approximation algorithms in $\tilde{O}(mn^{1-\epsilon})$ time for some positive $\epsilon$. Abboud, Vassilevska W., and Wang [SODA 2016] first studied min-distance problems achieving constant factor approximation algorithms on DAGs, obtaining a $3$-approximation algorithm for min-radius on DAGs which works in $\tilde{O}(m\sqrt{n})$ time, and showing that any $(2-\delta)$-approximation requires $n^{2-o(1)}$ time for any $\delta>0$, under the Hitting Set Conjecture. We close the gap, obtaining a $2$-approximation algorithm which runs in $\tilde{O}(m\sqrt{n})$ time. As the lower bound of Abboud et al only works for sparse DAGs, we further show that our algorithm is conditionally tight for dense DAGs using a reduction from Boolean matrix multiplication. Moreover, Abboud et al obtained a linear time $2$-approximation algorithm for min-diameter along with a lower bound stating that any $(3/2-\delta)$-approximation algorithm for sparse DAGs requires $n^{2-o(1)}$ time under SETH. We close this gap for dense DAGs by obtaining a $3/2$-approximation algorithm which works in $O(n^{2.350})$ time and showing that the approximation factor is unlikely to be improved within $O(n^{\omega - o(1)})$ time under the high dimensional Orthogonal Vectors Conjecture, where $\omega$ is the matrix multiplication exponent.

Multidimensional packing problems generalize the classical packing problems such as Bin Packing, Multiprocessor Scheduling by allowing the jobs to be $d$-dimensional vectors. While the approximability of the scalar problems is well understood, there has been a significant gap between the approximation algorithms and the hardness results for the multidimensional variants. In this paper, we close this gap by giving almost tight hardness results for these problems. 1. We show that Vector Bin Packing has no polynomial time $\Omega( \log d)$ factor asymptotic approximation algorithm when $d$ is a large constant, assuming $\textsf{P}\neq \textsf{NP}$. This matches the $\ln d + O(1)$ factor approximation algorithms (Chekuri, Khanna SICOMP 2004, Bansal, Caprara, Sviridenko SICOMP 2009, Bansal, Eli\'{a}s, Khan SODA 2016) upto constants. 2. We show that Vector Scheduling has no polynomial time algorithm with an approximation ratio of $\Omega\left( (\log d)^{1-\epsilon}\right)$ when $d$ is part of the input, assuming $\textsf{NP}\nsubseteq \textsf{ZPTIME}\left( n^{(\log n)^{O(1)}}\right)$. This almost matches the $O\left( \frac{\log d}{\log \log d}\right)$ factor algorithms(Harris, Srinivasan JACM 2019, Im, Kell, Kulkarni, Panigrahi SICOMP 2019). We also show that the problem is NP-hard to approximate within $(\log \log d)^{\omega(1)}$. 3. We show that Vector Bin Covering is NP-hard to approximate within $\Omega\left( \frac{\log d}{\log \log d}\right)$ when $d$ is part of the input, almost matching the $O(\log d)$ factor algorithm (Alon et al., Algorithmica 1998). Previously, no hardness results that grow with $d$ were known for Vector Scheduling and Vector Bin Covering when $d$ is part of the input and for Vector Bin Packing when $d$ is a fixed constant.

We give an algorithm, that given an $n$-vertex graph $G$ and an integer $k$, in time $2^{O(k)} n$ either outputs a tree decomposition of $G$ of width at most $2k + 1$ or determines that the treewidth of $G$ is larger than $k$. This is the first 2-approximation algorithm for treewidth that is faster than the known exact algorithms. In particular, our algorithm improves upon both the previous best approximation ratio of 5 in time $2^{O(k)} n$ and the previous best approximation ratio of 3 in time $2^{O(k)} n^{O(1)}$, both given by Bodlaender et al. [FOCS 2013, SICOMP 2016]. Our algorithm is based on a local improvement method adapted from a proof of Bellenbaum and Diestel [Comb. Probab. Comput. 2002].

This paper considers stochastic first-order algorithms for convex-concave minimax problems of the form $\min_{\bf x}\max_{\bf y}f(\bf x, \bf y)$, where $f$ can be presented by the average of $n$ individual components which are $L$-average smooth. For $\mu_x$-strongly-convex-$\mu_y$-strongly-concave setting, we propose a new method which could find a $\varepsilon$-saddle point of the problem in $\tilde{\mathcal O} \big(\sqrt{n(\sqrt{n}+\kappa_x)(\sqrt{n}+\kappa_y)}\log(1/\varepsilon)\big)$ stochastic first-order complexity, where $\kappa_x\triangleq L/\mu_x$ and $\kappa_y\triangleq L/\mu_y$. This upper bound is near optimal with respect to $\varepsilon$, $n$, $\kappa_x$ and $\kappa_y$ simultaneously. In addition, the algorithm is easily implemented and works well in practical. Our methods can be extended to solve more general unbalanced convex-concave minimax problems and the corresponding upper complexity bounds are also near optimal.

Let $p(n)$ denote the smallest prime divisor of the integer $n$. Define the function $g(k)$ to be the smallest integer $>k+1$ such that $p(\binom{g(k)}{k})>k$. So we have $g(2)=6$ and $g(3)=g(4)=7$. In this paper we present the following new results on the Erd\H{o}s-Selfridge function $g(k)$: We present a new algorithm to compute the value of $g(k)$, and use it to both verify previous work and compute new values of $g(k)$, with our current limit being $$ g(323)= 1\ 69829\ 77104\ 46041\ 21145\ 63251\ 22499. $$ We define a new function $\hat{g}(k)$, and under the assumption of our Uniform Distribution Heuristic we show that $$ \log g(k) = \log \hat{g}(k) + O(\log k) $$ with high "probability". We also provide computational evidence to support our claim that $\hat{g}(k)$ estimates $g(k)$ reasonably well in practice. There are several open conjectures on the behavior of $g(k)$ which we are able to prove for $\hat{g}(k)$, namely that $$ 0.525\ldots +o(1) \quad \le \quad \frac{\log \hat{g}(k)}{k/\log k} \quad \le \quad 1+o(1), $$ and that $$ \limsup_{k\rightarrow\infty} \frac{\hat{g}(k+1)}{\hat{g}(k)}=\infty.$$ Let $G(x,k)$ count the number of integers $n\le x$ such that $p(\binom{n}{k})>k$. Unconditionally, we prove that for large $x$, $G(x,k)$ is asymptotic to $x/\hat{g}(k)$. And finally, we show that the running time of our new algorithm is at most $g(k) \exp[ -c (k\log\log k) /(\log k)^2 (1+o(1))]$ for a constant $c>0$.

In this work, we consider the distributed optimization of non-smooth convex functions using a network of computing units. We investigate this problem under two regularity assumptions: (1) the Lipschitz continuity of the global objective function, and (2) the Lipschitz continuity of local individual functions. Under the local regularity assumption, we provide the first optimal first-order decentralized algorithm called multi-step primal-dual (MSPD) and its corresponding optimal convergence rate. A notable aspect of this result is that, for non-smooth functions, while the dominant term of the error is in $O(1/\sqrt{t})$, the structure of the communication network only impacts a second-order term in $O(1/t)$, where $t$ is time. In other words, the error due to limits in communication resources decreases at a fast rate even in the case of non-strongly-convex objective functions. Under the global regularity assumption, we provide a simple yet efficient algorithm called distributed randomized smoothing (DRS) based on a local smoothing of the objective function, and show that DRS is within a $d^{1/4}$ multiplicative factor of the optimal convergence rate, where $d$ is the underlying dimension.