論文の概要: A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond $N^{4/3}$
- arxiv url: http://arxiv.org/abs/2609.29881v1
- Date: Thu, 24 Sep 2026 14:33:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-25 21:10:10.009683
- Title: A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond $N^{4/3}$
- Title（参考訳）: シェルソートのための新しいギャップシーケンス:$N^{4/3}$を超えるRL駆動アルゴリズム発見
- Abstract要約: 実行可能ギャップ生成器を探索するRL駆動自己教師システムを提案する。
全ての提案は構築によって有効であり、実行された候補は正確な比較と移動数を返す。
第2の自己監督段階は有限プレフィックスのみをチューニングし、実用的なシーケンスは1,38,20,47,116,300,585,1416,3303,ldots$である。
- 参考スコア（独自算出の注目度）: 3.4382180427019673
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Choosing Shellsort gaps is a well-known open problem. For over sixty years, successful sequences have relied on human-designed formulas, numerical searches, or number-theoretic constructions. Although stronger general bounds exist for dense or mainly theoretical families, the worst-case upper bound for a short, sparse, and practically competitive construction has not advanced beyond $N^{4/3}$ for decades. We ask whether the sequence itself can instead be learned from execution. We present an RL-driven, self-supervised system that searches over executable gap generators. Every proposal is valid by construction, and executed candidates return exact comparison and move counts; no classical sequence is used as a target. Across five independent searches, the system discovers a common rational-geometric family. A second self-supervised stage tunes only a finite prefix, producing the practical sequence $1,3,8,20,47,116,300,585,1416,3303,\ldots$. Once frozen, it obtains the lowest equal-task average operation count among seven classical baselines on 25 large tasks with $10^7<N\leq 10^8$. We complete the learned tail without changing its practical behavior: only beyond $10^{1000}$, a zero-density set of unit companions $h_s+1$ removes the remaining congruence barriers. The resulting sparse sequence has matching polynomial upper and lower exponents, up to polylogarithmic factors: $Ω(N^{1.024296451657\ldots}) \leq T(N) \leq O(N^{1.024296451657\ldots}\operatorname{polylog} N)$. The lower bound follows from Zang's recent theorem for rational-geometric sequences; our contribution is the matching upper bound. Thus one exact sequence connects self-supervised discovery, large-scale practical performance, and a substantial step below the classical $N^{4/3}$ bound for sparse practical Shellsort sequences.
- Abstract（参考訳）: シェルソートギャップの選択は、よく知られたオープンな問題である。
60年以上にわたって、成功したシーケンスは、人間によって設計された公式、数値探索、数論的な構成に依存してきた。
より強い一般境界は、密度の強い、あるいは主に理論上の族に対して存在するが、最悪のケース上の上限は、短く、スパースで、実用的な競争的な構造は、何十年もの間、N^{4/3} を超えるほど進歩していない。
シーケンス自体が実行から学べるかどうかを問う。
実行可能ギャップ生成器を探索するRL駆動自己教師システムを提案する。
全ての提案は構築によって有効であり、実行された候補は正確な比較と移動数を返す。
5つの独立した探索で、システムは共通の有理幾何学的なファミリーを発見する。
第2の自己監督段階は有限プレフィックスのみをチューニングし、実用的なシーケンスは1,3,8,20,47,116,300,585,1416,3303,\ldots$である。
凍結すると、25のタスクで10^7<N\leq 10^8$の古典的な7つのベースラインの中で、最小の等タスク平均演算数が得られる。
学習したテールは、その実践的振る舞いを変えることなく完結する: 10^{1000}$を超えると、単位共役の零密度集合が$h_s+1$で、残りの共役障壁を除去する。
結果として得られるスパース配列は多項式上および下限の指数を持ち、ポリ対数因子:$Ω(N^{1.024296451657\ldots}) \leq T(N) \leq O(N^{1.024296451657\ldots}\operatorname{polylog} N)$である。
下界は、Zang の最近の有理幾何学的列に対する定理(英語版)に従い、我々の寄与は一致する上界である。
このように、1つの正確なシーケンスは、自己教師付き発見、大規模な実用性能、そしてスパース実用的なシェルソート列に対する古典的な$N^{4/3}$バウンドよりかなり低いステップを接続する。
関連論文リスト
- A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。
我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文 参考訳（メタデータ） (2026-09-09T10:13:43Z) - Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid [31.45779401617503]
クナスター・タルスキーの不動点定理(Knaster-Tarski fixed-point theorem)は、完備格子上のすべての単調函数が不動点を持つという定理である。
非負スペクトル逆法を用いて、$[n]k$上の単調関数の固定点を求めるために、$(klog n)$量子クエリローバウンドを証明した。
論文 参考訳（メタデータ） (2026-09-03T13:06:12Z) - An Argmax Principle for Sum-of-Squares Relaxations on the Sphere [42.540924632302925]
単位球面上の最適化問題の総和緩和を解析するためのargmax原理を開発する。
私たちの指導原則は、最大値が丸みを帯びた候補であることです。
論文 参考訳（メタデータ） (2026-08-03T17:58:00Z) - Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
ハミルトニアン$H = sum_j h_j$ の場合、ゲート上の下界と量子コンピュータ上の時間発展をシミュレートするクエリの複雑さを証明できる。
任意の項ノルムのホールドは$|h_j|$, time $t$, trace-distance error $$である。
論文 参考訳（メタデータ） (2026-07-22T07:41:32Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Quantum Algorithms for Gowers Norm Estimation, Polynomial Testing, and Arithmetic Progression Counting over Finite Abelian Groups [0.0]
有限アーベル群上のゴワーズノルム$Uk$を推定するための量子アルゴリズム群を提案する。
これらのアルゴリズムは、ガウワーズノルムに対する最近の逆定理と振幅推定を利用して高次相関を明らかにする。
論文 参考訳（メタデータ） (2025-08-02T06:58:12Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳（メタデータ） (2022-11-10T00:40:37Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - A Robust Spectral Algorithm for Overcomplete Tensor Decomposition [10.742675209112623]
オーバーコンプリートオーダー4テンソルを分解するスペクトルアルゴリズムを提案する。
我々のアルゴリズムは、有界スペクトルノルムの逆摂動に対して頑健である。
本アルゴリズムは半定値プログラミングを回避し,一連の線形代数演算として実装することができる。
論文 参考訳（メタデータ） (2022-03-05T17:25:37Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。