論文の概要: Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates
- arxiv url: http://arxiv.org/abs/2609.20701v1
- Date: Thu, 17 Sep 2026 17:02:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-20 08:55:54.393435
- Title: Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates
- Title（参考訳）: 非双対リプシッツ凸最適化のための安定運動:効率とほぼ最適オラクルレート
- Abstract要約: 本稿では,G$-Lipschitz 凸関数の最適化の1次オラクル複雑性を実現するための効率的なアルゴリズムについて検討する。
提案したセレクタのモンテカルロ平均は、高い確率で最適に近い速度を達成する。
- 参考スコア（独自算出の注目度）: 13.0201223534445
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study efficient algorithms for realizing the first-order oracle complexity of optimization of $G$-Lipschitz convex functions with respect to the $\ell_{q}$-norm over an $\ell_{p}$-ball of radius $R$, where $1\leq p,q\leq \infty$. For $p<q$, we obtain error $\widetilde{O}_{p,q}(GR/T^{1/p-(1/q-1/2)_{+}})$ after $T$ oracle queries, efficiently realizing the nearly optimal rates of (MBG+26), thereby resolving the nonsmooth end of the COLT 2015 open problem (Guz15b). In particular, the rate is $\widetilde{O}(GR/T)$ for Euclidean Lipschitzness over an $\ell_1$-ball of radius $R$ ($p=1,q=2$). Our solution consists of reducing convex Lipschitz optimization to the chasing nested convex sets problem in sublevel sets of an evolving bundle (LNN95; BBE+20): at each query we either find a point with low function value or we produce a deep cut in the current sublevel of the bundle, that we chase. The dichotomy between stability of selectors and forced movement by deep cuts bounds the number of iterations of the algorithm near optimally. For nested subsets of $R B_{p}^{d}$, we introduce a novel notion of stable center whose movement is bounded by $\widetilde{O}_{p,q}(RT^{1-1/p+(1/q-1/2)_{+}})$ in the $\ell_{q}$-norm after $T$ steps, which we show is nearly optimal in high dimensions. A Monte Carlo average of the proposed selector achieves near-optimal rates with high probability and can be implemented in polynomial time for our optimization algorithm in the real-arithmetic model.
- Abstract（参考訳）: 我々は、$\ell_{p}$-ball of radius $R$の上の$\ell_{q}$-normに対して、$G$-Lipschitz convex関数の最適化の1次オラクル複雑性を実現するための効率的なアルゴリズムについて研究する。
for $p<q$, we obtained error $\widetilde{O}_{p,q}(GR/T^{1/p-(1/q-1/2)_{+}})$ after $T$ oracle query, efficient realizing the almosttim rate of (MBG+26), sosolving the nonsmooth end of the COLT 2015 open problem (Guz15b)。
特に、Euclidean Lipschitznessの$\widetilde{O}(GR/T)$は半径$R$(p=1,q=2$)の$\ell_1$-ballである。
我々の解は、展開バンドル(LNN95; BBE+20)のサブレベル集合における追尾ネスト凸集合問題に対する凸リプシッツ最適化を減少させることで構成される。
セレクタの安定性と深いカットによる強制運動の間の二分法は、アルゴリズムの反復回数をほぼ最適に制限する。
R B_{p}^{d}$ のネストされた部分集合に対して、運動が $\widetilde{O}_{p,q}(RT^{1-1/p+(1/q-1/2)_{+}})$ で有界な安定中心の概念を導入する。
提案したセレクタのモンテカルロ平均は、高い確率で近似速度を達成し、実算数モデルにおける最適化アルゴリズムの多項式時間で実装できる。
関連論文リスト
- Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory [65.64123585249297]
メモリが$m$ の単位球上の$d$ 次元 1$-Lipschitz 凸関数を最小化する。
まず、そのようなアルゴリズムは、$tilde(fracd2sqrtm)$ Oracle queryを作らなければならないことを示す。
決定論的最適化アルゴリズムでは$tilde(mind1.6,fracd8/3m2/3)$クエリが必要である。
論文 参考訳（メタデータ） (2026-07-21T00:40:59Z) - Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
論文 参考訳（メタデータ） (2025-08-09T08:28:06Z) - Non-Euclidean High-Order Smooth Convex Optimization [9.940728137241214]
我々はH"より古い連続$q$-th微分を持つ凸対象の最適化のためのアルゴリズムを開発する。
提案アルゴリズムは,1leq pleq infty$ に対して $ell_p$-settings を含む,穏やかな条件下での一般ノルムに対して作用する。
論文 参考訳（メタデータ） (2024-11-13T19:22:34Z) - Oblivious Stochastic Composite Optimization [47.48197617884748]
我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。
3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。
我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Quadratic Memory is Necessary for Optimal Query Complexity in Convex
Optimization: Center-of-Mass is Pareto-Optimal [23.94542304111204]
本研究では,1次凸最適化に最適なオラクル複雑性を実現するためには,二次記憶が必要であることを示す。
単位球上の1ドルのLipschitz凸関数を1/d4$精度で最小化するためには、少なくともd2-delta$ビットのメモリを使用する決定論的一階述語アルゴリズムは$tildeOmega(d1+delta/3)$クエリを生成する必要がある。
論文 参考訳（メタデータ） (2023-02-09T22:37:27Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization [21.334985032433778]
分散最適化問題 $min_bf xinmathbb Rd f(bf x)triq frac1msum_i=1m f_i(bf x)triq frac1nsum_j=1n。
論文 参考訳（メタデータ） (2022-10-25T11:37:11Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - Near-Optimal Lower Bounds For Convex Optimization For All Orders of
Smoothness [26.71898403195793]
非常に滑らかな凸関数を最適化する複雑性について検討する。
正の整数 $p$ に対して、凸関数 $f$ の最小値 $epsilon$-approximate を求める。
我々は、この境界(ログファクタまで)にマッチする新しい下界を証明し、ランダム化アルゴリズムだけでなく、量子アルゴリズムにも適用する。
論文 参考訳（メタデータ） (2021-12-02T10:51:43Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。