Search

In this letter, we present an iterative algorithm for constructing high-dimensional incoherent Grassmannian Frames (GFs) which are sets of unit-norm vectors that are minimax optimal: the maximum absolute value of their inner products is a minimum. We formulate the GF design as a nonconvex optimization problem and solve it via an efficient iterative algorithm. The bulk of each iteration of the proposed algorithm is a Linear Program (LP) for which there are a host of efficient solvers. The proposed algorithm is based on the theoretically sound Minorization Maximization technique which, unlike some of the state-of-the-art design approaches, monotonically minimizes the design criterion and can construct GFs with low coherence values.

Stereo matching aiming to perceive the 3-D geometry of a scene facilitates numerous computer vision tasks used in advanced driver assistance systems (ADAS). Although numerous methods have been proposed for this task by leveraging deep convolutional neural networks (CNNs), stereo matching still remains an unsolved problem due to its inherent matching ambiguities. To overcome these limitations, we present a method for jointly estimating disparity and confidence from stereo image pairs through deep networks. We accomplish this through a minmax optimization to learn the generative cost aggregation networks and discriminative confidence estimation networks in an adversarial manner. Concretely, the generative cost aggregation networks are trained to accurately generate disparities at both confident and unconfident pixels from an input matching cost that are indistinguishable by the discriminative confidence estimation networks, while the discriminative confidence estimation networks are trained to distinguish the confident and unconfident disparities. In addition, to fully exploit complementary information of matching cost, disparity, and color image in confidence estimation, we present a dynamic fusion module. Experimental results show that this model outperforms the state-of-the-art methods on various benchmarks including real driving scenes.

Mixed strategy equilibria — Nash (NE) and maximin (MM) — are cornerstones of game theory, but their empirical relevance has always been questionable. We study in the laboratory two games, each with a unique NE and a unique (and distinct) MM in completely mixed strategies. Treatment variables include the matching protocol (pairwise random vs population mean matching), whether time is discrete or continuous, and whether players can specify explicit mixtures or only pure strategy realizations. NE mixes predict observed behavior relatively well in population mean matching treatments, and predict better than MM in all treatments. However, in most random pairwise treatments, uniform mixes predict better than NE. Regret-based and sign preserving dynamics capture regularities across all treatments.

Airline alliances provide more flights, include different destinations, and maximize revenues. In an alliance, collaborating airlines can offer tickets for an identical flight plan, unlike the traditional single airline approach. In particular, due to epidemic/pandemic events, such as COVID-19, the available customer demands become highly uncertain across many real airline alliance problems, and maintaining stable revenue is as important as maximizing the revenue in the alliance. A critical question is how the independent airline companies of an alliance should collaborate to maintain reliable maximum revenue. Therefore, this question was studied using a grey mathematical programming model for small-sized airline alliances under grey demand data. Some cooperative game theoretical solution concepts, such as Shapley, equal revenue, Nucleolus, and minimax core, are presented. A numerical study of a small-sized alliance with three airline companies was used to interpret the results of the cooperative game theory concepts. Three cases were considered based on the grey passenger demand structure of airline collaborations to share extra revenues and maintain stable revenue distribution that would maximize the expected revenue. Based on the obtained results, the synergy of collaboration increased with the increase in the size coalition in all of the cases, except for the cases of lower (L) and upper (U) demand levels.

A theory of refining pure strategy efficient Nash equilibria in finite noncooperative games under uncertainty is outlined. The theory is based on guaranteeing the corresponding payoffs for the players by using maximultimin, which is an expanded version of maximin. If a product of the players’ maximultimin subsets contains more than one efficient Nash equilibrium, a superoptimality rule is attached wherein minimization is substituted with summation. The superoptimality rule stands like a backup plan, and it is involved if maximultimin fails to produce just a single refined efficient equilibrium (a metaequilibrium). The number of the refinement possible outcomes is 10. There are 3 single-metaequilibrium cases, 3 partial reduction cases, and 4 fail cases. Despite successfulness of refinement drops as the game gets bigger, pessimistic estimation of its part is above 54 % for games with no more than four players.

In this paper, we construct a lower bound of the minimax risk in the estimation problem when we observe an unknoun pseudo-periodic vector-function in a Gaussian stationary noise with spectral density satisfying the vector version of the Muckenhoupt condition.

Exhausters are families of compact, convex sets which provide minmax or maxmin representations of positively homogeneous functions and they are efficient tools for the study of nonsmooth functions (Demyanov in Optimization 45:13–29, 1999). Upper and lower exhausters of positively homogeneous functions are employed to describe optimality conditions in geometric terms and also to find directions of steepest descent or ascent. Since an upper/lower exhauster may contain finitely or infinitely many compact convex sets, the problem of minimality and reduction of exhausters naturally arise. There are several approaches to reduce exhausters (Abbasov in J Glob Optim 74(4):737–751, 2019; Grzybowski et al. in J Glob Optim 46(4):589–601, 2010; Kucuk et al. in J Optim Theory Appl 165:693–707, 2015; Roshchina in J Optim Theory Appl 136:261–273, 2008; J Convex Anal 15(4):859–868, 2008). In this study, in the sense of inclusion-minimality, some reduction techniques for upper exhausters of positively homogeneous functions defined from $$\mathbb {R}^2$$ to $$\mathbb {R}$$ is proposed by means of a representation of support functions. These techniques have concrete geometric meanings and they form a basis for a necessary and sufficient condition for inclusion-minimality of exhausters. Some examples are presented to illustrate each reduction technique.

Cancer is a complicated worldwide health issue with an increasing death rate in recent years. With the swift blooming of the high throughput technology and several machine learning methods that have unfolded in recent years, progress in cancer disease diagnosis has been made based on subset features, providing awareness of the efficient and precise disease diagnosis. Hence, progressive machine learning techniques that can, fortunately, differentiate lung cancer patients from healthy persons are of great concern. This paper proposes a novel Wilcoxon Signed-Rank Gain Preprocessing combined with Generative Deep Learning called Wilcoxon Signed Generative Deep Learning (WS-GDL) method for lung cancer disease diagnosis. Firstly, test significance analysis and information gain eliminate redundant and irrelevant attributes and extract many informative and significant attributes. Then, using a generator function, the Generative Deep Learning method is used to learn the deep features. Finally, a minimax game (i.e., minimizing error with maximum accuracy) is proposed to diagnose the disease. Numerical experiments on the Thoracic Surgery Data Set are used to test the WS-GDL method's disease diagnosis performance. The WS-GDL approach may create relevant and significant attributes and adaptively diagnose the disease by selecting optimal learning model parameters. Quantitative experimental results show that the WS-GDL method achieves better diagnosis performance and higher computing efficiency in computational time, computational complexity, and false-positive rate compared to state-of-the-art approaches.

Machine learning classifiers are vulnerable to adversarial perturbation, and their presence raises security concerns, especially in recommendation systems. While attacks and defense mechanisms in recommendation systems have received significant attention, Basic Iterative Method (BIM), which has been shown in Computer Vision to increase attack effectiveness by more than 60%, has received little attention in ownership recommendation. As a result, ownership recommender systems may be more sensitive to iterative perturbations, resulting in significant generalization errors. Adversarial Training, a regularization strategy that can withstand worst-case iterative perturbations, could be a viable option for improving model robustness and generalization. In this paper, we implement BIM for ownership recommendations. Through adversarial training, we propose the Adversarial Consumer and Producer Recommendation (ACPR) approach that integrates ownership features into a multi-objective pairwise ranking to capture the user’s preferences. The ACPR method learns a core embedding for each user and two transformation matrices that project the user’s core embedding into two role embeddings (i.e., a producer and consumer role) using an extension of matrix factorization. To minimize the impact of iterative perturbation, we train a consumer and producer recommender objective function using minimax adversarial training. Empirical studies on two Large-scale applications show that our method outperforms standard recommendation methods and recent methods that model ownership information.

Heliosynchronous orbits are attractive for space system construction. As a result, the number of spacecraft operating therein is constantly increasing. To increase their efficiency, timely on-orbit servicing (both scheduled and emergency) is needed. Emergency on-orbit servicing of spacecraft is needed in the case of unforeseen, emergency situations with them. According to available statistical estimates, emergency situations with serviced spacecraft are not frequent. Because of this, serviced spacecraft must be within the reach of a service spacecraft for a long time. In planning emergency on-orbit servicing, the following limitations must be met: the time it takes the service spacecraft to approach any of the serviced spacecraft must not exceed its allowable value, and the service spacecraft’s allowable energy consumption must not be exceeded. This paper addresses the problem of searching for emergency on-orbit servicing that would be allowable in terms of time and energy limitations and would meet technical and economical constraints. The aim of this work is to develop a mathematical constrained optimization model for phasing orbit parameter choice, whose use would allow one to minimize the maximum time of transport operations in emergency on-orbit servicing of a spacecraft group in the region of heliosynchronous orbits. The problem is solved by constrained minimax optimization. What is new is the formulation of a minimax (guaranteeing) criterion for choosing phasing orbit parameters that minimize the maximum time of emergency on-orbit servicing transport operations. In the minimax approach, the problem is formulated as the problem of searching for the best solution such that the result is certain to be attained for any allowable sets of indeterminate factors. The proposed mathematical model may be used in planning emergency on-orbit service operations to minimize the maximum duration of emergency on-orbit servicing transport operations due to a special choice of the service spacecraft phasing and parking orbit parameters.

Summary This study investigates optimal minimax rates for specification testing when the alternative hypothesis is built on a set of nonsmooth functions. The set consists of bounded functions that are not necessarily differentiable with no smoothness constraints imposed on their derivatives. In the instrumental variable regression set up with an unknown error variance structure, we find that the optimal minimax rate is $n^{-1/4}$, where n is the sample size. The rate is achieved by a simple test based on the difference between nonparametric and parametric variance estimators. Simulation studies illustrate that the test has reasonable power against various nonsmooth alternatives. The empirical application to Engel curves specification emphasizes the good applicability of the test.

This paper is concerned with estimation of parameters defined by moment equalities. We introduce the exponentially tilted Hellinger distance (ETHD) estimator which is efficient under correct specification, and robust to both global and local misspecification. In the spirit of Schennach (2007), ETHD combines the Hellinger distance and the Kullback–Leibler information criterion. We show that it achieves optimal minimax robust properties under local deviations from the model and remains well-behaved under global misspecification.

We extend, to the framework of topological vector spaces, two results by Horvath and Kuratowski related to conditions for a family of closed sets to have compact and nonempty intersection. This extension enables us to introduce a number of applications such as the existence of maximal elements in preordered spaces, issues related to KKM functions, fixed point theorems, a variant of a matching theorem by Fan, and mainly the improvement of some minimax and variational inequalities.

Randomized response (RR) is a common privacy protection tool. It perturbs each true response using a probabilistic mechanism. Local differential privacy (LDP) is a rigorous privacy protection crite...

It is a challenging task to effectively estimate the upper bound as well as the lower bound of failure probability under epistemic and aleatory uncertainties in a dynamic environment. This paper proposes a novel approach to estimating both the lower and upper bounds of the time-variant hybrid failure probability by combining the proposed box moments and improved maximum entropy methods. The sparse grid sampling technique is first employed to simplify the time-variant hybrid performance function for the integration. A new continuous maximin algorithm based on the improved particle swarm optimization is then proposed for estimating the box moments. The probability density function and the time-variant hybrid failure probability can be finally estimated with the improved maximum entropy method by introducing the nonlinear transformation with an adjustable parameter. Two engineering examples are employed to testify the effectiveness of the proposed method.

In cybersecurity applications where machine learning algorithms are increasingly used to detect vulnerabilities, a somewhat unique challenge arises as exploits targeting machine learning models are constantly devised by the attackers. Traditional machine learning models are no longer robust and reliable when they are under attack. The action and reaction between machine learning systems and the adversary can be modeled as a game between two or more players. Under well‐defined attack models, game theory can provide robustness guarantee for machine learning models that are otherwise vulnerable to application‐time data corruption. We review two cases of game theory‐based machine learning techniques: in one case, players play a zero sum game by following a minimax strategy, while in the other case, players play a sequential game with one player as the leader and the rest as the followers. Experimental results on e‐mail spam and web spam datasets are presented. In the zero sum game, we demonstrate that an adversarial SVM model built upon the minimax strategy is much more resilient to adversarial attacks than standard SVM and one‐class SVM models. We also show that optimal learning strategies derived to counter overly pessimistic attack models can produce unsatisfactory results when the real attacks are much weaker. In the sequential game, we demonstrate that the mixed strategy, allowing a player to randomize over available strategies, is the best solution in general without knowing what types of adversaries machine learning applications are facing in the wild. We also discuss scenarios where players' behavior may derail rational decision making and models that consider such decision risks.

A new notion of linking is introduced to treat minima as minimax points in a unitary way. Critical points are located in conical annuli making possible to obtain multiplicity. For functionals defined on a Cartesian product, the localization of critical points is given on components and the variational properties of the components can differ, part of them being of minimum type, others of mountain pass type.

The article is devoted to the development of algorithms for operational planning of routes for a group of aircraft (AC). We consider group actions of small and unmanned aircraft in the "air taxi" mode, when there is no regular flight schedule between the points of destination, and requests are received "on call" for flights to points whose composition is unknown in advance and is of a random nature. The multicriteria task of planning a group flight in the "air taxi" mode is being solved. The solution to this problem is proposed using the apparatus of the queuing theory, according to which the system under consideration belongs to the class of multichannel queuing systems with waiting. A method for solving the problem of operational planning of aircraft actions is proposed. An algorithm for group target distribution of new claims between aircraft is developed on the basis of a modified minimax criterion for assigning the nearest aircraft for an object with a maximum service time. The developed algorithm is based on the following four main operations: in the first operation, priority unserved targets are selected according to the criterion of assigning a dynamic priority; in the second operation, the formed list is ranked according to another criterion, taking into account the importance and total distance of each ground object from the aircraft group, in three this operation selects the object with the maximum rank, and for it the task of assigning "own" aircraft is solved according to the third criterion of maximum proximity, in the fourth operation the conditions of non-intersection of the group flight routes are checked. A computer model of the system for servicing requests in the air taxi mode has been developed. The developed model makes it possible to analyze various scheduling algorithms, as well as to determine at each step the number of free claims and the number of free and busy aircraft. A comparison is made between the well-known in the theory of queuing and the proposed minimax approaches. It is shown that, in comparison with the known variants of scheduling in the queuing theory, on the basis of the proposed approach, the optimal number of used aircraft is achieved.

This article studies multiagent differential graphical games in linear dynamical networks. We point out that in existing graphical game formulations, being global Nash and being distributed are two contradicting properties. In particular, we prove that the best response strategy, most widely used in solving graphical games, leads to Nash but does not provide distributed solutions. On the other hand, the minmax strategy, recently developed in solving graphical games, provides distributed solutions but prevents the agents from reaching a global Nash equilibrium. In this article, we propose a novel differential graphical game formulation, which promises the existence of solutions that 1) lead to global Nash equilibrium and 2) are distributed in the sense that each agent only uses the state information of its own and its direct neighbors. Stability and Nash equilibrium properties of the proposed graphical game are proven, respectively. Simulation studies are conducted to illustrate the theoretical results.

Feature selection is an important procedure that is used in data mining to extract valuable information from large quantities of data. Existing penalization methods use a single penalty function to select important features. However, these methods do not yield sufficiently accurate predictions and selection outcomes. Therefore, construction of a concise and efficient prediction model would be beneficial. In this study, we propose a novel penalty function using a ridge and minimax concave penalty to overcome the limitations of individual penalty functions. Furthermore, we introduce a robust penalized feature selection method with Huber loss function, which is implemented by a local approximation algorithm. The theoretical properties of the algorithm have been described. Simulated and real-world data analyses are used to demonstrate the efficacy of the proposed method.

Mutual information is a measure of the dependence between random variables that has been used successfully in myriad applications in many fields. Generalized mutual information measures that go beyond classical Shannon mutual information have also received much interest in these applications. We derive the mean squared error convergence rates of kernel density-based plug-in estimators of general mutual information measures between two multidimensional random variables $\mathbf{X}$ and $\mathbf{Y}$ for two cases: 1) $\mathbf{X}$ and $\mathbf{Y}$ are continuous; 2) $\mathbf{X}$ and $\mathbf{Y}$ may have any mixture of discrete and continuous components. Using the derived rates, we propose an ensemble estimator of these information measures called GENIE by taking a weighted sum of the plug-in estimators with varied bandwidths. The resulting ensemble estimators achieve the $1/N$ parametric mean squared error convergence rate when the conditional densities of the continuous variables are sufficiently smooth. To the best of our knowledge, this is the first nonparametric mutual information estimator known to achieve the parametric convergence rate for the mixture case, which frequently arises in applications (e.g. variable selection in classification). The estimator is simple to implement and it uses the solution to an offline convex optimization problem and simple plug-in estimators. A central limit theorem is also derived for the ensemble estimators and minimax rates are derived for the continuous case. We demonstrate the ensemble estimator for the mixed case on simulated data and apply the proposed estimator to analyze gene relationships in single cell data., Published in IEEE Transactions on Information Theory in 2021; 42 pages, 3 figures; a shorter version of this paper was published at IEEE ISIT 2017 under the title "Ensemble estimation of mutual information"

Switchback experiments, where a firm sequentially exposes an experimental unit to random treatments, are among the most prevalent designs used in the technology sector, with applications ranging from ride-hailing platforms to online marketplaces. Although practitioners have widely adopted this technique, the derivation of the optimal design has been elusive, hindering practitioners from drawing valid causal conclusions with enough statistical power. We address this limitation by deriving the optimal design of switchback experiments under a range of different assumptions on the order of the carryover effect—the length of time a treatment persists in impacting the outcome. We cast the optimal experimental design problem as a minimax discrete optimization problem, identify the worst-case adversarial strategy, establish structural results, and solve the reduced problem via a continuous relaxation. For switchback experiments conducted under the optimal design, we provide two approaches for performing inference. The first provides exact randomization-based p-values, and the second uses a new finite population central limit theorem to conduct conservative hypothesis tests and build confidence intervals. We further provide theoretical results when the order of the carryover effect is misspecified and provide a data-driven procedure to identify the order of the carryover effect. We conduct extensive simulations to study the numerical performance and empirical properties of our results and conclude with practical suggestions. This paper was accepted by George Shanthikumar, big data analytics.

International audience; The challenge of producing accurate statistics while respecting the privacy of the individuals in a sample is an important area of research. We study minimax lower bounds for classes of differentially private estimators. In particular, we show how to characterize the power of a statistical test under differential privacy in a plug-and-play fashion by solving an appropriate transport problem. With specific coupling constructions, this observation allows us to derive Le Cam-type and Fano-type inequalities not only for regular definitions of differential privacy but also for those based on Renyi divergence. We then proceed to illustrate our results on three simple, fully worked out examples. In particular, we show that the problem class has a huge importance on the provable degradation of utility due to privacy. In certain scenarios, we show that maintaining privacy results in a noticeable reduction in performance only when the level of privacy protection is very high. Conversely, for other problems, even a modest level of privacy protection can lead to a significant decrease in performance. Finally, we demonstrate that the DP-SGLD algorithm, a private convex solver, can be employed for maximum likelihood estimation with a high degree of confidence, as it provides near-optimal results with respect to both the size of the sample and the level of privacy protection. This algorithm is applicable to a broad range of parametric estimation procedures, including exponential families.

This paper is part of an ongoing endeavor to bring the theory of fair division closer to practice by handling requirements from real-life applications. We focus on two requirements originating from the division of land estates: (1) each agent should receive a plot of a usable geometric shape, and (2) plots of different agents must be physically separated. With these requirements, the classic fairness notion of \emph{proportionality} is impractical, since it may be impossible to attain any multiplicative approximation of it. In contrast, the \emph{ordinal maximin share approximation}, introduced by Budish in 2011, provides meaningful fairness guarantees. We prove upper and lower bounds on achievable maximin share guarantees when the usable shapes are squares, fat rectangles, or arbitrary axis-aligned rectangles, and explore the algorithmic and query complexity of finding fair partitions in this setting. Our work makes use of tools and concepts from computational geometry such as independent sets of rectangles and guillotine partitions., Appears in the 30th International Joint Conference on Artificial Intelligence (IJCAI), 2021

The two-variable orthogonal least squares procedure was developed independently by Julius Ludwig Weisbach (1806–1871) and Robert Jackson Adcock (1826–1895). In this article we discuss aspects of tw...

The article presents the author’s approach to assessing the risks of corporate and financial security of the region. The purpose of the article is to develop, substantiate and test the author’s approach to assessing and measuring risks of corporate and financial security at the meso-level. The research used methods such as indicative method, comparison method, analysis, synthesis. The paper analyzes conceptual approaches to the concept of security risk, examines the distinctive characteristics of the definition of “risk” from the concepts of “threat” and “danger”. Further, the author examines the issue of the list of main risks in the field of corporate financial security, as a result of which a risk system is proposed that includes 7 main risks, which are assessed using a methodology based on the synthesis of an indicative approach and a minimax method using a normalizing function and a 100-point scale. For each of the risks, indicators are selected, and their threshold values are justified, which are used for comparison with the actual values of indicators, on the basis of which the level of risk is measured. Approbation of the approach proposed in the article was carried out on the example of the Komi Republic. As a result of the risk diagnostics, significant risks of the corporate and financial security of the region were identified, and some recommendations were proposed for solving the problem of improving the conditions for doing business in the region. The obtained results of the work can be used by public authorities in solving the problems of public administration and monitoring the risks of the corporate and financial security of the region.

We consider a spatial bargaining model where players collectively choose a facility location on a two-dimensional rectilinear distance space through bargaining using the unanimity rule. We show that as players become infinitely patient, their stationary subgame perfect equilibrium utilities converge to the utilities that satisfy the lexicographic maximin utility criterion introduced by Sen (Collective choice and social welfare, 1970).

The problem of optimal estimation of linear functionals constructed from unobserved values of a stochastic sequence with periodically stationary increments based on its observations at points $ k

We extend two classical scheduling and due-date assignment models. In the first (known in the literature as DIF), due-dates are determined by penalties for exceeding pre-specified deadlines. In the second (known as SLK), due-dates are assigned to jobs as a (linear) function of their processing times. We focus on the minmax versions of these models, and extend the single machine versions to a two-machine flowshop. We further extend the settings to that of a due-window. All the problems studied in this note are shown to have polynomial time solutions.

This article considers the minmax common due-window assignment in group scheduling with resource allocation on a single machine. In this problem, jobs are partitioned into groups. In a group, all j...

A novel actor-critic algorithm is introduced and applied to zero-sum differential game. The proposed novel structure consists of two actors and a critic. Different actors represent the control policies of different players, and the critic is used to approximate the state-action utility function. Instead of neural network, the fuzzy inference system is applied as approximators for the actors and critic so that the specific practical meaning can be represented by the linguistic fuzzy rules. Since the goals of the players in the game are completely opposite, the actors for different players are simultaneously updated in opposite directions during the training. One actor is updated updated toward the direction that can minimize the Q value while the other updated toward the direction that can maximize the Q value. A pursuit-evasion problem with two pursuers and one evader is taken as an example to illustrate the validity of our method. In this problem, the two pursuers the same actor and the symmetry in the problem is used to improve the replay buffer. At the end of this paper, some confrontations between the policies with different training episodes are conducted.