Currently, the best known tradeoff between approximation ratio and complexity for the Sparsest Cut problem is achieved by the algorithm in [Sherman, FOCS 2009]: it computes $O(\sqrt{(\log n)/\varepsilon})$-approximation using $O(n^\varepsilon\log^{O(1)}n)$ maxflows for any $\varepsilon\in[\Theta(1/\log n),\Theta(1)]$. It works by solving the SDP relaxation of [Arora-Rao-Vazirani, STOC 2004] using the Multiplicative Weights Update algorithm (MW) of [Arora-Kale, JACM 2016]. To implement one MW step, Sherman approximately solves a multicommodity flow problem using another application of MW. Nested MW steps are solved via a certain ``chaining'' algorithm that combines results of multiple calls to the maxflow algorithm. We present an alternative approach that avoids solving the multicommodity flow problem and instead computes ``violating paths''. This simplifies Sherman's algorithm by removing a need for a nested application of MW, and also allows parallelization: we show how to compute $O(\sqrt{(\log n)/\varepsilon})$-approximation via $O(\log^{O(1)}n)$ maxflows using $O(n^\varepsilon)$ processors. We also revisit Sherman's chaining algorithm, and present a simpler version together with a new analysis.
相關內容
Prior work has explicated the coloniality of artificial intelligence (AI) development and deployment through mechanisms such as extractivism, automation, sociological essentialism, surveillance, and containment. However, that work has not engaged much with alignment: teaching behaviors to a large language model (LLM) in line with desired values, and has not considered a mechanism that arises within that process: moral absolutism -- a part of the coloniality of knowledge. Colonialism has a history of altering the beliefs and values of colonized peoples; in this paper, I argue that this history is recapitulated in current LLM alignment practices and technologies. Furthermore, I suggest that AI alignment be decolonialized using three forms of openness: openness of models, openness to society, and openness to excluded knowledges. This suggested approach to decolonial AI alignment uses ideas from the argumentative moral philosophical tradition of Hinduism, which has been described as an open-source religion. One concept used is vi\'{s}e\d{s}a-dharma, or particular context-specific notions of right and wrong. At the end of the paper, I provide a suggested reference architecture to work toward the proposed framework.
In this study, we consider a class of linear matroid interdiction problems, where the feasible sets for the upper-level decision-maker (referred to as the leader) and the lower-level decision-maker (referred to as the follower) are given by partition matroids with a common ground set. In contrast to classical network interdiction models where the leader is subject to a single budget constraint, in our setting, both the leader and the follower are subject to several independent cardinality constraints and engage in a zero-sum game. While a single-level linear integer programming problem over a partition matroid is known to be polynomially solvable, we prove that the considered bilevel problem is NP-hard, even when the objective function coefficients are all binary. On a positive note, it turns out that, if the number of cardinality constraints is fixed for either the leader or the follower, then the considered class of bilevel problems admits several polynomial-time solution schemes. Specifically, these schemes are based on a single-level dual reformulation, a dynamic programming-based approach, and a 2-flip local search algorithm for the leader.
In this paper we investigate the existence, uniqueness and approximation of solutions of delay differential equations (DDEs) with the right-hand side functions $f=f(t,x,z)$ that are Lipschitz continuous with respect to $x$ but only H\"older continuous with respect to $(t,z)$. We give a construction of the randomized two-stage Runge-Kutta scheme for DDEs and investigate its upper error bound in the $L^p(\Omega)$-norm for $p\in [2,+\infty)$. Finally, we report on results of numerical experiments.
We present the new Orthogonal Polynomials Approximation Algorithm (OPAA), a parallelizable algorithm that estimates probability distributions using functional analytic approach: first, it finds a smooth functional estimate of the probability distribution, whether it is normalized or not; second, the algorithm provides an estimate of the normalizing weight; and third, the algorithm proposes a new computation scheme to compute such estimates. A core component of OPAA is a special transform of the square root of the joint distribution into a special functional space of our construct. Through this transform, the evidence is equated with the $L^2$ norm of the transformed function, squared. Hence, the evidence can be estimated by the sum of squares of the transform coefficients. Computations can be parallelized and completed in one pass. OPAA can be applied broadly to the estimation of probability density functions. In Bayesian problems, it can be applied to estimating the normalizing weight of the posterior, which is also known as the evidence, serving as an alternative to existing optimization-based methods.
In this paper, we formulate and analyse a geometric low-regularity integrator for solving the nonlinear Klein-Gordon equation in the $d$-dimensional space with $d=1,2,3$. The integrator is constructed based on the two-step trigonometric method and thus it has a simple form. Error estimates are rigorously presented to show that the integrator can achieve second-order time accuracy in the energy space under the regularity requirement in $H^{1+\frac{d}{4}}\times H^{\frac{d}{4}}$. Moreover, the time symmetry of the scheme ensures its good long-time energy conservation which is rigorously proved by the technique of modulated Fourier expansions. A numerical test is presented and the numerical results demonstrate the superiorities of the new integrator over some existing methods.
In this paper, we consider a numerical method for the multi-term Caputo-Fabrizio time-fractional diffusion equations (with orders $\alpha_i\in(0,1)$, $i=1,2,\cdots,n$). The proposed method employs a fast finite difference scheme to approximate multi-term fractional derivatives in time, requiring only $O(1)$ storage and $O(N_T)$ computational complexity, where $N_T$ denotes the total number of time steps. Then we use a Legendre spectral collocation method for spatial discretization. The stability and convergence of the scheme have been thoroughly discussed and rigorously established. We demonstrate that the proposed scheme is unconditionally stable and convergent with an order of $O(\left(\Delta t\right)^{2}+N^{-m})$, where $\Delta t$, $N$, and $m$ represent the timestep size, polynomial degree, and regularity in the spatial variable of the exact solution, respectively. Numerical results are presented to validate the theoretical predictions.
We study the edge-coloring problem in simple $n$-vertex $m$-edge graphs with maximum degree $\Delta$. This is one of the most classical and fundamental graph-algorithmic problems. Vizing's celebrated theorem provides $(\Delta+1)$-edge-coloring in $O(m\cdot n)$ deterministic time. This running time was improved to $O\left(m\cdot\min\left\{\Delta\cdot\log n, \sqrt{n}\right\}\right)$. It is also well-known that $3\left\lceil\frac{\Delta}{2}\right\rceil$-edge-coloring can be computed in $O(m\cdot\log\Delta)$ time deterministically. Duan et al. devised a randomized $(1+\varepsilon)\Delta$-edge-coloring algorithm with running time $O\left(m\cdot\frac{\log^6 n}{\varepsilon^2}\right)$. It was however open if there exists a deterministic near-linear time algorithm for this basic problem. We devise a simple deterministic $(1+\varepsilon)\Delta$-edge-coloring algorithm with running time $O\left(m\cdot\frac{\log n}{\varepsilon}\right)$. We also devise a randomized $(1+\varepsilon)\Delta$-edge-coloring algorithm with running time $O(m\cdot(\varepsilon^{-18}+\log(\varepsilon\cdot\Delta)))$. For $\varepsilon\geq\frac{1}{\log^{1/18}\Delta}$, this running time is $O(m\cdot\log\Delta)$.
We study discretizations of fractional fully nonlinear equations by powers of discrete Laplacians. Our problems are parabolic and of order $\sigma\in(0,2)$ since they involve fractional Laplace operators $(-\Delta)^{\sigma/2}$. They arise e.g.~in control and game theory as dynamic programming equations, and solutions are non-smooth in general and should be interpreted as viscosity solutions. Our approximations are realized as finite-difference quadrature approximations and are 2nd order accurate for all values of $\sigma$. The accuracy of previous approximations depend on $\sigma$ and are worse when $\sigma$ is close to $2$. We show that the schemes are monotone, consistent, $L^\infty$-stable, and convergent using a priori estimates, viscosity solutions theory, and the method of half-relaxed limits. We present several numerical examples.
In recent years, the Adaptive Antoulas-Anderson AAA algorithm has established itself as the method of choice for solving rational approximation problems. Data-driven Model Order Reduction (MOR) of large-scale Linear Time-Invariant (LTI) systems represents one of the many applications in which this algorithm has proven to be successful since it typically generates reduced-order models (ROMs) efficiently and in an automated way. Despite its effectiveness and numerical reliability, the classical AAA algorithm is not guaranteed to return a ROM that retains the same structural features of the underlying dynamical system, such as the stability of the dynamics. In this paper, we propose a novel algebraic characterization for the stability of ROMs with transfer function obeying the AAA barycentric structure. We use this characterization to formulate a set of convex constraints on the free coefficients of the AAA model that, whenever verified, guarantee by construction the asymptotic stability of the resulting ROM. We suggest how to embed such constraints within the AAA optimization routine, and we validate experimentally the effectiveness of the resulting algorithm, named stabAAA, over a set of relevant MOR applications.
When and why can a neural network be successfully trained? This article provides an overview of optimization algorithms and theory for training neural networks. First, we discuss the issue of gradient explosion/vanishing and the more general issue of undesirable spectrum, and then discuss practical solutions including careful initialization and normalization methods. Second, we review generic optimization methods used in training neural networks, such as SGD, adaptive gradient methods and distributed methods, and theoretical results for these algorithms. Third, we review existing research on the global issues of neural network training, including results on bad local minima, mode connectivity, lottery ticket hypothesis and infinite-width analysis.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191