Search

The celebrated minimax principle of Yao says that for any Boolean-valued function f with finite domain, there is a distribution µ over the domain of f such that computing f to error against inputs from µ is just as hard as computing f to error on worst-case inputs. Notably, however, the distribution µ depends on the target error level1: the hard distribution which is tight for bounded error might be trivial to solve to small bias, and the hard distribution which is tight for a small bias level might be far from tight for bounded error levels. In this work, we introduce a new type of minimax theorem which can provide a hard distribution µ that works for all bias levels at once. We show that this works for randomized query complexity, randomized communication complexity, some randomized circuit models, quantum query and communication complexities, approximate polynomial degree, and approximate logrank. We also prove an improved version of Impagliazzo's hardcore lemma. Our proofs rely on two innovations over the classical approach of using Von Neumann's minimax theorem or linear programming duality. First, we use Sion's minimax theorem to prove a minimax theorem for ratios of bilinear functions representing the cost and score of algorithms. Second, we introduce a new way to analyze low-bias randomized algorithms by viewing them as "forecasting algorithms" evaluated by a certain proper scoring rule. The expected score of the forecasting version of a randomized algorithm appears to be a more fine-grained way of analyzing the bias of the algorithm. We show that such expected scores have many elegant mathematical properties--for example, they can be amplified linearly instead of quadratically. We anticipate forecasting algorithms will find use in future work in which a fine-grained analysis of small-bias algorithms is required. [ABSTRACT FROM AUTHOR]

We investigate the concept of adjustability—the difference in objective values between two types of dynamic robust optimization formulations: one where (static) decisions are made before uncertainty realization, and one where uncertainty is resolved before (adjustable) decisions. This difference reflects the value of information and decision timing in optimization under uncertainty, and is related to several other concepts such as the optimality of decision rules in robust optimization. We develop a theoretical framework to quantify adjustability based on the input data of a robust optimization problem with a linear objective, linear constraints, and fixed recourse. We make very few additional assumptions. In particular, we do not assume constraint-wise separability or parameter nonnegativity that are commonly imposed in the literature for the study of adjustability. This allows us to study important but previously under-investigated problems, such as formulations with equality constraints and problems with both upper and lower bound constraints. Based on the discovery of an interesting connection between the reformulations of the static and fully adjustable problems, our analysis gives a necessary and sufficient condition—in the form of a theorem-of-the-alternatives—for adjustability to be zero when the uncertainty set is polyhedral. Based on this sharp characterization, we provide two efficient mixed-integer optimization formulations to verify zero adjustability. Then, we develop a constructive approach to quantify adjustability when the uncertainty set is general, which results in an efficient and tight poly-time algorithm to bound adjustability. We demonstrate the efficiency and tightness via both theoretical and numerical analyses. [ABSTRACT FROM AUTHOR]

In this article, we derive the minimax detection boundary for testing a sub-block of variables in a precision matrix under the Gaussian distribution. Compared to the results on the minimum rate of signals for testing precision matrices in literature, our result gives the exact minimum signal strength in a precision matrix that can be detected. We propose a thresholding test that is able to achieve the minimax detection boundary under certain cases by adaptively choosing the threshold level. The asymptotic distribution of the thresholding statistic for precision matrices is derived. Power analysis is conducted to show the proposed test is powerful against sparse and weak signals, which cannot be detected by the existing L m a x and L 2 tests. Simulation studies show the proposed test has an accurate size around the nominal level and is more powerful than the existing tests for detecting sparse and weak signals in precision matrices. Real data analysis on brain imaging data is carried out to illustrate the utility of the proposed test in practice, which reveals functional connectivity between brain regions for Alzheimer's disease patients and normal healthy people. [ABSTRACT FROM AUTHOR]

Let (R, 픪) be a local commutative Noetherian ring and I an ideal of R. Assume that M is a finitely generated R-module of finite projective dimension p and N is a finitely generated R-module of dimension d. We prove that H픪1(H Ip+d−1(M,N)) is Artinian. Moreover, if HomR(R/I,HIp+d−1(M,N)) is finitely generated, then HIp+d−1(M,N) is an I-cofinite R-module. [ABSTRACT FROM AUTHOR]

This study investigates the periodic inventory model for decaying goods that includes price discounts for backorders and considers that only a small portion of shortages are backlogged. The effect of managing lead time as a determining factor in the periodic inventory model. The present model develops a stochastic inventory model which together optimizes the backorder price discount, review period and the lead time for decaying items. During the protection interval, the demand has been looked at in two different ways: when demand distribution is known or not. The backorder ratio is influenced by price discount, and the suggested model assumes a constant deterioration rate. Numerical results show that a controlled lead time can yield significant savings. As far as the author knows, this is the first study to examine periodically deteriorating items with controlled lead times due to backorder discounts. On the other hand, as the products deteriorate at a faster pace, the overall annual cost rises. This research can help with the development of strategies for efficient inventory management of perishable commodities with backorder price reductions. [ABSTRACT FROM AUTHOR]

We discuss, and give examples of, methods for randomly implementing some minimax robust designs from the literature. These have the advantage, over their deterministic counterparts, of having bounded maximum loss in large and very rich neighbourhoods of the, almost certainly inexact, response model fitted by the experimenter. Their maximum loss rivals that of the theoretically best possible, but not implementable, minimax designs. The procedures are then extended to more general robust designs. For two-dimensional designs we sample from contractions of Voronoi tessellations, generated by selected basis points, which partition the design space. These ideas are then extended to k-dimensional designs for general k. [ABSTRACT FROM AUTHOR]

The localization of a robot is an important problem for accurate mapping via the mobile robot. In this paper, we propose minimax particle filtering (MPF) for the pose estimation of a mobile robot in the problem of simultaneous localization and mapping (SLAM) based on 2D LIDAR scans. Standard particle filtering has generic drawbacks such as particle degeneracy and particle impoverishment issues that cause the degraded quality of particles and result in unsatisfactory performance in practice while particle filtering is expected to show optimal performance in nonlinear problems, theoretically. Recently proposed MPF overcomes these limitations in PF implementation with increased quality of the particles in terms of particle diversity and variance of the weights. We test the proposed SLAM algorithm based on MPF with the datasets that were used for testing the standard Rao-Blackwellized PF (RBPF) SLAM and show the outperforming results, particularly in terms of the maximum translational/rotational errors that result in the overall diminished average errors. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the minmax single-machine scheduling problem with the slack due window, where the actual processing time of a job is the deterioration function of its starting time. The goal is to obtain the optimal schedule of the job and the related decision variables of the slack due window to minimize the linear combination cost function of the maximum earliness (tardiness) of the job and the due window. We show that this problem is solvable in O(n) time, and we carry out the numerical analysis, where $ n $ is the number of jobs. [ABSTRACT FROM AUTHOR]

A common problem faced in clinical studies is that of estimating the effect of the most effective (e.g. the one having the largest mean) treatment among $$k (\ge2)$$ k (≥ 2) available treatments. The most effective treatment is adjudged based on numerical values of some statistic corresponding to the $$k$$ k treatments. A proper design for such problems is the so-called "Drop-the-Losers Design (DLD)". We consider two treatments whose effects are described by independent Gaussian distributions having different unknown means and a common known variance. To select the more effective treatment, the two treatments are independently administered to $${n_1}$$ n 1 subjects each and the treatment corresponding to the larger sample mean is selected. To study the effect of the adjudged more effective treatment (i.e. estimating its mean), we consider the two-stage DLD in which $${n_2}$$ n 2 subjects are further administered the adjudged more effective treatment in the second stage of the design. We obtain some admissibility and minimaxity results for estimating the mean effect of the adjudged more effective treatment. The maximum likelihood estimator is shown to be minimax and admissible. We show that the uniformly minimum variance conditionally unbiased estimator (UMVCUE) of the selected treatment mean is inadmissible and obtain an improved estimator. In this process, we also derive a sufficient condition for inadmissibility of an arbitrary location and permutation equivariant estimator and provide dominating estimators in cases, where this sufficient condition is satisfied. The mean squared error and the bias performances of various competing estimators are compared via a simulation study. A real data example is also provided for illustration purpose. [ABSTRACT FROM AUTHOR]

AAA rational approximation has normally been carried out on a discrete set, typically hundreds or thousands of points in a real interval or complex domain. Here we introduce a continuum AAA algorithm that discretizes a domain adaptively as it goes. This enables fast computation of high-accuracy rational approximations on domains such as the unit interval, the unit circle, and the imaginary axis, even in some cases where resolution of singularities requires exponentially clustered sample points, support points, and poles. Prototype MATLAB (or Octave) and Julia codes aaax, aaaz, and aaai are provided for these three special domains; the latter two are equivalent by a Möbius transformation. Execution is very fast since the matrices whose SVDs are computed have only three times as many rows as columns. The codes include a AAA-Lawson option for improvement of a AAA approximant to minimax, so long as the accuracy is well above machine precision. The result returned is pole-free in the approximation domain. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Data Acquisition & Processing / Shu Ju Cai Ji Yu Chu Li is the property of Editorial Department of Journal of Nanjing University of Aeronautics & Astronautics and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The paper addresses asymptotic estimation of normal means under sparsity. The primary focus is estimation of multivariate normal means where we obtain exact asymptotic minimax error under global-local shrinkage prior. This extends the corresponding univariate work of Ghosh and Chakrabarti (2017). In addition, we obtain similar results for the Dirichlet-Laplace prior as considered in Bhattacharya et al. (2015). Also, following van der Pas et al. (2017), we have been able to derive credible sets for multivariate normal means under global-local priors. [ABSTRACT FROM AUTHOR]

The goal of phase II clinical trials is to evaluate the therapeutic efficacy of a new drug. Some investigators want to use the time-to-event endpoint as the primary endpoint of the phase II study to see the improvement of the therapeutic efficacy of a new drug in median survival time. Recently, median event time test (METT) has been proposed to provide a simple and straightforward rule which compares the observed median survival time with the prespecified threshold. However, median survival time would not be observed during the trial if the drug performs well and indeed cures most patients or if the accrual rate is so fast. To address the issues in clinical practice, we first propose a percentile event time test (PETT), which generalizes METT to any percentile of the survival time, and develop data-driven monitoring for phase II clinical trial designs based on PETT. We evaluate the performance of the method through simulations and illustrate the proposed method with a trial example. [ABSTRACT FROM AUTHOR]

We fully characterize the nonasymptotic minimax separation rate for sparse signal detection in the Gaussian sequence model with |$p$| equicorrelated observations, generalizing a result of Collier, Comminges and Tsybakov. As a consequence of the rate characterization, we find that strong correlation is a blessing, moderate correlation is a curse and weak correlation is irrelevant. Moreover, the threshold correlation level yielding a blessing exhibits phase transitions at the |$\sqrt{p}$| and |$p-\sqrt{p}$| sparsity levels. We also establish the emergence of new phase transitions in the minimax separation rate with a subtle dependence on the correlation level. Additionally, we study group structured correlations and derive the minimax separation rate in a model including multiple random effects. The group structure turns out to fundamentally change the detection problem from the equicorrelated case and different phenomena appear in the separation rate. [ABSTRACT FROM AUTHOR]

Adaptive designs are commonly used in clinical and drug development studies for optimum utilization of available resources. In this article, we consider the problem of estimating the effect of the selected (better) treatment using a two‐stage adaptive design. Consider two treatments with their effectiveness characterized by two normal distributions having different unknown means and a common unknown variance. The treatment associated with the larger mean effect is labeled as the better treatment. In the first stage of the design, each of the two treatments is independently administered to different sets of n1 subjects, and the treatment with the larger sample mean is chosen as the better treatment. In the second stage, the selected treatment is further administered to n2 additional subjects. In this article, we deal with the problem of estimating the mean of the selected treatment using the above adaptive design. We derive the uniformly minimum variance conditionally unbiased estimator (UMVCUE) of the mean effect of the selected treatment when multiple observations are available in the second stage. We show that the maximum likelihood estimator (a weighted sample average based on the first and the second stage data) is minimax and admissible for estimating the mean effect of the selected treatment. We also propose some plug‐in estimators obtained by plugging in the pooled sample variance in place of the common variance σ2, in some of the existing estimators where σ2 is known. The performances of various estimators of the mean effect of the selected treatment are compared via a simulation study. For the illustration purpose, we also provide a real‐data application. [ABSTRACT FROM AUTHOR]

In spatial-model computer simulations with artificial voters and candidates, the well-known minimax single-winner voting system far outperformed 10 other systems at picking the best winners. It essentially tied with two others (Schulze and ranked pairs), both of which are far more complex than minimax. Minimax's other advantages include Condorcet consistency, simplicity, monotonicity, and ease of voting because it allows tied and missing ranks. It also makes insincere strategic voting schemes difficult and dangerous for the schemers. The new minimax-TD system modifies minimax in three ways, all of which make it pick better winners, according to simulation studies: (a) TD includes Smith/minimax, (b) TD uses one particular definition of a candidate's "largest loss" in two-way elections, and (c) TD includes a multi-stage tie-breaker which breaks nearly all ties. TD avoids four of the worst anomalies afflicting classic minimax. Four other minimax anomalies can be ignored, leaving TD arguably free of anomalies. [ABSTRACT FROM AUTHOR]

Minimax problems of the form minx maxy Ѱ(x, y) have attracted increased interest largely due to advances in machine learning, in particular generative adversarial networks and adversarial learning. These are typically trained using variants of stochastic gradient descent for the two players. Although convex-concave problems are well understood with many efficient solution methods to choose from, theoretical guarantees outside of this setting are sometimes lacking even for the simplest algorithms. In particular, this is the case for alternating gradient descent ascent, where the two agents take turns updating their strategies. To partially close this gap in the literature we prove a novel global convergence rate for the stochastic version of this method for finding a critical point of Ѱ(.):= maxy Ѱ (.,y) in a setting which is not convex-concave. [ABSTRACT FROM AUTHOR]

The paper proves the minimax theorem for a specific class of functions that are defined on branching polylines in a linear space, not on convex subsets of a linear space. The existence of a saddle point for such functions does not follow directly from the classical minimax theorem and needs individual consideration based both on convex analysis and graph theory. The paper presents a self-sufficient analysis of the problem. It contains everything that enables a plain understanding of the main result and its proof and avoids using concepts outside the scope of obligatory mathematical education of engineers. The paper is addressed to researchers in applied mechanics, engineering, and other applied sciences as well as to mathematicians who lecture convex analysis and optimization methods to non-mathematicians. [ABSTRACT FROM AUTHOR]

Mixed‐strategy Nash equilibrium is the cornerstone of our understanding of strategic situations that require decision makers to be unpredictable. Using data from nearly half a million serves over 3000 tennis matches, and data on player rankings from the ATP and WTA, we examine whether the behavior of professional tennis players is consistent with equilibrium. We find that win rates conform remarkably closely to the theory for men, but conform somewhat less neatly for women. We show that the behavior in the field of more highly ranked (i.e., better) players conforms more closely to theory. We show that the statistical tests used in the prior related literature are not valid for large samples like ours; we develop a novel statistical test that is valid and show, via Monte Carlo simulations, that it is more powerful against the alternative that receivers follows a nonequilibrium mixture. [ABSTRACT FROM AUTHOR]

We investigate minimaxness and finiteness of formal local homology modules. At first we determine the Associated prime ideals of top formal local homology module. Then we discuss the maximum and minimum integers such that formal local homology modules are minimax. As a consequence, we find maximum and minimum integers such that formal local homology modules are of finite length. Also, we get a relation between finite and good formal local homology modules. [ABSTRACT FROM AUTHOR]

Alternating projection onto convex sets (POCS) provides an iterative procedure to find a signal that satisfies two or more convex constraints when the sets intersect. For nonintersecting constraints, the method of simultaneous projections produces a minimum mean square error (MMSE) solution. In certain cases, a minimax solution is more desirable. Generating a minimax solution is possible using dilated POCS. The minimax solution uses morphological dilation of nonintersecting signal convex constraints. The sets are progressively dilated to the point where there is intersection at a minimax solution. Examples are given contrasting the MMSE and minimax solutions in problems of tomographic reconstruction of images. Dilated POCS adds a new imaging modality for image synthesis. Lastly, morphological erosion of signal sets is suggested as a method to shrink the overlap when sets intersect at more than one point.

The study solves the problem of filtering nonlinear systems based on the minimax adaptive algorithm of nonlinear systems by Volterra series of the second order, provided that the autocorrelation functions of the useful signal and interference are known with some errors according to the criterion of the maximum standard error of filtering. The author analyses the stationary performance of a minimax adaptive Volterra filter of the second order with the least mean square (LMS) with a constant step size of µ with a time-varying setting. A quantitative assessment of the steadystate excess root-mean-square error (RMSE) has been established, in which the contribution of incorrect gradient adjustment and tracking error is well characterized. Then the optimal step size is set for a time-varying secondorder minimax Volterra filter. Thus, we can study the correlation between the excess MSE and the optimal step size, on the one hand, and the parameters of a time-varying nonlinear system, on the other hand. A simple solution with minimal root-mean-square error for the minimax Volterra filter is obtained, based on the assumption that the input signal of the filter is Gaussian. In addition, we propose an iterative factorization method for developing a subclass of minimax Volterra filters, which can greatly simplify filtering operations. In addition, an adaptive algorithm for the Volterra filter is investigated, as well as its average convergence and asymptotic excess root-mean-square error. Finally, the usefulness of the Volterra filter is demonstrated by its use in studies of nonlinear drift oscillations of moored vessels exposed to random sea waves.

This paper presents the design of a desired linear phase digital Finite Impulse Response (FIR) High Pass (HP) filter based on Adaptive Systematic Cuckoo Search Algorithm (ACSA). The deviation, or error from the desired response, is assessed along with the stop-band and pass-band attenuation of the filter. The Cuckoo Search algorithm (CS) is used to avoid local minima because the error surface is typically non-differentiable, nonlinear, and multimodal. The ACSA is applied to the minimax criterion (L∞-norm) based error fitness function, which offers a better equiripple response for passband and stopband, high stopband attenuation, and rapid convergence for the developed optimal HP FIR filter algorithm. The simulation findings demonstrate that when compared to the Parks McClellan (PM), Particle Swarm Optimization (PSO), CRazy Particle Swarm Optimization (CRPSO), and Cuckoo Search algorithms, the proposed HP FIR filter employing ACSA leads to better solutions.

We propose a new approach for visual object tracking based on a combined method of minimax estimator and sequential Monte Carlo filtering. The proposed approach adopts a minimax strategy in the standard particle filtering framework for the problem. Particle filtering is based on probabilistic methodology, while a minimax estimator belongs to deterministic approaches. Experiments show outperforming results of the proposed approach compared to the standard particle filtering in terms of tracking accuracy. We also investigate the computational complexity of the proposed algorithm in terms of elapsed processing time. In this paper, we focus on the particle filtering framework only for the performance comparison between the two methods. [ABSTRACT FROM AUTHOR]

This paper derives a macroeconomic resilient control framework that provides the optimal feedback fiscal and monetary policy responses in response to a potentially large negative external incident. We simulate the model for the U.S. under the conditions that prevailed throughout the 2020 economic crisis that occurred due to the government lockdown that was caused by the coronavirus pandemic. We develop a discrete-time soft-constrained linear-quadratic dynamic game under a worst-case design with multiple disturbances. Within this context, we introduce a resilience feedback response and compare the case where the policymakers counter in response the external incident with the case when they do not counter. This framework is especially applicable to large-scale macroeconomic tracking control models and wavelet-based control models when formulating the magnitudes of the policy changes necessary for the unemployment rate and national output variables to maintain acceptable tracking errors in the periods following a major disruption. Our policy recommendations include the maintenance of "rainy day" funds at appropriate levels of government to mitigate the effects of large adverse events. [ABSTRACT FROM AUTHOR]

Here is a sample of the results proved in this paper: Let f:R→R be a continuous function, let ρ>0 and let ω:[0,ρ[→[0,+∞[ be a continuous increasing function such that limt→ρ-∫0εω(t)=+∞. Consider C0([0,1])×C0([0,1]) endowed with the norm ∥(α,β)∥=∫¹0|α(t)|dt+∫¹0|β(t)|dt. Then, the following assertions are equivalent: (a) the restriction of f to [-√ρ/2,√ρ/2] is not constant; (b) for every convex set S⊆C0([0,1])×C0([0,1]) dense in C0([0,1])×C0([0,1]), there exists (α,β)∈S such that the problem ... has at least two classical solutions. [ABSTRACT FROM AUTHOR]

We show that the choice of stepsize in Korpelevich’s extragradient algorithm is sharp, while the choice of stepsize in Popov’s extragradient algorithm can be relaxed. We also extend Korpelevich’s extragradient algorithm and Popov’s extragradient algorithm (with larger stepsize) to the infinite-dimensional Hilbert space framework, with weak convergence. [ABSTRACT FROM AUTHOR]

Modern scientific studies often collect datasets in the form of tensors. These datasets call for innovative statistical analysis methods. In particular, there is a pressing need for tensor clustering methods to understand the heterogeneity in the data. We propose a tensor normal mixture model approach to enable probabilistic interpretation and computational tractability. Our statistical model leverages the tensor covariance structure to reduce the number of parameters for parsimonious modeling, and at the same time explicitly exploits the correlations for better variable selection and clustering. We propose a doubly enhanced expectation–maximization (DEEM) algorithm to perform clustering under this model. Both the expectation-step and the maximization-step are carefully tailored for tensor data in order to maximize statistical accuracy and minimize computational costs in high dimensions. Theoretical studies confirm that DEEM achieves consistent clustering even when the dimension of each mode of the tensors grows at an exponential rate of the sample size. Numerical studies demonstrate favorable performance of DEEM in comparison to existing methods. [ABSTRACT FROM AUTHOR]

Chess engines, computer programs designed to play chess, have become increasingly popular in recent years due to their ability to challenge human players and provide insights into the game that were previously inaccessible. However, many existing chess engines prioritize maximum performance at the expense of customizable and extensible software design, which would benefit new coming developers in the field. To address this issue, we present GoFish , a chess engine developed in Golang that achieves a balance between performance and design to serve as a modular and easy-to-extend chess engine development framework. At its core, the chess engine has two vital functions: the move search function and the position evaluation function, both of which are performance-critical. The engine has been developed with the aim of decoupling the search and evaluation modules, enabling developers to easily integrate their custom implementations for these two functions. Simultaneously, the engine automatically handles other intricate internal modules. Consequently, our proposed framework significantly reduces the development effort required to implement and compare core algorithms within the chess engine. Moreover, the engine includes default move search and evaluation implementations that have reached a playing strength comparable to that of a grandmaster. Our work is the first in the literature to present a chess engine developed in the Go programming language that strikes a balance between code performance, extendibility, and readability. [ABSTRACT FROM AUTHOR]

The article considers an adaptive sequential nonparametric estimation of a multivariate regression with assigned mean integrated squared error (MISE) and minimax mean stopping time when the estimator matches performance of an oracle knowing all nuisance parameters and functions. It is known that the problem has no solution if regression belongs to a Sobolev class of differentiable functions. What if an underlying regression is smoother, say, analytic? It is shown that in this case it is possible to match performance of the oracle. Furthermore, similar to the classical Stein solution for a parameter estimation, a two-stage sequential procedure solves the problem. The proposed regression estimator for the first stage, based on a sample with fixed sample size, is of interest on its own, and a thought-provoking environmental example of reducing potent greenhouse gas emission by an anaerobic digestion system is used to discuss a number of important topics for small samples. [ABSTRACT FROM AUTHOR]