Página 1 dos resultados de 1317 itens digitais encontrados em 0.005 segundos

Heuristic pattern search for bound constrained minimax problems

Espírito Santo, I. A. C. P.; Fernandes, Edite Manuela da G. P.
Fonte: Springer-Verlag Publicador: Springer-Verlag
Tipo: Parte de Livro
Publicado em //2011 ENG
Relevância na Pesquisa
37.11%
This paper presents a pattern search algorithm and its hybridization with a random descent search for solving bound constrained minimax problems. The herein proposed heuristic pattern search method combines the Hooke and Jeeves (HJ) pattern and exploratory moves with a randomly generated approxi- mate descent direction. Two versions of the heuristic algorithm have been applied to several benchmark minimax problems and compared with the original HJ pat- tern search algorithm.

Seleção da carteira de ativos de uma seguradora em tempos de crise : o critério Minimax

Silva, Patrícia Filipa Pegas da
Fonte: Instituto Superior de Economia e Gestão Publicador: Instituto Superior de Economia e Gestão
Tipo: Dissertação de Mestrado
Publicado em /09/2012 POR
Relevância na Pesquisa
37.11%
Mestrado em Decisão Económica e Empresarial; A atual crise económica e financeira trouxe novos contornos ao problema da seleção de carteiras de ativos. No caso particular das companhias seguradoras, tradicionalmente pautadas por critérios prudenciais, a questão assume importância acrescida. Neste trabalho, com base em Polak et al. (2010), apresenta-se a aplicação dos modelos Minimax na escolha da carteira ótima de uma seguradora, de modo a obter uma rentabilidade mínima, qualquer que seja o cenário razoavelmente previsível. São resolvidos três problemas, distintos mas interrelacionados, em certas condições. Fazem-se duas extensões ao modelo original: a introdução de um conjunto muito mais alargado de estados da natureza, integrando de modo explícito os cenários de crise; a modelização das séries temporais das rentabilidades dos ativos elegíveis, para fins de previsão dos estados da natureza futuros. Em ambos os casos se obtêm resultados muito satisfatórios.; The present economic and financial crisis brought new issues to the asset portfolio selection problem. As insurance companies are traditionally bound to prudential criteria, the topic is particularly important in their context. In this work, inspired in Polak et al. (2010)...

Convex Sets Strict Separation in the Minimax Theorem

Ferreira, Manuel Alberto M.; Matos, Maria Cristina Peixoto
Fonte: Hikari Ltd. Publicador: Hikari Ltd.
Tipo: Artigo de Revista Científica
Publicado em //2014 ENG
Relevância na Pesquisa
36.95%
The convex sets strict separation is very useful to obtain mathematical optimization results. The minimax theorem, a key result in Game Theory is an example. It will be outlined in this work.

Hierarchical Clustering With Prototypes via Minimax Linkage

Bien, Jacob; Tibshirani, Robert
Fonte: PubMed Publicador: PubMed
Tipo: Artigo de Revista Científica
Publicado em //2011 EN
Relevância na Pesquisa
27.28%
Agglomerative hierarchical clustering is a popular class of methods for understanding the structure of a dataset. The nature of the clustering depends on the choice of linkage—that is, on how one measures the distance between clusters. In this article we investigate minimax linkage, a recently introduced but little-studied linkage. Minimax linkage is unique in naturally associating a prototype chosen from the original dataset with every interior node of the dendrogram. These prototypes can be used to greatly enhance the interpretability of a hierarchical clustering. Furthermore, we prove that minimax linkage has a number of desirable theoretical properties; for example, minimax-linkage dendrograms cannot have inversions (unlike centroid linkage) and is robust against certain perturbations of a dataset. We provide an efficient implementation and illustrate minimax linkage’s strengths as a data analysis and visualization tool on a study of words from encyclopedia articles and on a dataset of images of human faces.

Tuning support vector machines for minimax and Neyman-Pearson classification

Scott, Clayton D.; Baraniuk, Richard G.; Davenport, Mark A.
Fonte: Universidade Rice Publicador: Universidade Rice
Tipo: Relatório
EN_US
Relevância na Pesquisa
36.95%
This paper studies the training of support vector machine (SVM) classifiers with respect to the minimax and Neyman-Pearson criteria. In principle, these criteria can be optimized in a straightforward way using a cost-sensitive SVM. In practice, however, because these criteria require especially accurate error estimation, standard techniques for tuning SVM parameters, such as crossvalidation, can lead to poor classifier performance. To address this issue, we first prove that the usual cost-sensitive SVM, here called the 2C-SVM, is equivalent to another formulation called the 2nu-SVM. We then exploit a characterization of the 2nu-SVM parameter space to develop a simple yet powerful approach to error estimation based on smoothing. In an extensive experimental study we demonstrate that smoothing significantly improves the accuracy of cross-validation error estimates, leading to dramatic performance gains. Furthermore, we propose coordinate descent strategies that offer significant gains in computational efficiency, with little to no loss in performance.

Prediction and Filtering of Stationary Processes: Yaglom’s Method and Minimax Filtering

Mascher, Philipp
Fonte: Quens University Publicador: Quens University
Tipo: Tese de Doutorado
EN
Relevância na Pesquisa
36.95%
The aim of this work is to give a basic introduction to the theory of stationary stochastic processes, particularly to the somewhat specialized problem of prediction and filtering of such processes. Kolmogorov was the first to make a contribution to its solution using involved mathematical theory. In the years following the publication of Wiener’s famous book, the theory gained considerable popularity from the applied sciences, particularly radio engineering. In this work, we shall present Yaglom’s method to solving the problems considered in Wiener’s book. This alternative approach is entirely based on rather basic facts from Hilbert space theory and the theory of complex variables. As it turns out, the theory of filtering of stationary processes heavily relies on spectral properties of the processes. In particular, Yaglom’s approach assumes complete knowledge of the spectral densities. In this work, however, we shall not be concerned with the problem of estimating such quantities based on a finite sample. Instead, in order to account for uncertainty as frequently encountered in practice, we shall discuss the problem of minimax filtering which has emerged from the practical need of allowing for incomplete knowledge about spectral properties.

Teoria dos jogos e a relação entre o “Teorema Minimax” de John Von Neumann e o “Equilíbrio de Nash” de John Nash

Costa, Cristiene dos Santos
Fonte: Universidade Católica de Brasília Publicador: Universidade Católica de Brasília
Tipo: Trabalho de Conclusão de Curso Formato: Texto
PT_BR
Relevância na Pesquisa
36.95%
Este texto contém um pouco da Teoria dos Jogos baseada nos trabalhos de John Von Neumann e de John Forbes Nash Jr, aplicada a problemas que podem ser enfrentados em situações do mundo real. A estrutura do texto segue uma ordem de construção do conhecimento sobre a teoria, iniciando pela idéia geral, passando pelo Teorema Minimax e finalizando com o Equilíbrio de Nash; Matemática

Empirical Entropy, Minimax Regret and Minimax Risk

Rakhlin, Alexander; Sridharan, Karthik; Tsybakov, Alexandre B.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 05/08/2013
Relevância na Pesquisa
27.38%
We consider the random design regression model with square loss. We propose a method that aggregates empirical minimizers (ERM) over appropriately chosen random subsets and reduces to ERM in the extreme case, and we establish sharp oracle inequalities for its risk. We show that, under the $\epsilon^{-p}$ growth of the empirical $\epsilon$-entropy, the excess risk of the proposed method attains the rate $n^{-\frac{2}{2+p}}$ for $p\in(0,2]$ and $n^{-1/p}$ for $p> 2$ where $n$ is the sample size. Furthermore, for $p\in(0,2]$, the excess risk rate matches the behavior of the minimax risk of function estimation in regression problems under the well-specified model. This yields a conclusion that the rates of statistical estimation in well-specified models (minimax risk) and in misspecified models (minimax regret) are equivalent in the regime $p\in(0,2]$. In other words, for $p\in(0,2]$ the problem of statistical learning enjoys the same minimax rate as the problem of statistical estimation. On the contrary, for $p>2$ we show that the rates of the minimax regret are, in general, slower than for the minimax risk. Our oracle inequalities also imply the $v\log(n/v)/n$ rates for Vapnik-Chervonenkis type classes of dimension $v$ without the usual convexity assumption on the class; we show that these rates are optimal. Finally...

Minimax state estimation for linear descriptor systems

Zhuk, Sergiy
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 26/02/2011
Relevância na Pesquisa
27.34%
Author's Summary of the dissertation for the degree of the Candidate of Science (physics and mathematics). The aim of the dissertation is to develop a generalized Kalman Duality concept applicable for linear unbounded non-invertible operators and introduce the minimax state estimation theory and algorithms for linear differential-algebraic equations. In particular, the dissertation pursues the following goals: - develop generalized duality concept for the minimax state estimation theory for DAEs with unknown but bounded model error and random observation noise with unknown but bounded correlation operator; - derive the minimax state estimation theory for linear DAEs with unknown but bounded model error and random observation noise with unknown but bounded correlation operator; - describe how the DAE model propagates uncertain parameters; - estimate the worst-case error; - construct fast estimation algorithms in the form of filters; - develop a tool for model validation, that is to assess how good the model describes observed phenomena. The dissertation contains the following new results: - generalized version of the Kalman duality principle is proposed allowing to handle unbounded linear model operators with non-trivial null-space; - new definitions of the minimax estimates for DAEs based on the generalized Kalman duality principle are proposed; - theorems of existence for minimax estimates are proved; - new minimax state estimation algorithms (in the form of filter and in the variational form) for DAE are proposed.

Optimal Grouping for Group Minimax Hypothesis Testing

Varshney, Kush R.; Varshney, Lav R.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 24/07/2013
Relevância na Pesquisa
27.38%
Bayesian hypothesis testing and minimax hypothesis testing represent extreme instances of detection in which the prior probabilities of the hypotheses are either completely and precisely known, or are completely unknown. Group minimax, also known as Gamma-minimax, is a robust intermediary between Bayesian and minimax hypothesis testing that allows for coarse or partial advance knowledge of the hypothesis priors by using information on sets in which the prior lies. Existing work on group minimax, however, does not consider the question of how to define the sets or groups of priors; it is assumed that the groups are given. In this work, we propose a novel intermediate detection scheme formulated through the quantization of the space of prior probabilities that optimally determines groups and also representative priors within the groups. We show that when viewed from a quantization perspective, group minimax amounts to determining centroids with a minimax Bayes risk error divergence distortion criterion: the appropriate Bregman divergence for this task. Moreover, the optimal partitioning of the space of prior probabilities is a Bregman Voronoi diagram. Together, the optimal grouping and representation points are an epsilon-net with respect to Bayes risk error divergence...

Torsion-free covers for solvable minimax groups

Kropholler, Peter; Lorensen, Karl
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 26/10/2015
Relevância na Pesquisa
27.28%
We prove that every finitely generated solvable minimax group can be realized as a quotient of a torsion-free solvable minimax group. This result has an application to the investigation of random walks on finitely generated solvable minimax groups. Our methods also allow us to completely characterize the solvable minimax groups that are homomorphic images of torsion-free solvable minimax groups.

Improved minimax estimation of a multivariate normal mean under heteroscedasticity

Tan, Zhiqiang
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 28/05/2015
Relevância na Pesquisa
27.28%
Consider the problem of estimating a multivariate normal mean with a known variance matrix, which is not necessarily proportional to the identity matrix. The coordinates are shrunk directly in proportion to their variances in Efron and Morris' (J. Amer. Statist. Assoc. 68 (1973) 117-130) empirical Bayes approach, whereas inversely in proportion to their variances in Berger's (Ann. Statist. 4 (1976) 223-226) minimax estimators. We propose a new minimax estimator, by approximately minimizing the Bayes risk with a normal prior among a class of minimax estimators where the shrinkage direction is open to specification and the shrinkage magnitude is determined to achieve minimaxity. The proposed estimator has an interesting simple form such that one group of coordinates are shrunk in the direction of Berger's estimator and the remaining coordinates are shrunk in the direction of the Bayes rule. Moreover, the proposed estimator is scale adaptive: it can achieve close to the minimum Bayes risk simultaneously over a scale class of normal priors (including the specified prior) and achieve close to the minimax linear risk over a corresponding scale class of hyper-rectangles. For various scenarios in our numerical study, the proposed estimators with extreme priors yield more substantial risk reduction than existing minimax estimators.; Comment: Published at http://dx.doi.org/10.3150/13-BEJ580 in the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)

Minimax Estimation of Nonregular Parameters and Discontinuity in Minimax Risk

Song, Kyungchul
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 10/03/2014
Relevância na Pesquisa
27.28%
When a parameter of interest is nondifferentiable in the probability, the existing theory of semiparametric efficient estimation is not applicable, as it does not have an influence function. Song (2014) recently developed a local asymptotic minimax estimation theory for a parameter that is a nondifferentiable transform of a regular parameter, where the nondifferentiable transform is a composite map of a continuous piecewise linear map with a single kink point and a translation-scale equivariant map. The contribution of this paper is two fold. First, this paper extends the local asymptotic minimax theory to nondifferentiable transforms that are a composite map of a Lipschitz continuous map having a finite set of nondifferentiability points and a translation-scale equivariant map. Second, this paper investigates the discontinuity of the local asymptotic minimax risk in the true probability and shows that the proposed estimator remains to be optimal even when the risk is locally robustified not only over the scores at the true probability, but also over the true probability itself. However, the local robustification does not resolve the issue of discontinuity in the local asymptotic minimax risk.

Minimax Robust Function Reconstruction in Reproducing Kernel Hilbert Spaces

Barton, Richard J.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
27.34%
In this paper, we present a unified approach to function approximation in reproducing kernel Hilbert spaces (RKHS) that establishes a previously unrecognized optimality property for several well-known function approximation techniques, such as minimum-norm interpolation, smoothing splines, and pseudo-inverses. We consider the problem of approximating a function belonging to an arbitrary real-valued RKHS on R^d based on approximate observations of the function. The observations are approximate in the sense that the actual observations (i.e., the true function values) are known only to belong to a convex set of admissible observations. We seek a minimax optimal approximation for the function that minimizes the supremum of the RKHS norm on the error between the true function and the chosen approximation subject only to the conditions that the true function belongs to a uniformly bounded uncertainty set of functions that satisfy the constraints on the observations and that the approximation is a member of the RKHS. We refer to such a solution as a minimax robust reconstruction. We characterize the solution to the minimax robust reconstruction problem and show that it is equivalent to solving a straightforward convex optimization problem. We demonstrate that a minimax robust reconstruction will generally be more stable than an approximation based on interpolation through a nominal set of observations and that...

Mini-Minimax Uncertainty Quantification for Emulators

Regier, Jeffrey C.; Stark, Philip B.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
27.28%
Consider approximating a "black box" function $f$ by an emulator $\hat{f}$ based on $n$ noiseless observations of $f$. Let $w$ be a point in the domain of $f$. How big might the error $|\hat{f}(w) - f(w)|$ be? If $f$ could be arbitrarily rough, this error could be arbitrarily large: we need some constraint on $f$ besides the data. Suppose $f$ is Lipschitz with known constant. We find a lower bound on the number of observations required to ensure that for the best emulator $\hat{f}$ based on the $n$ data, $|\hat{f}(w) - f(w)| \le \epsilon$. But in general, we will not know whether $f$ is Lipschitz, much less know its Lipschitz constant. Assume optimistically that $f$ is Lipschitz-continuous with the smallest constant consistent with the $n$ data. We find the maximum (over such regular $f$) of $|\hat{f}(w) - f(w)|$ for the best possible emulator $\hat{f}$; we call this the "mini-minimax uncertainty" at $w$. In reality, $f$ might not be Lipschitz or---if it is---it might not attain its Lipschitz constant on the data. Hence, the mini-minimax uncertainty at $w$ could be much smaller than $|\hat{f}(w) - f(w)|$. But if the mini-minimax uncertainty is large, then---even if $f$ satisfies the optimistic regularity assumption---$|\hat{f}(w) - f(w)|$ could be large...

Minimax Filtering via Relations between Information and Estimation

No, Albert; Weissman, Tsachy
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
27.42%
We investigate the problem of continuous-time causal estimation under a minimax criterion. Let $X^T = \{X_t,0\leq t\leq T\}$ be governed by the probability law $P_{\theta}$ from a class of possible laws indexed by $\theta \in \Lambda$, and $Y^T$ be the noise corrupted observations of $X^T$ available to the estimator. We characterize the estimator minimizing the worst case regret, where regret is the difference between the causal estimation loss of the estimator and that of the optimum estimator. One of the main contributions of this paper is characterizing the minimax estimator, showing that it is in fact a Bayesian estimator. We then relate minimax regret to the channel capacity when the channel is either Gaussian or Poisson. In this case, we characterize the minimax regret and the minimax estimator more explicitly. If we further assume that the uncertainty set consists of deterministic signals, the worst case regret is exactly equal to the corresponding channel capacity, namely the maximal mutual information attainable across the channel among all possible distributions on the uncertainty set of signals. The corresponding minimax estimator is the Bayesian estimator assuming the capacity-achieving prior. Using this relation, we also show that the capacity achieving prior coincides with the least favorable input. Moreover...

Predicting The Performance of Minimax and Product in Game-Tree

Chi, Ping-Chung; Nau, Dana
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 27/03/2013
Relevância na Pesquisa
27.42%
The discovery that the minimax decision rule performs poorly in some games has sparked interest in possible alternatives to minimax. Until recently, the only games in which minimax was known to perform poorly were games which were mainly of theoretical interest. However, this paper reports results showing poor performance of minimax in a more common game called kalah. For the kalah games tested, a non-minimax decision rule called the product rule performs significantly better than minimax. This paper also discusses a possible way to predict whether or not minimax will perform well in a game when compared to product. A parameter called the rate of heuristic flaw (rhf) has been found to correlate positively with the. performance of product against minimax. Both analytical and experimental results are given that appear to support the predictive power of rhf.; Comment: Appears in Proceedings of the Second Conference on Uncertainty in Artificial Intelligence (UAI1986)

Minimax Multi-Task Learning and a Generalized Loss-Compositional Paradigm for MTL

Mehta, Nishant A.; Lee, Dongryeol; Gray, Alexander G.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 13/09/2012
Relevância na Pesquisa
27.28%
Since its inception, the modus operandi of multi-task learning (MTL) has been to minimize the task-wise mean of the empirical risks. We introduce a generalized loss-compositional paradigm for MTL that includes a spectrum of formulations as a subfamily. One endpoint of this spectrum is minimax MTL: a new MTL formulation that minimizes the maximum of the tasks' empirical risks. Via a certain relaxation of minimax MTL, we obtain a continuum of MTL formulations spanning minimax MTL and classical MTL. The full paradigm itself is loss-compositional, operating on the vector of empirical risks. It incorporates minimax MTL, its relaxations, and many new MTL formulations as special cases. We show theoretically that minimax MTL tends to avoid worst case outcomes on newly drawn test tasks in the learning to learn (LTL) test setting. The results of several MTL formulations on synthetic and real problems in the MTL and LTL test settings are encouraging.; Comment: appearing at NIPS 2012

Nonparametric Regression Estimation Based on Spatially Inhomogeneous Data: Minimax Global Convergence Rates and Adaptivity

Antoniadis, Anestis; Pensky, Marianna; Sapatinas, Theofanis
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
27.38%
We consider the nonparametric regression estimation problem of recovering an unknown response function f on the basis of spatially inhomogeneous data when the design points follow a known compactly supported density g with a finite number of well separated zeros. In particular, we consider two different cases: when g has zeros of a polynomial order and when g has zeros of an exponential order. These two cases correspond to moderate and severe data losses, respectively. We obtain asymptotic minimax lower bounds for the global risk of an estimator of f and construct adaptive wavelet nonlinear thresholding estimators of f which attain those minimax convergence rates (up to a logarithmic factor in the case of a zero of a polynomial order), over a wide range of Besov balls. The spatially inhomogeneous ill-posed problem that we investigate is inherently more difficult than spatially homogeneous problems like, e.g., deconvolution. In particular, due to spatial irregularity, assessment of minimax global convergence rates is a much harder task than the derivation of minimax local convergence rates studied recently in the literature. Furthermore, the resulting estimators exhibit very different behavior and minimax global convergence rates in comparison with the solution of spatially homogeneous ill-posed problems. For example...

A Minimax Robust Decoding Algorithm

Wei, Lei; Li, Zheng Feng; James, Matthew; Petersen, Ian R
Fonte: Institute of Electrical and Electronics Engineers (IEEE Inc) Publicador: Institute of Electrical and Electronics Engineers (IEEE Inc)
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.95%
In this correspondence we study the decoding problem in an uncertain noise environment. If the receiver knows the noise probability density function (pdf) at each time slot or its a priori probability, the standard Viterbi algorithm (VA) or the a posteriori probability (APP) algorithm can achieve optimal performance. However, if the actual noise distribution differs from the noise model used to design the receiver, there can be significant performance degradation due to the model mismatch. The minimax concept is used to minimize the worst possible error performance over a family of possible channel noise pdf's. We show that the optimal robust scheme is difficult to derive; therefore, alternative, practically feasible, robust decoding schemes are presented and implemented on VA decoder and two-way APP decoder. Performance analysis and numerical results show our robust decoders have a performance advantage over standard decoders in uncertain noise channels, with no or little computational overhead. Our robust decoding approach can also explain why for turbo decoding overestimating the noise variance gives better results than underestimating it.