Bi-objective Optimization in Role Mining

• URL: http://arxiv.org/abs/2403.16757v1
• Date: Mon, 25 Mar 2024 13:36:20 GMT
• Title: Bi-objective Optimization in Role Mining
• Abstract summary: Role mining is a technique used to derive a role-based authorization policy from an existing policy. We first introduce the Generalized Noise Role Mining problem (GNRM) We show that GNRM is fixed parameter tractable, with parameter $r + k$, where $r$ is the number of roles in the solution. We then report the results of our experimental work using the integer programming solver Gurobi to solve instances of BO-GNRM.
• Score: 6.121341817409735
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Role mining is a technique used to derive a role-based authorization policy from an existing policy. Given a set of users $U$, a set of permissions $P$ and a user-permission authorization relation $\mahtit{UPA}\subseteq U\times P$, a role mining algorithm seeks to compute a set of roles $R$, a user-role authorization relation $\mathit{UA}\subseteq U\times R$ and a permission-role authorization relation $\mathit{PA}\subseteq R\times P$, such that the composition of $\mathit{UA}$ and $\mathit{PA}$ is close (in some appropriate sense) to $\mathit{UPA}$. In this paper, we first introduce the Generalized Noise Role Mining problem (GNRM) -- a generalization of the MinNoise Role Mining problem -- which we believe has considerable practical relevance. Extending work of Fomin et al., we show that GNRM is fixed parameter tractable, with parameter $r + k$, where $r$ is the number of roles in the solution and $k$ is the number of discrepancies between $\mathit{UPA}$ and the relation defined by the composition of $\mathit{UA}$ and $\mathit{PA}$. We further introduce a bi-objective optimization variant of GNRM, where we wish to minimize both $r$ and $k$ subject to upper bounds $r\le \bar{r}$ and $k\le \bar{k}$, where $\bar{r}$ and $\bar{k}$ are constants. We show that the Pareto front of this bi-objective optimization problem (BO-GNRM) can be computed in fixed-parameter tractable time with parameter $\bar{r}+\bar{k}$. We then report the results of our experimental work using the integer programming solver Gurobi to solve instances of BO-GNRM. Our key findings are that (a) we obtained strong support that Gurobi's performance is fixed-parameter tractable, (b) our results suggest that our techniques may be useful for role mining in practice, based on our experiments in the context of three well-known real-world authorization policies.

Related papers

• Bandit Max-Min Fair Allocation [30.8580020414087]
  We study a new decision-making problem called the bandit max-min fair allocation (BMMFA) problem.<n>The goal of this problem is to maximize the minimum utility among agents with additive valuations.<n>One key feature of this problem is that each agent's valuation for each item can only be observed through the semi-bandit feedback.
  arXiv  Detail & Related papers  (2025-05-08T12:09:20Z)
• Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning [4.899818550820576]
  We propose a new $textttSUBPLE-MFQ$ ($textbfSubsample$-$textbfMean-$textbfF$ield-$textbfQ$-learning) and a decentralized randomized policy for a system with $n$ agents.<n>We prove that this learned policy converges to the optimal policy on the order of $tilde$O (1/sqrtk)$ as the number of subsampled agents $k$ increases.
  arXiv  Detail & Related papers  (2024-12-01T03:45:17Z)
• Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
  We quantify the performance of the approximation with the Monge-Kantorovich $p$-cost. We may then reform the problem as minimizing a functional $mathscrJ_p(f)$ under a constraint on the Sobolev budget.
  arXiv  Detail & Related papers  (2024-09-25T01:30:16Z)
• Efficient Reinforcement Learning in Probabilistic Reward Machines [15.645062155050732]
  We design an algorithm for Probabilistic Reward Machines (PRMs) that achieves a regret bound of $widetildeO(sqrtHOAT)$. We also present a new simulation lemma for non-Markovian rewards, which enables reward-free exploration for any non-Markovian reward.
  arXiv  Detail & Related papers  (2024-08-19T19:51:53Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  We study the generalized low-rank matrix bandit problem, proposed in citelu2021low under the Generalized Linear Model (GLM) framework. To overcome the computational infeasibility and theoretical restrain of existing algorithms, we first propose the G-ESTT framework. We show that G-ESTT can achieve the $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret while G-ESTS can achineve the $tildeO
  arXiv  Detail & Related papers  (2024-01-14T14:14:19Z)
• Learning Thresholds with Latent Values and Censored Feedback [18.129896050051432]
  We show a problem where the unknown reward $g(gamma, v)$ depends on the proposed threshold $gamma$ and latent value $v$ and it can be $only$ achieved if the threshold is lower than or equal to the unknown latent value. This problem has broad applications in practical scenarios, e.g., reserve price optimization in online auctions, online task assignments in crowdsourcing, setting recruiting bars in hiring.
  arXiv  Detail & Related papers  (2023-12-07T19:30:08Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  We propose a provably efficient reinforcement learning algorithm (both computationally and statistically) with general value function approximations. Our algorithm achieves reasonable regret bounds when applied to both the linear setting and the sparse high-dimensional linear setting.
  arXiv  Detail & Related papers  (2023-02-22T20:21:25Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP) We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
  arXiv  Detail & Related papers  (2022-12-01T15:57:58Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  We consider episodic reinforcement learning in reward-mixing Markov decision processes (RMMDPs) Our goal is to learn a near-optimal policy that nearly maximizes the $H$ time-step cumulative rewards in such a model.
  arXiv  Detail & Related papers  (2022-10-05T22:52:00Z)
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations [79.66404989555566]
  We consider the more realistic setting of agnostic RL with rich observation spaces and a fixed class of policies $Pi$ that may not contain any near-optimal policy. We provide an algorithm for this setting whose error is bounded in terms of the rank $d$ of the underlying MDP.
  arXiv  Detail & Related papers  (2021-06-22T03:20:40Z)
• A No-Free-Lunch Theorem for MultiTask Learning [19.645741778058227]
  We consider a seemingly favorable classification scenario where all tasks $P_t$ share a common optimal classifier $h*,$. We show that, even though such regimes admit minimax rates accounting for both $n$ and $N$, no adaptive algorithm exists.
  arXiv  Detail & Related papers  (2020-06-29T03:03:29Z)
• Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
  We consider the question of learning $Q$-function in a sample efficient manner for reinforcement learning with continuous state and action spaces. We develop a simple, iterative learning algorithm that finds $epsilon$-Schmidt $Q$-function with sample complexity of $widetildeO(frac1epsilonmax(d1), d_2)+2)$ when the optimal $Q$-function has low rank $r$ and the factor $$ is below a certain threshold.
  arXiv  Detail & Related papers  (2020-06-11T00:55:35Z)
• Robust Interference Management for SISO Systems with Multiple Over-the-Air Computations [16.52374405363812]
  We consider the over-the-air computation of sums over a shared complex-valued MAC. Finding appropriate Tx-Rx scaling factors balance between a low error in the computation of $s_n$ and the interference induced by it.
  arXiv  Detail & Related papers  (2020-04-21T11:15:26Z)

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.