論文の概要: Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness

• arxiv url: http://arxiv.org/abs/2609.00045v1
• Date: Sun, 30 Aug 2026 02:47:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-02 16:31:35.758289
• Title: Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness
• Title（参考訳）: デンス弱ハディング:非凸における複雑ギャップの閉鎖と個々人の平滑さ下でのPL有限和最適化
• Abstract要約: 我々は、各$_maxgeq 3$に対して、個々の滑らかさの下で下界に一致することを証明した。 また、各$_maxgeq 3$に対して、個々の滑らかさの下で下界が一致することを証明する。
• 参考スコア（独自算出の注目度）: 8.428362872515416
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Under individual smoothness, the optimal incremental first-order oracle (IFO) complexity of nonconvex finite-sum optimization has remained open. Known algorithms use $O(n+\sqrt{n}\,ΔL_{\max}/\varepsilon^2)$ calls, while prior lower bounds miss a factor of $\sqrt{n}$. We prove the matching lower bound for randomized IFO algorithms whose component indices and query points may depend on the complete preceding transcript and private randomness. This determines the minimax IFO complexity up to universal constants under both individual and mean-squared smoothness. Under the global Polyak-Lojasiewicz (PL) condition, the standard PAGE guarantee is not tight when $κ_{\mathrm{ms}}<\sqrt{n}$. Restarted PAGE attains $O(n+n\log(Δ/\varepsilon)/(1+\log(\sqrt{n}/κ_{\mathrm{ms}})))$ for $1\leqκ_{\mathrm{ms}}\leq\sqrt{n}$, and $O(n+κ_{\mathrm{ms}}\sqrt{n}\log(Δ/\varepsilon))$ for $κ_{\mathrm{ms}}\geq\sqrt{n}$. We prove matching lower bounds under individual smoothness for every $κ_{\max}\geq 3$; the same hard instances also give the mean-squared lower bounds. In the small-$κ_{\max}$ range, their average objective is globally strongly convex. Our lower bounds use dense weak hiding. A fixed sign table spreads each hidden direction across the components. Each queried row carries little information, while the exact row average preserves the full signal after rescaling. A bounded radial map handles arbitrary query points, and a smooth gate makes unopened links invisible to both function values and gradients. Balancing the rows needed to reveal one stage with the number of stages allowed by individual smoothness yields the missing $\sqrt{n}$ factor.
• Abstract（参考訳）: 個々人の滑らかさの下では、非凸有限サム最適化の最適インクリメンタル一階オラクル(IFO)の複雑さは未解決のままである。 既知のアルゴリズムは$O(n+\sqrt{n}\,ΔL_{\max}/\varepsilon^2)$コールを使用する。 IFOアルゴリズムのパラメータと問合せ点が、前回の書き起こしと私的ランダム性に依存している場合、一致した下界を証明した。 これにより、ミニマックス IFO の複雑性は、個人と平均二乗の滑らかさの両方の下で普遍定数まで決定される。 グローバルなPolyak-Lojasiewicz (PL) 条件の下では、標準 PAGE 保証は $κ_{\mathrm{ms}}<\sqrt{n}$ のとき厳密でない。 再起動された PAGE は $O(n+n\log(Δ/\varepsilon)/(1+\log(\sqrt{n}/κ_{\mathrm{ms}}))$ for $1\leqκ_{\mathrm{ms}}\leq\sqrt{n}$, and $O(n+κ_{\mathrm{ms}}\sqrt{n}\log(Δ/\varepsilon))$ for $κ_{\mathrm{ms}}\geq\sqrt{n}$である。 我々は、各$κ_{\max}\geq 3$ に対して、個々の滑らかさの下で下界が一致することを証明する。 小さな$κ_{\max}$範囲では、それらの平均的な目的は、大まかに凸である。 我々の下限は密度の弱い隠蔽を使う。 固定記号テーブルは、各隠れた方向をコンポーネントに広げる。 クエリされた各行は、ほとんど情報を持たないが、正確な行平均は、再スケーリング後に全信号を保存する。 有界ラジアル写像は任意のクエリポイントを処理し、滑らかなゲートは、関数値と勾配の両方に非開リンクを見えないものにする。 行のバランシングは、個々の滑らかさによって許されるステージの数で1つのステージを明らかにするのに必要なもので、欠けている$\sqrt{n}$ factorをもたらす。

関連論文リスト

• Quantum Query Complexity of Persistence Statistics in Graph Zigzags [2.895030292351388]
  本研究では、スナップショット・アジャシエンスビットからジグザグバー寿命のスカラーサマリーを推定するクエリ複雑性について検討した。 ランクがグラフの回路ランクであるグラフの場合、非線形バーコード関数はエッジと成分数の平均となる。 すべての固定パワーウェイトに対して$xr$,$rge2$、均一ウィンドウ平均では、最悪のケースの複雑さは$widetilde(nsqrt m/varepsilon)$ Quantumと$(n2m)$ classicalである。
  論文  参考訳（メタデータ） (2026-09-05T02:16:28Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• 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)
• Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity [22.615156512223763]
  本研究では,有限サム構造を目的とする分散楽観的すべり(SVOGS)法を提案する。 我々は$mathcal O(delta D2/varepsilon)$、$mathcal O(n+sqrtndelta D2/varepsilon)$、$tildemathcal O(n+sqrtndelta+L)D2/varepsilon)$の局所呼び出しを証明している。
  論文  参考訳（メタデータ） (2024-05-25T08:34:49Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• 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)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods [39.87865197769047]
  分離可能なミニマックス最適化問題 $min_x max_y f(x) - g(y) + h(x, y)$, where $f$ and $g$ have smoothness and strong convexity parameters $(Lx, mux)$, $(Ly, muy)$, and $h$ is convex-concave with a $(Lambdaxx, Lambdaxy, Lambdayymuyright)$。
  論文  参考訳（メタデータ） (2022-02-09T18:57:47Z)
• Decentralized Stochastic Variance Reduced Extragradient Method [25.21457349137344]
  本稿では,$min_xmax_y fx,y triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumiの分散凸-凹極小最適化問題を考察する。
  論文  参考訳（メタデータ） (2022-02-01T16:06:20Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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