論文の概要: Learning and Testing Convex Functions

• arxiv url: http://arxiv.org/abs/2511.11498v1
• Date: Fri, 14 Nov 2025 17:19:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-17 22:42:18.740475
• Title: Learning and Testing Convex Functions
• Title（参考訳）: 凸関数の学習とテスト
• Authors: Renato Ferreira Pinto, Cassandra Marcussen, Elchanan Mossel, Shivam Nadimpalli,
• Abstract要約: 本稿では,ガウス空間上の実数値凸関数の学習と証明の問題について考察する。 数学における関数の凸性に関する広範な研究にもかかわらず、その学習可能性とテスト容易性は、主に離散的あるいは限定的な設定でのみ検討されている。
• 参考スコア（独自算出の注目度）: 18.95992615547965
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We consider the problems of \emph{learning} and \emph{testing} real-valued convex functions over Gaussian space. Despite the extensive study of function convexity across mathematics, statistics, and computer science, its learnability and testability have largely been examined only in discrete or restricted settings -- typically with respect to the Hamming distance, which is ill-suited for real-valued functions. In contrast, we study these problems in high dimensions under the standard Gaussian measure, assuming sample access to the function and a mild smoothness condition, namely Lipschitzness. A smoothness assumption is natural and, in fact, necessary even in one dimension: without it, convexity cannot be inferred from finitely many samples. As our main results, we give: - Learning Convex Functions: An agnostic proper learning algorithm for Lipschitz convex functions that achieves error $\varepsilon$ using $n^{O(1/\varepsilon^2)}$ samples, together with a complementary lower bound of $n^{\mathrm{poly}(1/\varepsilon)}$ samples in the \emph{correlational statistical query (CSQ)} model. - Testing Convex Functions: A tolerant (two-sided) tester for convexity of Lipschitz functions with the same sample complexity (as a corollary of our learning result), and a one-sided tester (which never rejects convex functions) using $O(\sqrt{n}/\varepsilon)^n$ samples.
• Abstract（参考訳）: 本稿では,ガウス空間上の実数値凸関数の問題を考察する。 数学、統計学、計算機科学にまたがる関数の凸性に関する広範な研究にもかかわらず、学習可能性とテスト容易性は離散的あるいは制限された環境でのみ研究されてきた。 対照的に、これらの問題を標準ガウス測度の下で高次元で研究し、関数へのサンプルアクセスと軽度な滑らかさ条件、すなわちリプシッツネスを仮定する。 滑らかさの仮定は自然であり、実際は1次元においても必要である:それなしでは、凸性は有限個のサンプルから推測することはできない。 主な結果として, - Learning Convex Functions: A agnostic proper learning algorithm for Lipschitz convex function that achieve a error $\varepsilon$ using $n^{O(1/\varepsilon^2)}$ sample, with a complementary lower bound of $n^{\mathrm{poly}(1/\varepsilon)} $ sample in the \emph{correlational statistical query (CSQ) model。 -凸関数のテスト:Lipschitz関数の凸性に対する耐性(両側)テスタと、サンプルO(\sqrt{n}/\varepsilon)^n$を使用する一方(凸関数を決して拒否しない)テスタ。

関連論文リスト

• Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions [41.43895948769255]
  非滑らかな非漸近公正問題のクラスを$min_x[yin Yphi(x, y) - max_zin Zpsix(x, z)]$の形で示す。 本稿では,これらの問題を解く最初の方法であるエンベロープ近似勾配SMAGを提案する。
  論文  参考訳（メタデータ） (2024-05-28T20:52:46Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• The Sample Complexity Of ERMs In Stochastic Convex Optimization [13.896417716930687]
  実際に$tildeO(fracdepsilon+frac1epsilon2)$データポイントも十分であることを示す。 さらに、この結果を一般化し、全ての凸体に対して同様の上界が成り立つことを示す。
  論文  参考訳（メタデータ） (2023-11-09T14:29:25Z)
• 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)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  高確率状態に着目して離散分布を試験する問題について検討する。 一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-14T16:09:17Z)
• Downsampling for Testing and Learning in Product Distributions [24.48103093661132]
  未知確率分布が $mathbbRd$ 上の積分布であるような分布自由なプロパティテストと学習問題について検討する。 ハーフスペースの交叉、しきい値関数、凸集合、および$k$交互関数などの多くの重要な関数のクラスでは、既知のアルゴリズムは、分布のサポートサイズに依存する複雑さを持つ。 本稿では,これらの問題を解消する一般手法として,ダウンログ(downlog)を提案する。
  論文  参考訳（メタデータ） (2020-07-15T02:46:44Z)
• Convex Regression in Multidimensions: Suboptimality of Least Squares Estimators [4.758195657080579]
  最小二乗推定器は、$d$が5以上の場合の2乗誤差損失において$d$次元凸関数を推定するのに最適である。 i)ポリトープでサポートされている有界凸関数(ランダム設計)、(ii)任意の凸領域でサポートされているリプシッツ凸関数(ランダム設計)、(iii)ポリトープでサポートされている凸関数(固定設計)である。
  論文  参考訳（メタデータ） (2020-06-03T04:57:05Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)

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

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