論文の概要: The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
- arxiv url: http://arxiv.org/abs/2609.20687v1
- Date: Thu, 17 Sep 2026 16:55:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-20 08:55:54.388735
- Title: The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
- Title（参考訳）: 非双対設定におけるリプシッツ凸最適化の1次Oracle複雑度
- Abstract要約: 目的のための$ell_p$-ball上での1次ブラックボックス凸最適化について,$ell_q$-normで検討した。
我々の結果は一般に、実現可能な集合 $X$ と可能な下位次数の集合 $H$ が凸であり、中心対称であり、ミンマックスの定理の一種を認めるときに適用される。
- 参考スコア（独自算出の注目度）: 19.52344367809103
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study first-order black-box convex optimization over an $\ell_p$-ball for objectives Lipschitz in the $\ell_q$-norm, solving in the affirmative the nonsmooth version of the COLT open question (Guz15b) on whether the geometry of a smaller feasible set ($p < q$) can improve convergence rates in convex optimization, and matching prior lower bounds up to logarithmic factors. Our rates include \(\widetilde O(1/T)\) for convex Euclidean-Lipschitz optimization over the $\ell_1$-ball, improving on the $O(1/\sqrt{T})$ classical rate under general assumptions. The key technical device is a new online learning game, where the comparator is evaluated using the maximum of affine losses observed so far. We bound the value of this game above and below in terms of a combinatorial online learning quantity: the sequential fat-shattering dimension, which we characterize for the $\ell_p / \ell_q$ case. Our results generally apply when the feasible set $X$ and the set of possible subgradients $H$ are convex, centrally symmetric, and admit a type of minmax theorem, advancing on a fundamental question by Sridharan [Sri12, Section 10.1.2, Q3]. As a geometric consequence of our analysis, of independent interest, we obtain estimates for the expected distance of a convex hull of samples to their mean in several Banach geometries, a version of the celebrated Wendel's theorem (Wen62), but quantitative and for bounded general distributions as opposed to centrally symmetric ones.
- Abstract（参考訳）: 目的に対する$\ell_p$-ball上の一階ブラックボックス凸最適化について、Lipschitz in the $\ell_q$-norm, solve in the affirmative the nonsmooth version of the COLT open question (Guz15b) on the geometry of a small feasible set(p < q$) can improve convergence rate in convex optimization and matching prior lower bounds to logarithmic factors。
我々のレートは、凸ユークリッド-リプシッツ最適化の$\ell_1$-ballに対する \(\widetilde O(1/T)\) を含み、一般的な仮定の下では$O(1/\sqrt{T})$classic rateを改善する。
キーとなる技術装置は新しいオンライン学習ゲームであり、コンパレータはこれまでに観測されたアフィン損失の最大値を用いて評価される。
我々は、このゲームの価値を、組合せオンライン学習量、つまり、$\ell_p / \ell_q$のケースを特徴付けるシーケンシャルな脂肪散乱次元の観点から、上述と下記の値に縛り付ける。
我々の結果は一般に、実現可能な集合 $X$ と可能な下位次数の集合 $H$ が凸で中心対称であり、ミンマックスの定理の型を認め、スリダラン(Sri12, section 10.1.2, Q3) の基本的な問題に進むときに適用される。
解析の幾何学的帰結として、独立な興味から、いくつかのバナッハ測度においてサンプルの凸殻から平均までの平均までの距離の推定値を得る(ウェンデルの定理(英語版)(Wen62))が、中央対称のものと対照的に定量的で有界な一般分布に対してである。
関連論文リスト
- An Argmax Principle for Sum-of-Squares Relaxations on the Sphere [42.540924632302925]
単位球面上の最適化問題の総和緩和を解析するためのargmax原理を開発する。
私たちの指導原則は、最大値が丸みを帯びた候補であることです。
論文 参考訳（メタデータ） (2026-08-03T17:58:00Z) - Pointwise Complexity for Gaussian Fields: Upper Envelopes, Algorithmic Lower Bounds, and Separation [5.082462420126421]
中心ガウス過程に対する分散対応点ワイド・メジャー化測度定理を証明した。
この定理は古典的なジェネリックチェインのフィールドレベルの再利用可能な洗練を提供する。
アルゴリズム的下界は固定推定器の点次複雑性の局所幾何学的証明を提供することを示す。
論文 参考訳（メタデータ） (2026-06-06T01:50:06Z) - Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。
これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
論文 参考訳（メタデータ） (2026-05-22T15:05:33Z) - Intrinsic Wasserstein Rates for Score-Based Generative Models on Smooth Manifolds [61.14405512940818]
Scoreベースの生成モデルは高次元空間で訓練されていることを示す。
有限固有アンカーとガウス・ニュートンによる最も近い射影座標のReLU実装を用いる。
論文 参考訳（メタデータ） (2026-05-15T10:20:05Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - The Sample Complexity Of ERMs In Stochastic Convex Optimization [13.896417716930687]
実際に$tildeO(fracdepsilon+frac1epsilon2)$データポイントも十分であることを示す。
さらに、この結果を一般化し、全ての凸体に対して同様の上界が成り立つことを示す。
論文 参考訳（メタデータ） (2023-11-09T14:29:25Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization [11.017632675093628]
非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
論文 参考訳（メタデータ） (2022-06-30T02:17:11Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Thinking Outside the Ball: Optimal Learning with Gradient Descent for
Generalized Linear Stochastic Convex Optimization [37.177329562964765]
我々は凸リプシッツ損失を伴う線形予測、あるいはより一般に一般化線型形式の凸最適化問題を考える。
この設定では、初期反復が明示的な正規化や投影を伴わずにグラディエント Descent (GD) を停止し、過大なエラーを最大$epsilon$で保証することを示した。
しかし、標準球における一様収束は、$Theta (1/epsilon4)$サンプルを用いた最適下界学習を保証できることを示しているが、分布依存球における一様収束に依存している。
論文 参考訳（メタデータ） (2022-02-27T09:41:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。