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

Exact computation of shortest paths in weighted graphs has been traditionally studied in one of two settings. First, one can assume that the edge weights are real numbers and all the performed operations on reals (typically comparisons and additions) take constant time. Classical Dijkstra's and Bellman-Ford algorithms have been described in this setting. More efficient exact shortest paths algorithms have been obtained for integer-weighted graphs. Integrality assumption not only enables faster algorithms but also allows implementing the aforementioned algorithms in a much more realistic word RAM model where only arithmetic operations on $O(\log{n})$-bit integers are performed in constant time. On the word RAM one can as efficiently exactly encode even \emph{rational-weighted} instances with $O(\log{n})$-bit numerators and denominators. However, the known exact real-weighted shortest paths algorithms, run on such a rational input, can easily encounter intermediate values of $\Theta(n)$ bits if represented exactly. This leads to a factor-$\Omega(n)$ slowdown on the word RAM. At the same time, the scaling algorithms suited for integer weights do not produce exact solutions for rational inputs without dramatically increasing their accuracy. In this paper, we design randomized exact single-source shortest paths algorithms for rational-weighted graphs on the word RAM. Most importantly, in the non-negative case, we obtain a near-linear time algorithm matching Dijkstra's algorithm running time up to polylogarithmic factors. In presence of negative weights, we give an $\tilde{O}(n^{2.5})$-time algorithm breaking through the best known strongly polynomial bound attained by Bellman-Ford for sufficiently dense graphs.

Minimum Weight Cycle (MWC) is the problem of finding a simple cycle of minimum weight in a graph $G=(V,E)$. This is a fundamental graph problem with classical sequential algorithms that run in $\tilde{O}(n^3)$ and $\tilde{O}(mn)$ time where $n=|V|$ and $m=|E|$. In recent years this problem has received significant attention in the context of hardness through fine grained sequential complexity as well as in design of faster sequential approximation algorithms. For computing minimum weight cycle in the distributed CONGEST model, near-linear in $n$ lower and upper bounds on round complexity are known for directed graphs (weighted and unweighted), and for undirected weighted graphs; these lower bounds also apply to any $(2-\epsilon)$-approximation algorithm. This paper focuses on round complexity bounds for approximating MWC in the CONGEST model: For coarse approximations we show that for any constant $\alpha >1$, computing an $\alpha$-approximation of MWC requires $\Omega (\frac{\sqrt n}{\log n})$ rounds on weighted undirected graphs and on directed graphs, even if unweighted. We complement these lower bounds with a sublinear $\tilde{O}(n^{2/3}+D)$-round algorithm to compute a $(2+\epsilon)$-approximation of undirected weighted MWC. We also give a $\tilde{O}(n^{4/5}+D)$-round algorithm to compute 2-approximate directed unweighted MWC and $(2+\epsilon)$-approximate directed weighted MWC. To obtain the sublinear round bounds, we design an efficient algorithm for computing $(1+\epsilon)$-approximate shortest paths from $k$ sources in directed and weighted graphs, which is of independent interest. We present an algorithm that runs in $\tilde{O}(\sqrt{nk} + D)$ rounds if $k \ge n^{1/3}$ and $\tilde{O}(\sqrt{nk} + k^{2/5}n^{2/5+o(1)}D^{2/5} + D)$ rounds if $k<n^{1/3}$, which smoothly interpolates between the best known upper bounds for SSSP when $k=1$ and APSP when $k=n$.

All machine learning algorithms use a loss, cost, utility or reward function to encode the learning objective and oversee the learning process. This function that supervises learning is a frequently unrecognized hyperparameter that determines how incorrect outputs are penalized and can be tuned to improve performance. This paper shows that training speed and final accuracy of neural networks can significantly depend on the loss function used to train neural networks. In particular derivative values can be significantly different with different loss functions leading to significantly different performance after gradient descent based Backpropagation (BP) training. This paper explores the effect on performance of using new loss functions that are also convex but penalize errors differently compared to the popular Cross-entropy loss. Two new classification loss functions that significantly improve performance on a wide variety of benchmark tasks are proposed. A new loss function call smooth absolute error that outperforms the Squared error, Huber and Log-Cosh losses on datasets with significantly many outliers is proposed. This smooth absolute error loss function is infinitely differentiable and more closely approximates the absolute error loss compared to the Huber and Log-Cosh losses used for robust regression.

Multibody dynamics simulators are an important tool in many fields, including learning and control for robotics. However, many existing dynamics simulators suffer from inaccuracies when dealing with constrained mechanical systems due to unsuitable integrators with bad energy behavior and problematic constraint violations, for example for contact interactions. Variational integrators are numerical discretization methods that can reduce physical inaccuracies when simulating mechanical systems, and formulating the dynamics in maximal coordinates allows for easy and numerically robust incorporation of constraints such as kinematic loops or contacts. Therefore, this article derives a variational integrator for mechanical systems with equality and inequality constraints in maximal coordinates. Additionally, efficient graph-based sparsity-exploiting algorithms for solving the integrator are provided and implemented as an open-source simulator. The evaluation of the simulator shows improved physical accuracy due to the variational integrator and the advantages of the sparse solvers. Comparisons to minimal-coordinate algorithms show improved numerical robustness and application examples of a walking robot and an exoskeleton with explicit constraints demonstrate the necessity and capabilities of maximal coordinates.

In adaptive data analysis, a mechanism gets $n$ i.i.d. samples from an unknown distribution $D$, and is required to provide accurate estimations to a sequence of adaptively chosen statistical queries with respect to $D$. Hardt and Ullman (FOCS 2014) and Steinke and Ullman (COLT 2015) showed that in general, it is computationally hard to answer more than $\Theta(n^2)$ adaptive queries, assuming the existence of one-way functions. However, these negative results strongly rely on an adversarial model that significantly advantages the adversarial analyst over the mechanism, as the analyst, who chooses the adaptive queries, also chooses the underlying distribution $D$. This imbalance raises questions with respect to the applicability of the obtained hardness results -- an analyst who has complete knowledge of the underlying distribution $D$ would have little need, if at all, to issue statistical queries to a mechanism which only holds a finite number of samples from $D$. We consider more restricted adversaries, called \emph{balanced}, where each such adversary consists of two separated algorithms: The \emph{sampler} who is the entity that chooses the distribution and provides the samples to the mechanism, and the \emph{analyst} who chooses the adaptive queries, but has no prior knowledge of the underlying distribution (and hence has no a priori advantage with respect to the mechanism). We improve the quality of previous lower bounds by revisiting them using an efficient \emph{balanced} adversary, under standard public-key cryptography assumptions. We show that these stronger hardness assumptions are unavoidable in the sense that any computationally bounded \emph{balanced} adversary that has the structure of all known attacks, implies the existence of public-key cryptography.

For the first time, multi-task learning is proposed to improve the flexibility of NN-based equalizers in coherent systems. A "single" NN-based equalizer improves Q-factor by up to 4 dB compared to CDC, without re-training, even with variations in launch power, symbol rate, or transmission distance.

\textit{Relative overgeneralization} (RO) occurs in cooperative multi-agent learning tasks when agents converge towards a suboptimal joint policy due to overfitting to suboptimal behavior of other agents. In early work, optimism has been shown to mitigate the \textit{RO} problem when using tabular Q-learning. However, with function approximation optimism can amplify overestimation and thus fail on complex tasks. On the other hand, recent deep multi-agent policy gradient (MAPG) methods have succeeded in many complex tasks but may fail with severe \textit{RO}. We propose a general, yet simple, framework to enable optimistic updates in MAPG methods and alleviate the RO problem. Specifically, we employ a \textit{Leaky ReLU} function where a single hyperparameter selects the degree of optimism to reshape the advantages when updating the policy. Intuitively, our method remains optimistic toward individual actions with lower returns which are potentially caused by other agents' sub-optimal behavior during learning. The optimism prevents the individual agents from quickly converging to a local optimum. We also provide a formal analysis from an operator view to understand the proposed advantage transformation. In extensive evaluations on diverse sets of tasks, including illustrative matrix games, complex \textit{Multi-agent MuJoCo} and \textit{Overcooked} benchmarks, the proposed method\footnote{Code can be found at \url{//github.com/wenshuaizhao/optimappo}.} outperforms strong baselines on 13 out of 19 tested tasks and matches the performance on the rest.

Internet of Things (IoT) technologies are the foundation of a fully connected world. Currently, IoT devices (or nodes) primarily use dedicated sensors to sense and collect data at large scales, and then transmit the data to target nodes or gateways through wireless communication for further processing and analytics. In recent years, research efforts have been made to explore the feasibility of using wireless communication for sensing (while assiduously improving the transmission performance of wireless signals), in an attempt to achieve integrated sensing and communication (ISAC) for smart IoT of the future. In this paper, we leverage the capabilities of LoRa, a long-range IoT communication technology, to explore the possibility of using LoRa signals for both sensing and communication. Based on LoRa, we propose ISAC designs in two typical scenarios of smart IoT, and verify the feasibility and effectiveness of our designs in soil moisture monitoring and human presence detection.

In multi-turn dialog, utterances do not always take the full form of sentences \cite{Carbonell1983DiscoursePA}, which naturally makes understanding the dialog context more difficult. However, it is essential to fully grasp the dialog context to generate a reasonable response. Hence, in this paper, we propose to improve the response generation performance by examining the model's ability to answer a reading comprehension question, where the question is focused on the omitted information in the dialog. Enlightened by the multi-task learning scheme, we propose a joint framework that unifies these two tasks, sharing the same encoder to extract the common and task-invariant features with different decoders to learn task-specific features. To better fusing information from the question and the dialog history in the encoding part, we propose to augment the Transformer architecture with a memory updater, which is designed to selectively store and update the history dialog information so as to support downstream tasks. For the experiment, we employ human annotators to write and examine a large-scale dialog reading comprehension dataset. Extensive experiments are conducted on this dataset, and the results show that the proposed model brings substantial improvements over several strong baselines on both tasks. In this way, we demonstrate that reasoning can indeed help better response generation and vice versa. We release our large-scale dataset for further research.

Neural machine translation (NMT) is a deep learning based approach for machine translation, which yields the state-of-the-art translation performance in scenarios where large-scale parallel corpora are available. Although the high-quality and domain-specific translation is crucial in the real world, domain-specific corpora are usually scarce or nonexistent, and thus vanilla NMT performs poorly in such scenarios. Domain adaptation that leverages both out-of-domain parallel corpora as well as monolingual corpora for in-domain translation, is very important for domain-specific translation. In this paper, we give a comprehensive survey of the state-of-the-art domain adaptation techniques for NMT.