No article text was recorded for this version.
adversarial function construction
Version 1 of 172 papers78 conceptsfrozen 2026-10-04
Papers in this version
- Blog: On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions
- Blog: Tight analyses for subgradient descent I: Lower bounds
- Blog: Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere
- Blog: New and Improved Bounds for Markov Paging
- Blog: Optimal complexity and certification of Bregman first-order methods
- Blog: Smooth strongly convex interpolation and exact worst-case performance of first-order methods
- Blog: Lower bounds for finding stationary points II: first-order methods
- Blog: Lower Bounds on the Noiseless Worst-Case Complexity of Efficient Global Optimization
- Blog: Gradient Descent Is Optimal Under Lower Restricted Secant Inequality And Upper Error Bound
- Blog: Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization
- Blog: Comparison of Proximal First-Order Primal and Primal-Dual Algorithms via Performance Estimation
- Blog: Lower bounds for non-convex stochastic optimization
- Blog: Tight Stability Bounds for Robust Distributed Learning: Byzantine Failures Hurt Generalization More than Data Poisoning
- Blog: Maximization of Approximately Submodular Functions
- Blog: Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory
- Blog: Tight Complexity Bounds for Optimizing Composite Objectives
- Blog: Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization
- Blog: On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization
- Blog: Tight Risk Bounds for Gradient Descent on Separable Data
- Blog: Lower Bounds for Greedy Teaching Set Constructions
- Blog: A General Analysis Framework of Lower Complexity Bounds for Finite-Sum Optimization
- Blog: On the complexity of finding stationary points of smooth functions in one dimension
- Blog: Dimension-Free Iteration Complexity of Finite Sum Optimization Problems
- Blog: Generalization Lower Bounds for GD and SGD in Smooth Stochastic Convex Optimization
- Blog: Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
- Blog: How Good is SGD with Random Shuffling?
- Blog: On lower complexity bounds for large-scale smooth convex optimization
- Blog: Minimax Optimal Submodular Optimization with Bandit Feedback
- Blog: On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms
- Blog: On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization
- Blog: Gradient Descent’s Last Iterate is Often (slightly) Suboptimal
- Blog: Optimal strategies and minimax lower bounds for online convex games [Technical Report No. UCB/EECS-2008-19]
- Blog: Theoretical Analysis on how Learning Rate Warmup Accelerates Convergence
- Blog: Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
- Blog: $L^p$ sampling numbers for the Fourier-analytic Barron space
- Blog: Lower Bounds on the Worst-Case Complexity of Efficient Global Optimization
- Blog: Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization
- Blog: Is Local SGD Better than Minibatch SGD?
- Blog: Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems
- Blog: Path Length Bounds for Gradient Descent and Flow
- Blog: Information-Theoretic Bounds for Integral Estimation
- Blog: Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond
- Blog: An optimal gradient method for smooth (possibly strongly) convex minimization
- Blog: Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond
- Blog: Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD
- Blog: Stability of SGD: Tightness analysis and improved bounds
- Blog: Tight analyses for non-smooth stochastic gradient descent
- Blog: Lower complexity bounds for minimizing regularized functions
- Blog: On the oracle complexity of smooth strongly convex minimization
- Blog: Curvature and complexity: Better lower bounds for geodesically convex optimization
- Blog: Logistic Regression: Tight Bounds for Stochastic and Online Optimization
- Blog: Closing the convergence gap of SGD without replacement
- Blog: On Regret Bounds of Thompson Sampling for Bayesian Optimization
- Blog: Flat Minima and Generalization: Insights from Stochastic Convex Optimization
- Blog: Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees
- Blog: The Complexity of Finding Stationary Points with Stochastic Gradient Descent
- Blog: Sharp Convergence Rates for Matching Pursuit
- Blog: Delegated Online Search
- Blog: The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
- Blog: Tight Lower Bounds and Optimal Algorithms for Stochastic Nonconvex Optimization with Heavy-Tailed Noise
Showing 60 of 72 papers.
History & citation
Current · Permanent link
- Adversarial Function Construction for Optimization Lower Bounds merged into this direction (63% overlap)
Cite this direction
Latest version (a living page):
@misc{lacuna_adversarial_function_construction_41a9791f,
title = {adversarial function construction},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/adversarial-function-construction/rdr_41a9791f89614676b96830c4ad2a0cef},
note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}This exact version (version 1, frozen text):
@misc{lacuna_adversarial_function_construction_41a9791f_v1,
title = {adversarial function construction},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/adversarial-function-construction/rdr_41a9791f89614676b96830c4ad2a0cef/v/1},
note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}