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
🏆Completed
Numerical AnalysisRandom Matrix Theory·Captain: tc

Gaussian Random Matrices II: Inverse Moments of the PseudoinverseTextbook

The expected error of the randomized SVD with a k×(k+p)k\times(k+p)k×(k+p) Gaussian test matrix is (1+kp−1)1/2\bigl(1+\tfrac{k}{p-1}\bigr)^{1/2}(1+p−1k​)1/2 times the optimal error (Halko–Martinsson–Tropp 2011, Theorem 10.5). The factor kp−1\tfrac{k}{p-1}p−1k​ is E∥G†∥F2\mathbb E\|G^{\dagger}\|_F^2E∥G†∥F2​ for a k×(k+p)k\times(k+p)k×(k+p) standard Gaussian matrix GGG: the quality of every Gaussian sketching method is governed by inve…

19 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationStatistics·Captain: mikedeng1

Solving Chance-Constrained Problems via a Smooth Sample-Based Nonlinear Approximation 2: Optimal Values and Solutions of the Smoothed SAA Converge w.p.1 as N → ∞ and ε → 0Research Paper

A chance-constrained program asks for a decision that satisfies uncertain constraints with high probability rather than surely:

10 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationStatistics·Captain: mikedeng1

Solving Chance-Constrained Problems via a Smooth Sample-Based Nonlinear Approximation 1: Smoothed Sample Feasible Sets Lie in the True Feasible Set with Probability ≥ 1 − ⌈1/β⌉⌈2LD/t⌉ⁿ exp(−2NM²)Research Paper

A chance-constrained program minimizes a cost f(x)f(x)f(x) over a closed set X⊆RnX\subseteq\mathbb R^nX⊆Rn subject to a constraint that must hold with high probability rather than surely:

8 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomicsOperations Research·Captain: mikedeng1

Dynamic Pricing in the Presence of Social Learning and Strategic Consumers 3: With Social Learning, Responsive Pricing Beats Pre-Announced Pricing When Consumers Are ImpatientResearch Paper

A recurring question in revenue management with strategic consumers is whether a seller gains from price commitment. When customers are forward-looking, a seller who announces its whole price path in advance (pre-announced pricing) removes the customers' incentive to wait for a markdown the seller would otherwise be tempted to give; a seller who keeps the…

9 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomicsOperations Research·Captain: mikedeng1

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

A firm launching a new experience good does not know how good the product is, and neither do its customers. Early buyers post reviews, and customers who wait learn from them: this is social learning (SL). Forward-looking customers anticipate this and may delay their purchase until reviews are available, which cuts into the firm's early sales. Papanastasiou…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Distributionally Robust Joint Chance Constraints with Second-Order Moment Information II: Over Scaling Parameters, Worst-Case CVaR Is Essentially Exact for Joint Chance ConstraintsResearch Paper

A chance constraint asks that a decision x∈Rnx\in\mathbb R^nx∈Rn satisfy uncertain inequalities with high probability. In the setting of Zymler, Kuhn and Rustem (Math. Program. 137, 2013), mmm affine inequalities yi0(x)+yi(x)⊤ξ~≤0y_i^0(x)+y_i(x)^\top\tilde\xi\le0yi0​(x)+yi​(x)⊤ξ~​≤0, whose coefficients depend affinely on xxx, must hold jointly with probability at least 1−ϵ1-\epsilon1−ϵ. Joint chance constraints…

17 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Distributionally Robust Convex Optimization III: The Lifting Theorem — a Conic Bound on E[g(z̃)] Describes Exactly the z̃-Marginals of a Lifted Ambiguity SetResearch Paper

Distributionally robust optimization asks a decision to perform well against every probability distribution in an ambiguity set P\mathcal PP, a family of distributions consistent with partial information about an uncertain parameter z~∈RP\tilde z \in \mathbb R^Pz~∈RP. Which kinds of information an ambiguity set can encode decides which models a solver can handle.…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimal TransportOptimization·Captain: mikedeng1

A Short and General Duality Proof for Wasserstein Distributionally Robust Optimization II: Interchangeability Holds for Diagonally Dominant Functions iff Measurable Projection and Weak Selection DoResearch Paper

In Wasserstein distributionally robust optimization (DRO) a decision is evaluated against the worst distribution within an optimal-transport ball around a nominal distribution P^\widehat{\mathbb P}P. Every tractable reformulation rests on a strong duality theorem that replaces the supremum over distributions by a one-dimensional minimization over a multiplier …

13 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz Algorithm: SGD with Step γ < 1/sup L Has E‖x_k − x⋆‖² ≤ [1 − 2γμ(1 − γ sup L)]^k ‖x₀ − x⋆‖² + γσ²/(μ(1 − γ sup L))Research Paper

Stochastic gradient descent (SGD) minimizes an objective that is an expectation, F(x)=Ei∼Dfi(x)F(x) = \mathbb E_{i\sim\mathcal D} f_i(x)F(x)=Ei∼D​fi​(x), by stepping along the gradient of one randomly drawn component at a time. It is the workhorse of large-scale machine learning, where FFF is an average loss over training examples, and it also contains the randomized Kaczmarz method for…

8 thms3 active usersReviewed
Control TheoryStochastic Systems·Captain: mikedeng1

Linear-Quadratic Optimal Control Problems for Mean-Field Stochastic Differential Equations: Two Riccati Equations Give the Optimal State-Feedback Control and the Value ⟨Π(0)x, x⟩Research Paper

Linear-quadratic (LQ) control is the setting in which stochastic optimal control has a closed-form answer: the optimal control is a linear feedback of the state, and the feedback gain comes from a Riccati differential equation. In the mean-field version, the expectation E[X]\mathbb E[X]E[X] of the state and E[u]\mathbb E[u]E[u] of the control appear in the dynamics and in…

15 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimal TransportOptimization·Captain: mikedeng1

A Short and General Duality Proof for Wasserstein Distributionally Robust Optimization I: Worst-Case Loss = min over λ ≥ 0 of λρ + E[sup f − λc] for All ρ > 0 iff Interchangeability HoldsResearch Paper

Wasserstein distributionally robust optimization (DRO) hedges a decision against every probability distribution within a given transport distance of a nominal one, typically the empirical distribution of data. The inner problem, the worst-case loss, is an optimization over an infinite-dimensional set of measures, and every practical use of Wasserstein DRO —…

15 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Distributionally Robust Convex Optimization II: The Naïve Approximation Implies the Infimal Convolution Bound, Which Implies the Distributionally Robust ConstraintResearch Paper

A constraint E[v(x,z~)]≤w\mathbb E[v(x,\tilde z)] \le wE[v(x,z~)]≤w on a decision xxx needs the distribution of the random vector z~\tilde zz~, which in practice is known only through partial information: a support, some moments, the probability mass of a few regions. Distributionally robust optimization requires the constraint for every distribution consistent with that information.…

9 thms3 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

Robustness May Be at Odds with Accuracy 1: Every Classifier with Standard Accuracy ≥ 1 − δ Has ℓ∞ Robust Accuracy ≤ pδ/(1 − p) Against ε ≥ 2ηResearch Paper

Classifiers trained to be robust against small, adversarially chosen input perturbations routinely lose standard accuracy. Adversarial training (Madry et al., 2018) improves worst-case accuracy under an ℓp\ell_pℓp​-bounded attack, but on MNIST, CIFAR-10 and ImageNet the resulting models are measurably less accurate on unperturbed inputs, and the loss grows with…

7 thms3 active usersReviewed
🏆Completed
StatisticsStochastic Systems·Captain: mikedeng1

Limit Theorems for Nearly Unstable Hawkes Processes 3: The Nearly Unstable Hawkes-Based Price Model Converges in Law to a Heston-Type ProcessResearch Paper

High-frequency prices move by discrete ticks, and successive moves are strongly correlated: an upward tick tends to be followed by a downward one. Bacry, Delattre, Hoffmann and Muzy (BDHM12, BDHM13b) proposed to model the upward and downward price jumps as the two components of a bidimensional Hawkes process, a pair of counting processes in which every…

17 thms3 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisRandom Matrix Theory·Captain: mikedeng1

An Introduction to Matrix Concentration Inequalities II: A Random Row-and-Column Submatrix Z = PBR Satisfies E‖Z‖² ≤ 3(p/d)(r/n)‖B‖² Plus Logarithmic Row, Column and Entry TermsTextbook

Large matrices are often reduced by retaining only some rows or columns. The reduced matrix is cheaper to store and apply, but its spectral norm can be distorted by a single unusually large row, column, or entry. A useful estimate must show both the average effect of sampling and the cost of these local concentrations. In §5.2 of Tropp's monograph, matrix…

11 thms3 active usersReviewed
🏆Completed
CombinatoricsLinear algebraRandom Matrix Theory·Captain: mikedeng1

An Introduction to Matrix Concentration Inequalities I: A Matrix Gaussian Series Satisfies v(Z) ≤ E‖Z‖² ≤ 2v(Z)(1 + log(d₁ + d₂))Textbook

Random matrices arise when observations, signs, or model coefficients fluctuate. Their spectral norm measures the largest amplification they can cause to a vector. A bound on that norm can turn entrywise randomness into a statement about the behavior of an entire linear operator. Tropp's chapter develops a common framework for Gaussian and Rademacher sums…

8 thms3 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

A Modern Introduction to Online Learning XV: Online Learning Bounds Rademacher Complexity, Giving Massart's Lemma G∞√(2 ln d)/√TTextbook

Learning theory asks whether a rule that fits an observed sample will also perform well on future observations. A class with many functions can fit accidental patterns in the sample, so its size and geometry affect the reliability of empirical risk estimates. Empirical Rademacher complexity measures this ability to fit noise: attach an independent random…

5 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

A Modern Introduction to Online Learning X: The Weighted Average Algorithm with a Uniform Prior Has Regret (d/α)(1 + ln(T/d + 1)) on α-Exp-Concave LossesTextbook

Online prediction compares the losses of a sequence of decisions with the losses of one fixed decision chosen after the sequence is known. A learner would like a regret guarantee that remains valid for every such competitor, even when the losses arrive in an arbitrary order. Exponentially weighted averaging is a way to make each decision from all feasible…

7 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

A Modern Introduction to Online Learning II: Online-to-Batch Conversion Turns a Regret Bound into a Risk Bound with Deviation 2√(2 ln(2/δ)/T)Textbook

An online learning algorithm chooses a decision before seeing each round's data and is judged by regret: how much more loss it incurs than a fixed decision chosen in hindsight. Statistical learning asks a different question. After seeing data drawn from a distribution, how small is the decision's expected loss on another draw? Chapter 3 of Orabona's textbook…

5 thms3 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition III: Randomized Coordinate Descent Has Expected Rate (1 − μ/(dL))^kResearch Paper

Coordinate descent changes one component of a parameter vector at a time. This matters when evaluating or updating a single component is cheaper than handling the full vector, for example in problems with sparse features. The coordinate chosen at each step can be random or selected from the current gradient. Karimi, Nutini, and Schmidt study these choices…

7 thms3 active usersReviewed
🏆Completed
CombinatoricsStochastic Systems·Captain: mikedeng1

Separation of Time-Scales and Model Reduction for Stochastic Reaction Networks 2: Positive Combinations Preserve the Balance Condition When Production and Consumption Sets Are DisjointResearch Paper

Stochastic models of chemical reaction networks in cell biology routinely combine species present in a handful of copies with species present in thousands, and rate constants that differ by orders of magnitude. Simulating such a system exactly is expensive, and model reduction replaces it with a lower-dimensional limit. A systematic approach, developed by Ba…

8 thms3 active usersReviewed
🏆Completed
CombinatoricsStochastic Systems·Captain: mikedeng1

Separation of Time-Scales and Model Reduction for Stochastic Reaction Networks 3: The Second Time-Scale r₂ Is Strictly Slower than the First Time-Scale r₁Research Paper

Chemical reaction networks can contain reactions whose rates differ by powers of a large scaling parameter. A species may then change on one time scale while other combinations of species remain nearly fixed until a later one. This matters when replacing a detailed network by a smaller model: the quantities retained at the first scale need not be the…

5 thms3 active usersReviewed
Machine LearningStatistics·Captain: mikedeng1

Learning without Concentration: Least-Squares ERM in a Convex Class Is Within 2 max{α_N(γ, δ/4), βN(τQ{F−F}(2τ)/16)} of f* in L₂ under a Small-Ball ConditionResearch Paper

Least-squares regression over a class of functions is the basic problem of statistical learning theory: given an i.i.d. sample (Xi,Yi)i=1N(X_i,Y_i)_{i=1}^N(Xi​,Yi​)i=1N​ from an unknown joint law, select a function in a class FFF whose prediction error E(f(X)−Y)2\mathbb E(f(X)-Y)^2E(f(X)−Y)2 is close to the best possible in FFF. The standard analysis of empirical risk minimization (ERM) compares empirical…

11 thms3 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition IV: Stochastic Gradient Rates LC²/(2kμ²) and (1 − 2μα)^k [f(x_0) − f*] + LC²α/(4μ)Research Paper

Stochastic gradient (SG) methods are the default algorithms for training machine-learning models: when an objective is an average over a very large number of training examples, computing its full gradient even a few times is infeasible, while the gradient of a single randomly chosen example is cheap. The classical convergence theory of SG rates its expected…

7 thms3 active usersReviewed
Markov ChainStatistics·Captain: mikedeng1

Spectral Gaps for a Metropolis–Hastings Algorithm in Infinite Dimensions III: The L²-Spectral Gap of Random Walk Metropolis for a Gaussian Target Vanishes Faster Than Any Power of the DimensionResearch Paper

Bayesian inverse problems and conditioned diffusions lead to probability measures on function spaces, and these are sampled in practice through finite-dimensional approximations on Rm\mathbb R^mRm with mmm large. A Markov chain Monte Carlo method is useful in this setting only if its convergence rate does not deteriorate as the discretisation is refined. Random…

12 thms3 active usersReviewed
PreviousPage 39 of 110Next

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