論文の概要: Sample Complexity of Stochastic Optimization with Integer Variables

• arxiv url: http://arxiv.org/abs/2605.07239v1
• Date: Fri, 08 May 2026 04:52:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-11 19:43:38.804626
• Title: Sample Complexity of Stochastic Optimization with Integer Variables
• Title（参考訳）: 整数変数を用いた確率最適化のサンプル複雑性
• Authors: Hongyu Cheng, Yinghao Zheng, Marco Molinaro, Amitabh Basu,
• Abstract要約: 整数最適化は、目的の制約の構造に依存して、標本数よりも厳密かつ厳密に要求されることが示される。 連続最適化の文献からよく知られた$()$サンプルの複雑さと比較して、$()$ソリューションを報告するために$()サンプルが必要である。
• 参考スコア（独自算出の注目度）: 8.697177927706521
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We establish sample complexity results for stochastic optimization over the integers, especially with a view to understand the complexity with respect to the corresponding continuous optimization problem. We show that integer optimization can sometimes require strictly more samples and sometimes strictly smaller number of samples, depending on the structure of the objective and constraints. 1. For Lipschitz objectives over subsets of the $\ell_\infty$ ball, the statistical complexity of general stochastic mixed-integer, nonlinear, nonconvex optimization is exactly the same as stochastic linear optimization with just bound constraints. 2. For Lipschitz objectives over subsets of the $\ell_2$ ball, we show that integer optimization can require strictly *smaller* sample size compared to the continuous setting in a certain regime. To get to this result, we also establish tight sample complexity results for nonconvex continuous stochastic optimization which, to the best of our knowledge, do not appear in prior work. 3. For strongly convex, smooth objectives, integer optimization has high statistical complexity compared to the continuous setting. In particular, we show that integer optimization requires $Ω(1/ε^2)$ samples to report an $ε$-approximate solution, compared to the well-known $O(1/ε)$ sample complexity from the continuous optimization literature.
• Abstract（参考訳）: 整数に対する確率的最適化のためのサンプル複雑性結果を確立し、特に、対応する連続最適化問題に対する複雑性の理解を視野に入れた。 整数最適化は、目的と制約の構造によらず、厳密に多くのサンプルを必要とすることや、厳密に少ないサンプル数を必要とすることがあることを示す。 1. $\ell_\infty$ Ball の部分集合上のリプシッツの目的に対して、一般確率的混合整数、非線形、非凸最適化の統計複雑性は、単に束縛された制約を持つ確率線型最適化と全く同じである。 2. $\ell_2$ Ball の部分集合上のLipschitz の目的に対して、整数最適化は特定の状態における連続的な設定よりも厳密な *小* サンプルサイズを必要とすることを示す。 この結果を得るために、非凸連続確率最適化のための厳密なサンプル複雑性結果も確立する。 3. 厳密で滑らかな目的に対して, 整数最適化は連続的な設定に比べて統計的に複雑である。 特に、整数最適化には$Ω(1/ε^2)$サンプルが必要であり、連続最適化の文献からよく知られた$O(1/ε)$サンプル複雑性と比較して、$ε$-近似解を報告する。

関連論文リスト

• Zeroth-Order Methods for Stochastic Nonconvex Nonsmooth Composite Optimization [51.63258496873442]
  合成最適化問題に関するこれまでの研究は、滑らか性の主要な部分、あるいはこれら2つの近似滑らか性点をそれぞれ除外した機械学習の例を必要とする。 本研究では,この問題に対する2つの新しいアルゴリズムを提案する。 これらのアルゴリズムは数値実験により有効であることを示す。
  論文  参考訳（メタデータ） (2025-10-06T02:35:42Z)
• Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models [55.07411490538404]
  本稿では,次元$d$の適応的複雑性依存性を改善する並列サンプリング手法を提案する。 我々の手法は科学計算による並列シミュレーション技術に基づいている。
  論文  参考訳（メタデータ） (2024-12-10T11:50:46Z)
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Optimal Algorithms for Stochastic Multi-Level Compositional Optimization [46.77664277596764]
  目的関数が複数の最適でない関数の制限である多段階合成最適化の問題を解く。 また,適応型多レベル分散低減法 (SMVR) を用いることで,同じ複雑性を実現するが,実際はより高速に収束する。
  論文  参考訳（メタデータ） (2022-02-15T16:02:32Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  機械学習に多くの応用がある非SBO問題を考察する。 本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-05T18:28:42Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Stochastic Recursive Variance Reduction for Efficient Smooth Non-Convex Compositional Optimization [20.410012564838933]
  構成最適化は、強化学習における価値関数の評価やポートフォリオ管理など、多くの重要な機械学習タスクで発生する。 本稿では, 一般的なスムーズな非帰納的設定における一般的な構成最適化について検討する。
  論文  参考訳（メタデータ） (2019-12-31T18:59:13Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。