Strong minimax lower bounds for learning

Minimax lower bounds for concept learning state, for example, thatfor each sample size $n$ and learning rule $g_n$, there exists a distributionof the observation $X$ and a concept $C$ to be learnt such that the expectederror of $g_n$ is at least a constant times $V/n$, where $V$ is the VC dimensionof the concept class. However, these bounds do not tell anything about therate of decrease of the error for a {\sl fixed} distribution--concept pair.\\In this paper we investigate minimax lower bounds in such a--stronger--sense.We show that for several natural $k$--parameter concept classes, includingthe class of linear halfspaces, the class of balls, the class of polyhedrawith a certain number of faces, and a class of neural networks, for any{\sl sequence} of learning rules $\{g_n\}$, there exists a fixed distributionof $X$ and a fixed concept $C$ such that the expected error is larger thana constant times $k/n$ for {\sl infinitely many n}. We also obtain suchstrong minimax lower bounds for the tail distribution of the probabilityof error, which extend the corresponding minimax lower bounds.

Minimax lower bounds for the two-armed bandit problem

We obtain minimax lower bounds on the regret for the classicaltwo--armed bandit problem. We provide a finite--sample minimax version of the well--known log $n$ asymptotic lower bound of Lai and Robbins. Also, in contrast to the log $n$ asymptotic results on the regret, we show that the minimax regret is achieved by mere random guessing under fairly mild conditions on the set of allowable configurations of the two arms. That is, we show that for {\sl every} allocation rule and for {\sl every} $n$, there is a configuration such that the regret at time $n$ is at least 1 -- $\epsilon$ times the regret of random guessing, where $\epsilon$ is any small positive constant.

Minimax regret and strategic uncertainty

This paper introduces a new solution concept, a minimax regret equilibrium, which allows for the possibility that players are uncertain about the rationality and conjectures of their opponents. We provide several applications of our concept. In particular, we consider pricesetting environments and show that optimal pricing policy follows a non-degenerate distribution. The induced price dispersion is consistent with experimental and empirical observations (Baye and Morgan (2004)).

The minimax distortion redundancy in empirical quantizer design

We obtain minimax lower and upper bounds for the expected distortionredundancy of empirically designed vector quantizers. We show that the meansquared distortion of a vector quantizer designed from $n$ i.i.d. datapoints using any design algorithm is at least $\Omega (n^{-1/2})$ awayfrom the optimal distortion for some distribution on a bounded subset of${\cal R}^d$. Together with existing upper bounds this result shows thatthe minimax distortion redundancy for empirical quantizer design, as afunction of the size of the training data, is asymptotically on the orderof $n^{1/2}$. We also derive a new upper bound for the performance of theempirically optimal quantizer.

The von Neumann Minimax Theorem and its relatives and a study of externality in on-line auctions

This work consists of a theoretical part and an experimental one. The first part provides a simple treatment of the celebrated von Neumann minimax theorem as formulated by Nikaid6 and Sion. It also discusses its relationships with fundamental theorems of convex analysis. The second part is about externality in sponsored search auctions. It shows that in these auctions, advertisers have externality effects on each other which influence their bidding behavior. It proposes Hal R.Varian model and shows how adding externality to this model will affect its properties. In order to have a better understanding of the interaction among advertisers in on-line auctions, it studies the structure of the Google advertisements networ.k and shows that it is a small-world scale-free network.

Aspekte der linearen Minimax-Schätzung

Es werde das lineare Regressionsmodell y = X b + e mit den ueblichen Bedingungen betrachtet. Weiter werde angenommen, dass der Parametervektor aus einem Ellipsoid stammt. Ein optimaler Schaetzer fuer den Parametervektor ist durch den Minimax-Schaetzer gegeben. Nach der entscheidungstheoretischen Formulierung des Minimax-Schaetzproblems werden mit dem Bayesschen Ansatz, Spektralen Methoden und der Darstellung von Hoffmann und Laeuter Wege zur Bestimmung des Minimax- Schaetzers dargestellt und in Beziehung gebracht. Eine Betrachtung von Modellen mit drei Einflussgroeßen und gemeinsamen Eigenvektor fuehrt zu einer Strukturierung des Problems nach der Vielfachheit des maximalen Eigenwerts. Die Bestimmung des Minimax-Schaetzers in einem noch nicht geloesten Fall kann auf die Bestimmung einer Nullstelle einer nichtlinearen reellwertigen Funktion gefuehrt werden. Es wird ein Beispiel gefunden, in dem die Nullstelle nicht durch Radikale angegeben werden kann. Durch das Intervallschachtelungs-Prinzip oder Newton-Verfahren ist die numerische Bestimmung der Nullstelle moeglich. Durch Entwicklung einer Fixpunktgleichung aus der Darstellung von Hoffmann und Laeuter war es in einer Simulation moeglich die angestrebten Loesungen zu finden.

Relativistic LCAO with Minimax Principle and New Balanced Basis Sets

Relativistic density functional theory is widely applied in molecular calculations with heavy atoms, where relativistic and correlation effects are on the same footing. Variational stability of the Dirac Hamiltonian is a very important field of research from the beginning of relativistic molecular calculations on, among efforts for accuracy, efficiency, and density functional formulation, etc. Approximations of one- or two-component methods and searching for suitable basis sets are two major means for good projection power against the negative continuum. The minimax two-component spinor linear combination of atomic orbitals (LCAO) is applied in the present work for both light and super-heavy one-electron systems, providing good approximations in the whole energy spectrum, being close to the benchmark minimax finite element method (FEM) values and without spurious and contaminated states, in contrast to the presence of these artifacts in the traditional four-component spinor LCAO. The variational stability assures that minimax LCAO is bounded from below. New balanced basis sets, kinetic and potential defect balanced (TVDB), following the minimax idea, are applied with the Dirac Hamiltonian. Its performance in the same super-heavy one-electron quasi-molecules shows also very good projection capability against variational collapse, as the minimax LCAO is taken as the best projection to compare with. The TVDB method has twice as many basis coefficients as four-component spinor LCAO, which becomes now linear and overcomes the disadvantage of great time-consumption in the minimax method. The calculation with both the TVDB method and the traditional LCAO method for the dimers with elements in group 11 of the periodic table investigates their difference. New bigger basis sets are constructed than in previous research, achieving high accuracy within the functionals involved. Their difference in total energy is much smaller than the basis incompleteness error, showing that the traditional four-spinor LCAO keeps enough projection power from the numerical atomic orbitals and is suitable in research on relativistic quantum chemistry. In scattering investigations for the same comparison purpose, the failure of the traditional LCAO method of providing a stable spectrum with increasing size of basis sets is contrasted to the TVDB method, which contains no spurious states already without pre-orthogonalization of basis sets. Keeping the same conditions including the accuracy of matrix elements shows that the variational instability prevails over the linear dependence of the basis sets. The success of the TVDB method manifests its capability not only in relativistic quantum chemistry but also for scattering and under the influence of strong external electronic and magnetic fields. The good accuracy in total energy with large basis sets and the good projection property encourage wider research on different molecules, with better functionals, and on small effects.

Tribalism as a Minimax-Regret Strategy: Evidence from Voting in the 2007 Kenyan Elections

Although many studies find that voting in Africa approximates an ethnic census in that voting is primarily along ethnic lines, hardly any of the studies have sought to explain ethnic voting following a rational choice framework. Using data of voter opinions from a survey conducted two weeks before the December 2007 Kenyan elections, we find that the expected benefits associated with a win by each of the presidential candidates varied significantly across voters from different ethnic groups. We hypothesize that decision to participate in the elections was influenced by the expected benefits as per the minimax-regret voting model. We test the predictions of this model using data of voter turnout in the December 2007 elections and find that turnout across ethnic groups varied systematically with expected benefits. The results suggest that individuals participated in the elections primarily to avoid the maximum regret should a candidate from another ethnic group win. The results therefore offer credence to the minimax regret model as proposed by Ferejohn and Fiorina (1974) and refute the Downsian expected utility model.

Optimal, minimax, and Bayesian two-stage designs in two-dose phase II clinical trials

Background: For most cytotoxic and biologic anti-cancer agents, the response rate of the drug is commonly assumed to be non-decreasing with an increasing dose. However, an increasing dose does not always result in an appreciable increase in the response rate. This may especially be true at high doses for a biologic agent. Therefore, in a phase II trial the investigators may be interested in testing the anti-tumor activity of a drug at more than one (often two) doses, instead of only at the maximum tolerated dose (MTD). This way, when the lower dose appears equally effective, this dose can be recommended for further confirmatory testing in a phase III trial under potential long-term toxicity and cost considerations. A common approach to designing such a phase II trial has been to use an independent (e.g., Simon's two-stage) design at each dose ignoring the prior knowledge about the ordering of the response probabilities at the different doses. However, failure to account for this ordering constraint in estimating the response probabilities may result in an inefficient design. In this dissertation, we developed extensions of Simon's optimal and minimax two-stage designs, including both frequentist and Bayesian methods, for two doses that assume ordered response rates between doses. ^ Methods: Optimal and minimax two-stage designs are proposed for phase II clinical trials in settings where the true response rates at two dose levels are ordered. We borrow strength between doses using isotonic regression and control the joint and/or marginal error probabilities. Bayesian two-stage designs are also proposed under a stochastic ordering constraint. ^ Results: Compared to Simon's designs, when controlling the power and type I error at the same levels, the proposed frequentist and Bayesian designs reduce the maximum and expected sample sizes. Most of the proposed designs also increase the probability of early termination when the true response rates are poor. ^ Conclusion: Proposed frequentist and Bayesian designs are superior to Simon's designs in terms of operating characteristics (expected sample size and probability of early termination, when the response rates are poor) Thus, the proposed designs lead to more cost-efficient and ethical trials, and may consequently improve and expedite the drug discovery process. The proposed designs may be extended to designs of multiple group trials and drug combination trials.^

Consolidation of a wsn and minimax method to rapidly neutralise intruders in strategic installations

Due to the sensitive international situation caused by still-recent terrorist attacks, there is a common need to protect the safety of large spaces such as government buildings, airports and power stations. To address this problem, developments in several research fields, such as video and cognitive audio, decision support systems, human interface, computer architecture, communications networks and communications security, should be integrated with the goal of achieving advanced security systems capable of checking all of the specified requirements and spanning the gap that presently exists in the current market. This paper describes the implementation of a decision system for crisis management in infrastructural building security. Specifically, it describes the implementation of a decision system in the management of building intrusions. The positions of the unidentified persons are reported with the help of a Wireless Sensor Network (WSN). The goal is to achieve an intelligent system capable of making the best decision in real time in order to quickly neutralise one or more intruders who threaten strategic installations. It is assumed that the intruders’ behaviour is inferred through sequences of sensors’ activations and their fusion. This article presents a general approach to selecting the optimum operation from the available neutralisation strategies based on a Minimax algorithm. The distances among different scenario elements will be used to measure the risk of the scene, so a path planning technique will be integrated in order to attain a good performance. Different actions to be executed over the elements of the scene such as moving a guard, blocking a door or turning on an alarm will be used to neutralise the crisis. This set of actions executed to stop the crisis is known as the neutralisation strategy. Finally, the system has been tested in simulations of real situations, and the results have been evaluated according to the final state of the intruders. In 86.5% of the cases, the system achieved the capture of the intruders, and in 59.25% of the cases, they were intercepted before they reached their objective.

An extended minimax disparity to determine the OWA operator weights

This paper contributes to extend the minimax disparity to determine the ordered weighted averaging (OWA) model based on linear programming. It introduces the minimax disparity approach between any distinct pairs of the weights and uses the duality of linear programming to prove the feasibility of the extended OWA operator weights model. The paper finishes with an open problem. © 2006 Elsevier Ltd. All rights reserved.

Finding relevant search engine results:a minimax linear programming approach

For a submitted query to multiple search engines finding relevant results is an important task. This paper formulates the problem of aggregation and ranking of multiple search engines results in the form of a minimax linear programming model. Besides the novel application, this study detects the most relevant information among a return set of ranked lists of documents retrieved by distinct search engines. Furthermore, two numerical examples aree used to illustrate the usefulness of the proposed approach.

Improving minimax disparity model to determine the OWA operator weights

Determining the Ordered Weighted Averaging (OWA) operator weights is important in decision making applications. Several approaches have been proposed in the literature to obtain the associated weights. This paper provides an alternative disparity model to identify the OWA operator weights. The proposed mathematical model extends the existing disparity approaches by minimizing the sum of the deviation between two distinct OWA weights. The proposed disparity model can be used for a preference ranking aggregation. A numerical example in preference ranking and an application in search engines prove the usefulness of the generated OWA weights.