Metric Entropy-Free Sample Complexity Bounds for Sample Average Approximation in Convex Stochastic Programming

• URL: http://arxiv.org/abs/2401.00664v6
• Date: Fri, 28 Mar 2025 15:39:14 GMT
• Title: Metric Entropy-Free Sample Complexity Bounds for Sample Average Approximation in Convex Stochastic Programming
• Authors: Hongcheng Liu, Jindong Tong,
• Abstract summary: It has been shown that entropy-free complexity rates are attainable under a uniform Lipschitz condition.<n>This paper presents perhaps the first set of metric entropy-free sample complexity bounds for the SAA under standard SP assumptions.
• Score: 0.6906005491572401
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies sample average approximation (SAA) in solving convex or strongly convex stochastic programming (SP) problems. In estimating SAA's sample efficiency, the state-of-the-art sample complexity bounds entail metric entropy terms (such as the logarithm of the feasible region's covering number), which often grow polynomially with problem dimensionality. While it has been shown that metric entropy-free complexity rates are attainable under a uniform Lipschitz condition, such an assumption can be overly critical for many important SP problem settings. In response, this paper presents perhaps the first set of metric entropy-free sample complexity bounds for the SAA under standard SP assumptions -- in the absence of the uniform Lipschitz condition. The new results often lead to an $O(d)$-improvement in the complexity rate than the state-of-the-art. From the newly established complexity bounds, an important revelation is that SAA and the canonical stochastic mirror descent (SMD) method, two mainstream solution approaches to SP, entail almost identical rates of sample efficiency, lifting a theoretical discrepancy of SAA from SMD also by the order of $O(d)$. Furthermore, this paper explores non-Lipschitzian scenarios where SAA maintains provable efficacy but the corresponding results for SMD remain mostly unexplored, indicating the potential of SAA's better applicability in some irregular settings. Our numerical experiment results on SAA for solving a simulated SP problem align with our theoretical findings.

Related papers

• Stochastic Optimization with Optimal Importance Sampling [49.484190237840714]
  We propose an iterative-based algorithm that jointly updates the decision and the IS distribution without requiring time-scale separation between the two. Our method achieves the lowest possible variable variance and guarantees global convergence under convexity of the objective and mild assumptions on the IS distribution family.
  arXiv  Detail & Related papers  (2025-04-04T16:10:18Z)
• Sharpness-Aware Minimization: General Analysis and Improved Rates [10.11126899274029]
  Sharpness-Aware Minimization (SAM) has emerged as a powerful method for improving generalization in machine learning models. We provide an analysis of SAM and its unnormalized variant rule rule (USAM) under one update. We present results of the new size under a relaxed more natural assumption.
  arXiv  Detail & Related papers  (2025-03-04T03:04:06Z)
• Sample Complexity of the Sign-Perturbed Sums Method [0.0]
  The Sign-Perturbed Sums (SPS) method constructs exact, non-asymptotic confidence regions for the true system parameters. We study the sample complexity of SPS for general linear regression problems. The difference between the theoretical bounds and the empirical sizes of SPS confidence regions is investigated experimentally.
  arXiv  Detail & Related papers  (2024-09-02T13:18:53Z)
• Sample Complexity of the Sign-Perturbed Sums Identification Method: Scalar Case [0.0]
  Sign-Perturbed Sum (SPS) is a powerful finite-sample system identification algorithm. This paper studies the behaviour of SPS confidence intervals.
  arXiv  Detail & Related papers  (2024-01-28T22:44:41Z)
• Fast Shapley Value Estimation: A Unified Approach [71.92014859992263]
  We propose a straightforward and efficient Shapley estimator, SimSHAP, by eliminating redundant techniques. In our analysis of existing approaches, we observe that estimators can be unified as a linear transformation of randomly summed values from feature subsets. Our experiments validate the effectiveness of our SimSHAP, which significantly accelerates the computation of accurate Shapley values.
  arXiv  Detail & Related papers  (2023-11-02T06:09:24Z)
• SA-Solver: Stochastic Adams Solver for Fast Sampling of Diffusion Models [66.67616086310662]
  Diffusion Probabilistic Models (DPMs) have achieved considerable success in generation tasks. As sampling from DPMs is equivalent to solving diffusion SDE or ODE which is time-consuming, numerous fast sampling methods built upon improved differential equation solvers are proposed. We propose SA-of-r, which is an improved efficient Adams method for solving diffusion SDE to generate data with high quality.
  arXiv  Detail & Related papers  (2023-09-10T12:44:54Z)
• The Curse of Memory in Stochastic Approximation: Extended Version [1.534667887016089]
  Theory and application of approximation (SA) has grown within the control systems community since the earliest days of adaptive control. Recent results establish remarkable performance of SA with (sufficiently small) constant step-size $alpha>0$.
  arXiv  Detail & Related papers  (2023-09-06T12:22:32Z)
• The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model [61.87673435273466]
  This paper investigates model robustness in reinforcement learning (RL) to reduce the sim-to-real gap in practice. We adopt the framework of distributionally robust Markov decision processes (RMDPs), aimed at learning a policy that optimize the worst-case performance when the deployed environment falls within a prescribed uncertainty set around the nominal MDP.
  arXiv  Detail & Related papers  (2023-05-26T02:32:03Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way Partial AUC (OPAUC) and Two-way Partial AUC (TPAUC) measures the average performance of a binary classifier. Most of the existing methods could only optimize PAUC approximately, leading to inevitable biases that are not controllable. We present a simpler reformulation of the PAUC problem via distributional robust optimization AUC.
  arXiv  Detail & Related papers  (2022-10-08T08:26:22Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  Policy gradient (PG) is one of the most popular reinforcement learning (RL) problems. "vanilla" theoretical understanding of PG trajectory is one of the most popular methods for solving RL problems.
  arXiv  Detail & Related papers  (2021-07-23T19:38:17Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  We propose the amortized conditional normalized maximum likelihood (ACNML) method as a scalable general-purpose approach for uncertainty estimation. Our algorithm builds on the conditional normalized maximum likelihood (CNML) coding scheme, which has minimax optimal properties according to the minimum description length principle. We demonstrate that ACNML compares favorably to a number of prior techniques for uncertainty estimation in terms of calibration on out-of-distribution inputs.
  arXiv  Detail & Related papers  (2020-11-05T08:04:34Z)
• Exact and Approximation Algorithms for Sparse PCA [1.7640556247739623]
  This paper proposes two exact mixed-integer SDPs (MISDPs) We then analyze the theoretical optimality gaps of their continuous relaxation values and prove that they are stronger than that of the state-of-art one. Since off-the-shelf solvers, in general, have difficulty in solving MISDPs, we approximate SPCA with arbitrary accuracy by a mixed-integer linear program (MILP) of a similar size as MISDPs.
  arXiv  Detail & Related papers  (2020-08-28T02:07:08Z)
• Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
  This work shows that these hardness barriers do not preclude efficient reinforcement learning for rich and interesting subclasses of Partially Observable Decision Processes (POMDPs) We present a sample-efficient algorithm, OOM-UCB, for episodic finite undercomplete POMDPs, where the number of observations is larger than the number of latent states and where exploration is essential for learning, thus distinguishing our results from prior works.
  arXiv  Detail & Related papers  (2020-06-22T17:58:54Z)
• $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a Robust Divergence Estimator [95.71091446753414]
  We propose to use a nearest-neighbor-based $gamma$-divergence estimator as a data discrepancy measure. Our method achieves significantly higher robustness than existing discrepancy measures.
  arXiv  Detail & Related papers  (2020-06-13T06:09:27Z)
• Decidability of Sample Complexity of PAC Learning in finite setting [1.8130068086063333]
  PAC machine learning of various concepts can be exactly determined when the support of the probability measures considered as models satisfies an a-priori bound. This result contrasts with the recently discovered undecidability of EMX within ZFC for finitely supported probabilities.
  arXiv  Detail & Related papers  (2020-02-26T14:27:36Z)
• Stochastic Approximation versus Sample Average Approximation for population Wasserstein barycenters [2.3025186469300434]
  In the machine learning and optimization community, there are two main approaches for the convex risk problem, namely, the minimization Approximation (SA) and the Sample Average Approximation (SAA) We show that for the Wasserstein barycenter problem this superiority can be inverted. We provide a detailed comparison by stating the complexity bounds for the SA and the SAA implementations calculating barycenters defined with respect to optimal transport distances and entropy-regularized optimal transport distances.
  arXiv  Detail & Related papers  (2020-01-21T18:54:39Z)

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.