Search

The minimax excess risk optimization (MERO) problem is a new variation of the traditional distributionally robust optimization (DRO) problem, which achieves uniformly low regret across all test distributions under suitable conditions. In this paper, we propose a zeroth-order stochastic mirror descent (ZO-SMD) algorithm available for both smooth and non-smooth MERO to estimate the minimal risk of each distrbution, and finally solve MERO as (non-)smooth stochastic convex-concave (linear) minimax optimization problems. The proposed algorithm is proved to converge at optimal convergence rates of $\mathcal{O}\left(1/\sqrt{t}\right)$ on the estimate of $R_i^*$ and $\mathcal{O}\left(1/\sqrt{t}\right)$ on the optimization error of both smooth and non-smooth MERO. Numerical results show the efficiency of the proposed algorithm.

Due to their importance in various emerging applications, efficient algorithms for solving minimax problems have recently received increasing attention. However, many existing algorithms require prior knowledge of the problem parameters in order to achieve optimal iteration complexity. In this paper, we propose two completely parameter-free alternating gradient projection algorithms, i.e., the PF-AGP-NSC algorithm and the PF-AGP-NC algorithm, to solve the smooth nonconvex-strongly concave and nonconvex-concave minimax problems respectively using a backtracking strategy, which does not require prior knowledge of parameters such as the Lipschtiz constant $L$ or the strongly concave constant $\mu$. Moreover, we show that the total number of gradient calls of the PF-AGP-NSC algorithm and the PF-AGP-NC algorithm to obtain an $\varepsilon$-stationary point is upper bounded by $\mathcal{O}\left( L\kappa^3\varepsilon^{-2} \right)$ and $\mathcal{O}\left( L^4\varepsilon^{-4} \right)$ respectively, where $\kappa$ is the condition number. As far as we know, the PF-AGP-NSC algorithm and the PF-AGP-NC algorithm are the first completely parameter-free algorithms for solving nonconvex-strongly concave minimax problems and nonconvex-concave minimax problems respectively. Numerical results validate the efficiency of the proposed PF-AGP algorithm.

In this paper, we study second-order algorithms for the convex-concave minimax problem, which has attracted much attention in many fields such as machine learning in recent years. We propose a Lipschitz-free cubic regularization (LF-CR) algorithm for solving the convex-concave minimax optimization problem without knowing the Lipschitz constant. It can be shown that the iteration complexity of the LF-CR algorithm to obtain an $\epsilon$-optimal solution with respect to the restricted primal-dual gap is upper bounded by $\mathcal{O}(\frac{\rho\|z^0-z^*\|^3}{\epsilon})^{\frac{2}{3}}$, where $z^0=(x^0,y^0)$ is a pair of initial points, $z^*=(x^*,y^*)$ is a pair of optimal solutions, and $\rho$ is the Lipschitz constant. We further propose a fully parameter-free cubic regularization (FF-CR) algorithm that does not require any parameters of the problem, including the Lipschitz constant and the upper bound of the distance from the initial point to the optimal solution. We also prove that the iteration complexity of the FF-CR algorithm to obtain an $\epsilon$-optimal solution with respect to the gradient norm is upper bounded by $\mathcal{O}(\frac{\rho\|z^0-z^*\|^2}{\epsilon})^{\frac{2}{3}}$. Numerical experiments show the efficiency of both algorithms. To the best of our knowledge, the proposed FF-CR algorithm is the first completely parameter-free second-order algorithm for solving convex-concave minimax optimization problems, and its iteration complexity is consistent with the optimal iteration complexity lower bound of existing second-order algorithms with parameters for solving convex-concave minimax problems.

In this paper, we propose a Minimax Trust Region (MINIMAX-TR) algorithm and a Minimax Trust Region Algorithm with Contractions and Expansions(MINIMAX-TRACE) algorithm for solving nonconvex-strongly concave minimax problems. Both algorithms can find an $(\epsilon, \sqrt{\epsilon})$-second order stationary point(SSP) within $\mathcal{O}(\epsilon^{-1.5})$ iterations, which matches the best well known iteration complexity.

Permitting the transmission of unknown quantum states over long distances by using entanglement, quantum teleportation serves as an important building block for many quantum technologies. However, in the noisy intermediate-scale quantum era, the practical realization of quantum teleportation is inevitably challenged by the noise-induced decoherence. We here propose a noise-mitigation mechanism applicable in both the discrete- and continuous-variable quantum teleportation schemes. Via investigating the non-Markovian decoherence dynamics of the two types of quantum teleportation schemes, we find that, as long as a bound state is formed in the energy spectrum of the total system consisting of the involved subsystems and their respective reservoirs, the quantum superiority of the fidelity is persistently recovered. Supplying an insightful understanding of the noise-mitigation protocols, our result paves the way to the practical realization of noise-tolerant quantum teleportation.

In this paper, we study zeroth-order algorithms for nonconvex minimax problems with coupled linear constraints under the deterministic and stochastic settings, which have attracted wide attention in machine learning, signal processing and many other fields in recent years, e.g., adversarial attacks in resource allocation problems and network flow problems etc. We propose two single-loop algorithms, namely the zero-order primal-dual alternating projected gradient (ZO-PDAPG) algorithm and the zero-order regularized momentum primal-dual projected gradient algorithm (ZO-RMPDPG), for solving deterministic and stochastic nonconvex-(strongly) concave minimax problems with coupled linear constraints. The iteration complexity of the two proposed algorithms to obtain an $\varepsilon$-stationary point are proved to be $\mathcal{O}(\varepsilon ^{-2})$ (resp. $\mathcal{O}(\varepsilon ^{-4})$) for solving nonconvex-strongly concave (resp. nonconvex-concave) minimax problems with coupled linear constraints under deterministic settings and $\tilde{\mathcal{O}}(\varepsilon ^{-3})$ (resp. $\tilde{\mathcal{O}}(\varepsilon ^{-6.5})$) under stochastic settings respectively. To the best of our knowledge, they are the first two zeroth-order algorithms with iterative complexity guarantees for solving nonconvex-(strongly) concave minimax problems with coupled linear constraints under the deterministic and stochastic settings., Comment: arXiv admin note: text overlap with arXiv:2212.04672

Stochastic nonconvex minimax problems have attracted wide attention in machine learning, signal processing and many other fields in recent years. In this paper, we propose an accelerated first-order regularized momentum descent ascent algorithm (FORMDA) for solving stochastic nonconvex-concave minimax problems. The iteration complexity of the algorithm is proved to be $\tilde{\mathcal{O}}(\varepsilon ^{-6.5})$ to obtain an $\varepsilon$-stationary point, which achieves the best-known complexity bound for single-loop algorithms to solve the stochastic nonconvex-concave minimax problems under the stationarity of the objective function.

The notion of tamed Dirichlet space was proposed by Erbar, Rigoni, Sturm and Tamanini as a Dirichlet space having a weak form of Bakry-\'Emery curvature lower bounds in distribution sense. After their work, Braun established a vector calculus for it, in particular, the space of $L^2$-normed $L^{\infty}$-module describing vector fields, $1$-forms, Hessian in $L^2$-sense. In this framework, we establish the Littlewood-Paley-Stein inequality for $1$-forms as an element of $L^p$-cotangent bundles and boundedness of Riesz transforms, which partially solves the problem raised by Kawabi-Miyokawa., Comment: 68 pages. arXiv admin note: text overlap with arXiv:2307.12514; text overlap with arXiv:2108.12374 by other authors

The notion of tamed Dirichlet space by distributional lower Ricci curvature bounds was proposed by Erbar, Rigoni, Sturm and Tamanini as the Dirichlet space having a weak form of Bakry-\'Emery curvature lower bounds in distribution sense. In this framework, we establish the Littlewood-Paley-Stein inequality for $L^p$-functions and $L^p$-boundedness of $q$-Riesz transforms with $q>1$, which partially generalizes the result by Kawabi-Miyokawa.

Groomed jet substructure measurements, the momentum splitting fraction $z_g$ and the groomed jet radius $R_g$, of inclusive, D$^0$-tagged and B$^0$-tagged jets in $pp$ and central PbPb collisions at $\sqrt{s}=5.02$ TeV are predicted and investigated. Charged jets are constrained in a relatively low transverse momentum interval 15 $\leq p_{\rm T}^{\rm jet\ ch} <$ 30 GeV/$c$ where the QCD emissions are sensitive to mass effects. In $pp$ collisions, heavy flavor jets have less momentum-balanced splittings than inclusive jets and the larger quark mass is, the less momentum-balanced splittings are. B$^0$-tagged jets distribute at lager $R_g$ than both D$^0$-tagged and inclusive jets, while D$^0$-tagged jets distribute at smaller $R_g$ than inclusive jets. That can be explained by the competition between parton mass effects and flavour effects on splitting-angle distributions. In $A$+$A$ collisions, jet quenching effects further suppress the momentum-balanced splittings and enhance the large-angle splittings. Heavy flavor jets suffer more $z_g$ and less $R_g$ modifications due to jet-medium interactions. The mass hierarchy in $z_g$ of inclusive, D$^0$-tagged, B$^0$-tagged jets and competition between mass effects and Casimir colour factors in $R_g$ can also be observed in PbPb collisions.

Nonconvex minimax problems have attracted wide attention in machine learning, signal processing and many other fields in recent years. In this paper, we propose a primal-dual alternating proximal gradient (PDAPG) algorithm for solving nonsmooth nonconvex-(strongly) concave minimax problems with coupled linear constraints, respectively. The iteration complexity of the two algorithms are proved to be $\mathcal{O}\left( \varepsilon ^{-2} \right)$ (resp. $\mathcal{O}\left( \varepsilon ^{-4} \right)$) under nonconvex-strongly concave (resp. nonconvex-concave) setting to reach an $\varepsilon$-stationary point. To our knowledge, it is the first algorithm with iteration complexity guarantees for solving the nonconvex minimax problems with coupled linear constraints.

In this paper, we consider a class of nonconvex-nonconcave minimax problems, i.e., NC-PL minimax problems, whose objective functions satisfy the Polyak-\L ojasiewicz (PL) condition with respect to the inner variable. We propose a zeroth-order alternating gradient descent ascent (ZO-AGDA) algorithm and a zeroth-order variance reduced alternating gradient descent ascent (ZO-VRAGDA) algorithm for solving NC-PL minimax problem under the deterministic and the stochastic setting, respectively. The total number of function value queries to obtain an $\epsilon$-stationary point of ZO-AGDA and ZO-VRAGDA algorithm for solving NC-PL minimax problem is upper bounded by $\mathcal{O}(\varepsilon^{-2})$ and $\mathcal{O}(\varepsilon^{-3})$, respectively. To the best of our knowledge, they are the first two zeroth-order algorithms with the iteration complexity gurantee for solving NC-PL minimax problems.

When measuring the value of a function to be minimized is not only expensive but also with noise, the popular simultaneous perturbation stochastic approximation (SPSA) algorithm requires only two function values in each iteration. In this paper, we propose a method requiring only one function measurement value per iteration in the average sense. We prove the strong convergence and asymptotic normality of the new algorithm. Experimental results show the effectiveness and potential of our algorithm., Comment: 17 pages, 3 figures

The DArk Matter Particle Explorer (DAMPE) is well suitable for searching for monochromatic and sharp $\gamma$-ray structures in the GeV$-$TeV range thanks to its unprecedented high energy resolution. In this work, we search for $\gamma$-ray line structures using five years of DAMPE data. To improve the sensitivity, we develop two types of dedicated data sets (including the BgoOnly data which is the first time to be used in the data analysis for the calorimeter-based gamma-ray observatories) and adopt the signal-to-noise ratio optimized regions of interest (ROIs) for different DM density profiles. No line signals or candidates are found between 10 and 300 GeV in the Galaxy. The constraints on the velocity-averaged cross section for $\chi\chi \to \gamma\gamma$ and the decay lifetime for $\chi \to \gamma\nu$, both at 95% confidence level, have been calculated and the systematic uncertainties have been taken into account. Comparing to the previous Fermi-LAT results, though DAMPE has an acceptance smaller by a factor of $\sim 10$, similar constraints on the DM parameters are achieved and below 100 GeV the lower limits on the decay lifetime are even stronger by a factor of a few. Our results demonstrate the potential of high-energy-resolution observations on dark matter detection., Comment: 14 pages, 8 figures. Update the content to keep up with the published version

In this paper, we study zeroth-order algorithms for nonconvex-concave minimax problems, which have attracted widely attention in machine learning, signal processing and many other fields in recent years. We propose a zeroth-order alternating randomized gradient projection (ZO-AGP) algorithm for smooth nonconvex-concave minimax problems, and its iteration complexity to obtain an $\varepsilon$-stationary point is bounded by $\mathcal{O}(\varepsilon^{-4})$, and the number of function value estimation is bounded by $\mathcal{O}(d_{x}+d_{y})$ per iteration. Moreover, we propose a zeroth-order block alternating randomized proximal gradient algorithm (ZO-BAPG) for solving block-wise nonsmooth nonconvex-concave minimax optimization problems, and the iteration complexity to obtain an $\varepsilon$-stationary point is bounded by $\mathcal{O}(\varepsilon^{-4})$ and the number of function value estimation per iteration is bounded by $\mathcal{O}(K d_{x}+d_{y})$. To the best of our knowledge, this is the first time that zeroth-order algorithms with iteration complexity gurantee are developed for solving both general smooth and block-wise nonsmooth nonconvex-concave minimax problems. Numerical results on data poisoning attack problem and distributed nonconvex sparse principal component analysis problem validate the efficiency of the proposed algorithms.

Much recent research effort has been directed to the development of efficient algorithms for solving minimax problems with theoretical convergence guarantees due to the relevance of these problems to a few emergent applications. In this paper, we propose a unified single-loop alternating gradient projection (AGP) algorithm for solving smooth nonconvex-(strongly) concave and (strongly) convex-nonconcave minimax problems. AGP employs simple gradient projection steps for updating the primal and dual variables alternatively at each iteration. We show that it can find an $\varepsilon$-stationary point of the objective function in $\mathcal{O}\left( \varepsilon ^{-2} \right)$ (resp. $\mathcal{O}\left( \varepsilon ^{-4} \right)$) iterations under nonconvex-strongly concave (resp. nonconvex-concave) setting. Moreover, its gradient complexity to obtain an $\varepsilon$-stationary point of the objective function is bounded by $\mathcal{O}\left( \varepsilon ^{-2} \right)$ (resp., $\mathcal{O}\left( \varepsilon ^{-4} \right)$) under the strongly convex-nonconcave (resp., convex-nonconcave) setting. To the best of our knowledge, this is the first time that a simple and unified single-loop algorithm is developed for solving both nonconvex-(strongly) concave and (strongly) convex-nonconcave minimax problems. Moreover, the complexity results for solving the latter (strongly) convex-nonconcave minimax problems have never been obtained before in the literature. Numerical results show the efficiency of the proposed AGP algorithm. Furthermore, we extend the AGP algorithm by presenting a block alternating proximal gradient (BAPG) algorithm for solving more general multi-block nonsmooth nonconvex-(strongly) concave and (strongly) convex-nonconcave minimax problems. We can similarly establish the gradient complexity of the proposed algorithm under these four different settings.

Scintillation light from liquid noble gas in a neutrino or dark matter experiment lies typically within the vacuum ultraviolet (VUV) region and might be strongly absorbed by surrounding materials such as light guides or photomultiplier. Tetraphenyl butadiene (TPB) is a fluorescent material and acts as a wavelength shifter (WLS) which can turn the UV light to the visible light around a peak wavelength of 425 nm, enabling the light signals to be detected easily for physics study. Compared with a traditional TPB coating method using vapor deposition, we propose an alternative technique with a spin coating procedure in order to facilitate the development of neutrino and dark matter detectors. This article introduces how to fabricate the TPB film on acrylics using the spin coating method, reports measurement of sample film thickness and roughness, shows the reemission spectrum, and quantifies the wavelength shifting efficiency (WLSE)., Comment: 8 pages, 8 figures and 4 tables

The multiple-input multiple-output (MIMO) detection problem is a fundamental problem in modern digital communications. Semidefinite relaxation (SDR) based algorithms are a popular class of approaches to solving the problem because the algorithms have a polynomial-time worst-case complexity and generally can achieve a good detection error rate performance. In spite of the existence of various different SDRs for the MIMO detection problem in the literature, very little is known about the relationship between these SDRs. This paper aims to fill this theoretical gap. In particular, this paper shows that two existing SDRs for the MIMO detection problem, which take quite different forms and are proposed by using different techniques, are equivalent. As a byproduct of the equivalence result, the tightness of one of the above two SDRs under a sufficient condition can be obtained., Comment: 5 pages, 2 figures, accepted for publication in 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2019)