Search the feasible region without drifting out of it
Implement projected iterative loss ascent with original-input constraints, best-candidate tracking, and reproducible restarts.
On this page
The question for today
What you’ll understand
- Compute an infinity-ball and box projection step.
- Explain how restarts strengthen empirical search without certifying it.
- Preserve attack successes and compare resource budgets honestly.
A single gradient step commits to the local direction at one input. Iterative projected attacks recompute that direction after each move while enforcing a fixed feasible set around the original example. Randomized restarts inspect different initial points because nonlinear losses may have several useful regions. These mechanisms make a more serious robustness test, but the inner maximization remains approximate. The implementation should make its search budget and candidate history auditable so a stronger run cannot accidentally discard a failure that an earlier iterate already found.
Project around the original input
For an infinity-ball image threat, the feasible coordinate interval is the intersection of the original pixel’s epsilon interval with the legal image box. Clip each proposed iterate to those fixed bounds. Clipping only into [0,1] enforces image validity but allows repeated steps to exceed the total threat budget. Clipping around the previous iterate enforces a per-step budget and has the same drift problem. The clean original tensor must remain available and unchanged throughout the run.
Euclidean projection uses a radial rescaling for a norm ball, whereas an additional box intersection needs care. A sequential ball projection and box clipping can produce a feasible point for a box containing the original image, but should not be described automatically as the exact Euclidean projection onto the intersection. The optimization method and any approximation should be stated. Feasibility and exact projection optimality are different properties, and only the former is required to validate a found counterexample.
Preserve failures and explore starting points
Initialize each restart using a documented distribution over feasible points, and record its seed. Uniform sampling in an infinity box is straightforward before accounting for clipping at the image boundary; clipping a larger random box does not generally yield a uniform sample from the final intersection. Uniformity is not required for a valid attack, but the actual initialization law should be described accurately. Include the clean start as a useful reference when comparing restart policies.
Track the strongest relevant candidate across every iterate and restart. For deterministic untargeted classification, once a valid candidate is misclassified, preserve that success even if later steps return to the correct class. A maximum-loss candidate and a successful candidate need not be identical when a surrogate ranks them differently. Reevaluate saved candidates through the final wrapper. Adding restarts should not increase reported survival when earlier candidates and the same success definition are retained.
Treat convergence plots as diagnostics
Sweep step size, iteration count, loss formulation, and restart count on development examples while keeping the final evaluation protocol fixed. A large step may bounce across a narrow useful region; a tiny step may barely move within the allowed runtime. Plot best-so-far loss and cumulative valid failures rather than only final loss. Flat curves can indicate convergence, poor gradients, numerical saturation, or a broken constraint implementation, so they are not independently a robustness argument.
Budget comparisons should count actual model evaluations and backward passes, not only an iteration label. A restart with many gradient samples per step costs more than a deterministic single-gradient run. Report wall time and hardware as additional practical measurements. Retain per-example traces or sufficient summaries to inspect a sudden increase in survival after a code change. A seemingly stronger configuration that finds fewer failures deserves investigation before its result becomes a claimed defense improvement.
Work it through
Two projected steps at an image boundary
Let x=(0.9,0.2), total infinity budget ε=0.15, and step size η=0.1. Start at x and assume gradient signs remain (+,−). Compute two iterative steps using fixed original-input bounds.
The feasible lower bounds are (0.75,0.05) and upper bounds are (1,0.35). They remain fixed for both steps because the original input remains (0.9,0.2).
The first proposal is (1.0,0.1), already feasible, so z₁=(1.0,0.1). Its displacement from x is (0.1,−0.1).
The second proposal is (1.1,0), which projects to z₂=(1,0.05). Its displacement is (0.1,−0.15), giving infinity norm exactly 0.15 and satisfying both constraints.
The second raw proposal exceeds both a domain boundary and the allowed displacement. Fixed-bound projection returns a valid candidate without turning the total epsilon into a per-step allowance.
The living notebook
Explore the model
Interactive lab · optimization
Inspect step-size behavior in a simple iterative model
Reset, set Step size η to 1.5 and Initial position x₀ to 2. Predict x₁=−1 and x₂=0.5 after two successive Steps. Reset, explicitly set η=2.5 and x₀=2, then take two Steps: predict x₁=−3 and x₂=4.5, with an out-of-plot report. This instrument performs descent on x²/2 without projection; it illustrates step-size sensitivity, not PGD attack ascent or neural loss geometry.
- Position x0
- 2
- Objective x²/2
- 2
- Iteration behavior
- Stable step
Gradient descent on f(x) = x²/2: xₙ = (1 − η)ⁿx₀. Playback advances two discrete iterations per second. Values outside |x| ≤ 4 are explicitly reported. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forAn iteration count has little meaning without the update rule and step-size regime.
Pause & reason
Check your understanding
Your turn
Try it yourself
Three restarts find valid failures on sets {1,2,3}, {3,4}, and {2,5} among ten initially correct examples. What is attack-survival accuracy after preserving the union? Can it be computed by averaging the restart failure counts?
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
List distinct failed example IDs once.
Compare with the solution
The union is {1,2,3,4,5}, so five examples fail and survival accuracy is 5/10=50 percent. Averaging counts 3,2,2 loses overlap information and does not give the cumulative worst-case result. This 50 percent remains an empirical upper bound on exact finite-set robust accuracy under the stated feasible search.
Keep the idea
Take it with you
- Keep every projected iterate within a fixed original-input feasible set.
- Preserve successful candidates across steps, restarts, and attack variants.
- Report actual search resources and treat plateaus as diagnostic evidence.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.