Stochastic Estimation of the Maximum of a Regression Function

1952/09/01 by J. Kiefer, J. Wolfowitz · 2,177 citations
Engineering · Mathematics · #Advanced Control Systems Optimization #Applied mathematics #Combinatorics #Control Systems and Identification #Estimation #Function (biology) #Geometry #Mathematics #Point (geometry) #Regression #Regression analysis #Regression function #Statistician #Statistics

paper · pdf · doi:10.1214/aoms/1177729392

published in The Annals of Mathematical Statistics 23(3), 462-466 (Institute of Mathematical Statistics)

openalex publication_date 1952/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

Abstract

Let M(x) be a regression function which has a maximum at the unknown point θ. M(x) is itself unknown to the statistician who, however, can take observations at any level x. This paper gives a scheme whereby, starting from an arbitrary point x₁, one obtains successively x₂, x₃, ⋯ such that x_n converges to θ in probability as n → ∞.

Citations

• A Stochastic Approximation Method

Cited by

• The Modern Mathematics of Deep Learning
• Stochastic optimization on matrices and a graphon McKean–Vlasov limit
• Distributed stochastic gradient tracking methods
• Generalisation under gradient descent via deterministic PAC-Bayes
• Training Neural Networks with an algorithm for piecewise linear functions
• A trust-region method for derivative-free nonlinear constrained stochastic optimization
• Limit theorems for stochastic approximation algorithms
• Episodic Exploration for Deep Deterministic Policies: An Application to\n StarCraft Micromanagement Tasks
• Compositional Stochastic Average Gradient for Machine Learning and Related Applications
• On the Fundamental Limit of the Stochastic Gradient Identification Algorithm Under Non-Persistent Excitation
• OpenCML: End-to-End Framework of Open-world Machine Learning to Learn Unknown Classes Incrementally
• Mitigating Recommendation Biases via Group-Alignment and Global-Uniformity in Representation Learning
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
• Dynamically Addressing Unseen Rumor via Continual Learning
• Optimising Density Computations in Probabilistic Programs via Automatic Loop Vectorisation
• Coordinate Descent for Network Linearization
• Private Zeroth-Order Optimization with Public Data
• A Class of Multi-particle Reinforced Interacting Random Walks
• Online Covariance Matrix Estimation in Stochastic Gradient Descent
• Scalable Perturbation Learning for Online Self-Supervised Learning in Echo State Networks
• Lifelong Graph Learning
• Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions
• Comparison-Based Algorithms for One-Dimensional Stochastic Convex Optimization
• Subgradient Methods for Nonsmooth Convex Functions with Adversarial Errors
• Dilated Convolutions with Lateral Inhibitions for Semantic Image Segmentation
• Variational Policy Gradient Method for Reinforcement Learning with General Utilities
• Convergence in Models with Bounded Expected Relative Hazard Rates
• Multi-Resolution Model Fusion for Accelerating the Convolutional Neural Network Training
• Training Across Reservoirs: Using Numerical Differentiation To Couple Trainable Networks With Black-Box Reservoirs
• Maximum likelihood estimation of regularisation parameters in high-dimensional inverse problems: an empirical Bayesian approach. Part II: Theoretical Analysis
• Dopamine-driven synaptic credit assignment in neural networks
• Convergence Analysis of SGD under Expected Smoothness
• Query-Efficient Zeroth-Order Algorithms for Nonconvex Constrained Optimization
• A Unified Perspective on Optimization in Machine Learning and Neuroscience: From Gradient Descent to Neural Adaptation
• Uncertainty Quantification for Online Learning and Stochastic Approximation via Hierarchical Incremental Gradient Descent
• A Unified Zeroth-Order Optimization Framework via Oblivious Randomized Sketching
• Statistical Guarantees for High-Dimensional Stochastic Gradient Descent
• Noisy Optimization: Fast Convergence Rates with Comparison-Based Algorithms
• Generalize Symbolic Knowledge With Neural Rule Engine
• Shapley Interpretation and Activation in Neural Networks
• Differentiable Learning Under Triage
• A regret minimization approach to fixed-point iterations
• Effective continuous equations for adaptive SGD: a stochastic analysis view
• High-probability zeroth-order online convex optimisation beyond Euclidean geometry
• Training Continuously‐Coupled Reconfigurable Photonic Chips with Quantum Machine Learning
• Stochastic Approximation with Markov Noise: Analysis and applications in reinforcement learning
• Almost sure convergence of dropout algorithms for neural networks
• Distributed Learning for Proportional-Fair Resource Allocation in Coexisting WiFi Networks
• Model-Free Primal-Dual Methods for Network Optimization with Application to Real-Time Optimal Power Flow
• Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methods
• Scalability vs. Utility: Do We Have to Sacrifice One for the Other in Data Importance Quantification?
• Global Convergence and Acceleration for Single Observation Gradient Free Optimization
• Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation
• Positive-Congruent Training: Towards Regression-Free Model Updates
• Parameter Estimation for the SEIR Model Using Recurrent Nets
• Change Detection with Sparse Signals using Quantum Designs
• Adaptive Heavy-Tailed Stochastic Gradient Descent
• Revisit Stochastic Gradient Descent for Strongly Convex Objectives: Tight Uniform-in-Time Bounds
• Assessment of Reward Functions in Reinforcement Learning for Multi-Modal Urban Traffic Control under Real-World limitations
• DeepMerge: Classifying High-redshift Merging Galaxies with Deep Neural Networks
• An optimal experimental design approach to sensor placement in continuous stochastic filtering
• Search of RRATs on declinations from +42^∘ to +55^∘ with a neural network
• A Flocking-based Approach for Distributed Stochastic Optimization
• Audio-Visual Speech Enhancement: Architectural Design and Deployment Strategies
• Auto-Encoding Sequential Monte Carlo
• CGAP2: Context and gap aware predictive pose framework for early detection of gestures
• Domain Adaptation with Incomplete Target Domains
• Scandalously Parallelizable Mesh Generation
• Computational Advantages of Multi-Grade Deep Learning: Convergence Analysis and Performance Insights
• Stochastic Search with an Observable State Variable
• A Dimension-free Algorithm for Contextual Continuum-armed Bandits
• Sparse Stochastic Zeroth-Order Optimization with an Application to Bandit Structured Prediction
• SGD with Coordinate Sampling: Theory and Practice
• Robust Medical Instrument Segmentation Challenge 2019
• Domain2Vec: Domain Embedding for Unsupervised Domain Adaptation
• PatchGuard: A Provably Robust Defense against Adversarial Patches via Small Receptive Fields and Masking
• High Quality Related Search Query Suggestions using Deep Reinforcement Learning
• Kiefer Wolfowitz Algorithm is Asymptotically Optimal for a Class of Non-Stationary Bandit Problems
• Learning Image Attacks toward Vision Guided Autonomous Vehicles
• Taming Convergence for Asynchronous Stochastic Gradient Descent with Unbounded Delay in Non-Convex Learning
• Comparative validation of surgical phase recognition, instrument keypoint estimation, and instrument instance segmentation in endoscopy: Results of the PhaKIR 2024 challenge
• A Topic Guided Pointer-Generator Model for Generating Natural Language Code Summaries
• Inference by Stochastic Optimization: A Free-Lunch Bootstrap
• Exploiting Contextual Information with Deep Neural Networks
• Parameter estimation using simultaneous perturbation stochastic approximation
• Label Mapping Neural Networks with Response Consolidation for Class Incremental Learning
• PICCOLO: Point Cloud-Centric Omnidirectional Localization
• Gaussian MRF Covariance Modeling for Efficient Black-Box Adversarial Attacks
• Thompson Sampling Guided Stochastic Searching on the Line for Deceptive Environments with Applications to Root-Finding Problems
• Fast and Accurate Stellar Mass Predictions from Broad-Band Magnitudes with a Simple Neural Network: Application to Simulated Star-Forming Galaxies
• Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm
• Convergence Rate for the Last Iterate of Stochastic Gradient Descent Schemes
• Online Learning as Stochastic Approximation of Regularization Paths
• SGD with shuffling: optimal rates without component convexity and large epoch requirements
• Addressing Algorithmic Bottlenecks in Elastic Machine Learning with Chicle
• Identifying and Analyzing Sepsis States: A Retrospective Study on Patients with Sepsis in ICUs
• Breaking a Logarithmic Barrier in the Stopping Time Convergence Rate of Stochastic First-order Methods
• Consequential Ranking Algorithms and Long-term Welfare
• Learning Threshold-Type Investment Strategies with Stochastic Gradient Method
• Prediction of Hereditary Cancers Using Neural Networks
• Regular Tree Search for Simulation Optimization
• A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning
• A Stochastic Successive Minimization Method for Nonsmooth Nonconvex Optimization with Applications to Transceiver Design in Wireless Communication Networks
• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• Differential Privacy in Machine Learning: From Symbolic AI to LLMs
• Stochastic Heavy Ball
• Convergence of Momentum-Based Optimization Algorithms with Time-Varying Parameters
• Revisiting Révész's stochastic approximation method for the estimation of a regression function
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets
• Developing a Bubble Chamber Particle Discriminator Using Semi-Supervised Learning
• Lipschitz constants in experimental optimization
• On Stochastic Gradient and Subgradient Methods with Adaptive Steplength\n Sequences
• Thompson Sampling for Unimodal Bandits
• Online Asynchronous Distributed Regression
• Graph-based Knowledge Distillation by Multi-head Attention Network
• Regret in Online Combinatorial Optimization
• Nonparametric Learning Algorithms for Joint Pricing and Inventory Control with Lost Sales and Censored Demand
• Fair Decisions Despite Imperfect Predictions
• Stochastic Gradient Descent on a Tree: an Adaptive and Robust Approach to Stochastic Convex Optimization
• Adversarial Reinforcement Learning: A Duality-Based Approach To Solving Optimal Control Problems
• Wasserstein Distance Maximizing Intrinsic Control
• Random directions stochastic approximation with deterministic perturbations
• Screening for Sparse Online Learning
• Stochastic Approximation, Cooperative Dynamics and Supermodular Games
• Stochastic Euler Schemes and Dissipative Evolutions in the Space of Probability Measures
• A Bayesian Perspective of Convolutional Neural Networks through a Deconvolutional Generative Model
• Scaling Recurrent Neural Networks to a Billion Parameters with Zero-Order Optimization
• Behaviour Suite for Reinforcement Learning
• Online Statistical Inference of Constrained Stochastic Optimization via Random Scaling
• StoMADS: Stochastic blackbox optimization using probabilistic estimates
• Subgradient-Free Stochastic Optimization Algorithm for Non-smooth Convex Functions over Time-Varying Networks
• Stochastic optimization for numerical evaluation of imprecise probabilities
• A Selective Overview of Deep Learning
• Smoothed SGD for quantiles: Bahadur representation and Gaussian approximation
• Bias-Variance Tradeoff in a Sliding Window Implementation of the Stochastic Gradient Algorithm
• Convergence Rates of Finite Difference Stochastic Approximation Algorithms
• Revisiting Stochastic Approximation and Stochastic Gradient Descent
• The stochastic Auxiliary Problem Principle in Banach spaces: measurability and convergence
• Orthogonal-Padé Activation Functions: Trainable Activation functions for smooth and faster convergence in deep networks
• Federated Adversarial Domain Adaptation
• Self-supervised Knowledge Distillation Using Singular Value Decomposition
• KML: Using Machine Learning to Improve Storage Systems
• Predicting the Computational Cost of Deep Learning Models
• A Stochastic forward-backward splitting method for solving monotone inclusions in Hilbert spaces
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework
• Optimal experimental design and some related control problems
• A companion for the Kiefer–Wolfowitz–Blum stochastic approximation algorithm
• Optimum Experimental Designs
• Simulation-based Optimization of Toll Pricing in Large-Scale Urban Networks using the Network Fundamental Diagram: A Cross-Comparison of Methods
• Quantile estimation with adaptive importance sampling
• Finding best approximation pairs for two intersections of closed convex sets
• Optimal minimization of an unknown function in a nonparametric multivariate regression model thanks to a dimension reduction approach
• Stochastic proximal gradient methods for nonconvex problems in Hilbert spaces
• Robust and efficient algorithms for high-dimensional black-box quantum optimization
• GRADIENT-BASED STOCHASTIC OPTIMIZATION METHODS IN BAYESIAN EXPERIMENTAL DESIGN
• ORTHOSEG: A DEEP MULTIMODAL CONVOLUTONAL NEURAL NETWORK ARCHITECTURE FOR SEMANTIC SEGMENTATION OF ORTHOIMAGERY
• EXPLICIT HESTON SOLUTIONS AND STOCHASTIC APPROXIMATION FOR PATH-DEPENDENT OPTION PRICING
• Ensemble Kalman inversion: a derivative-free technique for machine learning tasks
• VecHGrad for Solving Accurately Complex Tensor Decomposition
• How Learnable Grids Recover Fine Detail in Low Dimensions: A Neural Tangent Kernel Analysis of Multigrid Parametric Encodings
• An overview of SPSA: recent development and applications
• Faster State Preparation across Quantum Phase Transition Assisted by Reinforcement Learning
• A proximal subgradient method for nonconvex stochastic optimization under the Kurdyka-Łojasiewicz condition
• Deriving the Gradients of Some Popular Optimal Transport Algorithms
• Recognition of Human Activities Using Continuous Autoencoders with Wearable Sensors. [europepmc]
• DeepPoseKit, a software toolkit for fast and robust animal pose estimation using deep learning. [europepmc]
• DeepSuccinylSite: a deep learning based approach for protein succinylation site prediction. [europepmc]
• Recognition and Repetition Counting for Local Muscular Endurance Exercises in Exercise-Based Rehabilitation: A Comparative Study Using Artificial Intelligence Models. [europepmc]
• Predicting aggressive histopathological features in esophageal cancer with positron emission tomography using a deep convolutional neural network. [europepmc]
• Balrog: A universal protein model for prokaryotic gene prediction. [europepmc]
• A graph neural network framework for causal inference in brain networks. [europepmc]
• O-WCNN: an optimized integration of spatial and spectral feature map for arrhythmia classification. [europepmc]
• Identifying Peripheral Neuropathy in Colour Fundus Photographs Based on Deep Learning. [europepmc]
• A Framework for Stochastic Optimization of Parameters for Integrative Modeling of Macromolecular Assemblies. [europepmc]
• A Deep Learning Method for Fully Automatic Stomatal Morphometry and Maximal Conductance Estimation. [europepmc]
• Novel Video Surveillance-Based Fire and Smoke Classification Using Attentional Feature Map in Capsule Networks. [europepmc]
• Interactive Deep Learning for Shelf Life Prediction of Muskmelons Based on an Active Learning Approach. [europepmc]
• Advancements in Oncology with Artificial Intelligence-A Review Article. [europepmc]
• Neural Network-Based Calculator for Rat Glomerular Filtration Rate. [europepmc]
• Ice thickness monitoring for cryo-EM grids by interferometry imaging. [europepmc]
• Deep learning pose estimation for multi-cattle lameness detection. [europepmc]
• Efficient shallow learning as an alternative to deep learning. [europepmc]
• Optimization of breeding program design through stochastic simulation with kernel regression. [europepmc]
• OCT-angiography based artificial intelligence-inferred fluorescein angiography for leakage detection in retina [Invited]. [europepmc]
• An ensemble deep learning diagnostic system for determining Clinical Activity Scores in thyroid-associated ophthalmopathy: integrating multi-view multimodal images from anterior segment slit-lamp photographs and facial images. [europepmc]
• An analysis of information segregation in parallel streams of a multi-stream convolutional neural network. [europepmc]
• Edge computing based real-time Nephrops (Nephrops norvegicus) catch estimation in demersal trawls using object detection models. [europepmc]
• Identification of molecular subtypes of dementia by using blood-proteins interaction-aware graph propagational network. [europepmc]
• Optimization of breeding program design through stochastic simulation with evolutionary algorithms. [europepmc]

Related

• A Stochastic Approximation Method
• On minimax estimation problem for stationary stochastic sequences from observations in special sets of points
• Asymptotics of maximum likelihood estimators based on Markov chain Monte Carlo methods
• Maximum likelihood estimation of regularisation parameters in high-dimensional inverse problems: an empirical Bayesian approach. Part II: Theoretical Analysis
• On generalized max-linear models and their statistical interpolation