Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userApproximation Bounds for Sparse Programs
73
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We show that sparsity constrained optimization problems over low dimensional spaces tend to have a small duality gap. We use the Shapley-Folkman theorem to derive both data-driven bounds on the duality gap, and an efficient primalization procedure to recover feasible points satisfying these bounds. These error bounds are proportional to the rate of growth of the objective with the target cardinality, which means in particular that the relaxation is nearly tight as soon as the target cardinality is large enough so that only uninformative features are added.
rate research
Read More
We propose a sigmoidal approximation for the value-at-risk (that we call SigVaR) and we use this approximation to tackle nonlinear programs (NLPs) with chance constraints. We prove that the approximation is conservative and that the level of conservatism can be made arbitrarily small for limiting parameter values. The SigVar approximation brings scalability benefits over exact mixed-integer reformulations because its sample average approximation can be cast as a standard NLP. We also establish explicit connections between SigVaR and other smooth sigmoidal approximations recently reported in the literature. We show that a key benefit of SigVaR over such approximations is that one can establish an explicit connection with the conditional value at risk (CVaR) approximation and exploit this connection to obtain initial guesses for the approximation parameters. We present small- and large-scale numerical studies to illustrate the developments.
Several issues in machine learning and inverse problems require to generate discrete data, as if sampled from a model probability distribution. A common way to do so relies on the construction of a uniform probability distribution over a set of $N$ points which minimizes the Wasserstein distance to the model distribution. This minimization problem, where the unknowns are the positions of the atoms, is non-convex. Yet, in most cases, a suitably adjusted version of Lloyds algorithm -- in which Voronoi cells are replaced by Power cells -- leads to configurations with small Wasserstein error. This is surprising because, again, of the non-convex nature of the problem, as well as the existence of spurious critical points. We provide explicit upper bounds for the convergence speed of this Lloyd-type algorithm, starting from a cloud of points sufficiently far from each other. This already works after one step of the iteration procedure, and similar bounds can be deduced, for the corresponding gradient descent. These bounds naturally lead to a modified Poliak-Lojasiewicz inequality for the Wasserstein distance cost, with an error term depending on the distances between Dirac masses in the discrete distribution.
Scenario programs have established themselves as efficient tools towards decision-making under uncertainty. To assess the quality of scenario-based solutions a posteriori, validation tests based on Bernoulli trials have been widely adopted in practice. However, to reach a theoretically reliable judgement of risk, one typically needs to collect massive validation samples. In this work, we propose new a posteriori bounds for convex scenario programs with validation tests, which are dependent on both realizations of support constraints and performance on out-of-sample validation data. The proposed bounds enjoy wide generality in that many existing theoretical results can be incorporated as particular cases. To facilitate practical use, a systematic approach for parameterizing a posteriori probability bounds is also developed, which is shown to possess a variety of desirable properties allowing for easy implementations and clear interpretations. By synthesizing comprehensive information about support constraints and validation tests, improved risk evaluation can be achieved for randomized solutions in comparison with existing a posteriori bounds. Case studies on controller design of aircraft lateral motion are presented to validate the effectiveness of the proposed a posteriori bounds.
We investigate the feasibility of sample average approximation (SAA) for general stochastic optimization problems, including two-stage stochastic programming without the relatively complete recourse assumption. Instead of analyzing problems with specific structures, we utilize results from the Vapnik-Chervonenkis (VC) dimension and Probably Approximately Correct learning to provide a general framework that offers explicit feasibility bounds for SAA solutions under minimal structural or distributional assumption. We show that, as long as the hypothesis class formed by the feasbible region has a finite VC dimension, the infeasibility of SAA solutions decreases exponentially with computable rates and explicitly identifiable accompanying constants. We demonstrate how our bounds apply more generally and competitively compared to existing results.
We consider integer programs (IP) defined by equations and box constraints, where it is known that determinants in the constraint matrix are one measure of complexity. For example, Artmann et al. showed that an IP can be solved in strongly polynomial time if the constraint matrix is bimodular, that is, the determinants are bounded in absolute value by two. Determinants are also used to bound the $ell_1$-distance between IP solutions and solutions of its linear relaxation. One of the first works to quantify the complexity of IPs with bounded determinants was that of Heller, who identified the maximum number of differing columns in a totally unimodular constraint matrix. So far, each extension of Hellers bound to general determinants has been exponential in the determinants or the number of equations. We provide the first column bound that is polynomial in both values. As a corollary, we give the first $ell_1$-distance bound that is polynomial in the determinants and the number of equations. We also show a tight bound on the number of differing columns in a bimodular constraint matrix; this is the first tight bound since Hellers result. Our analysis reveals combinatorial properties of bimodular IPs that may be of independent interest, in particular in recognition algorithms for IPs with bounded determinants.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
