We introduce a lower bounding technique for the min max correlation clustering problem and, based on this technique, a combinatorial 4-approximation algorithm for complete graphs. This improves upon the previous best known approximation guarantees of 5, using a linear program formulation (Kalhan et al., 2019), and 4, for a combinatorial algorithm (Davies et al., 2023). We extend this algorithm by a greedy joining heuristic and show empirically that it improves the state of the art in solution quality and runtime on several benchmark datasets.
相關內容
We propose a new randomized method for solving systems of nonlinear equations, which can find sparse solutions or solutions under certain simple constraints. The scheme only takes gradients of component functions and uses Bregman projections onto the solution space of a Newton equation. In the special case of euclidean projections, the method is known as nonlinear Kaczmarz method. Furthermore, if the component functions are nonnegative, we are in the setting of optimization under the interpolation assumption and the method reduces to SGD with the recently proposed stochastic Polyak step size. For general Bregman projections, our method is a stochastic mirror descent with a novel adaptive step size. We prove that in the convex setting each iteration of our method results in a smaller Bregman distance to exact solutions as compared to the standard Polyak step. Our generalization to Bregman projections comes with the price that a convex one-dimensional optimization problem needs to be solved in each iteration. This can typically be done with globalized Newton iterations. Convergence is proved in two classical settings of nonlinearity: for convex nonnegative functions and locally for functions which fulfill the tangential cone condition. Finally, we show examples in which the proposed method outperforms similar methods with the same memory requirements.
In many practical control applications, the performance level of a closed-loop system degrades over time due to the change of plant characteristics. Thus, there is a strong need for redesigning a controller without going through the system modeling process, which is often difficult for closed-loop systems. Reinforcement learning (RL) is one of the promising approaches that enable model-free redesign of optimal controllers for nonlinear dynamical systems based only on the measurement of the closed-loop system. However, the learning process of RL usually requires a considerable number of trial-and-error experiments using the poorly controlled system that may accumulate wear on the plant. To overcome this limitation, we propose a model-free two-step design approach that improves the transient learning performance of RL in an optimal regulator redesign problem for unknown nonlinear systems. Specifically, we first design a linear control law that attains some degree of control performance in a model-free manner, and then, train the nonlinear optimal control law with online RL by using the designed linear control law in parallel. We introduce an offline RL algorithm for the design of the linear control law and theoretically guarantee its convergence to the LQR controller under mild assumptions. Numerical simulations show that the proposed approach improves the transient learning performance and efficiency in hyperparameter tuning of RL.
Recently, Eldan, Koehler, and Zeitouni (2020) showed that Glauber dynamics mixes rapidly for general Ising models so long as the difference between the largest and smallest eigenvalues of the coupling matrix is at most $1 - \epsilon$ for any fixed $\epsilon > 0$. We give evidence that Glauber dynamics is in fact optimal for this "general-purpose sampling" task. Namely, we give an average-case reduction from hypothesis testing in a Wishart negatively-spiked matrix model to approximately sampling from the Gibbs measure of a general Ising model for which the difference between the largest and smallest eigenvalues of the coupling matrix is at most $1 + \epsilon$ for any fixed $\epsilon > 0$. Combined with results of Bandeira, Kunisky, and Wein (2019) that analyze low-degree polynomial algorithms to give evidence for the hardness of the former spiked matrix problem, our results in turn give evidence for the hardness of general-purpose sampling improving on Glauber dynamics. We also give a similar reduction to approximating the free energy of general Ising models, and again infer evidence that simulated annealing algorithms based on Glauber dynamics are optimal in the general-purpose setting.
We study the numerical approximation of multidimensional stochastic differential equations (SDEs) with distributional drift, driven by a fractional Brownian motion. We work under the Catellier-Gubinelli condition for strong well-posedness, which assumes that the regularity of the drift is strictly greater than $1-1/(2H)$, where $H$ is the Hurst parameter of the noise. The focus here is on the case $H<1/2$, allowing the drift $b$ to be a distribution. We compare the solution $X$ of the SDE with drift $b$ and its tamed Euler scheme with mollified drift $b^n$, to obtain an explicit rate of convergence for the strong error. This extends previous results where $b$ was assumed to be a bounded measurable function. In addition, we investigate the limit case when the regularity of the drift is equal to $1-1/(2H)$, and obtain a non-explicit rate of convergence. As a byproduct of this convergence, there exists a strong solution that is pathwise unique in a class of H\"older continuous solutions. The proofs rely on stochastic sewing techniques, especially to deduce new regularising properties of the discrete-time fractional Brownian motion. In the limit case, we introduce a critical Gr\"onwall-type lemma to quantify the error. We also present several examples and numerical simulations that illustrate our results.
We prove closed-form equations for the exact high-dimensional asymptotics of a family of first order gradient-based methods, learning an estimator (e.g. M-estimator, shallow neural network, ...) from observations on Gaussian data with empirical risk minimization. This includes widely used algorithms such as stochastic gradient descent (SGD) or Nesterov acceleration. The obtained equations match those resulting from the discretization of dynamical mean-field theory (DMFT) equations from statistical physics when applied to gradient flow. Our proof method allows us to give an explicit description of how memory kernels build up in the effective dynamics, and to include non-separable update functions, allowing datasets with non-identity covariance matrices. Finally, we provide numerical implementations of the equations for SGD with generic extensive batch-size and with constant learning rates.
Many generalised distributions exist for modelling data with vastly diverse characteristics. However, very few of these generalisations of the normal distribution have shape parameters with clear roles that determine, for instance, skewness and tail shape. In this chapter, we review existing skewing mechanisms and their properties in detail. Using the knowledge acquired, we add a skewness parameter to the body-tail generalised normal distribution \cite{BTGN}, that yields the \ac{FIN} with parameters for location, scale, body-shape, skewness, and tail weight. Basic statistical properties of the \ac{FIN} are provided, such as the \ac{PDF}, cumulative distribution function, moments, and likelihood equations. Additionally, the \ac{FIN} \ac{PDF} is extended to a multivariate setting using a student t-copula, yielding the \ac{MFIN}. The \ac{MFIN} is applied to stock returns data, where it outperforms the t-copula multivariate generalised hyperbolic, Azzalini skew-t, hyperbolic, and normal inverse Gaussian distributions.
In this paper, we introduce the quantum adaptive distribution search (QuADS), a quantum continuous optimization algorithm that integrates Grover adaptive search (GAS) with the covariance matrix adaptation - evolution strategy (CMA-ES), a classical technique for continuous optimization. QuADS utilizes the quantum-based search capabilities of GAS and enhances them with the principles of CMA-ES for more efficient optimization. It employs a multivariate normal distribution for the initial state of the quantum search and repeatedly updates it throughout the optimization process. Our numerical experiments show that QuADS outperforms both GAS and CMA-ES. This is achieved through adaptive refinement of the initial state distribution rather than consistently using a uniform state, resulting in fewer oracle calls. This study presents an important step toward exploiting the potential of quantum computing for continuous optimization.
Mean-field molecular dynamics based on path integrals is used to approximate canonical quantum observables for particle systems consisting of nuclei and electrons. A computational bottleneck is the sampling from the Gibbs density of the electron operator, which due to the fermion sign problem has a computational complexity that scales exponentially with the number of electrons. In this work we construct an algorithm that approximates the mean-field Hamiltonian by path integrals for fermions. The algorithm is based on the determinant of a matrix with components based on Brownian bridges connecting permuted electron coordinates. The computational work for $n$ electrons is $\mathcal O(n^3)$, which reduces the computational complexity associated with the fermion sign problem. We analyze a bias resulting from this approximation and provide a computational error indicator. It remains to rigorously explain the surprisingly high accuracy.
We study the optimal sample complexity of neighbourhood selection in linear structural equation models, and compare this to best subset selection (BSS) for linear models under general design. We show by example that -- even when the structure is \emph{unknown} -- the existence of underlying structure can reduce the sample complexity of neighbourhood selection. This result is complicated by the possibility of path cancellation, which we study in detail, and show that improvements are still possible in the presence of path cancellation. Finally, we support these theoretical observations with experiments. The proof introduces a modified BSS estimator, called klBSS, and compares its performance to BSS. The analysis of klBSS may also be of independent interest since it applies to arbitrary structured models, not necessarily those induced by a structural equation model. Our results have implications for structure learning in graphical models, which often relies on neighbourhood selection as a subroutine.
This study evaluates four fracture simulation methods, comparing their computational expenses and implementation complexities within the Finite Element (FE) framework when employed on multiphase materials. Fracture methods considered encompass the Cohesive Zone Model (CZM) using zero-thickness cohesive interface elements (CIEs), the Standard Phase-Field Fracture (SPFM) approach, the Cohesive Phase-Field fracture (CPFM) approach, and an innovative hybrid model. The hybrid approach combines the CPFM fracture method with the CZM, specifically applying the CZM within the interface zone. The finite element model studied is characterized by three specific phases: Inclusions, matrix, and interface zone. The thorough assessment of these modeling techniques indicates that the CPFM approach stands out as the most effective computational model provided that the thickness of the interface zone is not significantly smaller than that of the other phases. In materials like concrete the interface thickness is notably small when compared to other phases. This leads to the hybrid model standing as the most authentic finite element model, utilizing CIEs within the interface to simulate interface debonding. A significant finding from this investigation is that the CPFM method is in agreement with the hybrid model when the interface zone thickness is not excessively small. This implies that the CPFM fracture methodology may serve as a unified fracture approach for multiphase materials, provided the interface zone's thickness is comparable to that of the other phases. In addition, this research provides valuable insights that can advance efforts to fine-tune material microstructures. An investigation of the influence of the interface material properties, morphological features and spatial arrangement of inclusions showes a pronounced effect of these parameters on the fracture toughness of the material.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191