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

We give a simple characterization of which functions can be computed deterministically by anonymous processes in disconnected dynamic networks, depending on the number of leaders in the network. In addition, we provide efficient distributed algorithms for computing all such functions assuming minimal or no knowledge about the network. Each of our algorithms comes in two versions: one that terminates with the correct output and a faster one that stabilizes on the correct output without explicit termination. Notably, these are the first deterministic algorithms whose running times scale linearly with both the number of processes and a parameter of the network which we call "dynamic disconnectivity". We also provide matching lower bounds, showing that all our algorithms are asymptotically optimal for any fixed number of leaders. While most of the existing literature on anonymous dynamic networks relies on classical mass-distribution techniques, our work makes use of a recently introduced combinatorial structure called "history tree", also developing its theory in new directions. Among other contributions, our results make definitive progress on two popular fundamental problems for anonymous dynamic networks: leaderless Average Consensus (i.e., computing the mean value of input numbers distributed among the processes) and multi-leader Counting (i.e., determining the exact number of processes in the network). In fact, our approach unifies and improves upon several independent lines of research on anonymous networks, including Nedic et al., IEEE Trans. Automat. Contr. 2009; Olshevsky, SIAM J. Control Optim. 2017; Kowalski-Mosteiro, ICALP 2019, SPAA 2021; Di Luna-Viglietta, FOCS 2022.

Given an undirected graph $G=(V,E)$ with a nonnegative edge length function and an integer $p$, $0 < p < |V|$, the $p$-centdian problem is to find $p$ vertices (called the {\it centdian set}) of $V$ such that the {\it eccentricity} plus {\it median-distance} is minimized, in which the {\it eccentricity} is the maximum (length) distance of all vertices to their nearest {\it centdian set} and the {\it median-distance} is the total (length) distance of all vertices to their nearest {\it centdian set}. The {\it eccentricity} plus {\it median-distance} is called the {\it centdian-distance}. The purpose of the $p$-centdian problem is to find $p$ open facilities (servers) which satisfy the quality-of-service of the minimum total distance ({\it median-distance}) and the maximum distance ({\it eccentricity}) to their service customers, simultaneously. If we converse the two criteria, that is given the bound of the {\it centdian-distance} and the objective function is to minimize the cardinality of the {\it centdian set}, this problem is called the converse centdian problem. In this paper, we prove the $p$-centdian problem is NP-Complete. Then we design the first non-trivial brute force exact algorithms for the $p$-centdian problem and the converse centdian problem, respectively. Finally, we design two approximation algorithms for both problems.

In this paper, we present several new results on minimizing a nonsmooth and nonconvex function under a Lipschitz condition. Recent work shows that while the classical notion of Clarke stationarity is computationally intractable up to some sufficiently small constant tolerance, the randomized first-order algorithms find a $(\delta, \epsilon)$-Goldstein stationary point with the complexity bound of $\tilde{O}(\delta^{-1}\epsilon^{-3})$, which is independent of dimension $d \geq 1$~\citep{Zhang-2020-Complexity, Davis-2022-Gradient, Tian-2022-Finite}. However, the deterministic algorithms have not been fully explored, leaving open several problems in nonsmooth nonconvex optimization. Our first contribution is to demonstrate that the randomization is \textit{necessary} to obtain a dimension-independent guarantee, by proving a lower bound of $\Omega(d)$ for any deterministic algorithm that has access to both $1^{st}$ and $0^{th}$ oracles. Furthermore, we show that the $0^{th}$ oracle is \textit{essential} to obtain a finite-time convergence guarantee, by showing that any deterministic algorithm with only the $1^{st}$ oracle is not able to find an approximate Goldstein stationary point within a finite number of iterations up to sufficiently small constant parameter and tolerance. Finally, we propose a deterministic smoothing approach under the \textit{arithmetic circuit} model where the resulting smoothness parameter is exponential in a certain parameter $M > 0$ (e.g., the number of nodes in the representation of the function), and design a new deterministic first-order algorithm that achieves a dimension-independent complexity bound of $\tilde{O}(M\delta^{-1}\epsilon^{-3})$.

A signal recovery problem is considered, where the same binary testing problem is posed over multiple, independent data streams. The goal is to identify all signals, i.e., streams where the alternative hypothesis is correct, and noises, i.e., streams where the null hypothesis is correct, subject to prescribed bounds on the classical or generalized familywise error probabilities. It is not required that the exact number of signals be a priori known, only upper bounds on the number of signals and noises are assumed instead. A decentralized formulation is adopted, according to which the sample size and the decision for each testing problem must be based only on observations from the corresponding data stream. A novel multistage testing procedure is proposed for this problem and is shown to enjoy a high-dimensional asymptotic optimality property. Specifically, it achieves the optimal, average over all streams, expected sample size, uniformly in the true number of signals, as the maximum possible numbers of signals and noises go to infinity at arbitrary rates, in the class of all sequential tests with the same global error control. In contrast, existing multistage tests in the literature are shown to achieve this high-dimensional asymptotic optimality property only under additional sparsity or symmetry conditions. These results are based on an asymptotic analysis for the fundamental binary testing problem as the two error probabilities go to zero. For this problem, unlike existing multistage tests in the literature, the proposed test achieves the optimal expected sample size under both hypotheses, in the class of all sequential tests with the same error control, as the two error probabilities go to zero at arbitrary rates. These results are further supported by simulation studies and extended to problems with non-iid data and composite hypotheses.

We introduce a new measure for the performance of online algorithms in Bayesian settings, where the input is drawn from a known prior, but the realizations are revealed one-by-one in an online fashion. Our new measure is called order-competitive ratio. It is defined as the worst case (over all distribution sequences) ratio between the performance of the best order-unaware and order-aware algorithms, and quantifies the loss that is incurred due to lack of knowledge of the arrival order. Despite the growing interest in the role of the arrival order on the performance of online algorithms, this loss has been overlooked thus far. We study the order-competitive ratio in the paradigmatic prophet inequality problem, for the two common objective functions of (i) maximizing the expected value, and (ii) maximizing the probability of obtaining the largest value; and with respect to two families of algorithms, namely (i) adaptive algorithms, and (ii) single-threshold algorithms. We provide tight bounds for all four combinations, with respect to deterministic algorithms. Our analysis requires new ideas and departs from standard techniques. In particular, our adaptive algorithms inevitably go beyond single-threshold algorithms. The results with respect to the order-competitive ratio measure capture the intuition that adaptive algorithms are stronger than single-threshold ones, and may lead to a better algorithmic advice than the classical competitive ratio measure.

We investigate the distributed complexity of maximal matching and maximal independent set (MIS) in hypergraphs in the LOCAL model. A maximal matching of a hypergraph $H=(V_H,E_H)$ is a maximal disjoint set $M\subseteq E_H$ of hyperedges and an MIS $S\subseteq V_H$ is a maximal set of nodes such that no hyperedge is fully contained in $S$. Both problems can be solved by a simple sequential greedy algorithm, which can be implemented naively in $O(\Delta r + \log^* n)$ rounds, where $\Delta$ is the maximum degree, $r$ is the rank, and $n$ is the number of nodes. We show that for maximal matching, this naive algorithm is optimal in the following sense. Any deterministic algorithm for solving the problem requires $\Omega(\min\{\Delta r, \log_{\Delta r} n\})$ rounds, and any randomized one requires $\Omega(\min\{\Delta r, \log_{\Delta r} \log n\})$ rounds. Hence, for any algorithm with a complexity of the form $O(f(\Delta, r) + g(n))$, we have $f(\Delta, r) \in \Omega(\Delta r)$ if $g(n)$ is not too large, and in particular if $g(n) = \log^* n$ (which is the optimal asymptotic dependency on $n$ due to Linial's lower bound [FOCS'87]). Our lower bound proof is based on the round elimination framework, and its structure is inspired by a new round elimination fixed point that we give for the $\Delta$-vertex coloring problem in hypergraphs. For the MIS problem on hypergraphs, we show that for $\Delta\ll r$, there are significant improvements over the naive $O(\Delta r + \log^* n)$-round algorithm. We give two deterministic algorithms for the problem. We show that a hypergraph MIS can be computed in $O(\Delta^2\cdot\log r + \Delta\cdot\log r\cdot \log^* r + \log^* n)$ rounds. We further show that at the cost of a worse dependency on $\Delta$, the dependency on $r$ can be removed almost entirely, by giving an algorithm with complexity $\Delta^{O(\Delta)}\cdot\log^* r + O(\log^* n)$.

This work proposes a universal and adaptive second-order method for minimizing second-order smooth, convex functions. Our algorithm achieves $O(\sigma / \sqrt{T})$ convergence when the oracle feedback is stochastic with variance $\sigma^2$, and improves its convergence to $O( 1 / T^3)$ with deterministic oracles, where $T$ is the number of iterations. Our method also interpolates these rates without knowing the nature of the oracle apriori, which is enabled by a parameter-free adaptive step-size that is oblivious to the knowledge of smoothness modulus, variance bounds and the diameter of the constrained set. To our knowledge, this is the first universal algorithm with such global guarantees within the second-order optimization literature.

Fully pairing all elements of a set while attempting to maximize the total benefit is a combinatorically difficult problem. Such pairing problems naturally appear in various situations in science, technology, economics, and other fields. In our previous study, we proposed an efficient method to infer the underlying compatibilities among the entities, under the constraint that only the total compatibility is observable. Furthermore, by transforming the pairing problem into a traveling salesman problem with a multi-layer architecture, a pairing optimization algorithm was successfully demonstrated to derive a high-total-compatibility pairing. However, there is substantial room for further performance enhancement by further exploiting the underlying mathematical properties. In this study, we prove the existence of algebraic structures in the pairing problem. We transform the initially estimated compatibility information into an equivalent form where the variance of the individual compatibilities is minimized. We then demonstrate that the total compatibility obtained when using the heuristic pairing algorithm on the transformed problem is significantly higher compared to the previous method. With this improved perspective on the pairing problem using fundamental mathematical properties, we can contribute to practical applications such as wireless communications beyond 5G, where efficient pairing is of critical importance.

For first-order smooth optimization, the research on the acceleration phenomenon has a long-time history. Until recently, the mechanism leading to acceleration was not successfully uncovered by the gradient correction term and its equivalent implicit-velocity form. Furthermore, based on the high-resolution differential equation framework with the corresponding emerging techniques, phase-space representation and Lyapunov function, the squared gradient norm of Nesterov's accelerated gradient descent (\texttt{NAG}) method at an inverse cubic rate is discovered. However, this result cannot be directly generalized to composite optimization widely used in practice, e.g., the linear inverse problem with sparse representation. In this paper, we meticulously observe a pivotal inequality used in composite optimization about the step size $s$ and the Lipschitz constant $L$ and find that it can be improved tighter. We apply the tighter inequality discovered in the well-constructed Lyapunov function and then obtain the proximal subgradient norm minimization by the phase-space representation, regardless of gradient-correction or implicit-velocity. Furthermore, we demonstrate that the squared proximal subgradient norm for the class of iterative shrinkage-thresholding algorithms (ISTA) converges at an inverse square rate, and the squared proximal subgradient norm for the class of faster iterative shrinkage-thresholding algorithms (FISTA) is accelerated to convergence at an inverse cubic rate.

For the intersection of the Stiefel manifold and the set of nonnegative matrices in $\mathbb{R}^{n\times r}$, we present global and local error bounds with easily computable residual functions and explicit coefficients. Moreover, we show that the error bounds cannot be improved except for the coefficients, which explains why two square-root terms are necessary in the bounds when $1 < r < n$ for the nonnegativity and orthogonality, respectively. The error bounds are applied to penalty methods for minimizing a Lipschitz continuous function with nonnegative orthogonality constraints. Under only the Lipschitz continuity of the objective function, we prove the exactness of penalty problems that penalize the nonnegativity constraint, or the orthogonality constraint, or both constraints. Our results cover both global and local minimizers.