Fugu-MT 論文翻訳(概要): A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model

論文の概要: A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model

arxiv url: http://arxiv.org/abs/2609.30215v1
Date: Thu, 24 Sep 2026 17:45:58 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-25 21:10:10.181078
Title: A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
Title（参考訳）: 会員Oracleモデルにおける凸体上の線形最適化のためのほぼ2次下界
Abstract要約: 線形最適化と凸体上の一様サンプリングのためのランダム化アルゴリズムに対して, ほぼ2次下界を証明した。我々の構成は、体積推定において同じ下限をも意味している。
参考スコア（独自算出の注目度）: 11.005676530963887
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We prove nearly quadratic lower bounds for randomized algorithms for linear optimization and uniform sampling over convex bodies in the membership oracle model. For linear optimization, this matches the known nearly quadratic upper bound up to a polylog factor in the dimension. For uniform sampling, this improves on the previous linear lower bound. Our construction also implies the same lower bound for volume estimation.
Abstract（参考訳）: 線形最適化と一様サンプリングのためのランダム化アルゴリズムに対して,会員オラクルモデルにおける凸体上のほぼ2次下界を証明した。線形最適化では、これは次元のポリログ因子までの既知の2次上界と一致する。均一サンプリングでは、これは以前の線形下界を改善する。我々の構成は、体積推定において同じ下限をも意味している。

関連論文リスト

GPU-friendly and Linearly Convergent First-order Methods for Certifying Optimal $k$-sparse GLMs [7.079949618914198]
ブランチ・アンド・バウンド(BnB)フレームワークは、パースペクティブ・リラクゼーションを使って最適性を証明できる。これらの緩和を解く既存の手法は計算集約的であり、スケーラビリティを制限している。我々は線形収束性と計算効率の両立した近位フレームワークを開発する。
論文参考訳（メタデータ） (2026-03-01T22:26:09Z)
Scalable Approximate Algorithms for Optimal Transport Linear Models [0.769672852567215]
エントロピー規則化OTデータフィット項を用いた非線形回帰モデルの一般クラスを解くための新しい枠組みを提案する。一般的なペナルティとデータ適合の条件に対する単純な乗法的更新を導出する。本手法は,実装の単純さと並列化の容易さから,大規模問題に適した手法である。
論文参考訳（メタデータ） (2025-04-06T20:37:25Z)
Differentially Private Optimization with Sparse Gradients [60.853074897282625]
微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
論文参考訳（メタデータ） (2024-04-16T20:01:10Z)
On the Partial Convexification for Low-Rank Spectral Optimization: Rank Bounds and Algorithms [1.7640556247739623]
低ランクスペクトル最適化問題(LSOP)は、複数の二辺行列の不等式を対象とする線形対象を最小化する。 LSOPの解法は一般にNPハードであるが、「LSOP-R」と呼ばれる部分凸化はしばしば抽出可能であり、高品質な解が得られる。
論文参考訳（メタデータ） (2023-05-12T17:46:29Z)
Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文参考訳（メタデータ） (2023-02-24T18:41:48Z)
Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文参考訳（メタデータ） (2021-01-19T04:24:23Z)
Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文参考訳（メタデータ） (2020-04-23T05:00:21Z)
Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文参考訳（メタデータ） (2020-02-21T17:45:32Z)
Geometry, Computation, and Optimality in Stochastic Optimization [24.154336772159745]
問題幾何学の計算および統計的結果とオンライン最適化について検討する。制約集合と勾配幾何学に焦点をあてて、どの次法と適応次法が最適(minimax)であるかという問題族を特徴づける。
論文参考訳（メタデータ） (2019-09-23T16:14:26Z)

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