Yang et al. (2023) recently addressed the open problem of solving Variational Inequalities (VIs) with equality and inequality constraints through a first-order gradient method. However, the proposed primal-dual method called ACVI is applicable when we can compute analytic solutions of its subproblems; thus, the general case remains an open problem. In this paper, we adopt a warm-starting technique where we solve the subproblems approximately at each iteration and initialize the variables with the approximate solution found at the previous iteration. We prove its convergence and show that the gap function of the last iterate of this inexact-ACVI method decreases at a rate of $\mathcal{O}(\frac{1}{\sqrt{K}})$ when the operator is $L$-Lipschitz and monotone, provided that the errors decrease at appropriate rates. Interestingly, we show that often in numerical experiments, this technique converges faster than its exact counterpart. Furthermore, for the cases when the inequality constraints are simple, we propose a variant of ACVI named P-ACVI and prove its convergence for the same setting. We further demonstrate the efficacy of the proposed methods through numerous experiments. We also relax the assumptions in Yang et al., yielding, to our knowledge, the first convergence result that does not rely on the assumption that the operator is $L$-Lipschitz. Our source code is provided at $\texttt{//github.com/mpagli/Revisiting-ACVI}$.
相關內容
Preordered semialgebras and semirings are two kinds of algebraic structures occurring in real algebraic geometry frequently and usually play important roles therein. They have many interesting and promising applications in the fields of real algebraic geometry, probability theory, theoretical computer science, quantum information theory, \emph{etc.}. In these applications, Strassen's Vergleichsstellensatz and its generalized versions, which are analogs of those Positivstellens\"atze in real algebraic geometry, play important roles. While these Vergleichsstellens\"atze accept only a commutative setting (for the semirings in question), we prove in this paper a noncommutative version of one of the generalized Vergleichsstellens\"atze proposed by Fritz [\emph{Comm. Algebra}, 49 (2) (2021), pp. 482-499]. The most crucial step in our proof is to define the semialgebra of the fractions of a noncommutative semialgebra, which generalizes the definitions in the literature. Our new Vergleichsstellensatz characterizes the relaxed preorder on a noncommutative semialgebra induced by all monotone homomorphisms to $\mathbb{R}_+$ by three other equivalent conditions on the semialgebra of its fractions equipped with the derived preorder, which may result in more applications in the future.
A model of computation for which reasonable yet still incomplete lower bounds are known is the read-once branching program. Here variants of complexity measures successful in the study of read-once branching programs are defined and studied. Some new or simpler proofs of known bounds are uncovered. Branching program resources and the new measures are compared extensively. The new variants are developed in part in the hope of tackling read-k branching programs for the tree evaluation problem studied in Cook et al. Other computation problems are studied as well. In particular, a common view of a function studied by Gal and a function studied by Bollig and Wegener leads to the general combinatorics of blocking sets. Technical combinatorial results of independent interest are obtained. New leads towards further progress are discussed. An exponential lower bound for non-deterministic read-k branching programs for the GEN function is also derived, independently from the new measures.
We study the problem of solving linear program in the streaming model. Given a constraint matrix $A\in \mathbb{R}^{m\times n}$ and vectors $b\in \mathbb{R}^m, c\in \mathbb{R}^n$, we develop a space-efficient interior point method that optimizes solely on the dual program. To this end, we obtain efficient algorithms for various different problems: * For general linear programs, we can solve them in $\widetilde O(\sqrt n\log(1/\epsilon))$ passes and $\widetilde O(n^2)$ space for an $\epsilon$-approximate solution. To the best of our knowledge, this is the most efficient LP solver in streaming with no polynomial dependence on $m$ for both space and passes. * For bipartite graphs, we can solve the minimum vertex cover and maximum weight matching problem in $\widetilde O(\sqrt{m})$ passes and $\widetilde O(n)$ space. In addition to our space-efficient IPM, we also give algorithms for solving SDD systems and isolation lemma in $\widetilde O(n)$ spaces, which are the cornerstones for our graph results.
This paper presents a general methodology for deriving information-theoretic generalization bounds for learning algorithms. The main technical tool is a probabilistic decorrelation lemma based on a change of measure and a relaxation of Young's inequality in $L_{\psi_p}$ Orlicz spaces. Using the decorrelation lemma in combination with other techniques, such as symmetrization, couplings, and chaining in the space of probability measures, we obtain new upper bounds on the generalization error, both in expectation and in high probability, and recover as special cases many of the existing generalization bounds, including the ones based on mutual information, conditional mutual information, stochastic chaining, and PAC-Bayes inequalities. In addition, the Fernique-Talagrand upper bound on the expected supremum of a subgaussian process emerges as a special case.
Interpolation-based methods are well-established and effective approaches for the efficient generation of accurate reduced-order surrogate models. Common challenges for such methods are the automatic selection of good or even optimal interpolation points and the appropriate size of the reduced-order model. An approach that addresses the first problem for linear, unstructured systems is the Iterative Rational Krylov Algorithm (IRKA), which computes optimal interpolation points through iterative updates by solving linear eigenvalue problems. However, in the case of preserving internal system structures, optimal interpolation points are unknown, and heuristics based on nonlinear eigenvalue problems result in numbers of potential interpolation points that typically exceed the reasonable size of reduced-order systems. In our work, we propose a projection-based iterative interpolation method inspired by IRKA for generally structured systems to adaptively compute near-optimal interpolation points as well as an appropriate size for the reduced-order system. Additionally, the iterative updates of the interpolation points can be chosen such that the reduced-order model provides an accurate approximation in specified frequency ranges of interest. For such applications, our new approach outperforms the established methods in terms of accuracy and computational effort. We show this in numerical examples with different structures.
Non-stationary multi-armed bandit (NS-MAB) problems have recently received significant attention. NS-MAB are typically modelled in two scenarios: abruptly changing, where reward distributions remain constant for a certain period and change at unknown time steps, and smoothly changing, where reward distributions evolve smoothly based on unknown dynamics. In this paper, we propose Discounted Thompson Sampling (DS-TS) with Gaussian priors to address both non-stationary settings. Our algorithm passively adapts to changes by incorporating a discounted factor into Thompson Sampling. DS-TS method has been experimentally validated, but analysis of the regret upper bound is currently lacking. Under mild assumptions, we show that DS-TS with Gaussian priors can achieve nearly optimal regret bound on the order of $\tilde{O}(\sqrt{TB_T})$ for abruptly changing and $\tilde{O}(T^{\beta})$ for smoothly changing, where $T$ is the number of time steps, $B_T$ is the number of breakpoints, $\beta$ is associated with the smoothly changing environment and $\tilde{O}$ hides the parameters independent of $T$ as well as logarithmic terms. Furthermore, empirical comparisons between DS-TS and other non-stationary bandit algorithms demonstrate its competitive performance. Specifically, when prior knowledge of the maximum expected reward is available, DS-TS has the potential to outperform state-of-the-art algorithms.
For a finite set of balls of radius $r$, the $k$-fold cover is the space covered by at least $k$ balls. Fixing the ball centers and varying the radius, we obtain a nested sequence of spaces that is called the $k$-fold filtration of the centers. For $k=1$, the construction is the union-of-balls filtration that is popular in topological data analysis. For larger $k$, it yields a cleaner shape reconstruction in the presence of outliers. We contribute a sparsification algorithm to approximate the topology of the $k$-fold filtration. Our method is a combination and adaptation of several techniques from the well-studied case $k=1$, resulting in a sparsification of linear size that can be computed in expected near-linear time with respect to the number of input points. Our method also extends to the multicover bifiltration, composed of the $k$-fold filtrations for several values of $k$, with the same size and complexity bounds.
Answer Set Programming with Quantifiers ASP(Q) extends Answer Set Programming (ASP) to allow for declarative and modular modeling of problems from the entire polynomial hierarchy. The first implementation of ASP(Q), called qasp, was based on a translation to Quantified Boolean Formulae (QBF) with the aim of exploiting the well-developed and mature QBF-solving technology. However, the implementation of the QBF encoding employed in qasp is very general and might produce formulas that are hard to evaluate for existing QBF solvers because of the large number of symbols and sub-clauses. In this paper, we present a new implementation that builds on the ideas of qasp and features both a more efficient encoding procedure and new optimized encodings of ASP(Q) programs in QBF. The new encodings produce smaller formulas (in terms of the number of quantifiers, variables, and clauses) and result in a more efficient evaluation process. An algorithm selection strategy automatically combines several QBF-solving back-ends to further increase performance. An experimental analysis, conducted on known benchmarks, shows that the new system outperforms qasp.
Given a boolean formula $\Phi$(X, Y, Z), the Max\#SAT problem asks for finding a partial model on the set of variables X, maximizing its number of projected models over the set of variables Y. We investigate a strict generalization of Max\#SAT allowing dependencies for variables in X, effectively turning it into a synthesis problem. We show that this new problem, called DQMax\#SAT, subsumes the DQBF problem as well. We provide a general resolution method, based on a reduction to Max\#SAT, together with two improvements for dealing with its inherent complexity. We further discuss a concrete application of DQMax\#SAT for symbolic synthesis of adaptive attackers in the field of program security. Finally, we report preliminary results obtained on the resolution on benchmark problems using a prototype DQMax\#SAT solver implementation.
Integrated visible light positioning and communication (VLPC), capable of combining advantages of visible light communications (VLC) and visible light positioning (VLP), is a promising key technology for the future Internet of Things. In VLPC networks, positioning and communications are inherently coupled, which has not been sufficiently explored in the literature. We propose a robust power allocation scheme for integrated VLPC Networks by exploiting the intrinsic relationship between positioning and communications. Specifically, we derive explicit relationships between random positioning errors, following both a Gaussian distribution and an arbitrary distribution, and channel state information errors. Then, we minimize the Cramer-Rao lower bound (CRLB) of positioning errors, subject to the rate outage constraint and the power constraints, which is a chance-constrained optimization problem and generally computationally intractable. To circumvent the nonconvex challenge, we conservatively transform the chance constraints to deterministic forms by using the Bernstein-type inequality and the conditional value-at-risk for the Gaussian and arbitrary distributed positioning errors, respectively, and then approximate them as convex semidefinite programs. Finally, simulation results verify the robustness and effectiveness of our proposed integrated VLPC design schemes.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191