Buchumschlag

Omnipredictors for Regression and the Approximate Rank of Convex Functions

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Gopalan, Parikshit, Okoroafor, Princewill, Raghavendra, Prasad, Shetty, Abhishek, Singhal, Mihir
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Machine Learning Computational Complexity Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

The communication complexity of distributed estimation
von: Gopalan, Parikshit, et al.
Veröffentlicht: (2025)

On Computationally Efficient Multi-Class Calibration
von: Gopalan, Parikshit, et al.
Veröffentlicht: (2024)

Near-Optimal Algorithms for Omniprediction
von: Okoroafor, Princewill, et al.
Veröffentlicht: (2025)

On optimal distinguishers for Planted Clique
von: Nagda, Ansh, et al.
Veröffentlicht: (2025)

Exact and Approximate Algorithms for Polytree Learning
von: Harviainen, Juha, et al.
Veröffentlicht: (2026)

On the Hardness of Approximation of the Fair k-Center Problem
von: Thejaswi, Suhas
Veröffentlicht: (2026)

Hardness of Learning Boolean Functions from Label Proportions
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

Breaking the $T^{2/3}$ Barrier for Sequential Calibration
von: Dagan, Yuval, et al.
Veröffentlicht: (2024)

Efficient Convex Optimization Requires Superlinear Memory
von: Marsden, Annie, et al.
Veröffentlicht: (2022)

Maximization of Approximately Submodular Functions
von: Horel, Thibaut, et al.
Veröffentlicht: (2024)

On Approximability of $\ell_2^2$ Min-Sum Clustering
von: S., Karthik C., et al.
Veröffentlicht: (2024)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
von: Dhawan, Abhishek, et al.
Veröffentlicht: (2024)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

Diversity-aware clustering: Computational Complexity and Approximation Algorithms
von: Thejaswi, Suhas, et al.
Veröffentlicht: (2024)

Superconstant Inapproximability of Decision Tree Learning
von: Koch, Caleb, et al.
Veröffentlicht: (2024)

Fast decision tree learning solves hard coding-theoretic problems
von: Koch, Caleb, et al.
Veröffentlicht: (2024)

Adaptive and oblivious statistical adversaries are equivalent
von: Blanc, Guy, et al.
Veröffentlicht: (2024)

Private graphon estimation via sum-of-squares
von: Chen, Hongjie, et al.
Veröffentlicht: (2024)

On the Power of Interactive Proofs for Learning
von: Gur, Tom, et al.
Veröffentlicht: (2024)

Low-degree phase transitions for detecting a planted clique in sublinear time
von: Mardia, Jay, et al.
Veröffentlicht: (2024)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
von: Blanc, Guy, et al.
Veröffentlicht: (2024)

Differentially Private Verification of Distribution Properties
von: Du, Elbert, et al.
Veröffentlicht: (2026)

Efficient and Private Property Testing via Indistinguishability
von: Dwork, Cynthia, et al.
Veröffentlicht: (2025)

A Distributional-Lifting Theorem for PAC Learning
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

Low-Degree Method Fails to Predict Robust Subspace Recovery
von: Jia, He, et al.
Veröffentlicht: (2026)

Feature Selection and Junta Testing are Statistically Equivalent
von: Beretta, Lorenzo, et al.
Veröffentlicht: (2025)

Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection
von: Sato, Atsuki, et al.
Veröffentlicht: (2025)

Samplability makes learning easier
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

Efficient Turing Machine Simulation with Transformers
von: Li, Qian, et al.
Veröffentlicht: (2025)

The Sample Complexity of Replicable Realizable PAC Learning
von: Larsen, Kasper Green, et al.
Veröffentlicht: (2026)

Is nasty noise actually harder than malicious noise?
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

Active Learning for Decision Trees with Provable Guarantees
von: Moakhar, Arshia Soltani, et al.
Veröffentlicht: (2026)

Rate-optimal community detection near the KS threshold via node-robust algorithms
von: Ding, Jingqiu, et al.
Veröffentlicht: (2025)

Computational-Statistical Tradeoffs from NP-hardness
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

Learning-Augmented Algorithms for Boolean Satisfiability
von: Attias, Idan, et al.
Veröffentlicht: (2025)

The Computational Complexity of Almost Stable Clustering with Penalties
von: Khodamoradi, Kamyar, et al.
Veröffentlicht: (2025)

AdaBoost is not an Optimal Weak to Strong Learner
von: Høgsgaard, Mikael Møller, et al.
Veröffentlicht: (2023)

Hardness of Maximum Likelihood Learning of DPPs
von: Grigorescu, Elena, et al.
Veröffentlicht: (2022)

Supersimulators
von: Dwork, Cynthia, et al.
Veröffentlicht: (2025)

Lower Bounds for Convexity Testing
von: Chen, Xi, et al.
Veröffentlicht: (2024)