Search

Discrete and mixed-variable optimization problems have appeared in several real-world applications. Most of the research on mixed-variable optimization considers a mixture of integer and continuous variables, and several integer handlings have been developed to inherit the optimization performance of the continuous optimization methods to mixed-integer optimization. In some applications, acceptable solutions are given by selecting possible points in the disjoint subspaces. This paper focuses on the optimization on sets of points and proposes an optimization method by extending the covariance matrix adaptation evolution strategy (CMA-ES), termed the CMA-ES on sets of points (CMA-ES-SoP). The CMA-ES-SoP incorporates margin correction that maintains the generation probability of neighboring points to prevent premature convergence to a specific non-optimal point, which is an effective integer-handling technique for CMA-ES. In addition, because margin correction with a fixed margin value tends to increase the marginal probabilities for a portion of neighboring points more than necessary, the CMA-ES-SoP updates the target margin value adaptively to make the average of the marginal probabilities close to a predefined target probability. Numerical simulations demonstrated that the CMA-ES-SoP successfully optimized the optimization problems on sets of points, whereas the naive CMA-ES failed to optimize them due to premature convergence., Comment: This paper has been accepted for presentation at PPSN2024

This paper is devoted to the mathematical analysis of a system of pseudo-parabolic partial differential equations governed by an energy functional, associated with anisotropic monochrome image processing. The energy functional is based on the one proposed by [Berkels et al. Cartoon extraction based on anisotropic image classification, SFB 611, 2006], which incorporates an orientation auto-adjustment mechanism, and our energy is a simplified version which reduces the order of derivatives to improve computational efficiency. The aim of this paper is to establish a stable minimization process that addresses some instability of the algorithm caused by the reduction of derivative order. As a part of the study, we here prove Main Theorems concerned with the well-posedness of the pseudo-parabolic system, and provide a mathematically rigorous guarantee for the stability of the image denoising process derived from our system., Comment: 26 pages

The majority of theoretical analyses of evolutionary algorithms in the discrete domain focus on binary optimization algorithms, even though black-box optimization on the categorical domain has a lot of practical applications. In this paper, we consider a probabilistic model-based algorithm using the family of categorical distributions as its underlying distribution and set the sample size as two. We term this specific algorithm the categorical compact genetic algorithm (ccGA). The ccGA can be considered as an extension of the compact genetic algorithm (cGA), which is an efficient binary optimization algorithm. We theoretically analyze the dependency of the number of possible categories $K$, the number of dimensions $D$, and the learning rate $\eta$ on the runtime. We investigate the tail bound of the runtime on two typical linear functions on the categorical domain: categorical OneMax (COM) and KVal. We derive that the runtimes on COM and KVal are $O(\sqrt{D} \ln (DK) / \eta)$ and $\Theta(D \ln K/ \eta)$ with high probability, respectively. Our analysis is a generalization for that of the cGA on the binary domain.

The covariance matrix adaptation evolution strategy (CMA-ES) is a stochastic search algorithm using a multivariate normal distribution for continuous black-box optimization. In addition to strong empirical results, part of the CMA-ES can be described by a stochastic natural gradient method and can be derived from information geometric optimization (IGO) framework. However, there are some components of the CMA-ES, such as the rank-one update, for which the theoretical understanding is limited. While the rank-one update makes the covariance matrix to increase the likelihood of generating a solution in the direction of the evolution path, this idea has been difficult to formulate and interpret as a natural gradient method unlike the rank-$\mu$ update. In this work, we provide a new interpretation of the rank-one update in the CMA-ES from the perspective of the natural gradient with prior distribution. First, we propose maximum a posteriori IGO (MAP-IGO), which is the IGO framework extended to incorporate a prior distribution. Then, we derive the rank-one update from the MAP-IGO by setting the prior distribution based on the idea that the promising mean vector should exist in the direction of the evolution path. Moreover, the newly derived rank-one update is extensible, where an additional term appears in the update for the mean vector. We empirically investigate the properties of the additional term using various benchmark functions., Comment: This paper has been accepted for presentation at PPSN2024. Updated experimental results and related sentences in Sections 6 and 7

The covariance matrix adaptation evolution strategy (CMA-ES) is a powerful optimization method for continuous black-box optimization problems. Several noise-handling methods have been proposed to bring out the optimization performance of the CMA-ES on noisy objective functions. The adaptations of the population size and the learning rate are two major approaches that perform well under additive Gaussian noise. The reevaluation technique is another technique that evaluates each solution multiple times. In this paper, we discuss the difference between those methods from the perspective of stochastic relaxation that considers the maximization of the expected utility function. We derive that the set of maximizers of the noise-independent utility, which is used in the reevaluation technique, certainly contains the optimal solution, while the noise-dependent utility, which is used in the population size and leaning rate adaptations, does not satisfy it under multiplicative noise. Based on the discussion, we develop the reevaluation adaptation CMA-ES (RA-CMA-ES), which computes two update directions using half of the evaluations and adapts the number of reevaluations based on the estimated correlation of those two update directions. The numerical simulation shows that the RA-CMA-ES outperforms the comparative method under multiplicative noise, maintaining competitive performance under additive noise., Comment: This paper has been accepted as a full paper at GECCO2024

In several real-world applications in medical and control engineering, there are unsafe solutions whose evaluations involve inherent risk. This optimization setting is known as safe optimization and formulated as a specialized type of constrained optimization problem with constraints for safety functions. Safe optimization requires performing efficient optimization without evaluating unsafe solutions. A few studies have proposed the optimization methods for safe optimization based on Bayesian optimization and the evolutionary algorithm. However, Bayesian optimization-based methods often struggle to achieve superior solutions, and the evolutionary algorithm-based method fails to effectively reduce unsafe evaluations. This study focuses on CMA-ES as an efficient evolutionary algorithm and proposes an optimization method termed safe CMA-ES. The safe CMA-ES is designed to achieve both safety and efficiency in safe optimization. The safe CMA-ES estimates the Lipschitz constants of safety functions transformed with the distribution parameters using the maximum norm of the gradient in Gaussian process regression. Subsequently, the safe CMA-ES projects the samples to the nearest point in the safe region constructed with the estimated Lipschitz constants. The numerical simulation using the benchmark functions shows that the safe CMA-ES successfully performs optimization, suppressing the unsafe evaluations, while the existing methods struggle to significantly reduce the unsafe evaluations., Comment: This paper has been accepted as a full paper at GECCO2024

Advances in brain decoding, particularly visual image reconstruction, have sparked discussions about the societal implications and ethical considerations of neurotechnology. As these methods aim to recover visual experiences from brain activity and achieve prediction beyond training samples (zero-shot prediction), it is crucial to assess their capabilities and limitations to inform public expectations and regulations. Our case study of recent text-guided reconstruction methods, which leverage a large-scale dataset (Natural Scene Dataset, NSD) and text-to-image diffusion models, reveals limitations in their generalizability. We found poor performance when applying these methods to a different dataset designed to prevent category overlaps between training and test sets. UMAP visualization of the text features with NSD images showed a limited diversity of semantic and visual clusters, with overlap between training and test sets. Formal analysis and simulations demonstrated that clustered training samples can lead to "output dimension collapse," restricting predictable output feature dimensions. Simulations further showed that diversifying the training set improved generalizability. However, text features alone are insufficient for mapping to the visual space. We argue that recent realistic reconstructions may primarily be a blend of classification into trained categories and generation of inauthentic images through text-to-image diffusion (hallucination). Diverse datasets and compositional representations spanning the image space are essential for genuine zero-shot prediction. Interdisciplinary discussions grounded in understanding the current capabilities and limitations, as well as ethical considerations, of the technology are crucial for its responsible development.

Black-box optimization problems often require simultaneously optimizing different types of variables, such as continuous, integer, and categorical variables. Unlike integer variables, categorical variables do not necessarily have a meaningful order, and the discretization approach of continuous variables does not work well. Although several Bayesian optimization methods can deal with mixed-category black-box optimization (MC-BBO), they suffer from a lack of scalability to high-dimensional problems and internal computational cost. This paper proposes CatCMA, a stochastic optimization method for MC-BBO problems, which employs the joint probability distribution of multivariate Gaussian and categorical distributions as the search distribution. CatCMA updates the parameters of the joint probability distribution in the natural gradient direction. CatCMA also incorporates the acceleration techniques used in the covariance matrix adaptation evolution strategy (CMA-ES) and the stochastic natural gradient method, such as step-size adaptation and learning rate adaptation. In addition, we restrict the ranges of the categorical distribution parameters by margin to prevent premature convergence and analytically derive a promising margin setting. Numerical experiments show that the performance of CatCMA is superior and more robust to problem dimensions compared to state-of-the-art Bayesian optimization algorithms., Comment: This paper has been accepted for presentation at GECCO2024. We have modified the equations in Table 1

A universal quantum computer can be used as a simulator capable of predicting properties of diverse quantum systems. Electronic structure problems in chemistry offer practical use cases around the hundred-qubit mark. This appears promising since current quantum processors have reached these sizes. However, mapping these use cases onto quantum computers yields deep circuits, and for for pre-fault-tolerant quantum processors, the large number of measurements to estimate molecular energies leads to prohibitive runtimes. As a result, realistic chemistry is out of reach of current quantum computers in isolation. A natural question is whether classical distributed computation can relieve quantum processors from parsing all but a core, intrinsically quantum component of a chemistry workflow. Here, we incorporate quantum computations of chemistry in a quantum-centric supercomputing architecture, using up to 6400 nodes of the supercomputer Fugaku to assist a Heron superconducting quantum processor. We simulate the N$_2$ triple bond breaking in a correlation-consistent cc-pVDZ basis set, and the active-space electronic structure of [2Fe-2S] and [4Fe-4S] clusters, using 58, 45 and 77 qubits respectively, with quantum circuits of up to 10570 (3590 2-qubit) quantum gates. We obtain our results using a class of quantum circuits that approximates molecular eigenstates, and a hybrid estimator. The estimator processes quantum samples, produces upper bounds to the ground-state energy and wavefunctions supported on a polynomial number of states. This guarantees an unconditional quality metric for quantum advantage, certifiable by classical computers at polynomial cost. For current error rates, our results show that classical distributed computing coupled to quantum processors can produce good approximate solutions for practical problems beyond sizes amenable to exact diagonalization.

We propose Test-Time Augmentation (TTA) as an effective technique for addressing combinatorial optimization problems, including the Traveling Salesperson Problem. In general, deep learning models possessing the property of invariance, where the output is uniquely determined regardless of the node indices, have been proposed to learn graph structures efficiently. In contrast, we interpret the permutation of node indices, which exchanges the elements of the distance matrix, as a TTA scheme. The results demonstrate that our method is capable of obtaining shorter solutions than the latest models. Furthermore, we show that the probability of finding a solution closer to an exact solution increases depending on the augmentation size.

We propose Deep Longitudinal Targeted Minimum Loss-based Estimation (Deep LTMLE), a novel approach to estimate the counterfactual mean of outcome under dynamic treatment policies in longitudinal problem settings. Our approach utilizes a transformer architecture with heterogeneous type embedding trained using temporal-difference learning. After obtaining an initial estimate using the transformer, following the targeted minimum loss-based likelihood estimation (TMLE) framework, we statistically corrected for the bias commonly associated with machine learning algorithms. Furthermore, our method also facilitates statistical inference by enabling the provision of 95% confidence intervals grounded in asymptotic statistical theory. Simulation results demonstrate our method's superior performance over existing approaches, particularly in complex, long time-horizon scenarios. It remains effective in small-sample, short-duration contexts, matching the performance of asymptotically efficient estimators. To demonstrate our method in practice, we applied our method to estimate counterfactual mean outcomes for standard versus intensive blood pressure management strategies in a real-world cardiovascular epidemiology cohort study.

In periodically driven (Floquet) systems, evolution typically results in an infinite-temperature thermal state due to continuous energy absorption over time. However, before reaching thermal equilibrium, such systems may transiently pass through a meta-stable state known as a prethermal state. This prethermal state can exhibit phenomena not commonly observed in equilibrium, such as discrete time crystals (DTCs), making it an intriguing platform for exploring out-of-equilibrium dynamics. Here, we investigate the relaxation dynamics of initially prepared product states under periodic driving in a kicked Ising model using the IBM Quantum Heron processor, comprising 133 superconducting qubits arranged on a heavy-hexagonal lattice, over up to $100$ time steps. We identify the presence of a prethermal regime characterised by magnetisation measurements oscillating at twice the period of the Floquet cycle and demonstrate its robustness against perturbations to the transverse field. Our results provide evidence supporting the realisation of a period-doubling DTC in a two-dimensional system. Moreover, we discover that the longitudinal field induces additional amplitude modulations in the magnetisation with a period incommensurate with the driving period, leading to the emergence of discrete time quasicrystals (DTQCs). These observations are further validated through comparison with tensor-network and state-vector simulations. Our findings not only enhance our understanding of clean DTCs in two dimensions but also highlight the utility of digital quantum computers for simulating the dynamics of quantum many-body systems, addressing challenges faced by state-of-the-art classical simulations., Comment: 8 pages, 4 figures + Supplemental Material (17 pages, 20 figures)

Layout-aware text-to-image generation is a task to generate multi-object images that reflect layout conditions in addition to text conditions. The current layout-aware text-to-image diffusion models still have several issues, including mismatches between the text and layout conditions and quality degradation of generated images. This paper proposes a novel layout-aware text-to-image diffusion model called NoiseCollage to tackle these issues. During the denoising process, NoiseCollage independently estimates noises for individual objects and then crops and merges them into a single noise. This operation helps avoid condition mismatches; in other words, it can put the right objects in the right places. Qualitative and quantitative evaluations show that NoiseCollage outperforms several state-of-the-art models. These successful results indicate that the crop-and-merge operation of noises is a reasonable strategy to control image generation. We also show that NoiseCollage can be integrated with ControlNet to use edges, sketches, and pose skeletons as additional conditions. Experimental results show that this integration boosts the layout accuracy of ControlNet. The code is available at https://github.com/univ-esuty/noisecollage., Comment: Accepted at CVPR 2024

The original KWC-system is widely used in materials science. It was proposed in [Kobayashi et al, Physica D, 140, 141--150 (2000)] and is based on the phase field model of planar grain boundary motion. This model suffers from two key challenges. Firstly, it is difficult to establish its relation to physics, in particular, a variational model. Secondly, it lacks uniqueness. The former has been recently studied within the realm of BV-theory. The latter only holds under various simplifications. This article introduces a pseudo-parabolic version of the KWC-system. A direct relationship with variational model (as gradient-flow) and uniqueness are established without making any unrealistic simplifications. Namely, this is the first KWC-system which is both physically and mathematically valid. The proposed model overcomes the well-known open issues., Comment: 24 pages

Towards the efficient simulation of near-term quantum devices using tensor network states, we introduce an improved real-space parallelizable matrix-product state (MPS) compression method. This method enables efficient compression of all virtual bonds in constant time, irrespective of the system size, with controlled accuracy, while it maintains the stability of the wavefunction norm without necessitating sequential renormalization procedures. In addition, we introduce a parallel regauging technique to partially restore the deviated canonical form, thereby improving the accuracy of the simulation in subsequent steps. We further apply this method to simulate unitary quantum dynamics and introduce an improved parallel time-evolving block-decimation (pTEBD) algorithm. We employ the improved pTEBD algorithm for extensive simulations of typical one- and two-dimensional quantum circuits, involving over 1000 qubits. The obtained numerical results unequivocally demonstrate that the improved pTEBD algorithm achieves the same level of simulation precision as the current state-of-the-art MPS algorithm but in polynomially shorter time, exhibiting nearly perfect weak scaling performance on a modern supercomputer., Comment: 21 pages, 13 figures

In recent years, quantum computing has evolved as an exciting frontier, with the development of numerous algorithms dedicated to constructing quantum circuits that adeptly represent quantum many-body states. However, this domain remains in its early stages and requires further refinement to understand better the effective construction of highly-entangled quantum states within quantum circuits. Here, we demonstrate that quantum many-body states can be universally represented using a quantum circuit comprising multi-qubit gates. Furthermore, we evaluate the efficiency of a quantum circuit constructed with two-qubit gates in quench dynamics for the transverse-field Ising model. In this specific model, despite the initial state being classical without entanglement, it undergoes long-time evolution, eventually leading to a highly-entangled quantum state. Our results reveal that a diamond-shaped quantum circuit, designed to approximate the multi-qubit gate-based quantum circuit, remarkably excels in accurately representing the long-time dynamics of the system. Moreover, the diamond-shaped circuit follows the volume law behavior in entanglement entropy, offering a significant advantage over alternative quantum circuit constructions employing two-qubit gates., Comment: 15 pages, 13 figures

In this article, we propose a new paradigm for training spiking neural networks (SNNs), spike accumulation forwarding (SAF). It is known that SNNs are energy-efficient but difficult to train. Consequently, many researchers have proposed various methods to solve this problem, among which online training through time (OTTT) is a method that allows inferring at each time step while suppressing the memory cost. However, to compute efficiently on GPUs, OTTT requires operations with spike trains and weighted summation of spike trains during forwarding. In addition, OTTT has shown a relationship with the Spike Representation, an alternative training method, though theoretical agreement with Spike Representation has yet to be proven. Our proposed method can solve these problems; namely, SAF can halve the number of operations during the forward process, and it can be theoretically proven that SAF is consistent with the Spike Representation and OTTT, respectively. Furthermore, we confirmed the above contents through experiments and showed that it is possible to reduce memory and training time while maintaining accuracy., Comment: 14 pages, 5 figures, Appendix:10 pages, 2 figures, v6:Published in Transactions on Machine Learning Research

In this paper, we consider a class of initial-boundary value problems governed by pseudo-parabolic total variation flows. The principal characteristic of our problem lies in the velocity term of the diffusion flux, a feature that can bring about stronger regularity than what is found in standard parabolic PDEs. Meanwhile, our total variation flow contains singular diffusion, and this singularity may lead to a degeneration of the regularity of solution. The objective of this paper is to clarify the power balance between these conflicting effects. Consequently, we will present mathematical results concerning the well-posedness and regularity of the solution in the Main Theorems of this paper., Comment: 31 pages

In this paper, we consider a coupled system, known as Kobayashi--Warren--Carter system, abbreviated as the KWC system. KWC system consists of an Allen--Cahn type equation and a singular diffusion equation, and it was proposed by [Kobayashi et al, Phys. D, 140, 141--150 (2000)] as a possible mathematical model of grain boundary motion. The focus of this work is on the dynamic boundary condition imposed in our KWC system, and the mathematical interest is in a conflicting situation between: the continuity of the transmission condition included in the dynamic boundary condition; and the discontinuity encouraged by the singular diffusion equation. On this basis, we will prove the Main Theorem concerned with the existence of solution to our KWC system with energy-dissipation. Additionally, as a sub-result, we will prove a key-lemma that is to give a certain mathematical interpretation for the conflicting situation., Comment: 43 pages

Ambigrams are graphical letter designs that can be read not only from the original direction but also from a rotated direction (especially with 180 degrees). Designing ambigrams is difficult even for human experts because keeping their dual readability from both directions is often difficult. This paper proposes an ambigram generation model. As its generation module, we use a diffusion model, which has recently been used to generate high-quality photographic images. By specifying a pair of letter classes, such as 'A' and 'B', the proposed model generates various ambigram images which can be read as 'A' from the original direction and 'B' from a direction rotated 180 degrees. Quantitative and qualitative analyses of experimental results show that the proposed model can generate high-quality and diverse ambigrams. In addition, we define ambigramability, an objective measure of how easy it is to generate ambigrams for each letter pair. For example, the pair of 'A' and 'V' shows a high ambigramability (that is, it is easy to generate their ambigrams), and the pair of 'D' and 'K' shows a lower ambigramability. The ambigramability gives various hints of the ambigram generation not only for computers but also for human experts. The code can be found at (https://github.com/univ-esuty/ambifusion)., Comment: Accepted at ICDAR 2023

The covariance matrix adaptation evolution strategy (CMA-ES) is an efficient continuous black-box optimization method. The CMA-ES possesses many attractive features, including invariance properties and a well-tuned default hyperparameter setting. Moreover, several components to specialize the CMA-ES have been proposed, such as noise handling and constraint handling. To utilize these advantages in mixed-integer optimization problems, the CMA-ES with margin has been proposed. The CMA-ES with margin prevents the premature convergence of discrete variables by the margin correction, in which the distribution parameters are modified to leave the generation probability for changing the discrete variable. The margin correction has been applied to ($\mu/\mu_\mathrm{w}$,$\lambda$)-CMA-ES, while this paper introduces the margin correction into (1+1)-CMA-ES, an elitist version of CMA-ES. The (1+1)-CMA-ES is often advantageous for unimodal functions and can be computationally less expensive. To tackle the performance deterioration on mixed-integer optimization, we use the discretized elitist solution as the mean of the sampling distribution and modify the margin correction not to move the elitist solution. The numerical simulation using benchmark functions on mixed-integer, integer, and binary domains shows that (1+1)-CMA-ES with margin outperforms the CMA-ES with margin and is better than or comparable with several specialized methods to a particular search domain.

In real-world applications, a machine learning model is required to handle an open-set recognition (OSR), where unknown classes appear during the inference, in addition to a domain shift, where the distribution of data differs between the training and inference phases. Domain generalization (DG) aims to handle the domain shift situation where the target domain of the inference phase is inaccessible during model training. Open domain generalization (ODG) takes into account both DG and OSR. Domain-Augmented Meta-Learning (DAML) is a method targeting ODG but has a complicated learning process. On the other hand, although various DG methods have been proposed, they have not been evaluated in ODG situations. This work comprehensively evaluates existing DG methods in ODG and shows that two simple DG methods, CORrelation ALignment (CORAL) and Maximum Mean Discrepancy (MMD), are competitive with DAML in several cases. In addition, we propose simple extensions of CORAL and MMD by introducing the techniques used in DAML, such as ensemble learning and Dirichlet mixup data augmentation. The experimental evaluation demonstrates that the extended CORAL and MMD can perform comparably to DAML with lower computational costs. This suggests that the simple DG methods and their simple extensions are strong baselines for ODG. The code used in the experiments is available at https://github.com/shiralab/OpenDG-Eval., Comment: 18 pages, 5 figures

We propose an efficient circuit structure of variational quantum circuit \textit{Ans\"{a}tze} used for the variational quantum eigensolver (VQE) algorithm in calculating gapped topological phases on the currently feasible noisy intermediate-scale quantum computers. An efficient circuit \textit{Ansatz} should include two layers: the initialization layer and the variational layer. In the initialization layer, a fixed depth circuit state with a compatible entanglement structure to the target topological phase is constructed. The circuit state is further adjusted subsequently to capture the details of the local correlations, which is dictated with the Hamiltonian, in the parametrized variational layer. Based on this strategy, we design a circuit \textit{Ansatz} to investigate the symmetry-protected topological Haldane phase in a \textit{non-exactly} solvable alternating spin-$1/2$ Heisenberg chain by VQE calculations. Main characterizations of the Haldane phase, including the long-ranged string order, the four-fold nearly degenerate ground states associated with four different localized edge mode patterns for the system with open boundaries, and the two-fold degeneracy of the entanglement spectrum, are all observed for the optimized shallow circuit state with only one depth variational layer both in numerical simulations and on real quantum computers. We further demonstrate that the computational capacity (i.e., expressibility) of this quantum circuit \textit{Ansatz} is determined not by the system size but only by the intrinsic correlation length of the system, thus implying that the scalable VQE calculation is possible., Comment: 16 pages, 17 figures

In this paper, a system of parabolic PDEs, called the Kobayashi--Warren--Carter system, is considered as a possible phase-field model of planar grain boundary motion. The Main Theorem is concerned with the existence of a time-periodic solution to the Kobayashi--Warren--Carter system, and the principal objective is to provide a proof without the use of a compromised assumption, which researchers have been forced to adopt in recent studies.