Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization

DOI10.1137/1.9781611974782.82zbMath1422.90031arXiv1512.09170OpenAlexW2551387064MaRDI QIDQ4575825

Cristóbal Guzmán, Vitaly Feldman, Santosh Vempala

Publication date: 16 July 2018

Published in: Mathematics of Operations Research, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1512.09170

zbMATH Keywords

nonlinearconvexdataprogrammingstatisticsstochastic

Mathematics Subject Classification ID

Computational learning theory (68Q32) Convex programming (90C25) Stochastic programming (90C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ On the Power of Learning from k-Wise Queries ⋮ Lower Bounds for Parallel and Randomized Convex Optimization ⋮ Relaxation schemes for the joint linear chance constraint based on probability inequalities ⋮ Polynomial‐time universality and limitations of deep learning ⋮ Adversarial manifold estimation ⋮ Unnamed Item ⋮ Unnamed Item

Uses Software

• SuLQ

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• First-order methods of smooth convex optimization with inexact oracle
• On lower complexity bounds for large-scale smooth convex optimization
• Halfspace matrices
• Unconditional lower bounds for learning intersections of halfspaces
• Geometric algorithms and combinatorial optimization
• A polynomial-time algorithm for learning noisy linear threshold functions
• Learning with restricted focus of attention
• Sharp uniform convexity and smoothness inequalities for trace norms
• A linear lower bound on the unbounded error probabilistic communication complexity.
• Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm
• Martingales in Banach Spaces
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• Evolvability of Real Functions
• Interactive privacy via the median mechanism
• Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias
• Sum-of-squares Lower Bounds for Planted Clique
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• An Efficient Sparse Regularity Concept
• Candidate One-Way Functions Based on Expander Graphs
• What Can We Learn Privately?
• Efficient noise-tolerant learning from statistical queries
• The Algorithmic Foundations of Differential Privacy
• Smooth Optimization with Approximate Gradient
• On the Generalization Ability of On-Line Learning Algorithms
• Relations between average case complexity and approximation complexity
• A Characterization of Strong Learnability in the Statistical Query Model
• The Matching Polytope has Exponential Extension Complexity
• Rounding of Polytopes in the Real Number Model of Computation
• A Complete Characterization of Statistical Query Learning with Applications to Evolvability
• Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization
• Information-Based Complexity, Feedback and Dynamics in Convex Programming
• Uncertainty Principles and Vector Quantization
• Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory
• Algorithmic stability for adaptive data analysis
• Simulated Annealing for Convex Optimization
• Linear vs. semidefinite extended formulations
• Understanding Machine Learning
• Privacy Aware Learning
• Solving convex programs by random walks
• Theory of Cryptography
• A simple polynomial-time rescaling algorithm for solving linear programs
• Hadamard matrices and their applications

This page was built for publication: Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization