Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUncertainty in Multi-Commodity Routing Networks: When does it help?
65
0
0.0
(
0
)
Added by
Shreyas Sekar
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the equilibrium behavior in a multi-commodity selfish routing game with many types of uncertain users where each user over- or under-estimates their congestion costs by a multiplicative factor. Surprisingly, we find that uncertainties in different directions have qualitatively distinct impacts on equilibria. Namely, contrary to the usual notion that uncertainty increases inefficiencies, network congestion actually decreases when users over-estimate their costs. On the other hand, under-estimation of costs leads to increased congestion. We apply these results to urban transportation networks, where drivers have different estimates about the cost of congestion. In light of the dynamic pricing policies aimed at tackling congestion, our results indicate that users perception of these prices can significantly impact the policys efficacy, and caution in the face of uncertainty leads to favorable network conditions.
rate research
Read More
We formulate and study the algorithmic mechanism design problem for a general class of resource allocation settings, where the center redistributes the private resources brought by individuals. Money transfer is forbidden. Distinct from the standard literature, which assumes the amount of resources brought by an individual to be public information, we consider this amount as an agents private, possibly multi-dimensional type. Our goal is to design truthful mechanisms that achieve two objectives: max-min and Pareto efficiency. For each objective, we provide a reduction that converts any optimal algorithm into a strategy-proof mechanism that achieves the same objective. Our reductions do not inspect the input algorithms but only query these algorithms as oracles. Applying the reductions, we produce strategy-proof mechanisms in a non-trivial application: network route allocation. Our models and result in the application are valuable on their own rights.
While second order optimizers such as natural gradient descent (NGD) often speed up optimization, their effect on generalization has been called into question. This work presents a more nuanced view on how the textit{implicit bias} of first- and second-order methods affects the comparison of generalization properties. We provide an exact asymptotic bias-variance decomposition of the generalization error of overparameterized ridgeless regression under a general class of preconditioner $boldsymbol{P}$, and consider the inverse population Fisher information matrix (used in NGD) as a particular example. We determine the optimal $boldsymbol{P}$ for both the bias and variance, and find that the relative generalization performance of different optimizers depends on the label noise and the shape of the signal (true parameters): when the labels are noisy, the model is misspecified, or the signal is misaligned with the features, NGD can achieve lower risk; conversely, GD generalizes better than NGD under clean labels, a well-specified model, or aligned signal. Based on this analysis, we discuss several approaches to manage the bias-variance tradeoff, and the potential benefit of interpolating between GD and NGD. We then extend our analysis to regression in the reproducing kernel Hilbert space and demonstrate that preconditioned GD can decrease the population risk faster than GD. Lastly, we empirically compare the generalization error of first- and second-order optimizers in neural network experiments, and observe robust trends matching our theoretical analysis.
While Bernoullis equation is one of the most frequently mentioned topics in Physics literature and other means of dissemination, it is also one of the least understood. Oddly enough, in the wonderful book Turning the world inside out [1], Robert Ehrlich proposes a demonstration that consists of blowing a quarter dollar coin into a cup, incorrectly explained using Bernoullis equation. In the present work, we have adapted the demonstration to show situations in which the coin jumps into the cup and others in which it does not, proving that the explanation based on Bernoullis is flawed. Our demonstration is useful to tackle the common misconception, stemming from the incorrect use of Bernoullis equation, that higher velocity invariably means lower pressure.
Numerous papers ask how difficult it is to cluster data. We suggest that the more relevant and interesting question is how difficult it is to cluster data sets {em that can be clustered well}. More generally, despite the ubiquity and the great importance of clustering, we still do not have a satisfactory mathematical theory of clustering. In order to properly understand clustering, it is clearly necessary to develop a solid theoretical basis for the area. For example, from the perspective of computational complexity theory the clustering problem seems very hard. Numerous papers introduce various criteria and numerical measures to quantify the quality of a given clustering. The resulting conclusions are pessimistic, since it is computationally difficult to find an optimal clustering of a given data set, if we go by any of these popular criteria. In contrast, the practitioners perspective is much more optimistic. Our explanation for this disparity of opinions is that complexity theory concentrates on the worst case, whereas in reality we only care for data sets that can be clustered well. We introduce a theoretical framework of clustering in metric spaces that revolves around a notion of good clustering. We show that if a good clustering exists, then in many cases it can be efficiently found. Our conclusion is that contrary to popular belief, clustering should not be considered a hard task.
The development of neural networks and pretraining techniques has spawned many sentence-level tagging systems that achieved superior performance on typical benchmarks. However, a relatively less discussed topic is what if more context information is introduced into current top-scoring tagging systems. Although several existing works have attempted to shift tagging systems from sentence-level to document-level, there is still no consensus conclusion about when and why it works, which limits the applicability of the larger-context approach in tagging tasks. In this paper, instead of pursuing a state-of-the-art tagging system by architectural exploration, we focus on investigating when and why the larger-context training, as a general strategy, can work. To this end, we conduct a thorough comparative study on four proposed aggregators for context information collecting and present an attribute-aided evaluation method to interpret the improvement brought by larger-context training. Experimentally, we set up a testbed based on four tagging tasks and thirteen datasets. Hopefully, our preliminary observations can deepen the understanding of larger-context training and enlighten more follow-up works on the use of contextual information.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
