Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Probability

2,743 missions · 1,549 completed

Missions

Open1194Completed1549All2743
Machine LearningOptimizationReinforcement Learning·Captain: mikedeng1

Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies: Random-Horizon Policy Gradient with Robbins–Monro Stepsizes Drives the Policy Gradient to Zero Almost SurelyResearch Paper

Policy gradient methods are the main family of reinforcement learning algorithms that search directly over a parameterized class of stochastic policies πθ\pi_\thetaπθ​, θ∈Rd\theta\in\mathbb R^dθ∈Rd, by stochastic gradient ascent on the expected discounted return. They underlie REINFORCE, actor-critic methods and their deep-learning descendants. The return is a nonconvex…

17 thms2 active usersReviewed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

Distributed Stochastic Gradient Tracking Methods I: With a Constant Stepsize, DSGT's Limiting Mean-Square Error Is at Most (Γ+1)ασ²/(Γμn) Plus a Network TermResearch Paper

Many learning and estimation problems are solved by a network of agents: each agent holds part of the data, can talk only to its neighbours, and wants to compute the minimizer of the average of all agents' objectives. Examples are sensor networks, multi-robot systems, and data-parallel training without a central server (Nedić and Ozdaglar 2009; Lian et al.…

18 thms2 active usersReviewed
Algorithmic Game TheoryGraph TheoryStochastic Systems·Captain: mikedeng1

A Case Study on Stochastic Games on Large Graphs in Mean Field and Sparse Regimes I: An Explicit Markovian Nash Equilibrium on Every Finite Transitive GraphResearch Paper

Mean field games describe Nash equilibria of large populations in which every player interacts with every other player symmetrically, through the empirical distribution of all states. Many systems of interest are not of this kind: agents in a network interact only with their neighbours, and the interaction structure is a graph rather than a complete graph.…

21 thms2 active usersReviewed
Optimal TransportStatistics·Captain: mikedeng1

Finite-Sample Guarantees for Wasserstein Distributionally Robust Optimization: Breaking the Curse of Dimensionality 1: Under T_p(τ), True Loss ≤ Empirical Loss + R(√(τt/n); −f) w.p. ≥ 1 − e^(−t)Research Paper

Wasserstein distributionally robust optimization (Wasserstein DRO) replaces the expected loss under an empirical distribution by the worst-case expected loss over all distributions within a Wasserstein distance ρ\rhoρ of it. It is used in operations research, statistics and machine learning to guard decisions and predictors against the gap between the sample…

10 thms2 active usersReviewed
Control TheoryOptimizationStochastic Systems·Captain: mikedeng1

Open-Loop and Closed-Loop Solvabilities for Stochastic Linear Quadratic Optimal Control Problems 4: A Problem Open-Loop Solvable at Every (t, x) but Closed-Loop Solvable on No [t, 1]Research Paper

In a stochastic linear–quadratic (LQ) optimal control problem a controller steers a linear stochastic differential equation and pays a quadratic cost. When the cost weights are allowed to be indefinite — as in mean–variance portfolio selection, where the control weight is zero — the problem can still be well posed, and two different notions of solution…

13 thms2 active usersReviewed
Control TheoryOptimizationStochastic Systems·Captain: mikedeng1

Open-Loop and Closed-Loop Solvabilities for Stochastic Linear Quadratic Optimal Control Problems 3: Open-Loop Solvability Is Equivalent to Convergence of the Riccati Minimizing SequenceResearch Paper

Linear–quadratic (LQ) optimal control is the basic test case of stochastic control: a linear stochastic differential equation, a quadratic cost, and an optimal control that one expects to be a linear feedback of the state computed from a Riccati equation. In the indefinite stochastic case the weighting matrices GGG, QQQ, RRR carry no sign condition. The cost can…

14 thms2 active usersReviewed
Algorithmic Game TheoryEconomicsOperations Research·Captain: mikedeng1

Dynamic Pricing in the Presence of Social Learning and Strategic Consumers 1: Under Pre-Announced Pricing, Social Learning Raises Optimal Expected Profit When Consumers Are Impatient or PatientResearch Paper

Online reviews let consumers learn about a new product from the experience of earlier buyers. For a firm selling to strategic consumers, who time their purchases, this social learning (SL) cuts two ways. Reviews reveal quality, which can raise second-period demand; but a consumer who expects reviews also has a new reason to wait, and every consumer who…

12 thms2 active usersReviewed
AnalysisMathematical Physics·Captain: mikedeng1

Conformal Weldings of Random Surfaces: SLE and the Quantum Gravity Zipper 2: For κ < 4, Reverse SLE_κ Zipping Welds Boundary Arcs of Equal Quantum Length, ν_h[z₋,0] = ν_h[0,z₊]Research Paper

Liouville quantum gravity (LQG) equips a planar domain with a random area measure μh\mu_hμh​ and a random boundary length measure νh\nu_hνh​. Both are built from an instance hhh of the Gaussian free field (GFF). The Schramm–Loewner evolution SLEκ\mathrm{SLE}_\kappaSLEκ​ is the conformally invariant random curve that describes interfaces in critical planar models. Sheffield's…

16 thms2 active usersReviewed
CombinatoricsGraph TheoryStatistics·Captain: mikedeng1

A Proof of the Block Model Threshold Conjecture: If s² > d, a Labelling of G(n, a/n, b/n) Correlated with the Planted Partition Can Be Found Asymptotically Almost SurelyResearch Paper

The stochastic block model is the basic random-graph model of a network with communities. It serves as a test bed for clustering algorithms in statistics, machine learning and theoretical computer science. In its sparse two-community form, each vertex has a constant expected degree, and the question is how much of the hidden partition a graph reveals. Using…

14 thms2 active usersReviewed
Markov ChainStatisticsStochastic Systems·Captain: mikedeng1

Can Local Particle Filters Beat the Curse of Dimensionality?: The Block Particle Filter Has a Local Error Bound Uniform in Time and in the Model DimensionResearch Paper

Nonlinear filtering asks for the conditional law of an unobserved Markov process given noisy partial observations of it. It is the computational core of data assimilation in weather forecasting, oceanography and geophysics, of target tracking, and of inference in large networked systems. The standard numerical method, the particle filter, replaces the…

13 thms2 active usersReviewed
Machine LearningOptimization·Captain: mikedeng1

On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points 2: Perturbed GD (Variant) Makes Half Its Iterates ε-Second-Order Stationary within Õ(ℓΔ_f/ε²) IterationsResearch Paper

Training a model in machine learning usually means minimizing a nonconvex function f:Rd→Rf:\mathbb R^d\to\mathbb Rf:Rd→R with first-order methods. Finding a global minimum of a general nonconvex function is NP-hard, so the classical guarantee for gradient descent (GD), xt+1=xt−η∇f(xt)x_{t+1}=x_t-\eta\nabla f(x_t)xt+1​=xt​−η∇f(xt​), is weaker: with step size η=1/ℓ\eta=1/\ellη=1/ℓ it reaches a point with …

9 thms2 active usersReviewed
Algorithmic Game TheoryOptimization·Captain: mikedeng1

Distributed Algorithms for Aggregative Games on Graphs III: Equal-Stepsize Gossip under Strong Monotonicity, limsup E‖x^k − x*‖² ≤ (α/μ)(2C²N + BC√(2nN)/(1 − √λ))Research Paper

In an aggregative game, each player's decision affects a common quantity, such as total production or total demand. An agent may be able to calculate its own preferred response while lacking direct access to that aggregate. Koshal, Nedić, and Shanbhag study how agents can estimate it by exchanging information only with neighbours on a communication graph.…

13 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Algorithms for #BIS-Hard Problems on Expander Graphs 4: On Almost Every Δ-Regular Bipartite Graph with Δ ≥ Cq² log² q, Proper q-Colorings Reduce to Kotecký–Preiss Polymer ModelsResearch Paper

Counting the proper qqq-colorings of a graph, and sampling one uniformly at random, are basic problems of approximate counting with a long history in statistical physics, where proper colorings are the zero-temperature antiferromagnetic Potts model. On bipartite graphs these problems are tied to #BIS, the problem of approximately counting independent sets in…

13 thms2 active usersReviewed
Machine LearningOptimization·Captain: mikedeng1

On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points 1: Perturbed SGD Makes Half Its Iterates ε-Second-Order Stationary within Õ(ℓΔ_f·𝔑/ε²) IterationsResearch Paper

Most training objectives in machine learning are smooth and nonconvex, and they are minimized by stochastic gradient descent (SGD) and its variants. For nonconvex fff the classical guarantee is convergence to an ϵ\epsilonϵ-first-order stationary point, ∥∇f(x)∥≤ϵ\|\nabla f(x)\|\le\epsilon∥∇f(x)∥≤ϵ: Ghadimi and Lan (arXiv:1309.5549) showed that SGD reaches one in …

17 thms2 active usersReviewed
Machine LearningOptimizationStatistics·Captain: mikedeng1

Robustness May Be at Odds with Accuracy 2: The Unit-Norm Soft-Margin SVM Is >99% Accurate but <1% Robust at ε ≥ 2η, While Adversarial Training Gives Accuracy pResearch Paper

Adversarial training asks a classifier to work even after an input has been changed within a prescribed perturbation budget. Tsipras, Santurkar, Engstrom, Turner, and Mądry studied why the classifier that performs best on ordinary inputs can behave very differently under these changes. Their explicit model separates one reliably predictive feature from many…

10 thms2 active usersReviewed
Graph TheoryMathematical Physics·Captain: mikedeng1

Algorithms for #BIS-Hard Problems on Expander Graphs 3: On Almost Every Δ-Regular Bipartite Graph, the Hard-Core Model at λ > 50 log²Δ/Δ Reduces to Two Kotecký–Preiss Polymer ModelsResearch Paper

The hard-core model assigns weight to independent vertex sets of a graph. Its partition function counts those sets when the activity is one and weights larger sets more heavily when the activity increases. Counting independent sets on bipartite graphs is a standard benchmark for approximate counting: the general problem is difficult, while random regular…

8 thms2 active usersReviewed
Algorithmic Game TheoryOptimization·Captain: mikedeng1

Distributed Algorithms for Aggregative Games on Graphs II: The Gossip Algorithm with Stepsizes 1/Γ_k(i) Converges Almost Surely to the Unique EquilibriumResearch Paper

In an aggregative game, each player's cost depends on its own decision and on the sum of all players' decisions. That form appears in resource sharing, production, and network games: a player may know its own choice while lacking a central feed of the aggregate. A distributed algorithm therefore has to estimate the aggregate through local communication as…

9 thms2 active usersReviewed
Operations ResearchOptimal TransportStochastic Systems·Captain: mikedeng1

A Stochastic Control Approach to No-Arbitrage Bounds Given Marginals, with an Application to Lookback Options: The Robust Superhedging Bound of g(X*_T) Given the Law of X_T Equals μ^HL(g)Research Paper

A lookback option pays a function of the running maximum of the underlying asset over the life of the contract. When the prices of European call options of all strikes at the maturity are quoted, the risk-neutral law μ\muμ of the terminal price is known, but the law of the whole path is not. The robust (model-free) superhedging cost of the lookback payoff is…

13 thms2 active usersReviewed
Machine LearningOptimization·Captain: mikedeng1

Stochastic Model-Based Minimization of Weakly Convex Functions 2: The Proximal Stochastic Subgradient Method Drives E‖∇φ_{1/ρ̄}(x_{t*})‖² to Zero at Rate O(1/√T)Research Paper

The proximal stochastic subgradient method is the workhorse of large-scale learning: to minimize a regularized population risk φ(x)=f(x)+r(x)\varphi(x) = f(x) + r(x)φ(x)=f(x)+r(x) with f(x)=Eξ∼P[f(x,ξ)]f(x) = \mathbb E_{\xi \sim P}[f(x,\xi)]f(x)=Eξ∼P​[f(x,ξ)], it samples a data point, takes a step against a sampled subgradient of fff, and applies the proximal map of the regularizer rrr. Its sample complexity is classical…

12 thms2 active usersReviewed
Functional AnalysisMarkov ChainStatistics·Captain: mikedeng1

Spectral Gaps for a Metropolis–Hastings Algorithm in Infinite Dimensions I: The pCN Algorithm Has a Wasserstein Spectral Gap Uniform in the Dimension When the Potential Is Globally LipschitzResearch Paper

Sampling from a distribution described relative to a Gaussian reference law is common in Bayesian inverse problems, where an unknown function or initial condition is inferred from noisy observations. Such a distribution is naturally infinite dimensional before it is approximated on a computer. A numerical method must therefore behave reliably as the…

10 thms2 active usersReviewed
Dynamical SystemsHarmonic AnalysisMachine Learning·Captain: mikedeng1

Approximation Bounds for Random Neural Networks and Reservoir Systems II: Echo State Networks with Random Weights Approximate Regular Functionals with an Explicit L² Error Bound (Theorem 2)Research Paper

Reservoir computing learns an input/output system from data in two stages. A dynamical system, the reservoir, is driven by the input sequence and its state is recorded; then only a linear readout of that state is trained, by least squares. The echo state network (ESN) is the most widely used reservoir: its state evolves by …

11 thms2 active usersReviewed
Harmonic AnalysisMachine Learning·Captain: mikedeng1

Approximation Bounds for Random Neural Networks and Reservoir Systems I: Random ReLU Networks with Sampled Inner Weights Approximate Fourier-Represented Functions on a Hilbert Space (Theorem 1)Research Paper

In random-feature models, also called extreme learning machines or random neural networks, the inner weights of a one-hidden-layer network are drawn at random and only the linear readout is trained. Training is then a least-squares problem, which is why such models, and their dynamic counterparts reservoir computing and echo state networks, are used in…

8 thms2 active usersReviewed
Dynamical SystemsMachine Learning·Captain: mikedeng1

Approximation Bounds for Random Neural Networks and Reservoir Systems III: Echo State Networks with Output Feedback and Random Weights Approximate Contracting Reservoirs (Theorem 4)Research Paper

An echo state network with output feedback is a recurrent model whose previous output is fed back into its next hidden-state update. In reservoir computing only the linear output weights are trained, while the internal weights are fixed, typically after being drawn at random. This raises a quantitative question: if the internal rows are sampled from a fixed…

8 thms2 active usersReviewed
Information TheoryQuantum Information·Captain: mikedeng1

Semidefinite Programming Hierarchies for Constrained Bilinear Optimization II: De Finetti Without Symmetry — Random Subsystems Are 3k^{3/2}d_B³ log d_B/√(n−k+1)-Close to Product in ExpectationResearch Paper

Quantum information often describes a system through a state shared among many small registers. One would like to replace the state on a few registers by a product of their individual states, because product states are easier to estimate and optimize over. The usual finite quantum de Finetti theorems obtain such approximations from permutation symmetry. A…

12 thms2 active usersReviewed
Optimization·Captain: visuddhi

VC Theory for Inventory Policies: Xie–Ma–Xin BoundsResearch Paper

An inventory policy chooses how much stock to order before demand is observed. Its quality is assessed by the holding and backlogging costs it incurs on future demand. A policy chosen to perform well on historical demand can overfit those observations. A useful statistical guarantee therefore controls the difference between historical and future costs…

6 thms2 active usersReviewed
PreviousPage 32 of 48Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me