Tightly Robust Optimization via Empirical Domain Reduction

• URL: http://arxiv.org/abs/2003.00248v1
• Date: Sat, 29 Feb 2020 12:24:56 GMT
• Title: Tightly Robust Optimization via Empirical Domain Reduction
• Authors: Akihiro Yabe and Takanori Maehara
• Abstract summary: We propose an algorithm to determine the scale such that the solution has a good objective value. Under some regularity conditions, the scale obtained by our algorithm is $O(sqrtn)$, whereas the scale obtained by a standard approach is $O(sqrtd/n)$.
• Score: 22.63829081634384
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Data-driven decision-making is performed by solving a parameterized optimization problem, and the optimal decision is given by an optimal solution for unknown true parameters. We often need a solution that satisfies true constraints even though these are unknown. Robust optimization is employed to obtain such a solution, where the uncertainty of the parameter is represented by an ellipsoid, and the scale of robustness is controlled by a coefficient. In this study, we propose an algorithm to determine the scale such that the solution has a good objective value and satisfies the true constraints with a given confidence probability. Under some regularity conditions, the scale obtained by our algorithm is asymptotically $O(1/\sqrt{n})$, whereas the scale obtained by a standard approach is $O(\sqrt{d/n})$. This means that our algorithm is less affected by the dimensionality of the parameters.

Related papers

• BO4IO: A Bayesian optimization approach to inverse optimization with uncertainty quantification [5.031974232392534]
  This work addresses data-driven inverse optimization (IO) The goal is to estimate unknown parameters in an optimization model from observed decisions that can be assumed to be optimal or near-optimal.
  arXiv  Detail & Related papers  (2024-05-28T06:52:17Z)
• Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Sets [10.26382228865201]
  We propose policy gradient algorithms for robust infinite-horizon Markov decision processes (MDPs) with non-rectangular uncertainty sets. The corresponding robust MDPs cannot be solved with dynamic programming techniques and are in fact provably intractable. We thus present the first complete solution scheme for robust MDPs with non-rectangular uncertainty sets offering global optimality guarantees.
  arXiv  Detail & Related papers  (2023-05-30T13:02:25Z)
• Quantization-Based Optimization: Alternative Stochastic Approximation of Global Optimization [0.0]
  We propose a global optimization algorithm based on quantizing the energy level of an objective function in an NP-hard problem. Numerical experiments show that the proposed algorithm outperforms conventional learning methods in solving NP-hard optimization problems.
  arXiv  Detail & Related papers  (2022-11-08T03:01:45Z)
• Efficient Learning of Decision-Making Models: A Penalty Block Coordinate Descent Algorithm for Data-Driven Inverse Optimization [12.610576072466895]
  We consider the inverse problem where we use prior decision data to uncover the underlying decision-making process. This statistical learning problem is referred to as data-driven inverse optimization. We propose an efficient block coordinate descent-based algorithm to solve large problem instances.
  arXiv  Detail & Related papers  (2022-10-27T12:52:56Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  We explore the connection between high-dimensional statistics and non-robust optimization in the presence of sparsity constraints. We develop novel and simple optimization formulations for these problems. As a corollary, we obtain that any first-order method that efficiently converges to station yields an efficient algorithm for these tasks.
  arXiv  Detail & Related papers  (2021-09-23T17:38:24Z)
• Distributionally Robust Optimization with Markovian Data [8.126833795693699]
  We study a program where the probability distribution of the uncertain problem parameters is unknown. We propose a data-driven distributionally to estimate the problem's objective function and optimal solution.
  arXiv  Detail & Related papers  (2021-06-12T10:59:02Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Aligning Partially Overlapping Point Sets: an Inner Approximation Algorithm [80.15123031136564]
  We propose a robust method to align point sets where there is no prior information about the value of the transformation. Our algorithm does not need regularization on transformation, and thus can handle the situation where there is no prior information about the values of the transformations. Experimental results demonstrate the better robustness of the proposed method over state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2020-07-05T15:23:33Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Implicit differentiation of Lasso-type models for hyperparameter optimization [82.73138686390514]
  We introduce an efficient implicit differentiation algorithm, without matrix inversion, tailored for Lasso-type problems. Our approach scales to high-dimensional data by leveraging the sparsity of the solutions.
  arXiv  Detail & Related papers  (2020-02-20T18:43:42Z)

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.