Adaptivity Complexity for Causal Graph Discovery
- URL: http://arxiv.org/abs/2306.05781v1
- Date: Fri, 9 Jun 2023 09:49:16 GMT
- Title: Adaptivity Complexity for Causal Graph Discovery
- Authors: Davin Choo, Kirankumar Shiragur
- Abstract summary: We study the problem of $r$-adaptivity, where the algorithm designer recovers the causal graph under a total of $r$ sequential rounds.
We provide a $r$-adaptive algorithm that achieves $O(minr,log n cdot n1/minr,log n)$ approximation with respect to the verification number.
- Score: 7.424262881242935
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Causal discovery from interventional data is an important problem, where the
task is to design an interventional strategy that learns the hidden ground
truth causal graph $G(V,E)$ on $|V| = n$ nodes while minimizing the number of
performed interventions. Most prior interventional strategies broadly fall into
two categories: non-adaptive and adaptive. Non-adaptive strategies decide on a
single fixed set of interventions to be performed while adaptive strategies can
decide on which nodes to intervene on sequentially based on past interventions.
While adaptive algorithms may use exponentially fewer interventions than their
non-adaptive counterparts, there are practical concerns that constrain the
amount of adaptivity allowed. Motivated by this trade-off, we study the problem
of $r$-adaptivity, where the algorithm designer recovers the causal graph under
a total of $r$ sequential rounds whilst trying to minimize the total number of
interventions. For this problem, we provide a $r$-adaptive algorithm that
achieves $O(\min\{r,\log n\} \cdot n^{1/\min\{r,\log n\}})$ approximation with
respect to the verification number, a well-known lower bound for adaptive
algorithms. Furthermore, for every $r$, we show that our approximation is
tight. Our definition of $r$-adaptivity interpolates nicely between the
non-adaptive ($r=1$) and fully adaptive ($r=n$) settings where our
approximation simplifies to $O(n)$ and $O(\log n)$ respectively, matching the
best-known approximation guarantees for both extremes. Our results also extend
naturally to the bounded size interventions.
Related papers
- Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
We propose an efficient adaptive minimax optimization algorithm (i.e., AdaFGDA) to solve these minimax problems.
It builds our momentum-based reduced and localSGD techniques, and it flexibly incorporate various adaptive learning rates.
arXiv Detail & Related papers (2022-11-14T12:32:18Z) - Verification and search algorithms for causal DAGs [11.038866111306728]
We give a characterization of a minimal sized set of atomic interventions to check the correctness of a claimed causal graph.
We generalize our results to the settings of bounded size interventions and node-dependent interventional costs.
Our result is the first known algorithm that gives a non-trivial approximation guarantee to the verifying size on general unweighted graphs.
arXiv Detail & Related papers (2022-06-30T15:52:30Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
We introduce novel online algorithms that can exploit smoothness and replace the dependence on $T$ in dynamic regret with problem-dependent quantities.
Our results are adaptive to the intrinsic difficulty of the problem, since the bounds are tighter than existing results for easy problems and safeguard the same rate in the worst case.
arXiv Detail & Related papers (2021-12-29T02:42:59Z) - Adapting to Misspecification in Contextual Bandits [82.55565343668246]
We introduce a new family of oracle-efficient algorithms for $varepsilon$-misspecified contextual bandits.
We obtain the first algorithm that achieves the optimal $O(dsqrtT + varepsilonsqrtdT)$ regret bound for unknown misspecification level.
arXiv Detail & Related papers (2021-07-12T21:30:41Z) - Intervention Efficient Algorithms for Approximate Learning of Causal
Graphs [22.401163479802094]
We study the problem of learning the causal relationships between a set of observed variables in the presence of latents.
Our goal is to recover the directions of all causal or ancestral relations in $G$, via a minimum cost set of interventions.
Our algorithms combine work on efficient intervention design and the design of low-cost separating set systems.
arXiv Detail & Related papers (2020-12-27T17:08:46Z) - Budgeted and Non-budgeted Causal Bandits [2.9005223064604078]
Learning good interventions in a causal graph can be modelled as a multi-armed bandit problem with side-information.
We propose an algorithm to minimize simple regret that optimally trades-off observations and interventions based on the cost of intervention.
Our results are experimentally validated and compared to the best-known bounds in the current literature.
arXiv Detail & Related papers (2020-12-13T13:31:14Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
We present a meta-algorithm that adapts to the optimal complexity with $tildeO(L5/6 T2/3)$ regret.
We also show that the meta-algorithm automatically admits significantly improved instance-dependent regret bounds.
arXiv Detail & Related papers (2020-11-19T10:00:54Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
Bilevel optimization is a class of problems which exhibit a two-level structure.
We propose a two-timescale approximation (TTSA) algorithm for tackling such a bilevel problem.
We show that a two-timescale natural actor-critic policy optimization algorithm can be viewed as a special case of our TTSA framework.
arXiv Detail & Related papers (2020-07-10T05:20:02Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
We propose differentially private (DP) algorithms for bound non-dimensional optimization.
We demonstrate two popular deep learning methods on the empirical advantages over standard gradient methods.
arXiv Detail & Related papers (2020-06-24T06:01:24Z) - Robust estimation via generalized quasi-gradients [28.292300073453877]
We show why many recently proposed robust estimation problems are efficiently solvable.
We identify the existence of "generalized quasi-gradients"
We show that generalized quasi-gradients exist and construct efficient algorithms.
arXiv Detail & Related papers (2020-05-28T15:14:33Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.